二分法与不动点迭代 | 杨星宇

求解非线性方程 $f(x) = 0$ 是整个代数学最古老、最核心的问题之一。对于一次和二次方程，求根公式给出了优雅的封闭解析解。然而，代数求根的道路很快便遭遇了数学上的叹息之墙：著名的 Abel-Ruffini 定理宣告，五次及以上的普遍多项式方程不存在根式通解；而包含三角函数或指数的超越方程（如 $\cos x = x$ 或 $x^3 + 4x^2 = 10$ ），在解析上更是无法直接反演。

当解析公式穷途末路，计算科学便接管了战场：我们转向迭代逼近 (Iterative Approximation)。迭代法不再奢求一步到位的精确闭式解，而是从一个初始猜测 $x_0$ 出发，构造一串在几何上向真解 $x^*$ 稳步收敛的数值序列 $x_0, x_1, x_2, \dots$ 。

本篇笔记深入探讨一维非线性方程求解的两大基石范式：

二分法 (Bisection Method)：实数轴上的“二分搜索”。它依托 Bolzano 介值定理，通过维护一个严格变号的区间套逐步逼近真解。它虽然每步只能稳定获得 1-bit（约 0.3 位十进制）精度，但具备永不发散的绝对可靠性。
不动点迭代 (Fixed-Point Iteration)：动力系统视角的范式转换。它将静态方程 $f(x) = 0$ 转换为动态反馈系统 $x_{n+1} = g(x_n)$ 。在 Banach 压缩映射定理的庇护下，迭代函数的局部斜率 $|g'(x^*)| < 1$ 成为吸引子收敛的核心动力。

根、不动点与动力学转换

在深入分析收敛性之前，我们首先建立“函数的零点”与“迭代映射的不动点”之间的形式对应。

定义根

若 $f(x^*) = 0$ ，就称 $x^*$ 是 $f$ 的根或零点。

定义不动点

对函数 $g \colon D \to \mathbb{R}$ ，若 $x^* \in D$ 满足 $g(x^*) = x^*$ ，就称 $x^*$ 是 $g$ 的不动点。在几何上，不动点恰好是曲线 $y = g(x)$ 与对角线 $y = x$ 的交点。

定义不动点迭代

给定初始点 $x_0 \in D$ ，由迭代函数 $g$ 生成的序列定义为

x_{n+1} = g(x_n), \qquad n = 0,1,2,\dots

只要每一步的函数求值均合法定义。

定义序列收敛

$x_n \to x^*$ 的数学含义是：对任意给定的误差容限 $\varepsilon > 0$ ，存在一个指标 $N$ ，使得只要 $n \ge N$ ，就有 $|x_n - x^*| < \varepsilon$ 。平移后的序列具有完全相同的极限： $x_n \to x^*$ 蕴含 $x_{n+1} \to x^*$ 。

任何求根问题 $f(x) = 0$ 都可以通过代数变换改写成无穷多种不动点形式 $x = g(x)$ 。例如，引入任意非零常数 $\lambda$ ，定义

g_\lambda(x) = x - \lambda f(x).

显然 $f(x) = 0$ 当且仅当 $g_\lambda(x) = x$ 。也就是说， $f$ 的根与 $g_\lambda$ 的不动点在集合上严格一致。然而，代数形式的等价仅仅是第一步：迭代动力系统 $x_{n+1} = g(x_n)$ 究竟是收敛还是发散，完全取决于函数 $g$ 的解析性质。

例代数等价与动力学收敛的巨大鸿沟

考虑求解方程 $f(x) = x^2 - 2 = 0$ 的正根 $\sqrt{2} \approx 1.4142$ 。我们可以构造多种不动点形式：

$x = x - \tfrac{1}{4}(x^2 - 2)$
$x = 2 / x$
$x = \tfrac{1}{2}(x + 2/x)$

这三种形式的代数不动点完全相同。然而在数值迭代下：形式 2 在初值 $x_0 = 1$ 下会陷入 $1 \to 2 \to 1 \to 2 \dots$ 的无限振荡死循环；形式 1 以一阶线性速率缓慢逼近；而形式 3（即巴比伦/牛顿法）每迭代一步，有效精度位数就翻倍。

因此，将 $f(x)=0$ 转化为 $x=g(x)$ 并不是解法，而是一个需要经过压缩性证明来检验的算法设计。

两个存在性工具

定理介值定理

若 $f$ 在 $[a,b]$ 上连续且 $f(a)f(b) < 0$ ，则存在 $x^* \in (a,b)$ 使 $f(x^*) = 0$ 。

证明

