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

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

- 作者：David（道雾轩）
- 专栏：数值计算的艺术（https://daiw.org/manual/numerical-computing.md）
- 最后更新：2026-07-14
- 原文：https://daiw.org/manual/numerical-computing/iteration-order
- 转载与引用：请注明出处并附原文链接（https://daiw.org/about/copyright）

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

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

## 收敛阶：误差怎么缩

设第 $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$）。

阶越高，收敛越快。但记住[牛顿那章](https://daiw.org/manual/numerical-computing/newton)的教训：**高阶通常伴随更脆的稳定性**——快和稳往往不可兼得。

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

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

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

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

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

<Callout type="warn">
  **不动点迭代收敛的条件：$|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$ 是门手艺**——这也解释了为什么[灾难性抵消那章](https://daiw.org/manual/numerical-computing/cancellation)说「等价数学、不等价数值」。
</Callout>

## 割线法：免导数的牛顿

[牛顿法](https://daiw.org/manual/numerical-computing/newton)要导数 $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})}
$$

```python
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$。**这是验证「我的方法收敛阶对不对」的实用手段**——写完一个迭代法，测一下它的实际阶，和理论对不对得上，是很好的[正确性检查](https://daiw.org/manual/numerical-computing/conditioning)。

## 求根方法总表

| 方法 | 收敛阶 | 要导数 | 可靠性 |
| --- | --- | --- | --- |
| [二分](https://daiw.org/manual/numerical-computing/bisection) | $1$（线性） | 否 | ✅ 保证收敛（要初始区间） |
| 不动点 | $1$（线性） | 否 | 需 $\lvert g'\rvert<1$ |
| 割线 | $\approx1.618$（超线性） | 否 | 较脆，但常够用 |
| [牛顿](https://daiw.org/manual/numerical-computing/newton) | $2$（二次） | 是 | 脆（需好起点） |

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

## 小结与下一站

收敛阶 $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 分解](https://daiw.org/manual/numerical-computing/gaussian-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 混合求根法。