每一步把正确位数翻倍
前十二章处理的都是「一步算完」的式子。卷 IV 换一种模式：一步步逼近。这带来一个漂亮的性质和一个新的麻烦。这一章讲性质——有一类迭代，每走一步，正确的位数就翻一倍。从半位起步，五步之后撞上 double 的天花板。而老老实实的二分法，要走 52 步。
求 √2，用牛顿法。迭代式化简之后特别简洁（这个式子巴比伦人三千七百年前就在用了）：
xₙ₊₁ = (xₙ + 2/xₙ) / 2
从 x₀ = 1 出发——这是个相当糟糕的起点，1 离 1.41421356… 差了 29%，连一位有效数字都算不上。
问：走几步之后，能拿到 double 的全部 15 到 16 位精度？
顺便对照：二分法（每次把区间对半砍）要走多少步？
逐步看
# xₙ₊₁ = (xₙ + 2/xₙ)/2，从 x₀ = 1 出发 # 真值 √2 = 1.4142135623730951 第 0 步 x = 1 相对误差 2.929e-1 正确位数 0.53 第 1 步 x = 1.5 相对误差 6.066e-2 正确位数 1.22 第 2 步 x = 1.4166666666666665 相对误差 1.735e-3 正确位数 2.76 第 3 步 x = 1.4142156862745097 相对误差 1.502e-6 正确位数 5.82 第 4 步 x = 1.4142135623746899 相对误差 1.128e-12 正确位数 11.95 ★ 第 5 步 x = 1.414213562373095 相对误差 1.570e-16 正确位数 15.80 ← 到顶了 第 6 步 x = 1.414213562373095 （不动了）
正确位数：0.53 → 1.22 → 2.76 → 5.82 → 11.95 → 15.80。
每一步大约翻一倍，直到撞上 double 的上限（15.95 位）就停住。五步。而二分法在同样的区间上要走 52 步——因为它每步只砍掉一个二进制位。
值得单独看一眼第 4 步到第 5 步：从 11.95 位跳到 15.80 位。按二次收敛本该跳到 23.9 位，但 double 只有 15.95 位可给。这就是这本书的天花板第一次以「好事」的形式出现——迭代法自带一个止损点：它算到机器精度就自动停下，不会继续往下钻。
用 mpmath 开 50 位精度重跑，第 5 步是 24.20 位——二次收敛在没有天花板的地方一直成立。
为什么会翻倍
牛顿法的想法一句话：在当前点把曲线换成它的切线，解切线的零点，当作下一个猜测。
xₙ₊₁ = xₙ − f(xₙ) / f′(xₙ)
展开泰勒之后能看到误差的递推关系：
eₙ₊₁ ≈ (f″(r) / 2f′(r)) · eₙ²
└─┬─┘
平方
误差 1e−3 ⇒ 下一步 1e−6
误差 1e−6 ⇒ 下一步 1e−12
误差 1e−12 ⇒ 下一步 1e−24（但 double 只到 1e−16，所以就停在那里）
「误差平方」和「正确位数翻倍」是同一句话。这类收敛叫二次收敛。
收敛速度分三档，认出它们值得花五分钟：
| 档 | 误差递推 | 每步多几位 | 典型算法 |
|---|---|---|---|
| 线性 | eₙ₊₁ ≈ C·eₙ | 固定几位（C=0.5 时 0.3 位） | 二分法、不动点迭代、梯度下降 |
| 超线性 | eₙ₊₁ ≈ C·eₙ^1.618 | × 1.618 | 割线法、拟牛顿（BFGS） |
| 二次 | eₙ₊₁ ≈ C·eₙ² | × 2 | 牛顿法 |
档位比常数重要得多。一个二次收敛的算法哪怕常数差十倍，也会在三四步之内追平并超过任何线性算法。这就是为什么优化里「用不用二阶信息」是一条如此重要的分界线。
三种失败
二次收敛有个前提：起点要离根足够近，而且 f′ 在根附近不接近 0。这两条一破，牛顿法就翻脸。
① 周期振荡：永远不收敛
f(x) = x³ − 2x + 2，从 x₀ = 0 出发： 0 → 1 → 0 → 1 → 0 → 1 → … ★ 完美的二周期。这个迭代永远不会停，也永远不会靠近任何根。
牛顿法没有全局收敛保证。它是个局部方法，而「局部」有多大，取决于函数长什么样——牛顿分形（Newton fractal）画的就是这件事：初值空间被切成无限复杂的碎片，相邻的两个起点可以收敛到完全不同的根。
② 重根：退化成线性
f(x) = x²（根是 0，但是重根），从 x₀ = 1 出发： 1.0 → 0.5 → 0.25 → 0.125 → 0.0625 → 0.03125 → 0.015625 → 0.0078125 ★ 每步只减半。这是线性收敛，不是二次。
原因是重根处 f′(r) = 0，误差递推里的分母塌了。要拿到 16 位精度得走 53 步，和二分法一样慢。（修法：用 xₙ₊₁ = xₙ − m·f/f′，m 是重数；或者对 f/f′ 用牛顿法。）
③ 导数接近 0：一步弹到天边
f(x) = x³ − x，从 x₀ = 0.5774 出发（这里 f′ ≈ 0）： 0.577400 → 2234.73 → 1489.82 → 993.214 → … ★ 一步就被甩到两千多。之后要慢慢爬回来。
迭代式里除以了一个接近 0 的数——第 5 章的条件数在这里发作。这也是实践里最常见的一种失败：不是不收敛，是先失控再花很久收回来。
收敛这个词在工程语境里常被当成「跑完了」的同义词，但它有三个必须分开的含义：
- 收敛性：会不会收敛。牛顿法不保证（见上面三种失败）；二分法保证（只要初始区间两端异号）。
- 收敛速度：每步进步多少。牛顿法二次，二分法线性。
- 收敛到哪：多根的函数里，收敛到哪个根取决于初值，而这个依赖关系可以是分形的。
「快」和「稳」在这里是明确对立的。工程上的标准做法是混合：先用二分法／黄金分割保证进入正确的区间，再切到牛顿法冲刺。Brent 方法就是这个思路的经典实现，scipy.optimize.brentq 用的就是它——它同时拿到了二分法的保证和牛顿法的速度。
把「位数翻倍」亲眼看一遍，顺便看看三种失败：
import math
def newton_sqrt2(x0=1.0, n=7):
T, x = math.sqrt(2), x0
for i in range(n):
err = abs(x - T) / T
d = 16.0 if err == 0 else max(0.0, -math.log10(err))
print(f'第 {i} 步 x = {x!r:<22} 相对误差 {err:.3e} 正确位数 {d:5.2f}')
x = (x + 2 / x) / 2
newton_sqrt2()
# 二分法要几步？
lo, hi, k = 1.0, 2.0, 0
while hi - lo > 2.3e-16:
m = (lo + hi) / 2
if m * m > 2: hi = m
else: lo = m
k += 1
print('二分法步数 =', k) # 52
# 失败 ①：周期振荡
x = 0.0
print('x³−2x+2 从 0 出发：', end=' ')
for _ in range(6):
print(f'{x:.0f}', end=' → ')
x = x - (x**3 - 2*x + 2) / (3*x*x - 2)
print('…')
把起点从 1.0 改成 1000000.0 试试——牛顿法只多花三四步就追上来了（因为前几步是「把量级砍半」，之后立刻进入二次收敛）。这是它另一个被低估的优点：对糟糕的起点相当宽容，只要不落在那几个病态点上。
python3 newton.py
在线：python.org/shell。想看 50 位精度下的收敛：pip install mpmath，把 math.sqrt(2) 换成 mpmath.sqrt(2)，第 5 步会是 24.20 位。
你的 CPU 就在用它。硬件的除法和开方指令，很多实现是「查表得到一个粗略倒数 + 两三步牛顿迭代」。因为二次收敛，8 位的查表结果两步就变成 32 位，三步变成 64 位。《雷神之锤 III》那段著名的「快速平方根倒数」（0x5f3759df）正是这个结构：一个位技巧给出粗略初值，再来一步牛顿。
训练里的一阶 vs 二阶。梯度下降是线性收敛，牛顿法是二次收敛——那为什么深度学习不用二阶方法？因为牛顿法要算 Hessian（n² 个数）并求逆（n³ 次运算），而 n 是几十亿。L-BFGS、K-FAC、Shampoo 这些方法都在同一件事上做文章：用便宜的近似换回一点超线性收敛。
反向传播里的隐式层。Deep Equilibrium Model、神经 ODE、可微优化层——这些结构的前向传播本身就是一个求根过程，内部跑的正是牛顿法或它的变体。「三种失败」在这里全都会真实发生，所以这类模型的训练稳定性一直是个研究问题。
金融的隐含波动率。从期权价格反解波动率没有闭式解，业界标准做法就是牛顿法（用 Vega 作为导数）。而深度实值／虚值期权的 Vega 接近 0——正好是失败模式 ③。所以生产代码里一律用 Brent 或者带保护的牛顿法。
「迭代算法多跑几步总是更准。跑到时间用完为止，或者跑一万步保险。」
牛顿法在这个例子里 5 步之后就不动了——第 6 步和第 5 步的结果位模式完全相同。再跑一万步，只是把同一个值算一万遍。
更糟的情况是多跑反而变差：接近机器精度时，f(xₙ) 本身已经全是噪声（第 3 章的相消：x² − 2 在 x ≈ √2 处就是两个相近数相减），迭代式会被噪声推着在最后几个 ulp 之间随机游走。有些实现会因此出现「误差不降反升」的尾巴。
正确的做法是写一个能真正判断「到头了」的停机条件——而这恰恰是下一章的内容，也是这一整套东西里最容易写错的部分。算法怎么走，教科书都讲；什么时候停，几乎没人讲。
正确答案是 C：5 步。正确位数走的是 0.53 → 1.22 → 2.76 → 5.82 → 11.95 → 15.80。二分法要 52 步。
A 「大约 50 步」——这是二分法的答案（52 步），也是所有线性收敛算法的答案。猜 A 的直觉是「每步进步一点点」，这对绝大多数迭代算法都成立。二次收敛是个例外，而且是个大到改变工程决策的例外。 B 「大约 16 步，每步一位」——这个模型是「线性收敛，每步一位十进制」，比 A 快但还是线性。实际上第 3 步就已经拿到 5.8 位了，比这个模型快一倍多；到第 4 步（11.95 位）已经把 16 步模型甩开三倍。指数增长和线性增长的差距，前几步看不出来，之后就追不上了。 D 「2 步」——太乐观了，但方向是对的。如果起点更好（比如 1.4 而不是 1），确实两三步就够。牛顿法的步数几乎只取决于起点有多少位是对的：起点 1 位 → 2、4、8、16，四步；起点 4 位 → 8、16，两步。所以「花点力气选个好起点」在这类算法里回报极高——这就是硬件除法器要查表的原因。这一章的改写是关于「选哪种迭代」，以及怎么把两种拼起来：
纯牛顿法：x -= f(x)/fp(x)，跑固定步数。快，但可能振荡、可能飞出去、可能收敛到别的根。
带保护的牛顿法：维护一个包住根的区间 [lo, hi]；每步先试牛顿，如果结果跳出区间或者没让 |f| 变小，就退回二分。既有保证又有速度，二十行代码。
直接用现成的：scipy.optimize.brentq（保证收敛 + 超线性）、newton（带 fprime 走牛顿，不带走割线）。Brent 方法是这类问题的默认答案。
没有导数：用割线法（超线性 1.618）而不是数值差分求导——数值差分本身就是第 3 章的相消，会把导数的精度砍掉一半。
顺便一条经常被忽略的：如果你要反复解同一族问题（每次参数略有不同），用上一次的解当这次的起点。牛顿法的步数几乎只取决于起点质量，这一招常常能把五步降到一步。这个技巧叫 warm start，在优化、渲染、物理引擎里到处都是。
这一章的一句话
二次收敛把「多算一会儿」变成了「多算两步」——但它是一份有条件的礼物，条件是起点够近、导数不接近零，而这两个条件没人替你检查。
下一章讲这套东西里最容易写错的部分：什么时候停。会看到三种听起来都很合理、实际上都会骗你的停机信号——其中一个能让循环永远停不下来，而它的写法是 while (Math.abs(x1 - x0) > 1e-9)，几乎每个人都这么写过。