必要时把 $f$ 换成 $-f$ ，可设 $f(a)<0<f(b)$ 。令 $S=\{x\in[a,b]:f(x)<0\}$ 。由实数完备性， $c=\sup S$ 存在；端点处的连续性保证 $a<c<b$ 。若 $f(c)<0$ ，连续性给出比 $c$ 更大且仍在 $S$ 中的点，与上确界矛盾；若 $f(c)>0$ ，则 $c$ 的整个小邻域都没有 $S$ 中的点，与 $S$ 中的点可从下方逼近上确界矛盾。因此 $f(c)=0$ 。

变号保证存在，不保证唯一。反过来， $f(a)f(b) > 0$ 也不能证明没有根：区间里可以穿过偶数次。

定理中值定理

若 $g$ 在 $[a,b]$ 上连续、在 $(a,b)$ 上可导，则对任意不同的 $x,y \in [a,b]$ ，存在介于二者之间的 $c$ ，使得

g(x) - g(y) = g'(c)\,(x-y).

证明

先设 $x<y$ ，从函数中减去割线：

h(t)=g(t)-g(x)-\frac{g(y)-g(x)}{y-x}(t-x).

于是 $h(x)=h(y)=0$ 。由已给出证明的 Rolle 定理，某个内点满足 $h'(c)=0$ ，代回即得公式。交换 $x,y$ 就覆盖另一种顺序。

介值定理制造根或不动点。中值定理把导数界变成函数改变量的界。

Lipschitz 条件与压缩

定义Lipschitz 条件

设 $g \colon [a,b] \to \mathbb{R}$ 。若存在有限常数 $L \in [0,\infty)$ ，使得对一切 $x,y \in [a,b]$ 有 $|g(x)-g(y)| \le L |x-y|$ ，就称 $g$ 在 $[a,b]$ 上是 Lipschitz 的。这样的 $L$ 叫 Lipschitz 常数。并不要求 $L < 1$ 。

定义压缩条件

若 Lipschitz 不等式对某个落在 $L \in [0,1)$ 里的常数成立，就称 $g$ 是 $[a,b]$ 上的压缩。若还满足 $g([a,b]) \subseteq [a,b]$ ，则 $g$ 是 $[a,b]$ 的压缩自映射：压缩让点靠近，自映射让每一步迭代仍留在区间里。

本文用 $L$ 同时表示 Lipschitz 常数，以及（当 $L < 1$ 时）压缩因子。 $L = 0$ 时 $g$ 是常数。有限的全局界 $|g'(x)| \le L < \infty$ 证明 $g$ 是 Lipschitz 的；只有当这个界可以取成 $L < 1$ 时，才证明 $g$ 是压缩。找到一个点使 $|g'(x)| > 1$ ，排除的是“用导数判别压缩”，并不能排除 Lipschitz 连续性。

命题导数界给出 Lipschitz 估计

若 $g$ 在 $[a,b]$ 上连续、在 $(a,b)$ 上可导，且存在有限 $L \ge 0$ 使 $|g'(s)| \le L$ 对一切 $s \in (a,b)$ 成立，则对一切 $x,y \in [a,b]$ 有 $|g(x)-g(y)| \le L |x-y|$ 。从而 $g$ 是 Lipschitz 的。若同一界还能取成 $L < 1$ ，则 $g$ 是压缩。

证明

若 $x = y$ ，结论显然。若 $x \neq y$ ，中值定理给出介于二者之间的 $c$ ，使 $g(x)-g(y) = g'(c)(x-y)$ 。取绝对值并用导数界，得到 $|g(x)-g(y)| = |g'(c)|\,|x-y| \le L |x-y|$ 。

这个全局常数是整段区间上的界，一般不是单独那个数 $|g'(x^*)|$ 。

二分法

设 $f$ 在 $[a_0,b_0]$ 上连续且 $f(a_0)f(b_0) < 0$ 。由介值定理，初始括号里至少有一个根。对 $k \ge 1$ ，令中点 $x_k = (a_{k-1}+b_{k-1})/2$ 。若 $f(x_k) = 0$ ，停止。否则保留端点值仍然异号的那一半。

命题括号不变式

在返回精确根之前，每一步二分都给出区间 $I_k = [a_k,b_k]$ ，满足

f(a_k)f(b_k) < 0, \qquad b_k - a_k = (b_0-a_0)/2^k,

且 $I_k$ 里至少有一个根。区间是套着的： $I_k \subseteq I_{k-1}$ 。

证明

