数值分析：非线性方程组迭代法

二分法

缺点

不动点迭代

构造思路

迭代法构造思路：将Ax=bAx=b等价改写为x=Mx+gx=Mx+g

仿照迭代法思路，将f(x)=0f(x)=0等价变换为x=φ(x)x=φ(x)。

xk+1=φ(xk),   k=0,1,2,⋯x_{k+1} = φ(x_k), \,\,\,k=0,1,2,\cdots

收敛条件

  1. ∀x∈[a,b]∀x∈[a,b]，有φ(x)∈[a,b]φ(x)∈[a,b]
  2. ∃L∈[0,1]∃L∈[0,1]，∀x,y∈[a,b]∀x,y∈[a,b]，有∣φ(x)−φ(y)∣≤L∣x−y∣|φ(x)-φ(y)|≤L|x-y|
    • LL称为利普希茨（Lipschitz）常数
  3. ∃L∈[0,1]∃L∈[0,1]， ∀x∈[a,b]∀x∈[a,b],有∣φ′(x)∣≤L<1|φ'(x)|≤L<1

满足以上任意一条（2、3本质是一条），则可得到。

∀x0∈[a,b]∀x_0∈[a,b]，由xk+1=φ(xk)x_{k+1}=φ(x_k)得到的序列收敛于φ(x)φ(x)在[a,b][a,b]上的唯一不动点。

误差估计式

简单迭代法的收敛性不但取决于迭代函数φ(x)\varphi(x)，还取决于x0x_0。

事后估计

∣x∗−xk∣≤11−L∣xk−xk−1∣|x^* - x_k| ≤ \dfrac{1}{1-L}|x_k - x_{k-1}|

先验估计

∣x∗−xk∣≤Lk1−L∣x1−x0∣|x^* - x_k| ≤ \dfrac{L^k}{1-L}|x_1 - x_0|

局部收敛性

设x∗x^*为方程x=φ(x)x=φ(x)的根，φ′(x)φ'(x)在x∗x^*的领域连续，且∣φ′(x∗)∣<1|\varphi'(x^*)|<1，则迭代过程xk+1=φ(xk)x_{k+1}=φ(x_k)在根x∗x^*领域具有局部收敛性。

收敛阶

设x∗x^*是φ(x)φ(x)的不动点，对于整数p>1p>1，迭代函数φ(x)φ(x)及其pp阶导数在x∗x^*的领域上连续，且满足：

φ′(x∗)=φ′′(x∗)=⋯=φ(p−1)(x∗)=0,   φ(p)(x∗)≠0φ'(x^*) = φ''(x^*) = \cdots = φ^{(p-1)}(x^*) = 0, \,\,\, φ^{(p)}(x^*)≠0

则迭代过程xk+1=φ(xk)x_{k+1} = φ(x_k)在x∗x^*的领域是 pp阶收敛的，且有

lim⁡k→∞ek+1(ek)p=φ(p)(x∗)p!=C\lim\limits_{k→∞} \dfrac{e_{k+1}}{(e_k)^p} = \dfrac{φ^{(p)}(x^*)}{p!} = C

也就是迭代过程的收敛速度依赖于迭代函数φ(x)\varphi(x)的选取。

例

xk+1=xk+c(xk2−5)x_{k+1} = x_k + c(x_k^2 - 5)，收敛到5\sqrt{5}（x∗=5x^*=\sqrt{5}）

  1. cc的取值时，收敛（局部收敛性）
  2. cc取何值时，满足平方收敛
  3. cc取何值时，收敛最快

解
φ(x)=x+c(x2−5)\varphi(x) = x + c(x^2 - 5)
φ′(x)=1+2cx\varphi'(x) = 1 + 2cx
φ′′(x)=2c\varphi''(x) = 2c

(1)

(2)

(3)

迭代加速

艾特金（Aitken）

x^k+1=xk−(xk+1−xk)2xk+2−2xk+1+xk   k=0,1,2,⋯\hat{x}_{k+1} = x_k - \dfrac{(x_{k+1}-x_k)^2}{x_{k+2}-2x_{k+1}+x_k} { \ \ \ } k=0,1,2,\cdots

该方法可以将一个线性收敛的序列{xk}\{x_k\}转化为平方收敛的序列{x^k}\{\hat{x}_k\}。

斯蒂芬森（Steffensen）

把Aitken加速法的加速技巧与原迭代xk+1=φ(xk)x_{k+1} = φ(x_k)相结合

