想求 $\sqrt3$，可以把问题写成 $x^2-3=0$，然后不断改进一个猜测。但“下一次更接近了”还不够：如果要交出误差不超过 $10^{-6}$ 的答案，你需要说明这个保证从哪里来。

求根方法各有不同的证据。二分法始终留住一个包含根的区间；Newton 法借助局部斜率，靠近单根时可以很快；不动点迭代则把问题变成重复代入。我们会把这些证据和各自的限制一起算出来。

先把根留在一个区间里

若 $f$ 在闭区间 $[a,b]$ 上连续，且 $f(a)$ 与 $f(b)$ 异号，介值定理保证区间内部至少有一个根。这里没有保证唯一，也没有要求导数存在。若某个端点已经满足 $f=0$，直接记录那个根即可。

取中点 $m=(a+b)/2$，计算 $f(m)$。如果它等于零，精确算术下已经求到根；否则，把与 $f(m)$ 同号的那个端点移到 $m$。新端点仍异号，区间长度恰好减半。这就是二分法。

例：把 $\sqrt3$ 夹住。 在 $[1,2]$ 上，$f(x)=x^2-3$ 连续，端点值分别为 、。第一次中点是 ，函数值为 ，所以保留右半段 。后面几步如下：

二分法先检查中点符号，再保留仍然夹住根的半段；两次更新后区间宽度为 0.25，中点误差不超过 0.125。

把初始区间记为 $I_0=[a_0,b_0]$，做过 $k$ 次区间更新后记为 $$，它的中点记为 。这样 是还没更新区间时的第一个中点。由每步缩半，

$$b_k-a_k=\frac{b_0-a_0}{2^k}, \qquad |m_k-r|\le\frac{b_0-a_0}{2^{k+1}},$$

其中 $r$ 是始终留在这些嵌套区间中的根。区间长度趋于零，左右端点趋于同一点；连续性和两侧符号保证那个点的函数值为零。因此，这既给出收敛，也给出计算前就知道的误差上界。

例如初始宽度为 1，要求中点绝对误差不超过 $10^{-3}$，需要 $2^{-(k+1)}\le10^{-3}$。最小整数 $k=9$：完成九次区间更新后，取当前中点，误差界为 。若某处把“第一次中点”编号为 1，公式里的指数会相应变化，不能只抄迭代次数而忽略编号。

在下面的实验中，从 $x^2-3$ 的 $[1,2]$ 开始，每一步先选择你认为应该保留的半段，再查看函数符号。观察区间宽度和中点误差界是否按同一比例缩小。切到跨越极点的例子，检查为什么“端点异号”这条记录仍不足以启动算法。

实验给出的保证来自连续性、可信的符号和保留下来的区间。在真实程序中，函数值也会舍入；接近零时，如果连符号都不能可靠确定，就需要更可靠的函数求值或区间计算，不能继续把理想算术的保证当作已经验证。

重复代入之前，看看它会不会把误差缩小

把 $f(x)=0$ 改写成 $x=g(x)$，便可以尝试

$$x_{n+1}=g(x_n).$$

满足 $g(r)=r$ 的 $r$ 称为不动点。相同方程可以有很多改写，迭代行为却不一样。我们只求 $x^2-x-2=0$ 的正根，把搜索范围限定为 $$。取

$$g(x)=\sqrt{2+x},$$

其不动点满足原方程；由于取了正平方根，这个改写不负责寻找负根 $-1$。

在 $[1,3]$ 上，$g(x)\in[\sqrt3,\sqrt5]\subset[1,3]$，所以每次代入都留在原区间。又有

$$|g'(x)|=\frac1{2\sqrt{2+x}}\le\frac1{2\sqrt3}<\frac13.$$

这意味着两次输入之间的距离，经过 $g$ 后至多变成原来的三分之一。下面把这件事推广成可以使用的结论。

设 $g$ 在闭区间 $[a,b]$ 上连续，并把整个区间映回自身；在内部可微，且存在 $0\le q<1$，使 $|g'(x)|\le q$。那么区间内有唯一不动点，从任意 出发的迭代都收敛到它。

存在性可以直接从介值定理看出：$g(a)-a\ge0$，$g(b)-b\le0$，所以连续函数 $g(x)-x$ 至少有一个零点。若有两个不动点 ，中值定理给出

$$|r-s|=|g(r)-g(s)|\le q|r-s|.$$

因为 $q<1$，只能有 $r=s$。同一估计还告诉我们

$$|x_{n+1}-r|\le q|x_n-r|\le q^{n+1}|x_0-r|.$$

迭代一直留在区间内，因而这份估计可以反复使用；右端趋于零，收敛就得到了保证。自映射条件不能省略：即使某段上导数小，第一步若已经走出那一段，后续也未必仍受这个导数界控制。