$I_0$ 由初始假设和介值定理成立。假定对 $I_{k-1}$ 成立。中点把它分成两个闭半区间。若中点不是根，则 $f(a_{k-1})f(x_k)$ 与 $f(x_k)f(b_{k-1})$ 恰有一个为负。留下那一半，变号括号得以保持，因而至少含一个根。它是前一括号的子集，宽度减半。归纳给出套叠和宽度公式。

直观上，二分法反复寻找介值定理保证有根的区间，直到区间足够小。假设成立时一定收敛，只是慢。

算法 1 缓存端点值的二分法

Require: 连续函数 $f$ ，端点 $a < b$ ，容差 $\varepsilon > 0$ ，最大中点数 $N_{\max}$

1:求值并缓存 $f_a = f(a)$ 、 $f_b = f(b)$

2:if $f_a = 0$ then

3:return $a$

4:end if

5:if $f_b = 0$ then

6:return $b$

7:end if

8:if $f_a f_b > 0$ then

9:拒绝该区间：不是已核证的括号

10:end if

11:for $k \gets 1$ to $N_{\max}$ do

12: $x \gets (a+b)/2$ ，只求一次 $f_x = f(x)$

13:if $f_x = 0$ then

14:return $x$

15:end if

16:if $f_a f_x < 0$ then

17: $b \gets x$ ， $f_b \gets f_x$

18:else

19: $a \gets x$ ， $f_a \gets f_x$

20:end if

21:if $(b-a)/2 < \varepsilon$ then

22:return 更新后括号的中点

23:end if

24:end for

25:报告已达最大迭代次数

两次初始端点求值之后，每圈只需一次新的函数求值。

定理二分法的收敛与先验误差

设 $f$ 在 $[a_0,b_0]$ 上连续且 $f(a_0)f(b_0) < 0$ 。套着的二分括号确定一个根 $x^*$ 。若 $x_k$ 是第 $k$ 个中点，则

|x^* - x_k| \le \Bigl(\frac{1}{2}\Bigr)^k (b_0 - a_0).

从而 $x_k \to x^*$ 。

证明

由括号不变式， $I_k$ 闭、非空、套叠，长度 $(b_0-a_0)/2^k \to 0$ 。闭区间套原理给出同时属于每个 $I_k$ 的唯一点 $x^*$ 。对每个 $k$ ，介值定理给出根 $r_k \in I_k$ 。 $r_k$ 与 $x^*$ 同在 $I_k$ 里，故 $|r_k-x^*| \le b_k-a_k \to 0$ 。于是 $r_k \to x^*$ ，连续性给出 $f(x^*) = 0$ 。

第 $k$ 步开始时，这个根 $x^*$ 和第 $k$ 个中点 $x_k$ 都在 $I_{k-1}$ 里。区间里任何一点离中点最远不超过半宽，所以

|x^* - x_k| \le \frac{b_{k-1}-a_{k-1}}{2} = \frac{b_0-a_0}{2^k}.

右端趋于零，故 $x_k \to x^*$ 。

这是先验估计：只用初始宽度和步数，不必知道根，也不必对 $f$ 求导。

命题达到严格容差的充分中点数

给定 $\varepsilon > 0$ ，整数

K = \Bigl\lfloor \log\bigl((b_0-a_0)/\varepsilon\bigr) / \log 2 \Bigr\rfloor + 1

足以保证 $|x^* - x_K| < \varepsilon$ 。

证明

先验估计严格小于 $\varepsilon$ ，当且仅当 $(b_0-a_0)/2^K < \varepsilon$ 。量都为正，这等价于 $K > \log((b_0-a_0)/\varepsilon)/\log 2$ 。对任意实数 $r$ ，已知满足 $K > r$ 的最小整数是 $\lfloor r \rfloor + 1$ 。

若目标是非严格界 $|x^*-x_K| \le \varepsilon$ ，则 $K = \lceil \log_2((b_0-a_0)/\varepsilon) \rceil$ 就够。差别只在对数比恰好是整数时出现。

设中点迭代次数为 $N$ 。由停机结果， $N = O(\log((b_0-a_0)/\varepsilon))$ 。若一次求 $f$ 的代价是 $T_f$ ，算法时间是 $O(N T_f)$ 。滚动存储是 $O(1)$ 。“线性收敛”说的是误差如何收缩。Big-O 运行时间数的是运算。即使两者都带对数，问的也不是同一件事。

