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

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

目录

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

6.1 一元非线性方程求根

$f$ 不是 $x$ 的线性函数的方程,统称为非线性方程一次方程

方程的解 满足 ,也称为方程的根、函数的零点、不动点

若 $f$ 在 $x^*$ 的邻域上可表示为

其中,$m$ 为正整数,则称 方程的 $m$ 重根函数 $f$ 的 $m$ 重零点。$m=1$ 时,称为单重根单重零点

若 $x^*$ 是 $f(x)=0$ 的 $m$ 重根,且 $g(x)$ 充分光滑,则可表示为:

若上式成立,则 $f(x)$ 在点 $x^*$ 处的 $Taylor$ 展开式为:

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

6.2 二分法

如果方程 $f(x)=0$ 中,$f \in C[a,b]$,且 $f(a) \cdot f(b) < 0$,则由二分法产生的序列 $\{x_n\}$ 收敛于方程的根 $x^*$,且有误差估计:

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

6.3.1 不动点迭代法

将方程改写为等价方程 $x=\varphi(x)$,从某个取定的初值 $x_0$ 开始,对应上式构建迭代公式:

这种求根的方法就称为迭代法函数迭代法,式中的 $\varphi(x)$ 称为迭代函数。如果 对函数 $\varphi(x)$ 满足 ,则称 为 $\varphi(x)$ 的不动点,因此函数迭代法也称为不动点迭代法

6.3.2 收敛性基本定理

设迭代公式中的迭代函数 $\varphi \in C[a,b]$ 满足条件:

  1. 映内性:当 $a \leqslant x \leqslant b$ 时,有 $a \leqslant \varphi(x) \leqslant b$
  2. 压缩性:存在常数 $0<L<1$,$L$ 称为压缩系数,使得:

则可得:

  1. 函数 $\varphi$ 在 $[a,b]$ 上存在唯一的不动点 $x^*$
  2. 对任意初值 $x_0 \in [a,b]$,迭代公式收敛于 ,即
  3. 迭代值有误差估计式

6.3.3 局部收敛定理

为 $\varphi$ 的不动点,$\varphi{}’(x)$ 在 的某个邻域 $\Delta$ 上存在、连续且 ,则迭代公式 $x_{k+1}=\varphi(x_k)$ 局部收敛

6.4 $Newton$ 迭代法

6.4.1 $Newton$ 迭代公式

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

  • $Newton$ 迭代公式:
  • $Newton$ 法也称为切线法,斜率为 $f{}’(x_k) = \displaystyle{\frac{f(x_k)}{x_k - x_{k+1}}}$

6.4.2 $Newton$ 迭代法的收敛性

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

,且在 $x^*$ 的邻域上 $f{}’’$ 存在、连续,则:

  1. $Newton$ 迭代公式(用于求方程单根)至少 2 阶局部收敛

6.4.3 重根的迭代改善

方法 1

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

此时迭代函数为 $\varphi(x) = x - m \displaystyle{\frac{f(x)}{f{}’(x)}}$

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

方法 2

作 $F(x) = \displaystyle{\frac{f(x)}{f{}’(x)}}$,如果 是 $f(x)=0$ 的 $m$ 重根($m>1$),则 是 $f{}’(x)=0$ 的 $m-1$ 重根,从而 $x^*$ 是 $F(x)=0$ 的单根。新迭代公式:

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

6.4.4 $Newton$ 迭代法用于求方根

$Newton$ 迭代法常用于求方根。如求平方根 $\sqrt{c}(c>0)$,令 $x=\sqrt{c}$,有 $x^2=c$,可得方程

则其正根 $x^*>0$,即为 $\sqrt{c}$。现用 $Newton$ 法可得相应的迭代公式:

整理成通用公式:

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

6.4.5 离散 $Newton$ 迭代法:割线法

$Newton$ 迭代的每一步都要计算导数值 $f{}’(x_k)$,当 $f(x)$ 的导数不存在时迭代公式还不能用。为此,考虑用函数 $f(x)$ 的差商代替求导

于是代入 $Newton$ 迭代公式,可得:

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

6.5.1 $Aitken$ 加速方案

对某种迭代过程 $x_{k+1} = \varphi(x_k)$ 的 $Aitken$(埃特金)加速方案:

令 $\Delta x_k = x_{k+1} - x_k$,$\Delta^2x_k = \Delta(\Delta x_k) = x_{k+2} - 2x_{k+1} + x_k$,则有:

称为 $Aitken\Delta^2$ 加速方案

6.5.2 拟 $Newton$ 迭代法

考虑非线性方程组 $\pmb{F}(x)=0$,其中:

当 $n=1$ 时,$\pmb{F}(\pmb{x})=f(x)$,是微分学中的一元函数,类似于一维情况下的不动点迭代方法。一元方程的 $Newton$ 迭代公式为:

将此迭代公式推广到方程组的情形,可得 $\pmb{F}(\pmb{x})=0$ 的 $Newton$ 迭代公式为:

其中,导数矩阵

为 $\pmb{F}(\pmb{x})$ 的 $Jacobi$ 矩阵,$\left(\pmb{F}{}’(\pmb{x})\right)^{-1}$ 为 $\pmb{F}\left(\pmb{x}\right)$ 的导数矩阵的逆矩阵。

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

最后,$Newton$ 法由 $\pmb{x}^{(k)}$ 计算 $\pmb{x}^{(k+1)}$ 的步骤是:

  1. 计算 $\pmb{F}(x^{(k)})$ 和 $\pmb{F}{}’(x^{(k)})$;
  2. 解线性方程组 $\pmb{F}{}’(x^{(k)})\Delta \pmb{x}^{(k)} = - \pmb{F}(\pmb{x}^{(k)})$,求得 $\Delta \pmb{x}^{(k)}$;
  3. 令 $\pmb{x}^{(k+1)} = \pmb{x}^{(k)} + \Delta \pmb{x}^{(k)}$.