闭区间自映射保证迭代有处可去，收缩估计控制两次输出之间的距离；两个条件承担不同作用。

对刚才的平方根迭代，从 $x_0=1$ 出发，得到约 $1.732051,1.931852,1.982890,1.995718$，逐渐走向 2。若改用同样来自原方程的 $g(x)=x^2-2$，在 2 附近有 ，小偏差反而会被放大。恰好从 2 出发当然不动；“局部排斥”不意味着连已经在根上的输入也会离开。

有时真根未知，$|x_n-r|$ 算不出来。收缩条件还给出一个后验误差界。相邻差满足

$$|x_{n+j+1}-x_{n+j}|\le q^{j+1}|x_n-x_{n-1}|.$$

把从 $x_n$ 走到极限的所有后续差相加，再用几何级数，

$$|x_n-r| \le \sum_{j=0}^{\infty}|x_{n+j+1}-x_{n+j}| \le\frac{q}{1-q}|x_n-x_{n-1}|.$$

这时，“相邻两步很接近”才有了明确的误差含义。没有已证的 $q<1$，单独看步长就不能照搬这个结论。

下面用折线把代入过程画出来：竖直走到 $y=g(x)$ 是计算函数值，水平走到 $y=x$ 是把输出变成下一次输入。比较同一个正根附近的两种改写，预测哪一种会收敛，再移动初值并逐步播放。对于收缩的那一种，同时核对后验上界。

Newton 法为什么能在根附近加速

若 $f$ 可微，在当前点 $x_n$ 用切线

$$\ell_n(x)=f(x_n)+f'(x_n)(x-x_n)$$

替代曲线。令切线的函数值等于零，就得到下一次猜测：

$$x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}.$$

这里要求 $f'(x_n)\ne0$。切线与横轴的交点是下一次输入，并不是曲线已经在那个地方等于零。

切线经过当前点，斜率取当前导数。把切线方程中的 y 设为 0，得到下一次输入；它代回原函数后仍有 0.0625 的残差。

例：继续求 $\sqrt3$。 对 $f(x)=x^2-3$，Newton 公式成为

$$x_{n+1}=\frac12\left(x_n+\frac3{x_n}\right).$$

从 $x_0=2$ 开始，$x_1=7/4=1.75$，接着 $x_2=97/56\approx1.732142857$。表中误差使用 作参考，以便观察速度：

| $n$ | $x_n$（约） | $|x_n^2-3|$（约） | $\mathrm{\mid }{x}_n-\sqrt{}$（约） | | --- | --- | --- | --- | | 0 | | | | | 1 | | | | | 2 | | | | | 3 | | | |

误差不是每次减少固定比例，而是越到后面缩得越快。设 $r$ 为单根，即 $f(r)=0$、$f'(r)\ne0$，并记 $$。假设 在根附近有连续二阶导数，在 处展开 ：

$$0=f(x_n)-f'(x_n)e_n+\frac{f''(\xi_n)}2e_n^2.$$

整理后代入 Newton 公式，得到精确的局部关系

