4. 迭代算法收敛：不动点迭代、牛顿法收敛条件、收敛阶的概念
各位同学，咱们今天聊点硬核的——迭代算法的收敛问题。
说实话，我刚入行那会儿，觉得迭代嘛，就是不断算呗。直到有一次，我写了个牛顿法解方程，结果死活不收敛，数值直接飞到了天上去。排查了半天，才发现初始点选得不对。嗯，从那以后，我对收敛条件就再也不敢马虎了。
这一节，咱们就掰开揉碎，把不动点迭代、牛顿法的收敛条件，还有收敛阶这几个概念讲清楚。
4.1 不动点迭代：最朴素的迭代思想
先说说不动点迭代。说白了，就是把一个方程 f(x)=0 改写成 x = g(x) 的形式。然后随便猜一个初始值 x0，代入右边算出 x1，再代入算出 x2……一直算到它不动了，那个值就是解。
举个例子，解方程 x^2 - 2 = 0，也就是求根号2。我们可以写成 x = 2/x，或者 x = (x + 2/x)/2。你试试看，第二种写法收敛特别快，第一种嘛……我劝你别试，会振荡的。
x_{k+1} = g(x_k)
这里有个关键问题：什么时候收敛？
我个人的经验是，看 g(x) 的导数。如果 |g'(x*)| < 1，那在解附近就是收敛的。如果大于1，那就发散。等于1？嗯，那是边界情况，需要单独分析。
g(x) = 1/x + 0.5 的形式，结果迭代了50步还没收敛。后来一检查，导数值接近0.9，收敛太慢了。换成牛顿法，3步搞定。
4.2 牛顿法：二阶收敛的利器
牛顿法，大家应该不陌生。它的迭代公式是：
x_{k+1} = x_k - f(x_k) / f'(x_k)这个公式的几何意义很直观：在 x_k 处做切线，切线与x轴的交点就是下一个点。你想想看，是不是比不动点迭代更聪明？
但牛顿法也不是万能的。它有几个收敛条件，我总结一下：
- f'(x*) ≠ 0：解处导数不能为零，否则切线水平，没法迭代了。
- 初始点足够接近真解：这是局部收敛性的要求。离远了，可能飞到别处去。
- f(x) 二阶连续可导：这是理论保证，实际中一般都能满足。
4.3 收敛阶：衡量迭代快慢的标尺
收敛阶这个概念，说白了就是衡量迭代一次，误差能缩小多少倍。
定义是这样的：如果存在常数 p ≥ 1 和 C > 0，使得
lim_{k→∞} |e_{k+1}| / |e_k|^p = C那么 p 就是收敛阶，C 是渐近误差常数。
常见的收敛阶有：
| 收敛阶 | 名称 | 典型算法 | 每次迭代误差缩小倍数 |
|---|---|---|---|
| p=1 | 线性收敛 | 不动点迭代（一般情况） | 约 C 倍（C<1） |
| p=2 | 二次收敛 | 牛顿法 | 误差平方级缩小 |
| 1 < p < 2 | 超线性收敛 | 割线法 | 介于两者之间 |
你想想看，二次收敛有多恐怖？如果当前误差是0.1，下一次误差就是0.01，再下一次是0.0001，再下一次是10的负8次方……基本上3到4步就能达到机器精度。
而线性收敛呢？每次误差乘以0.5，从0.1到10的负8次方，需要大约27步。差距一目了然。
4.4 三种迭代方法的对比
为了让大家看得更清楚，我做了一个对比表：
| 方法 | 迭代公式 | 收敛阶 | 每步计算量 | 适用场景 |
|---|---|---|---|---|
| 不动点迭代 | x_{k+1}=g(x_k) | 线性（p=1） | 低（只需算g） | 简单方程，精度要求不高 |
| 牛顿法 | x_{k+1}=x_k - f/f' | 二次（p=2） | 中（需算f和f'） | 光滑函数，高精度需求 |
| 割线法 | x_{k+1}=x_k - f_k*(x_k-x_{k-1})/(f_k-f_{k-1}) | 超线性（p≈1.618） | 低（只需算f） | 导数难求时 |
这里我想多说一句：不要盲目追求高收敛阶。牛顿法虽然二次收敛，但每步都要算导数。如果导数计算很贵（比如来自一个复杂的仿真程序），那割线法可能更划算。我在做电路仿真时，就经常用割线法，因为求导需要额外的仿真，太费时间了。
4.5 知识体系总览
下面这张图，是我自己画的，把这一节的核心逻辑串起来了：
这张图把三个核心概念的关系理清了。不动点迭代是基础，牛顿法是它的加速版，收敛阶则是衡量所有迭代方法的标尺。
4.6 一个简单的代码示例
最后，我给大家看一段代码，对比不动点迭代和牛顿法求解 x^2 - 2 = 0：
import numpy as np
# 不动点迭代：x = (x + 2/x)/2
def fixed_point(x0, tol=1e-10, max_iter=100):
x = x0
for i in range(max_iter):
x_new = (x + 2/x) / 2
if abs(x_new - x) < tol:
print(f"不动点迭代收敛，迭代次数: {i+1}")
return x_new
x = x_new
print("不动点迭代未收敛")
return x
# 牛顿法：x = x - (x^2-2)/(2x)
def newton(x0, tol=1e-10, max_iter=100):
x = x0
for i in range(max_iter):
f = x**2 - 2
fp = 2*x
x_new = x - f / fp
if abs(x_new - x) < tol:
print(f"牛顿法收敛，迭代次数: {i+1}")
return x_new
x = x_new
print("牛顿法未收敛")
return x
# 测试
x0 = 1.5
print(f"真解: {np.sqrt(2)}")
print(f"不动点迭代结果: {fixed_point(x0)}")
print(f"牛顿法结果: {newton(x0)}")运行结果会告诉你，牛顿法只需要3到4步，而不动点迭代需要10步以上。这就是二次收敛和线性收敛的差距。
好了，这一节的内容就到这里。收敛分析是数值计算的基石，搞懂了这些，后面学更高级的算法（比如共轭梯度法、拟牛顿法）就会轻松很多。