不动点与割线法 · 收敛阶怎么量 · 数值计算的艺术

二分是「线性」、牛顿是「二次」——这个「收敛阶」到底怎么定义、怎么测？这一章讲透不动点迭代（以及它收敛的条件）、免导数却快过二分的割线法（收敛阶是黄金比 1.618），并给一张求根方法的取舍总表。

不动点与割线法 · 收敛阶怎么量

前两章说二分「线性收敛」、牛顿「二次收敛」。这个「阶」到底啥意思？这一章把这把尺子讲清，顺带认识两个方法：最本质的不动点迭代，和最实用的割线法。

收敛阶：误差怎么缩

设第 $n$ 步的误差是 $e_n$ 。收敛阶（order of convergence） $p$ 描述误差怎么一步步缩小：

e_{n+1} \approx C\, e_n^{\,p}

$p=1$ （线性）：每步误差乘一个固定比例（如二分乘 $0.5$ ）。每步多算准固定位数。
$p=2$ （二次）：每步误差取平方。正确位数翻倍（牛顿）。
$1<p<2$ （超线性）：介于两者之间，比线性快、比二次省（割线法， $p\approx1.618$ ）。

阶越高，收敛越快。但记住牛顿那章的教训：高阶通常伴随更脆的稳定性——快和稳往往不可兼得。

不动点迭代：一切迭代的原型

求根最本质的框架，是不动点迭代：把 $f(x)=0$ 改写成 $x = g(x)$ 的形式，然后反复代入：

x_{n+1} = g(x_n)

「不动点」指 $x^* = g(x^*)$ 的那个点——迭代收敛到它，它就是解。最干净的例子：反复按计算器的 cos 键，数值会收敛到一个定值（方程 $x=\cos x$ 的解）：

import math
x = 0.5
for _ in range(30):
    x = math.cos(x)
print(x)      # 0.7390851332151607  —— 收敛到 cos 的不动点

不动点迭代收敛的条件： $|g'(x^*)| < 1$ 。 直觉： $g'$ 是迭代每步的「放大率」——小于 1，误差每步收缩（收敛）；大于 1，误差每步放大（发散）。而且 $|g'|$ 越小，线性收敛越快。

关键陷阱：同一个方程，改写成 $x=g(x)$ 的方式有很多种，有的收敛、有的发散！ 比如解 $x^2 - 2 = 0$ ：写成 $x = 2/x$ 会在两个值间震荡永不收敛（ $g'=-2/x^2$ ，在根处 $|g'|=1$ ）；而写成 $x = \frac{1}{2}(x + 2/x)$ （其实就是牛顿法）则飞快收敛。选对 $g$ 是门手艺——这也解释了为什么灾难性抵消那章说「等价数学、不等价数值」。

割线法：免导数的牛顿

牛顿法要导数 $f'$ ，可很多时候导数难求或根本没有（比如 $f$ 是一段复杂的仿真代码）。割线法（secant method） 的主意：用差商近似导数——拿最近两个点连一条割线，代替切线：

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

def secant(f, x0, x1, tol=1e-14, maxiter=50):
    f0, f1 = f(x0), f(x1)
    for _ in range(maxiter):
        if abs(f1) < tol:
            return x1
        x2 = x1 - f1 * (x1 - x0) / (f1 - f0)    # 差商代替 f'
        x0, f0, x1, f1 = x1, f1, x2, f(x2)
    return x1

root = secant(lambda x: x*x - 2, 1.0, 2.0)
print(root, abs(root - math.sqrt(2)))   # 几步就到 ~1e-15

它的收敛阶是 $p\approx1.618$ ——正是黄金比例（ $\frac{1+\sqrt5}{2}$ ），一个数学上的小惊喜。超线性，虽不及牛顿的二次，但省掉了求导数的麻烦，实践中常是更划算的选择。

怎么「测」出收敛阶

阶不只是理论——你能从一次真实运行里估出来。连续三步的误差 $e_{n-1},e_n,e_{n+1}$ ，代入：

p \approx \frac{\ln(e_{n+1}/e_n)}{\ln(e_n/e_{n-1})}

跑一遍牛顿法收集误差、代进去，你会得到接近 $2$ ；跑割线法，得到接近 $1.618$ 。这是验证「我的方法收敛阶对不对」的实用手段——写完一个迭代法，测一下它的实际阶，和理论对不对得上，是很好的正确性检查。

求根方法总表

方法	收敛阶	要导数	可靠性
二分	$1$ （线性）	否	✅ 保证收敛（要初始区间）
不动点	$1$ （线性）	否	需 $\lvert g'\rvert<1$
割线	$\approx1.618$ （超线性）	否	较脆，但常够用
牛顿	$2$ （二次）	是	脆（需好起点）

实践里默认用哪个？——混合方法。 成熟库的求根器（如 scipy.optimize.brentq，基于 Brent 方法）把二分的可靠和割线 / 反二次插值的快焊在一起：平时走快的，一旦跳出夹根区间就退回稳的二分。于是它既保证收敛、又通常超线性快。所以工程上：能用 brentq 就别自己裸写牛顿——除非你有充分理由（比如导数极易得、且你会给它加保险）。

小结与下一站

收敛阶 $p$ （ $e_{n+1}\approx C e_n^p$ ）衡量误差缩多快：线性（ $p=1$ ）、超线性（ $1<p<2$ ）、二次（ $p=2$ ）。不动点迭代是一切迭代的原型，收敛要 $|g'|<1$ 、且选对 $g$ 是手艺；割线法免导数、收敛阶是黄金比 $1.618$ ；阶还能从运行数据实测。实践默认用 Brent 类混合方法。

求根这一站到此结束——你握住了「可靠 vs 快」这条贯穿数值迭代的主线。下一站是数值计算里最庞大、也最基础的一块：解线性方程组 $Ax=b$ 。从人人都学过、但暗藏数值陷阱的高斯消元开始。👉 高斯消元与 LU 分解。

参考文献

[1] Burden & Faires.《Numerical Analysis》, §2.2, §2.4 —— 不动点迭代与割线法。
[2] Tim Sauer.《Numerical Analysis》, §1.2 —— 收敛阶的定义与测量。
[3] Richard Brent.《Algorithms for Minimization without Derivatives》1973 —— Brent 混合求根法。

不动点与割线法 · 收敛阶怎么量

本页目录