二分法、不动点迭代法、切线法
目录
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]$ 满足条件：
- 映内性：当 $a \leqslant x \leqslant b$ 时，有 $a \leqslant \varphi(x) \leqslant b$
- 压缩性：存在常数 $0<L<1$，$L$ 称为压缩系数，使得：
则可得：
- 函数 $\varphi$ 在 $[a,b]$ 上存在唯一的不动点 $x^*$；
- 对任意初值 $x_0 \in [a,b]$，迭代公式收敛于 ，即 ；
- 迭代值有误差估计式：
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{}’’$ 存在、连续，则：
- $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)}$ 的步骤是：
- 计算 $\pmb{F}(x^{(k)})$ 和 $\pmb{F}{}’(x^{(k)})$；
- 解线性方程组 $\pmb{F}{}’(x^{(k)})\Delta \pmb{x}^{(k)} = - \pmb{F}(\pmb{x}^{(k)})$，求得 $\Delta \pmb{x}^{(k)}$；
- 令 $\pmb{x}^{(k+1)} = \pmb{x}^{(k)} + \Delta \pmb{x}^{(k)}$.