$$e_{n+1}=\frac{f''(\xi_n)}{2f'(x_n)}e_n^2,$$

其中 $\xi_n$ 位于 $x_n$ 与 $r$ 之间。若小邻域内 $|f'|\ge m>0$、，就有 ，。

还要解释为什么迭代不会跳出这个邻域。由单根和导数连续性，可以选取一个闭邻域 $[r-\rho,r+\rho]$，使上述界成立，并进一步缩小 $\rho$，让 $C\rho\le1/2$。若 $|e_n|\le\rho$，则

$$|e_{n+1}|\le C\rho|e_n|\le\frac12|e_n|\le\rho.$$

于是从该邻域出发，后续一直留在其中并趋于根。这个论证同时给出了局部收敛和平方误差界，没有先假设迭代必然收敛。它仍未告诉我们任意一个远处初值是否合适。

若非零误差趋于零，且 $f''(r)\ne0$，上式的系数趋向非零常数，便有

$$\lim_{n\to\infty}\frac{|e_{n+1}|}{|e_n|^2} =\left|\frac{f''(r)}{2f'(r)}\right|.$$

这称为二次收敛。若该常数为零，可能更快，或有限步到根；不能一概说“恰好二阶”。有限精度中，当误差已接近舍入水平，理想的平方规律也会停止显现。

快的方法也会停在错误的地方

看 $f(x)=x^3-2x+2$。从 $x_0=0$ 出发，、，下一点为 1；在 1 处，、，又回到 0。两个点来回循环，导数都不为零，仍然没有收敛。

从 0 出发，Newton 更新在 0 和 1 之间来回循环；每一步分母都不为零，仍然不能保证收敛。

重根则是另一种问题。若

$$f(x)=(x-r)^m h(x),\qquad h(r)\ne0,\quad m\ge2,$$

且 $h$ 足够光滑，那么

$$\frac{f(x)}{f'(x)} =\frac{x-r}{m+(x-r)h'(x)/h(x)}.$$

当 $x\to r$，Newton 误差因此满足

$$e_{n+1}=\left(1-\frac1m\right)e_n+O(e_n^2).$$

它通常只剩线性收敛。对 $(x-1)^3$，甚至精确有 $e_{n+1}=(2/3)e_n$。如果重数 已知，可以改成 ，消掉刚才的一阶项，在相应光滑性和近初值条件下恢复至少二次收敛。不要凭几个迭代值猜一个重数，就把这个保证照搬过去。

没有导数时，用最近两点作割线

通过 $(x_{n-1},f(x_{n-1}))$ 与 $(x_n,f(x_n))$ 的直线，斜率为

$$d_n=\frac{f(x_n)-f(x_{n-1})}{x_n-x_{n-1}}.$$

把 Newton 公式中的导数换成这个斜率，得到割线法：

$$x_{n+1}=x_n- f(x_n)\frac{x_n-x_{n-1}}{f(x_n)-f(x_{n-1})}.$$

要给两个初值，且不能让分母为零。每一步保留最近两个函数值，通常只需增加一次函数求值。最近两点不一定夹住根，割线法本身没有二分法的区间保证。

对 $x^2-3$，从 $x_0=1,x_1=2$ 开始，割线依次给出 、、。第一步的直线连接 和 ，斜率为 3，横轴截点确实是 。

割线穿过曲线上的两个取样点，横轴上的空心点表示相应直线的零点。这里是几何示意，不是正文平方根算例的精确坐标图；箭头也不构成收敛保证。

在单根附近，割线通常是超线性收敛。黄金比出现在这里，并不是一个经验常数。假设 $f$ 在根附近有连续三阶导数，令 $f(r+e)=ae+be^2+O(e^3)$，其中 、。割线误差可写成

$$e_{n+1}= \frac{e_{n-1}f(r+e_n)-e_n f(r+e_{n-1})} {f(r+e_n)-f(r+e_{n-1})}.$$

分子的一阶项互相抵消，二阶项是 $b e_ne_{n-1}(e_n-e_{n-1})$；分母的首项是 。对不同的近根迭代点，光滑的差商展开于是给出

$$e_{n+1}=\left(\frac ba+O(|e_n|+|e_{n-1}|)\right)e_ne_{n-1}.$$

若 $b\ne0$，并把渐近误差规律写成 $|e_{n+1}|\sim K|e_n|^\alpha$，同样有 。误差乘积关系要求 ，故 。这是解释一般非退化情形收敛阶的渐近推导，完整局部收敛保证还要求两个初值足够接近；特殊函数可能更快，重根则不能套这个单根结论。

比较方法时，也要比较一次求值的成本。Newton 一步通常需要 $f$ 与 $f'$；割线一步只添一个 $f$ 值。导数很便宜时 Newton 可能占优，导数很贵时则未必。仅把 2 与 1.618 排个大小，不能得出所有程序的耗时结论。

在下面的比较实验中，用同一函数分别执行 Newton 和割线，并查看每一步的直线与数值记录。先在 $x^2-3$ 上观察接近根后的加速，再切到三次函数的循环例子。重根案例会让你看到另一种“慢”：点一直靠近根，但误差只按固定比例缩小。

让快速候选服从区间保证

有时可以同时使用两种证据：保留异号区间，再让 Newton 或插值给出一个候选点。如果候选不可靠，就回到二分。这里给一个规则简单、收敛容易证明的版本。

设当前区间为 $[a,b]$，宽度 $w=b-a$。从当前一个端点试算 Newton 候选 $z$。只有导数非零、候选和函数值都有限，且

$$a+\frac w4\le z\le b-\frac w4$$

时才接受；其余情况使用中点。算出所选点的函数值后，仍按符号保留夹住根的一段。

只有中央半区内的候选才被接受，因此保留下来的区间至多是原宽度的四分之三；退回二分时至多保留一半。

这样即使接受的候选并非中点，它也离两端至少四分之一宽度，所以保留下来的新区间至多宽 $3w/4$；回退二分则至多宽 $w/2$。连续性和可信符号使根一直留在区间内，而宽度至少按 $(3/4)^k$ 缩小，便得到全局夹逼保证。

这条保守规则可能拒绝已经很靠近根的优秀候选，因而不能承诺保留纯 Newton 的局部二次速度。实际的 Brent 类算法会结合插值、区间和更细的接受条件；本章实验实现的是刚刚定义的保护规则，不能把它与完整 Brent 算法混为一谈。回到第一个实验切换“带保护的 Newton”，观察哪一步接受候选、哪一步退回中点，以及区间是否仍持续缩小。

停止时，交出哪一种证据

二分或保护方法可以报告最终区间与中点，半宽就是明确的绝对误差界。不动点法在已验证的收缩条件下，可以报告后验界。Newton 或割线若只交一个近似值，则需要另外检查残差、步长、定义域和异常状态。

残差与根误差之间也有一条有条件的桥。若已知目标根 $r$ 与近似值 $\widehat r$ 同在一个区间，且这个区间上 $|f'(x)|\ge m>0$，中值定理给出

$$|f(\widehat r)|=|f'(\xi)|\,|\widehat r-r|, \qquad |\widehat r-r|\le\frac{|f(\widehat r)|}{m}.$$

没有 $m$，小残差未必是小根误差。例如 $f(x)=10^{-8}(x-2)$，在 $x=1$ 处残差只有 ${10}^{}$，离根却仍差 1。把函数乘以很小的常数会缩小残差，根的位置并没有改变。

实际程序还应区分“达到已设误差要求”与“无法再推进”。如果新点与旧点在浮点中完全相同，可能只是舍入造成停滞；超过最大步数、除数过小、函数值非有限，也应明确返回相应状态。双重检查很有用，但“步长小且残差小”本身依然不是无条件的根误差证明。

留几道题，把保证自己写出来

1. 对 $x^2-3$ 从 $[1,2]$ 二分，完成两次区间更新后，当前区间、中点及中点误差界分别是多少？若要求误差不超过 $10^{-6}$，最少要完成多少次更新？

查看解答

两次更新后为 $[1.5,1.75]$，中点为 $1.625$，界为 $0.125$。一般要求 $2^{-(k+1)}\le10^{-6}$，所以 。这里数的是区间更新；取当前中点无需再更新一次区间。

2. 用端点符号检测 $(x-1)^2$ 在 $[0,2]$ 上是否有根，为什么会遗漏？若将区间换成 $[-1,1]$ 并使用 $1/x$，又会出什么问题？

查看分析

第一个函数在根的两侧同号，端点同号不是“无根”的证据。第二个函数在零点无定义，不满足闭区间连续性，端点异号也不能推出有根。这两个反例分别说明异号只是可用的充分条件之一，而连续性是该保证的一部分。

3. 对 $g(x)=\sqrt{2+x}$、$[1,3]$，已经验证可取 $$。若某一步 ，给出当前点的误差界。若没有自映射条件，能否仅凭某处的导数值作同样保证？

查看解答

后验界为 $\frac{1/3}{1-1/3}\times0.006=0.003$。不能把一个点的导数或一个可能离开的区间上的导数界当作全程保证；需要确认迭代所在范围内的统一收缩条件，且每一步都留在该范围。

4. 对 $f(x)=(x-2)^4$，从 $x_0=3$ 做两步普通 Newton，再做一步已知重数为 4 的修正 Newton。比较误差。

查看计算

普通 Newton 每步使误差乘以 $3/4$，所以 $x_1=2.75$、$x_2=2.5625$。在 $x_2$ 应用修正公式 ，一步得到 2。这里 ，所以修正步在精确算术中恰好消掉全部误差；一般重根函数不能保证一步到根。

5. 用割线法求 $x^2-3=0$，初值为 1 和 2。验证新点为 $5/3$。若换成初值 $-2$ 与 2，会出现什么？

查看解答

斜率为 $(1-(-2))/(2-1)=3$，新点为 $2-1/3=5/3$。若用 $-2,2$，两处函数值都为 1，割线水平，分母为零，公式不能执行。两个输入不同不代表两个函数值必然不同。

6. 一个区间宽为 4，使用正文的中央半区准入规则。证明接受任意合格候选后，新区间宽不超过 3；解释为什么只要求候选在区间内部还不够保证同样的收缩比例。

查看推导

候选距左右端至少为 $4/4=1$。无论保留左段还是右段，其宽度都不超过 $4-1=3$。如果只要求在内部，候选可能离端点仅有极小距离，而保留的另一段几乎还是原宽，无法给出统一的 $3/4$ 收缩保证。

7. 已知 $f$ 的根与当前近似点都在 $[1,2]$，且该区间上 $|f'|\ge0.2$。残差不超过 $10^{-7}$ 时，根误差至多多少？把 换成 ，这一保证会改善吗？

查看解答

误差至多 $10^{-7}/0.2=5\times10^{-7}$。函数缩放后，残差和导数下界同时乘以 $10^{-4}$，二者之比不变。只报告变小后的残差，容易给出精度已经改善的错觉。

8

只要 Newton 法每一步的导数都不为零，迭代就一定收敛。

正确错误