作为具体算例，考虑把二分法应用于区间 $[1,2]$ 上的三次多项式 $f(x) = x^3 + 4x^2 - 10$ 。由于 $f(1) = -5 < 0$ 且 $f(2) = 14 > 0$ ，初始变号括号合法。对于目标容差 $\varepsilon = 10^{-4}$ ，理论上保证精度的严格中点步数是 $K = 14$ 。若仅使用残差准则，程序可能会提前终止（在第 9 步时就有 $|f(x_9)| < 10^{-4}$ ），但残差反映的是函数曲线在纵轴上与零的距离，而二分法的误差证书严格保证的是横轴上近似点与真实根的距离。

这个交互图需要启用 JavaScript。

不动点迭代

要把 $f(x) = 0$ 变成不动点问题，选非零常数 $\lambda$ ，令 $g_\lambda(x) = x - \lambda f(x)$ 。则 $f$ 的根恰好是 $g_\lambda$ 的不动点。对应算法是 $x_{n+1} = x_n - \lambda f(x_n)$ 。不同的 $\lambda$ 给出不同的映射。这里 $g_\lambda'(x) = 1 - \lambda f'(x)$ ，所以 $\lambda$ 会改变局部吸引或排斥。

命题收敛迭代的极限是不动点

设 $x_{n+1} = g(x_n)$ ， $x_n \to x^*$ ，且 $g$ 在 $x^*$ 连续。则 $g(x^*) = x^*$ 。

证明

由 $x_n \to x^*$ 得 $x_{n+1} \to x^*$ 。迭代规则给出 $x_{n+1} = g(x_n)$ ，故 $\lim x_{n+1} = \lim g(x_n)$ 。 $g$ 在 $x^*$ 连续，于是 $g(x_n) \to g(x^*)$ 。因此 $g(x^*) = x^*$ 。

这是必要条件，不是充分条件。映射可以有不动点，而迭代从它旁边散开。把极限送进 $g$ ，用的是 $g$ 的连续性，不是 $g$ 的线性。例如 $g(u) = u^2$ 非线性，但连续。

定理闭区间上的不动点定理

设 $g$ 在 $[a,b]$ 上连续且 $g([a,b]) \subseteq [a,b]$ 。则 $g$ 在 $[a,b]$ 上至少有一个不动点。

再设 $g'$ 在 $(a,b)$ 上存在，且存在常数 $0 \le L < 1$ ，使 $|g'(x)| \le L$ 对一切 $x \in (a,b)$ 成立。则不动点唯一，并且对每个 $x_0 \in [a,b]$ ，迭代 $x_{n+1} = g(x_n)$ 留在 $[a,b]$ 里并收敛到该不动点。

记号 $g([a,b])$ 表示把 $g$ 作用在区间里每个输入上得到的输出集合。导数界是判断压缩的方便充分条件，不能代替自映射条件。初学者常容易忽略自映射条件 $g([a,b]) \subseteq [a,b]$ 。若缺少这一前提，不仅无法保证不动点落在指定区间内，迭代序列在演化过程中也随时可能跳出区间导致无定义。

证明

存在性。 $x^*$ 是不动点当且仅当 $g(x^*)-x^* = 0$ 。令 $q(x) = g(x)-x$ ，它在 $[a,b]$ 上连续。因为 $g$ 把区间映回自身， $a \le g(a) \le b$ 、 $a \le g(b) \le b$ ，从而 $q(a) \ge 0$ 、 $q(b) \le 0$ 。若某一端为零，该端点就是不动点。否则 $q(a) > 0 > q(b)$ ，介值定理给出 $x^* \in (a,b)$ 使 $q(x^*) = 0$ 。

唯一性。 设 $p$ 、 $q$ 都是不动点。则 $p-q = g(p)-g(q)$ 。导数假设和中值定理给出 $|p-q| = |g(p)-g(q)| \le L |p-q|$ 。由于 $L < 1$ ，只能 $p = q$ 。

不变性与收敛。 自映射让每一步迭代留在 $[a,b]$ 。设 $x^*$ 是唯一不动点。则 $|x^*-x_{n+1}| = |g(x^*)-g(x_n)| \le L |x^*-x_n|$ ，归纳得 $|x^*-x_n| \le L^n |x^*-x_0|$ 。 $L < 1$ ，右端趋于零。

局部导数检验解释单个不动点附近的行为： $|g'(x^*)| < 1$ 时，在 $g'$ 适当连续的假设下局部吸引； $|g'(x^*)| > 1$ 时局部排斥。局部检验并不能证明从大区间里每个点都收敛。

算法 2 带后验检验的不动点迭代

Require: 映射 $g$ ，初值 $x_0$ ，压缩界 $0 \le L < 1$ ，目标误差 $\varepsilon > 0$ ，最大步数 $N_{\max}$

1: $x \gets x_0$