{yk=φ(xk)zk=φ(yk)xk+1=xk−(yk−xk)2zk−2yk+xkk=0,1,2,⋯\begin{cases} y_k = φ(x_k) \\ z_k = φ(y_k) \\ x_{k+1} = x_k - \dfrac{(y_k - x_k)^2}{z_k - 2y_k + x_k} & k=0,1,2,\cdots \end{cases}

亦可记作

xk+1=ψ(x)   k=0,1,2,⋯x_{k+1} = \psi(x) { \ \ \ } k=0,1,2,\cdots

说明

牛顿迭代

构造思路

泰勒公式：f(x)=f(x0)0!+f′(x0)1!(x−x0)+f′′(x0)2!(x−x0)2+⋯+f(n)(x0)n!(x−x0)n+Rn(x)f(x) = \dfrac{f(x_0)}{0!} + \dfrac{f'(x_0)}{1!}(x-x_0) + \dfrac{f''(x_0)}{2!}(x-x_0)^2 + \cdots + \dfrac{f^{(n)}(x_0)}{n!}(x-x_0)^n + R_n(x)

取x0x_0作为初始近似值，将f(x)f(x)在x0x_0做一阶Taylor展开：

f(x)=f(x0)+f′(x0)(x−x0)+f′′(ξ)2!(x−x0)2f(x) = f(x_0) + f'(x_0)(x-x_0) + \dfrac{f''(ξ)}{2!}(x-x_0)^2

其中f′′(ξ)2!(x−x0)2\dfrac{f''(ξ)}{2!}(x-x_0)^2是高阶小量，故只取前两项线性部分，利用线性方程来近似替代非线性方程。

0=f(x∗)≈f(x0)+f′(x0)(x∗−x0)0 = f(x^*) ≈ f(x_0) + f'(x_0)(x^*-x_0)

牛顿迭代公式

xk+1=xk−f(xk)f′(xk),   k=0,1,⋯x_{k+1} = x_k - \dfrac{f(x_k)}{f'(x_k)}, \,\,\, k=0,1,\cdots

几何意义

切线渐进

收敛性

牛顿下山法

如果x0x_0距离x∗x^*比较远的话，可能导致牛顿是迭代法是发散的，为使得x0x_0影响降到最低，使用牛顿下山法。

定义

满足∣f(xk+1)∣<∣f(xk)∣|f(x_{k+1})|<|f(x_{k})|即具有单调性的牛顿迭代法，称为牛顿下山法。

构造思路

若由xkx_k得到的xk+1x_{k+1}不能使∣f∣|f|减小，则再xkx_k和xk+1x_{k+1}之间找一个更好的点xk+1‾\overline{x_{k+1}}，使得∣f(xk+1‾)∣<∣f(xk)∣|f(\overline{x_{k+1}})|<|f(x_k)|。

xk+1‾=λ[xk−f(xk)f′(xk)]+(1−λ)xk=xk−λf(xk)f′(xk)\overline{x_{k+1}} = λ\left[{ x_k - \dfrac{f(x_k)}{f'(x_k)} }\right] + (1-λ)x_k = x_k - λ\dfrac{f(x_k)}{f'(x_k)}

当λ=1λ=1（此时就是牛顿迭代法）代入效果不好时，将λλ减半计算。

简化法

xk+1=xk−f(x)M   k=0,1,2,⋯x_{k+1} = x_k - \dfrac{f(x)}{M} \,\,\, k=0,1,2,\cdots

其中MM为常数。该方法只具有线性收敛。

割线法

xk+1=xk−f(xk)f(xk)−f(xk−1)(xk−xk−1),   k=1,2,3,⋯x_{k+1} = x_k - \dfrac{f(x_k)}{f(x_k) - f(x_{k-1})}(x_k - x_{k-1}), \,\,\, k=1,2,3,\cdots

割线法收敛阶为p=1+52≈1.618p=\dfrac{1+\sqrt{5}}{2} ≈ 1.618。

重根法

xk+1=xk−f(xk)f′(xk)f′(xk)2−f(xk)f′′(xk),   k=0,1,2,⋯x_{k+1} = x_k - \dfrac{f(x_k)f'(x_k)}{f'(x_k)^2 - f(x_k)f''(x_k)} , \,\,\, k=0,1,2,\cdots

上式用于求方程f(x)=0f(x)=0重根的具有平方收敛的迭代法，且不需要知道根的重数。