什么时候可以停下来
教科书花很多篇幅讲迭代怎么走，几乎不讲什么时候停。而在真实代码里，停机条件是 bug 密度最高的一行——它同时要处理精度、性能、死循环和量级，而它通常被随手写成一个 1e-9。这一章拆三种停机信号，每一种都有一个它骗你的场景。
用牛顿法解 x² = 10²⁰（真解是 10¹⁰）。停机条件写成最常见的那一种：
let x0 = 1, x1 = 0;
do {
x0 = x1 || 1;
x1 = (x0 + 1e20 / x0) / 2;
} while (Math.abs(x1 - x0) > 1e-9); // ← 步长小于 1e-9 就停
问：这个循环会怎么样？
第二问：如果把判据换成「残差小于 1e-9」，也就是 Math.abs(x1*x1 - 1e20) > 1e-9，会好一些吗？
① 步长判据：在大数上永远达不到
真解是 10¹⁰。 ulp(10¹⁰) = 1.9073486328125e−6 也就是说：在答案附近，两个相邻的 double 之间就差 1.9 × 10⁻⁶。 ⟨|x₁ − x₀| 要么是 0（完全收敛，两步给出同一个 double），要么至少是 1.9e−6。⟩ 它不可能落在 (0, 1e−9) 这个区间里。 而牛顿法收敛之后 x₁ 和 x₀ 完全相等 ⇒ |x₁ − x₀| = 0 < 1e−9 ⇒ 会退出。 ★ 但只要迭代在最后两个 ulp 之间来回抖动（这在噪声下很常见）， 步长永远是 1.9e−6，判据永远不满足 —— 死循环。
答案是 C：这段代码可能永远不退出，而且它退不退出取决于运气。在 x² = 10²⁰ 这个具体例子上它恰好收敛到不动点然后退出；把 1e20 换成 1.23456789e20，或者换个初值，很容易撞上末尾抖动。
这类 bug 最恶劣的地方在于它不可复现。同一份代码，换个输入就挂；换台机器（第 19 章）也可能挂。而它在测试用例（数字都在 1 附近）上永远是绿的。
修法是把绝对判据换成相对判据：
// 这么写：绝对步长 while (Math.abs(x1 - x0) > 1e-9) // 改成：相对步长 + 迭代上限 while (Math.abs(x1 - x0) > 1e-12 * Math.abs(x1) && ++k < 100)
1e-12 * |x1| 在 10¹⁰ 附近是 10⁻²，远大于 ulp，正常可达。而在 0.001 附近是 10⁻¹⁵，也正常可达。相对判据自动跟着量级走。
那个 ++k < 100 不是防御性编程，是必需品。任何浮点迭代都必须有迭代上限，理由在这一章反复出现：你无法证明步长一定会降到某个绝对值以下。
② 残差判据：残差小不代表离根近
第二问的答案是：不一定更好，有时更糟。看这个：
f(x) = (x−1)³ | 离根多远 |x−1| | 残差 |f(x)| |
|---|---|---|
| x = 1.001 | 10⁻³ | 10⁻⁹ |
| x = 1.0001 | 10⁻⁴ | 10⁻¹² |
| x = 1.00001 | 10⁻⁵ | 10⁻¹⁵ |
残差已经到 10⁻¹⁵ 了——比机器精度还小——而你离根还有 10⁻⁵。用残差当判据，你会在离根十万分之一的地方宣布胜利。
这就是第 7 章那件事在迭代语境下的复现：残差量的是后向误差，你想要的是前向误差，中间隔着条件数。这里 f′(1) = 0（重根），条件数是无穷大。
反方向也会出问题：如果 f 的量级很大（比如 f(x) = 10¹⁰(x−1)），那么在离根 10⁻¹⁶ 的地方残差还有 10⁻⁶，判据永远不满足。残差判据必须归一化——除以 |f(x₀)| 或者 |f′|·|x|，否则它的量纲根本对不上。
③ 步长趋于 0，不代表在收敛
这一条最反直觉，用一个一行的反例最清楚：
xₙ₊₁ = xₙ + 1/n （调和级数） 一百万步之后： 步长 = 1e−6 ← 早就小于任何合理的 tol x = 14.392727 ← 还在涨，而且会一直涨到无穷 ★ 步长趋于 0 是收敛的必要条件，不是充分条件。
这在实践里不是数学游戏。任何线性收敛且收敛因子接近 1 的迭代，都长这样：步长每步只缩小 0.1%，看起来「快停了」，实际上离答案还有十万八千里。梯度下降在病态的损失面上（长条形山谷）就是这个样子——loss 曲线看着平了，其实只是在沿着谷底慢慢挪。
一个能用的停机条件至少有三个部分，缺一不可：
- 相对判据（跟着量级走）：
|Δx| ≤ rtol·|x| + atol。atol兜住 x 接近 0 的情况——和第 12 章的比较判据是同一个式子，因为它们本来就是同一件事。 - 迭代上限：
k < kmax。不是可选项。没有它，任何浮点迭代都可能不终止。 - 无进展检测：如果连续几步残差不降（甚至上升），提前退出并报告没收敛，而不是继续跑或者假装成功。
还有第四条，最常被跳过、也最重要：退出之后要告诉调用方「你是怎么退出的」。收敛了、撞上迭代上限了、还是卡住了——这三种情况的结果可信度完全不同。scipy.optimize 的返回对象里那个 success 和 message 字段，就是干这个的，而它们经常被无视。
tolerance（容差）这个参数名在数值库里指的东西各不相同，用之前一定要看文档：
xtol：自变量的容差 —— 步长判据。ftol：函数值的容差 —— 残差判据。gtol：梯度的容差 —— 优化里的一阶最优性判据。rtol / atol：相对／绝对，通常和上面三个组合出现（xrtol、fatol……）。
它们量的是完全不同的东西，而且互相之间没有换算关系（换算系数就是条件数，你不知道）。「把 tol 调小一点」这个动作，在不同的参数上意味着完全不同的事——把 ftol 调小可能毫无作用（残差已经是噪声了），把 xtol 调小可能直接死循环。
一个能直接抄的模板
function solve(f, fp, x0, opts = {}) {
const { rtol = 1e-12, atol = 0, maxIter = 100, ftol = 0 } = opts;
let x = x0, fx = f(x), best = Math.abs(fx), stall = 0;
for (let k = 0; k < maxIter; k++) {
const d = f(x) / fp(x);
const xn = x - d;
// ① 相对 + 绝对的步长判据
if (Math.abs(xn - x) <= rtol * Math.abs(xn) + atol)
return { x: xn, iters: k + 1, status: 'converged' };
// ③ 无进展检测：残差连续三步没变好就认输
const fn = Math.abs(f(xn));
if (fn >= best) { if (++stall >= 3) return { x: xn, iters: k + 1, status: 'stalled' }; }
else { best = fn; stall = 0; }
// ② 可选的残差判据（要归一化）
if (ftol > 0 && fn <= ftol * Math.abs(fx))
return { x: xn, iters: k + 1, status: 'residual' };
x = xn;
}
return { x, iters: maxIter, status: 'maxiter' }; // ★ 如实报告，别假装成功
}
二十行。它比「跑一百步然后返回 x」多的那些代码，全部是在处理「我怎么知道自己算完了」这一个问题。
三个反例，一个个看：
import math
# ① 步长判据在大数上够不着
print('ulp(1e10) =', math.ulp(1e10)) # 1.9073486328125e-06
print(' ⇒ |Δx| < 1e-9 在 1e10 附近永远达不到（除非 Δx 恰好是 0）')
# ② 残差小 ≠ 离根近
for x in (1.001, 1.0001, 1.00001):
print(f'x={x:<9} 离根 {abs(x-1):.0e} 残差 |f(x)| = {(x-1)**3:.3e}')
# ③ 步长趋于 0 ≠ 收敛
x = 0.0
for n in range(1, 1_000_001): x += 1 / n
print(f'走了一百万步，步长 = 1e-6，x = {x:.6f}，还在涨')
# 对比：相对判据在两个量级上都工作
def newton(a, rtol=1e-12, maxiter=100):
x = a
for k in range(maxiter):
xn = (x + a / x) / 2
if abs(xn - x) <= rtol * abs(xn): return xn, k + 1, 'converged'
x = xn
return x, maxiter, 'maxiter'
for a in (2.0, 1e20, 1e-20):
print(a, newton(a))
最后那三行会打出三个 'converged'——同一个 rtol=1e-12，在 2、10²⁰、10⁻²⁰ 上都正常工作。换成绝对判据，其中至少一个会挂。
python3 stop.py
在线：python.org/shell（一百万步循环大概两秒）。
训练循环的 early stopping。「验证集 loss 连续 N 轮没下降就停」——这就是上面的「无进展检测」，而且是它最有名的应用。patience 这个超参数就是上面那个 stall >= 3。两者的推理完全相同：单步的进展是有噪声的，要看趋势，而且要给出「为什么停」的理由。
数据库和分布式系统的重试。「重试到成功为止」是同一类 bug——没有上限的循环。指数退避 + 最大重试次数 + 明确的失败返回，结构上就是上面那个模板。
物理引擎的求解器。刚体约束求解每帧跑固定的迭代次数（比如 10 次），而不是跑到收敛——因为帧预算是硬约束。这是第四种停机条件：按预算停。它带来的后果（约束没解完，物体互相穿透一点）被当成可接受的视觉误差。这是个很值得学的工程姿态：明确地选择「算不完」，而不是假装算完了。
CI 里的数值测试。如果一个测试断言「优化器一定收敛到 1e-9」，那它迟早会在某台机器上随机失败（第 19 章）。正确的断言是「收敛了，且状态是 converged，且残差在合理范围」，而不是一个硬编码的精度数字。
「步长已经小于 1e-9 了，说明已经收敛，可以停了。」
这句话有三个独立的漏洞，这一章各给了一个反例：
① 1e-9 是绝对量，而 double 的分辨力随量级变化。在 10¹⁰ 附近，最小的非零步长就是 1.9×10⁻⁶——这个判据在那里从来没有被满足过，退出全靠步长恰好等于 0。
② 步长小只说明「这一步走得少」，不说明「离目标近」。xₙ₊₁ = xₙ + 1/n 的步长趋于 0，而它发散到无穷。线性收敛且因子接近 1 的迭代，全都长这样。
③ 就算真收敛了，收敛到的也可能不是你要的东西——牛顿法可能收敛到另一个根（第 13 章），优化器可能收敛到另一个局部极小。「停下来了」和「对了」是两件事，而停机条件只能验证前者。
正确答案是 C：这个循环可能永远不退出，因为 ulp(10¹⁰) = 1.9073486328125 × 10⁻⁶，步长要么是 0 要么至少这么大，落不进 (0, 10⁻⁹)。第二问：换成残差判据不一定更好——在重根附近，残差 10⁻¹⁵ 时离根还有 10⁻⁵。
(1 + 1e20)/2 − 1 ≈ 5×10¹⁹，大得吓人。牛顿法在远处的步长是巨大的，它靠这个快速逼近正确量级，然后才进入二次收敛。这也提醒一件事：把步长判据写成绝对值时，你其实同时在假设「答案的量级」和「步长的量级」——而这两个假设通常都没被写下来。
停机条件的改写，一条一条来：
while (Math.abs(x1 - x0) > 1e-9)
while (Math.abs(x1 - x0) > rtol * Math.abs(x1) + atol && ++k < maxIter)
return x; —— 调用方不知道你是收敛了还是跑满了
return { x, iters, status }; —— status 三选一：converged / maxiter / stalled
for (let i = 0; i < 1000; i++) x = step(x); —— 固定步数，不知道够不够
固定步数是一种合法的策略（实时系统就该这么做），但要明说：函数名叫 refineFixed，文档写「跑 N 步，不保证收敛」。把「算不完」变成一个显式的契约，而不是一个隐藏的假设。
最后一条通用建议，可能是这一章最值钱的：任何用了浮点迭代的函数，都应该能回答「我为什么停下来了」。写不出这个答案的实现，早晚会在某个输入上悄悄给出一个没收敛的结果——而且没人会知道。
这一章的一句话
停机条件不是一个数，是三件事的合取：一个跟着量级走的相对判据、一个不可省略的迭代上限、以及一句诚实的「我是怎么停的」。
下一章从一维迭代回到线性代数，讲一条被无数教科书写在公式里、却被所有实用库拒绝执行的操作：求逆矩阵。会看到一个 2×2 的方程组，不选主元的高斯消元给出 [0, 1]，而正确答案是 [1, 1]——第一个分量整个丢了，而修法只是「把两行换个位置」。