迭代被吸向一个不动点
往计算器里输入任意一个数，然后不停按 cos 键。结果会停在某个值附近不再变化，大约 0.7391。把函数的输出反复喂回它自己，这个简单动作就是不动点迭代：x，然后 g(x)，再 g(g(x))。当到达 g(x)=x 的点，也就是输入什么就原样输出什么的点，它就停下。那就是不动点。神奇之处在于，几乎无论从哪里出发，都会被吸向同一个点。但有个条件：在不动点附近，斜率 |g'| 必须小于 1，这样每一步距离才会缩小，形成收缩。这个想法藏在各处，从解方程到计算机图形、经济均衡，再到谷歌的网页排名。而牛顿法本质上也只是一种非常快的不动点迭代。
蓝色曲线是 g(x)=cos x，虚线是 y=x。它们相交的绿点就是不动点。点击一步会画出蛛网（cobweb）：从当前的 x 竖直上到曲线读出下一个值，再水平走到 y=x 线，把它当作新的 x。把起点 x0 移到任何地方，都能看到蛛网盘旋着被吸向交点。这一张图就是不动点迭代的全部。
为什么有些迭代会聚拢，有些会发散？答案就是一个斜率。这里的 g 是直线，不动点在 1，滑块 a 正是 g'。把 |a| 保持在 1 以下，绿色的蛛网就整整齐齐地收进不动点，这就是收缩。把 |a| 提到 1 以上，它变红，被推离不动点而发散。而且 |a| 越接近 0，需要的步数越少。小斜率就是快收敛。
还是同一条直线 g，但这次盯住 a 的符号。斜率的大小决定是否收敛，符号决定形状。a 为正时，是从单侧单调逼近不动点的阶梯。a 为负时，是跨过不动点上下来回的螺旋，每一步符号翻转而振荡。把滑块拖过 0，就能看到阶梯变螺旋、螺旋变阶梯的那一刻。
收敛或许有保证，但速度天差地别。达到 1e-6 容差所需的步数大约是 n ≈ log(tol)/log|g'|，曲线把这个步数对 |g'| 画出来。把滑块设在 0.5 附近，二十步左右就结束；推向 0.95，步数就暴涨到几百。接近 1 的收缩确实会收敛，却慢得让人着急。这正是为什么值得追求更聪明的方法。
这就是那个更聪明的方法。普通的不动点迭代是线性收敛，误差每一步只按固定比例（比如一半）缩小，柱子缓缓下降。牛顿法是二次收敛，误差每一步被平方，正确位数翻倍，柱子像悬崖一样跌落。用开关切换两者：要达到同样的 1e-10 精度，线性需要几十步，而二次只需四五步。这就是为什么牛顿法是最快的不动点迭代，它巧妙地把 g 设计成在根处 g'=0。