数值分析学习笔记--非线性方程求解

不动点迭代

如有疏漏，敬请指正。

对于非线性方程，我们往往可以通过迭代法计算其近似数值解。由于非线性方程的根一般不止一个。因此在求解非线性方程时，要给定初始值或求解范围。

二分迭代

二分迭代是一个很简单直观的非线性方程求解算法，其理论基础是介值定理，即设函数$f(x)$在$[a,b]$上连续，且$f(a)f(b)<0$，则$f(x)$在$[a,b]$上至少有一个零点。在计算中，可以通过对分区间，缩小区间范围来搜索零点。

在实务中，常用$sgn(f(a)) \cdot sgn(f(x))>0$替代$f(a) \cdot f(x)>0$，以避免数值溢出。

对分法算法较为简单，但是需要注意的是，即使$f(x)$在$[a,b]$上有零点，也未必有$f(a)f(b)<0$，这限制了对分法的使用范围。

对于给定的方程$f(x)=0$，可以将其转化为等价形式$x=\varphi (x)$。给定初值$x_0$，由此构造迭代序列$x_{k+1}=\varphi(x_k),k=1,2, \cdots$，若$\varphi(x)$连续且迭代收敛，即

$\lim_{k \to \infty} x_{k+1}=\lim_{k \to \infty} \varphi(x_k)=\alpha$

则有$\alpha = \varphi (\alpha)$，而$\alpha$就是方程$f(x)=0$的根。

若$\varphi$定义在$[a,b]$上，如果$\varphi$满足

当$x \in [a,b]$时有$a \leq \varphi(x) \leq b$
$\varphi (x)$在$[a,b]$上可导，且存在正数$L<1$，使得对任意的$x \in [a,b]$，有$| \varphi’(x) | \leq L$

则在$[a,b]$上有唯一的点$x^{\ast}$满足$x^*=\varphi(x^{\ast})$，称$x^{\ast}$为$\varphi(x)$的不动点。迭代格式$x_{k+1}=\varphi(x_k)$对任意初值$x_0 \in [a,b]$均收敛于$x^{\ast}$，误差估计式为

$| x^{\ast}-x_k | \leq \frac{L^k}{1-L} |x_1-x_0|$

构造收敛迭代格式，有两个要素：

牛顿迭代是一种常用的不动点迭代方式。

首先，对$f(x)$在$x_0$进行泰勒展开，有

$f(x)=f(x_0)+f'(x_0)(x-x_0)+\frac{f''(x_0)}{2!} (x-x_0)^2 + \cdots$

取上式线性部分作为$f(x) \approx 0$的近似值，有

$x_1=x_0-\frac{f(x_0)}{f'(x_0)}$

其中我们设$f’(x_0) \neq 0$。

一直迭代下去，可得

$x_{k+1}=x_k-\frac{f(x_k)}{f'(x_k)}$

对应于$f(x)=0$的Newton迭代方程是$\varphi (x)=x-\frac{f(x)}{f’(x)}$

$\varphi '(x)=\frac{f(x)f''(x)}{(f'(x))^2}$

若$\alpha$是$f(x)$的单根，有$| \varphi ‘(\alpha) |=0$，且只要初值$x_0$充分接近$\alpha$，就有$| \varphi ‘(x_0) |<1$，牛顿迭代收敛。

如果存在$M>0$，使得

$\lim_{k \to \infty} \frac{|e_{k+1}|}{|e_k|^n}=\lim_{k \to \infty} \frac{|x_{k+1}- \alpha|}{|x_k - \alpha|^n}=M$

那么记迭代收敛的阶为n。

分析可知，牛顿迭代是二阶迭代方法。

若$\alpha$是$f(x)$的p重根，以下迭代格式是二阶方法

$x_{k+1}=x_k-p\frac{f(x_k)}{f'(x_k)},k=1,2, \cdots$

牛顿迭代格式的收敛与否和初始值密切相关，当初始值在某根附近时迭代才能收敛到这个根。

如果方程没有实数根，那么迭代也不收敛。

在牛顿迭代格式中，用差商替代导数，并且给定两个初始值$x_0$和$x_1$，得到弦截法的迭代格式：

$x_{k+1}=x_k-\frac{f(x_k)(x_k-x_{k-1})}{f(x_k)-f(x_{k-1})},k=1,2, \cdots$

使用这个方法迭代求根，每次只需计算一次函数值，但这个方法的迭代速度慢于牛顿迭代法。

弦截法为1.618阶迭代方法。