§1
求方程 $f(x)=0$ 的根（零点）是数值分析的基本问题。当 $f$ 是非线性函数（高次多项式、超越函数）时，解析根通常不存在或难以写出，必须依赖迭代法在给定精度内逼近。本章介绍从最稳健的二分法到高效的牛顿法、割线法，并建立统一衡量收敛快慢的"收敛阶"概念。
设真根为 $\alpha$（即 $f(\alpha)=0$），第 $n$ 步近似为 $x_n$，误差 $e_n=|\alpha-x_n|$。
一、二分法（对分法）
原理（介值定理）. 若 $f$ 在 $[a,b]$ 连续且 $f(a)f(b)<0$，则 $(a,b)$ 内至少存在一个根。
每次取中点 $c=(a+b)/2$：
- 若 $f(c)=0$，则 $c$ 即为根；
- 若 $f(a)f(c)<0$，根在左半区间，令 $b=c$；
- 否则根在右半区间，令 $a=c$。
误差界与收敛. 第 $n$ 次二分后区间长度为 $(b-a)/2^n$，根必落在其中，故近似中点的误差满足
$$|x_n-\alpha|\le \frac{b-a}{2^{n+1}}\quad\text{（按区间长计）}\quad \frac{b-a}{2^n}.$$
误差呈线性收敛（每步误差减半）。
- 优点：绝对稳健，只要端点异号必收敛；无需导数。
- 缺点：收敛慢；只能求实根；一次只能隔离出一个根。
二、不动点迭代
把方程改写为等价形式 $x=g(x)$，迭代
$$x_{n+1}=g(x_n).$$
若序列收敛到 $\alpha$，则 $\alpha=g(\alpha)$ 即为不动点，也是原方程根。
局部收敛定理. 若 $g$ 在根 $\alpha$ 邻域连续可微且
$$|g'(\alpha)|<1,$$
则从足够靠近 $\alpha$ 的初值出发序列收敛（压缩映射）。$|g'(\alpha)|$ 越小收敛越快；若 $|g'(\alpha)|>1$ 则发散。
收敛域说明. 收敛性仅保证在 $\alpha$ 附近（压缩区）成立；初值落在收敛域外可能不收敛，故初值选择很重要。
三、牛顿法（Newton–Raphson）
用切线近似函数：在 $x_n$ 处作 $f$ 的线性化，令其零点为下一步：
$$x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}.$$
几何上即"用切线与 $x$ 轴交点作为新近似"。
- 收敛速度：在单根且初值充分好时，牛顿法具有二次收敛——误差满足 $e_{n+1}\approx C e_n^2$。
- 优点：收敛极快。
- 缺点：需计算导数 $f'$；对初值敏感，可能发散、陷入周期循环（如某些振荡函数）；遇重根时降为线性收敛。
四、割线法（弦截法）
用差商代替导数，免去求导：
$$x_{n+1}=x_n-\frac{f(x_n)(x_n-x_{n-1})}{f(x_n)-f(x_{n-1})}.$$
它需要两个初值 $x_0,x_1$，用过两点的割线（弦）与 $x$ 轴交点作为新近似。
- 收敛阶：超线性，约为黄金比 $\displaystyle p=\frac{1+\sqrt5}{2}\approx1.618$。
- 优点：无需导数，比二分快得多。
- 缺点：仍需初值较好；可能不收敛。
五、收敛阶的定义与对比
定义. 若存在常数 $C>0$ 与阶数 $p\ge1$ 使
$$\lim_{n\to\infty}\frac{|e_{n+1}|}{|e_n|^p}=C,$$
则称迭代为 $p$ 阶收敛。
| 方法 | 是否需要导数 | 收敛阶 $p$ | 优点 | 缺点 |
|---|---|---|---|---|
| 二分法 | 否 | $1$（线性） | 稳健、必收敛 | 慢、仅实根 |
| 不动点迭代 | 否 | $1$（当 $\lvert g'\rvert<1$） | 简单 | 依赖 $g$ 的构造 |
| 牛顿法 | 是 | $2$（二次） | 极快 | 需导数、初值敏感 |
| 割线法 | 否 | $\approx1.618$ | 快、免导数 | 初值敏感 |
二分每步误差减半，牛顿每步有效数字约翻倍，割线居中。
六、例题与解答
例题1（牛顿法）. 解 $f(x)=x^3-x-1=0$，取 $x_0=1$，$f'(x)=3x^2-1$。
$$x_{n+1}=x_n-\frac{x_n^3-x_n-1}{3x_n^2-1}.$$
- $x_0=1$，$f(1)=-1$，$f'(1)=2$，$x_1=1-(-1)/2=1.5$；
- $x_1=1.5$，$f=3.375-1.5-1=0.875$，$f'=5.75$，$x_2=1.5-0.875/5.75\approx1.34783$；
- $x_2\approx1.34783$，$f\approx-0.10068$，$f'\approx4.4573$，$x_3\approx1.34783+0.10068/4.4573\approx1.37081$；
- 继续迭代精化，根约为 $\alpha\approx1.32472$。
验证：代入 $x=1.32472$ 得 $f\approx-2\times10^{-6}\approx0$。✓
例题2（二分法求 $\sqrt2$）. 求 $f(x)=x^2-2=0$ 在 $[1,2]$ 的根，即 $\sqrt2$。$f(1)=-1<0$，$f(2)=2>0$。
| $n$ | $a$ | $b$ | 中点 $c$ | $f(c)$ 符号 |
|---|---|---|---|---|
| 0 | 1 | 2 | 1.5 | $+$ |
| 1 | 1 | 1.5 | 1.25 | $-$ |
| 2 | 1.25 | 1.5 | 1.375 | $-$ |
| 3 | 1.375 | 1.5 | 1.4375 | $+$ |
第 3 次后区间长 $(2-1)/2^3=0.125$，根落在 $[1.375,1.4375]$，中点 $1.40625$，误差界 $\le0.0625$；迭代 4 次后区间长 $0.0625$，可把 $\sqrt2\approx1.4142$ 控制在误差 $0.03125$ 内。✓
练习
1. 用二分法求 $f(x)=x^3-2x-5=0$ 在 $[2,3]$ 的根，至少进行 3 次二分，给出误差界。
2. 对 $f(x)=x^2-2=0$ 写出牛顿迭代公式，并说明在 $x_0=1.5$ 时的收敛趋势。
3. 不动点迭代 $x=g(x)=x-f(x)$ 用于 $f(x)=x^2-2$，判断在 $x\approx\sqrt2$ 处是否收敛。
4. 割线法为何比二分法快？其收敛阶大约是多少？
参考答案与提示
1. $f(2)=-1<0,f(3)=16>0$。中点 2.5($+$)→[2,2.5]；2.25($-$)→[2.25,2.5]；2.375($+$)→[2.25,2.375]。3 次后误差界 $(3-2)/2^3=0.125$，根约 $2.0946$。
2. $x_{n+1}=\frac12(x_n+2/x_n)$。$x_0=1.5\to1.4167\to1.4142$，每步有效数字约翻倍，体现二次收敛。
3. $g(x)=x-(x^2-2)=2-x^2$，$g'(\sqrt2)=-2\sqrt2\approx-2.83$，$|g'|>1$，发散；需改写 $g$（如 $g=\frac12(x+2/x)$）。
4. 割线用差商近似导数，收敛阶 $p=(1+\sqrt5)/2\approx1.618$，高于二分的线性 1，故更快。
本章小结
- 二分法稳健但线性收敛，适合粗定位与保底。
- 不动点迭代收敛需 $|g'(\alpha)|<1$，依赖改写方式。
- 牛顿法二次收敛、最快，但需导数且初值敏感。
- 割线法免导数、超线性收敛（约 $1.618$ 阶）。
- 收敛阶 $p$ 统一定量：二分 $1$、牛顿 $2$、割线 $\approx1.618$。
- 实践中常以二分定位初值，再用牛顿 / 割线加速。
互动演示
拖动下方控件观察动态过程。
牛顿法切线迭代：从初值出发沿切线逼近方程的根（f(x)=x^3-x-1，根约 1.3247）。