跳到主要内容

非线性方程数值解：迭代与收敛

寻找方程 f(x)=0f(x) = 0 的根是数值分析的基本问题。由于解析解往往难以获得，我们通常构造迭代序列 {xk}\{x_k\}，使其收敛于实根 x∗x^*。

1. 二分法 (Bisection Method)​

基于连续函数的介值定理。若 f(a)⋅f(b)<0f(a) \cdot f(b) < 0，则在 (a,b)(a, b) 内至少存在一个根。

  • 算法：每次取中点 c=(a+b)/2c = (a+b)/2，根据 f(c)f(c) 的符号缩小区间。
  • 评价：收敛速度慢（线性收敛），但非常稳健，常用于为更高级的算法提供初始值。
  • 误差估计：第 nn 步后的区间长度为 (b−a)/2n(b-a)/2^n。

2. 不动点迭代 (Fixed-Point Iteration)​

将 f(x)=0f(x) = 0 改写为等价形式 x=ϕ(x)x = \phi(x)。从 x0x_0 出发，令 xk+1=ϕ(xk)x_{k+1} = \phi(x_k)。

2.1 压缩映射原理​

定理：若 ϕ(x)\phi(x) 在 [a,b][a, b] 上满足：

  1. ϕ(x)∈[a,b]\phi(x) \in [a, b] 对于所有 x∈[a,b]x \in [a, b]；
  2. ∣ϕ′(x)∣≤L<1|\phi'(x)| \le L < 1 （压缩常数）； 则迭代格式 xk+1=ϕ(xk)x_{k+1} = \phi(x_k) 对任意初始值 x0∈[a,b]x_0 \in [a, b] 均收敛。

2.2 收敛阶 (Order of Convergence)​

若 ϕ′(x∗)=ϕ′′(x∗)=⋯=ϕ(p−1)(x∗)=0\phi'(x^*) = \phi''(x^*) = \dots = \phi^{(p-1)}(x^*) = 0 且 ϕ(p)(x∗)≠0\phi^{(p)}(x^*) \neq 0，则该迭代法具有 pp 阶收敛。

3. Newton 迭代法 (Newton's Method)​

Newton 法是利用 f(x)f(x) 的一阶泰勒展开构造的迭代格式： xk+1=xk−f(xk)f′(xk)x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)}

3.1 几何意义​

xk+1x_{k+1} 是曲线 y=f(x)y = f(x) 在点 (xk,f(xk))(x_k, f(x_k)) 处切线与 xx 轴交点的横坐标。

3.2 局部平方收敛性​

定理：若 x∗x^* 是 f(x)=0f(x)=0 的单根（即 f′(x∗)≠0f'(x^*) \neq 0），且 f′′(x)f''(x) 连续，则 Newton 法在 x∗x^* 附近是平方收敛的（p=2p=2）。

重根陷阱

若 x∗x^* 是 mm 重根（m>1m > 1），Newton 法将退化为线性收敛。此时可采用改进格式： xk+1=xk−mf(xk)f′(xk)x_{k+1} = x_k - m \frac{f(x_k)}{f'(x_k)} 以恢复平方收敛。

4. 弦截法 (Secant Method)​

Newton 法需要计算导数，这在某些情况下较为困难。弦截法利用前两步的斜率代替导数： xk+1=xk−f(xk)(xk−xk−1)f(xk)−f(xk−1)x_{k+1} = x_k - \frac{f(x_k)(x_k - x_{k-1})}{f(x_k) - f(x_{k-1})} 收敛阶为 1+52≈1.618\frac{1+\sqrt{5}}{2} \approx 1.618（超线性收敛）。

✍️ 典型例题​

例 1：分析迭代格式 xk+1=xk+2x_{k+1} = \sqrt{x_k + 2} 求解 x2−x−2=0x^2 - x - 2 = 0 正根的收敛性。

解析：

  1. 该方程的正根为 x∗=2x^* = 2。
  2. 迭代函数 ϕ(x)=x+2\phi(x) = \sqrt{x+2}。
  3. 计算导数：ϕ′(x)=12x+2\phi'(x) = \frac{1}{2\sqrt{x+2}}。
  4. 在 x∗=2x^* = 2 处，ϕ′(2)=124=1/4\phi'(2) = \frac{1}{2\sqrt{4}} = 1/4。
  5. 因为 ∣ϕ′(2)∣<1|\phi'(2)| < 1，由压缩映射原理知，该迭代格式局部收敛，且为线性收敛。
例 2：利用 Newton 法求 C\sqrt{C} 的迭代格式。

设 f(x)=x2−C=0f(x) = x^2 - C = 0。 f′(x)=2xf'(x) = 2x。 代入 Newton 公式： xk+1=xk−xk2−C2xk=12(xk+Cxk)x_{k+1} = x_k - \frac{x_k^2 - C}{2x_k} = \frac{1}{2} \left( x_k + \frac{C}{x_k} \right) 这就是著名的巴比伦算法，具有平方收敛特性。

🚀 专项训练​

前往 数值分析专题练习库 挑战 Aitken 加速法与重根判别题目。