二分法、不动点迭代法、切线法

《应用数值分析》
《应用数值分析》

目录

6. 非线性方程组的数值解法

6.1 一元非线性方程求根

对 f 不是 x 的线性函数的方程，统称为非线性方程或一次方程。

方程的解 x∗ 满足 f(x∗)≡0，也称为方程的根、函数的零点、不动点。

若 f 在 x∗ 的邻域上可表示为

f(x)=(x−x∗)mg(x),g(x∗)≠0

其中，m 为正整数，则称 x∗ 是方程的 m 重根或函数 f 的 m 重零点。m=1 时，称为单重根或单重零点。

若 x∗ 是 f(x)=0 的 m 重根，且 g(x) 充分光滑，则可表示为：

{f(x∗)=0,f′(x∗)=0,⋯,f(m−1)(x∗)=0f(m)(x∗)≠0

若上式成立，则 f(x) 在点 x∗ 处的 Taylor 展开式为：

f(x)=f(m)(ξ)m!(x−x∗)m,ξ 在 x 与 x∗ 之间

求根思想：把有根区间或隔离区间逐步缩小

6.2 二分法

如果方程 f(x)=0 中，f∈C[a,b]，且 f(a)⋅f(b)<0，则由二分法产生的序列 {xn} 收敛于方程的根 x∗，且有误差估计：

|x∗−xn|⩽b−a2n

6.3 不动点迭代法及其收敛性理论

6.3.1 不动点迭代法

将方程改写为等价方程 x=φ(x)，从某个取定的初值 x0 开始，对应上式构建迭代公式：

xk+1=φ(xk)(k=0,1,⋯)

这种求根的方法就称为迭代法或函数迭代法，式中的 φ(x) 称为迭代函数。如果 x∗ 对函数 φ(x) 满足 x∗=φ(x∗)，则称 x∗ 为 φ(x) 的不动点，因此函数迭代法也称为不动点迭代法。

6.3.2 收敛性基本定理

设迭代公式中的迭代函数 φ∈C[a,b] 满足条件：

  1. 映内性：当 a⩽x⩽b 时，有 a⩽φ(x)⩽b
  2. 压缩性：存在常数 0<L<1，L 称为压缩系数，使得：
|φ(x)−φ(˜x)|⩽L|x−˜x|,∀x,˜x∈[a,b]

则可得：

  1. 函数 φ 在 [a,b] 上存在唯一的不动点 x∗；
  2. 对任意初值 x0∈[a,b]，迭代公式收敛于 x∗，即 limk→∞xk=x∗；
  3. 迭代值有误差估计式：
|x∗−xk|⩽L1−L|xk−xk−1|,|x∗−xk|⩽Lk1−L|x1−x0|.

6.3.3 局部收敛定理

设 x∗ 为 φ 的不动点，φ′(x) 在 x∗ 的某个邻域 Δ 上存在、连续且 |φ′(x∗)|<1，则迭代公式 xk+1=φ(xk) 局部收敛

6.4 Newton 迭代法

6.4.1 Newton 迭代公式

解一元非线性方程 f(x)=0

  • Newton 迭代公式：
xk+1=xk−f(xk)f′(xk)(k=0,1,⋯)
  • Newton 法也称为切线法，斜率为 f′(xk)=f(xk)xk−xk+1

6.4.2 Newton 迭代法的收敛性

Newton 迭代公式在单根附近至少是 2 阶局部收敛的。

设 f(x∗)=0，f′(x∗)≠0，且在 x∗ 的邻域上 f″ 存在、连续，则：

  1. Newton 迭代公式（用于求方程单根）至少 2 阶局部收敛
limk→∞xk+1−x∗(xk−x∗)2=f″(x∗)2f′(x∗)

6.4.3 重根的迭代改善

方法 1

如果已知重根的重数 m(m>1)，则利用 m 构造新迭代公式：

xk+1=xk−mf(xk)f′(xk)(k=0,1,⋯)

此时迭代函数为 φ(x)=x−mf(x)f′(x)

这种方法的缺点是要事先知道重根的重数，但实际应用中往往并不知道。

方法 2

作 F(x)=f(x)f′(x)，如果 x∗ 是 f(x)=0 的 m 重根（m>1），则 x∗ 是 f′(x)=0 的 m−1 重根，从而 x∗ 是 F(x)=0 的单根。新迭代公式：

xk+1=xk−f(xk)f′(xk)[f′(xk)]2−f(xk)f″(xk)(k=0,1,⋯)

这种方法的缺点是需要 f 的 2 阶导数

6.4.4 Newton 迭代法用于求方根

Newton 迭代法常用于求方根。如求平方根 √c(c>0)，令 x=√c，有 x2=c，可得方程

f(x)=x2−c=0

则其正根 x∗>0，即为 √c。现用 Newton 法可得相应的迭代公式：

xk+1=xk−x2−c2xk(k=0,1,⋯)

整理成通用公式：

xk+1=12(xk+cxk)(k=0,1,⋯)

其意义就是把开方运算通过加法和除法来实现，这也是计算机系统（内部）做开方运算的实际做法。

6.4.5 离散 Newton 迭代法：割线法

Newton 迭代的每一步都要计算导数值 f′(xk)，当 f(x) 的导数不存在时迭代公式还不能用。为此，考虑用函数 f(x) 的差商代替求导：

f′(xk)≈f(xk)−f(xk−1)xk−xk−1

于是代入 Newton 迭代公式，可得：

xk+1=xk−f(xk)f(xk)−f(xk−1)(xk−xk−1)(k=1,2,⋯)

6.5 非线性方程组的 Newton 迭代法与拟 Newton 迭代法

6.5.1 Aitken 加速方案

对某种迭代过程 xk+1=φ(xk) 的 Aitken（埃特金）加速方案：

{迭代：xk+1=φ(xk)再迭代：xk+2=φ(xk+1)加速：ˉxk=xk−(xk+1−xk)2xk+2−2xk+1+xk

令 Δxk=xk+1−xk，Δ2xk=Δ(Δxk)=xk+2−2xk+1+xk，则有：

ˉxk=xk−(Δxk)2Δ2xk

称为 AitkenΔ2 加速方案。

6.5.2 拟 Newton 迭代法

考虑非线性方程组 FF(x)=0，其中：

FF(x)=[f1(x1,x2,⋯,xn)f2(x1,x2,⋯,xn)⋮fn(x1,x2,⋯,xn)]=[f1(xx)f2(xx)⋮fn(xx)]

当 n=1 时，FF(xx)=f(x)，是微分学中的一元函数，类似于一维情况下的不动点迭代方法。一元方程的 Newton 迭代公式为：

xk+1=xk−f(xk)f′(xk), 其中f′(xk)≠0

将此迭代公式推广到方程组的情形，可得 FF(xx)=0 的 Newton 迭代公式为：

xx(k+1)=xx(k)−(FF′(xx(k)))−1FF(xx(k))

其中，导数矩阵

FF′(xx)=[∂f1(xx)∂x1∂f1(xx)∂x2⋯∂f1(xx)∂xn∂f2(xx)∂x1∂f2(xx)∂x2⋯∂f2(xx)∂xn⋮⋮⋮∂fn(xx)∂x1∂fn(xx)∂x2⋯∂fn(xx)∂xn]

为 FF(xx) 的 Jacobi 矩阵，(FF′(xx))−1 为 FF(xx) 的导数矩阵的逆矩阵。

上面的 Newton 迭代公式只是一种形式记号，实际计算可采用下列形式：

{FF′(x(k))Δxx(k)=−FF(xx(k))xx(k+1)=xx(k)+Δxx(k)(k=0,1,2,⋯)

最后，Newton 法由 xx(k) 计算 xx(k+1) 的步骤是：

  1. 计算 FF(x(k)) 和 FF′(x(k))；
  2. 解线性方程组 FF′(x(k))Δxx(k)=−FF(xx(k))，求得 Δxx(k)；
  3. 令 xx(k+1)=xx(k)+Δxx(k).