不动点迭代
在计算器里放进一个数，反复按 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 的收缩确实会聚拢，但慢得难受。所以需要更快的方法。横轴是斜率的大小，纵轴是需要的步数。
更快的方法就在这里。普通的不动点迭代是线性收敛，误差像减半那样每步只按固定比例缩小。条缓缓下降。牛顿法是 2 次收敛，误差每步被平方，正确位数翻倍，条像悬崖一样落下。在两者之间切换，同样的精度 1e-10，线性要几十步，2 次只要几步。牛顿把 g 设计成 g'=0，所以它是最快的不动点迭代。