2:for $n \gets 0$ to $N_{\max}-1$ do

3: $y \gets g(x)$

4:if $L = 0$ then

5:return $y$

6:end if

7:if $L/(1-L)\, |y-x| \le \varepsilon$ then

8:return $y$

9:end if

10: $x \gets y$

11:end for

12:报告已达最大迭代次数

停机检验来自可计算估计

|x^* - x_{n+1}| \le \frac{L}{1-L}\, |x_{n+1}-x_n|.

证明

由压缩估计，对一切 $j \ge n+1$ 有 $|x_{j+1}-x_j| \le L |x_j-x_{j-1}|$ ，从而 $|x_{j+1}-x_j| \le L^{j-n} |x_{n+1}-x_n|$ 。对 $m > n+1$ ，三角不等式和等比级数给出

|x_m - x_{n+1}| \le |x_{n+1}-x_n| \sum_{j=n+1}^{m-1} L^{j-n}.

令 $m \to \infty$ ，得到 $|x^*-x_{n+1}| \le \frac{L}{1-L}|x_{n+1}-x_n|$ 。

先验估计 $|x^*-x_n| \le L^n |x^*-x_0|$ 意味着 $N$ 随 $1/\varepsilon$ 对数增长，但常数在 $L$ 靠近 $1$ 时变差。滚动存储是 $O(1)$ 。

这个交互图需要启用 JavaScript。

典型例题与辨析

练习余弦迭代

考虑 $[0,1]$ 上的 $\cos x - x = 0$ 。写成 $x = g(x)$ ，其中 $g(x) = \cos x$ 。从 $x_0 = 1/2$ 出发考虑 $x_{n+1} = g(x_n)$ 。证明方程在 $[0,1]$ 上恰有一个根， $g([0,1]) \subseteq [0,1]$ ，并且迭代收敛。

证明

令 $F(x) = \cos x - x$ 。它连续， $F(0) = 1 > 0$ ， $F(1) = \cos 1 - 1 < 0$ ，介值定理给出一个根。又 $F'(x) = -\sin x - 1 < 0$ 在 $[0,1]$ 上成立，故 $F$ 严格递减，根唯一。

对 $x \in [0,1]$ ，余弦在此区间递减，故 $\cos 1 \le \cos x \le 1$ 。由于 $0 < \cos 1 < 1$ ，映射把 $[0,1]$ 映回自身。

$g(x) = \cos x$ 在 $[0,1]$ 上连续、在 $(0,1)$ 上可导，且 $|g'(x)| = \sin x \le \sin 1 < 1$ 。不动点定理的全部假设以 $L = \sin 1$ 成立。因此 $g$ 在 $[0,1]$ 上有唯一不动点，迭代对每个 $x_0 \in [0,1]$ 都收敛，包括 $x_0 = 1/2$ 。

练习检验假设

设 $g(x) = x - \frac{1}{\pi}\sin(\pi x)$ ， $x \in [0,1]$ 。证明 $g$ 把 $[0,1]$ 映入自身，从而至少有一个不动点；再证明用于唯一性的导数条件失败，并在 $[0,1]$ 上解 $g(x) = x$ 。

证明

因为 $g'(x) = 1 - \cos(\pi x) \ge 0$ ， $g$ 递增。端点值是 $g(0) = 0$ 、 $g(1) = 1$ ，故 $0 \le g(x) \le 1$ 。连续性和自映射给出至少一个不动点。

唯一性的导数条件失败： $|g'(2/3)| = |1 - \cos(2\pi/3)| = 3/2 > 1$ ，不存在 $L < 1$ 使 $|g'(x)| \le L$ 在整个 $(0,1)$ 上成立。映射仍然是 Lipschitz 的，可取常数 $L = 2$ ，因为 $0 \le g'(x) \le 2$ 。单凭这个 Lipschitz 估计给不出唯一性。

不动点方程是 $\sin(\pi x) = 0$ ，在 $[0,1]$ 上恰好当 $x = 0$ 或 $x = 1$ 。所以有两个不动点。

连续性配合不变区间保证了不动点的存在性；全局导数压缩界则进一步确立了唯一性，并确保从区间内任意初值出发均全局收敛。若自映射条件失效，该定理无法给出任何保证；若仅是压缩界不满足，不动点仍可能存在，但其唯一性与迭代收敛性必须借助其他手段单独判定。

下一篇把 Newton 法写成一个特别选定的不动点映射。本页属于计算数学阅读路径。

根、不动点与动力学转换

两个存在性工具

Lipschitz 条件与压缩

二分法

不动点迭代

典型例题与辨析

评论