数值分析：非线性方程的求解

2019-04-01 本文已影响0人 Bocchi

1 逐步搜索法

连续函数的零点定理：设 $f(x)$ 在区间 $[a,b]$ 上连续，且有 $f(a)f(b)<0$ ，说明方程 $f(x)=0$ ，在区间 $[a,b]$ 上至少有一个实数根 $x^*$ 。

依据上面的定理，我们可以设计以下算法：
我们从左端点 $x_0=a$ 出发，按某一个预定的步长 $h$ ，如取 $h=(b-a)/n$ （n 为正整数），向右迈进。考虑节点 $x_1=x_0+h$ 处的函数值，有3种可能：

节点 $x_1$ 的函数值与左端点 $a$ 的函数值同号，即 $f(x_1)f(a)>0$ ；
这时，我们无法判断 $a$ 与 $x_1$ 之间是否有方程的实根，因此我们继续向右迈步，每跨一步进行一次根的搜索。
$f(x_1)=0$
这时， $x_1$ 便是方程的一个实根
节点 $x_1$ 的函数值与左端点 $a$ 的函数值异号，即 $f(x_1)f(a)<0$ ；
这时，节点 $x_1$ 与 $a$ 之间必有方程的一个实根。

我们可以证明，必存在某节点 $x_k$ 处的函数值异号，则在 $x_{k-1}$ 与 $x_k$ 必存在一个实根。此时可取 $\frac{x_{k-1}+x_{k}}{2}$ 作为初始近似值。根的搜索到此结束。这种根的搜索方法称为逐步搜索法

2 二分法

优点：条件简单
缺点：收敛速度慢、不易求偶数重根

2.1 基本思路

考察有根区间 $[a,b]$ ，取中点 $x_0=\frac{a+b}2$ 将它分成两半，假设中点 $x_0$ 不是 $f(x)$ 的零点，然后检查 $f(x_0)$ 与 $f(a)$ 是否同号。
如果确定是同号，说明所求的根 $x^*$ 在 $x_0$ 的右侧，这时令 $a_1=x_0,b_1=b$ ；否则 $x^*$ 必在 $x_0$ 的左侧。
这时令 $a_1=a,b_1=x_0$ 。不管出现哪种情况 $[a_1,b_1]$ 的长度均为 $[a,b]$ 长度的一半。

对于压缩了的有根区间 $[a_1,b_1]$ 又可施行同样的手段，如此反复二分下去，即可得出一系列有根区间
$[a,b]\supset[a_1,b_1]\supset[a_2,b_2]\supset...\supset[a_k,b_k]\supset...$ 其中每个区间都是前一个的一半，因此 $k\to\infty$ 时 $[a_k,b_k]$ 的长度
$\lim\limits_{k\to\infty}b_k-a_k=\lim\limits_{k\to\infty}\frac{b-a}{2^k}=0$ 因此这些区间必定最终收敛于 $x^*$ ，由于我们不能也不必无限做下去，因此，我们选取第 $k$ 次二分后的中点 $x_k=\frac{a_k+b_k}{2}$ 作为根的近似值。误差为： $|x^*-x_k| \le \frac{b_k-a_k}{2}=\frac{b-a}{2^{k+1}}$

给定精确度求解二分次数时，利用公式求解即可！！

2.2 计算步骤

（1）输入有根区间端点 $a,b$ 及预先给定的精度 $\varepsilon$
（2）计算 $x=\frac{a+b}2$
（3）若 $f(a)f(x)$ 同号，则令 $a=x$ ，转向下一步；否则令 $b=x$ ，转向下一步。
（4）若 $b-a<\varepsilon$ ，则输出方程满足精度要求的根 $x$ ，否则转向步骤 (2)

3 不动点迭代法

优点：算法简单，对任意初值都能得到同样的结果
缺点：迭代格式选取需要考虑收敛性

3.1 基本思路

已知方程 $f(x)=0$ 在区间 $[a,b]$ 内有唯一的根 $x^*$ ，将上式改写成等价的形式 $x=\varphi(x)$ ，取 $x_0 \in [a,b]$ ，用递推公式 $x_{k+1}=\varphi(x_k),(k=0,1,...)$ ，可以得到序列 $x_0,x_1,...$ 。
如果当 $k\to\infty$ 时，序列 $\{x_k\}$ 有极限 $\lim\limits_{k\to\infty}x_k=x^*$ ，则称迭代法 收敛于 $x^*$ ，且 $x^*=\varphi(x^*)$ 。否则称迭代法发散。
若迭代法收敛，称 $\varphi(x)$ 为 迭代函数， $x_{k+1}=\varphi(x_k)$ 为 迭代格式， $\{x_k\}$ 为 迭代序列。

3.2 收敛定理

定理 1（全局收敛定理） 设迭代函数 $\varphi(x)$ 在 $[a,b]$ 上有连续一阶导数，且
（1）当 $x\in[a,b]$ 时， $a\le\varphi(x)\le b$ ；
（2）存在正数 $q<1$ （ $q$ 为利普希茨常数）,使对任意 $x\in[a,b]$ ，有 $|\varphi{'}(x)|\le q<1$ ;
则方程 $x=\varphi(x)$ 在区间上存在唯一的根 $x^*$ ，且对任意初值 $x_0\in[a,b]$ ，由迭代格式 $x_{k+1}=\varphi(x_k)$ 在区间上存在唯一的根 $x^*$ ，且对任意初值 $x_0\in[a,b]$ ，有迭代格式所确定的序列 $\{x_k\}$ 收敛于 $x^*$

推论如果 $|\varphi'(x)>1|$ ，则迭代格式 $x_{k+1}=\varphi(x_k)$ 所确定的序列 $\{x_k\}$ ，对任意初值 $x_0\in[a,b]$ 发散

定理 2 设 $\varphi(x) \in C[a,b]$ 满足定理1中的两个条件1，则对任意 $x_0\in [a,b]$ 由迭代式 $x_{k+1}=\varphi(x_k)$ 得到的迭代序列 $\{x_k\}$ 收敛到 $\varphi(x)$ 的不动点 $x^*$ ，并有误差估计 $|x_k-x^*| \leq \frac{L^k}{1-L} |x_1-x_0|$ 不难推导出（后验误差估计法） $|x^*-x_k|\leq\frac{1}{1-L}|x_{k+1}-x_k|$

注：先验误差估计不用计算 $x_k$ 的值，如误差定理推导迭代次数。而后验误差估计需要计算相关的近似值

3.3 计算步骤

（对于迭代过程 $x_{k+1}=\varphi(x_k)$ ）
（1）选取初始近似值 $x_0$ ，精确度 $\varepsilon$ ；
（2）由方程 $f(x)=0$ 确定迭代函数 $\varphi(x)$
（3）按照迭代格式 $x_{k+1}=\varphi(x_k)$ 计算 $x_1=\varphi(x_0)$
（4）如果 $|x_1-x_0| \le \varepsilon$ ，则停止计算否则用 $x_1$ 代替 $x_0$ 重复（3）和（4）

3.4 局部收敛性与收敛阶

定义 1 设 $\varphi(x)$ 有不动点 $x^*$ ，如果存在 $x^*$ 的某个邻域 $R:|x-x^*|\le \delta$ ，对任意 $x_0 \in R$ ，迭代法 $x_{k+1}=\varphi(x)$ 产生的序列 $\{x_k\} \subset R$ ，且收敛到 $x^*$ ，则称迭代法 $x_{k+1}=\varphi(x)$ 局部收敛

定理 3（局部收敛定理） 设迭代函数 $\varphi(x)$ 在 $x^*$ 的邻域上有连续一阶导数，且有 $|\varphi{'}(x)|<1$ ;则称迭代格式 $x_{k+1}=\varphi(x_k)$ 在根 $x^*$ 的邻域上具有 局部收敛性。

定义 2 设迭代过程 $x_{k+1}=\varphi(x_k)$ 收敛于方程 $x=\varphi(x)$ 的根 $x^*$ ，如果当 $k \to \infty$ 时迭代误差 $e^k=x_k-x^*$ 满足渐进关系式
$\frac{e_{k+1}}{e_k^p} \to C\mbox{，常数}C \neq 0$ 则称该迭代过程是 $p$ 阶收敛 的。特别的， $p=1(|C|<1)$ 时称为 线性收敛 ， $p>1$ 时称为 超线性收敛， $p=2$ 时称为 平方收敛

定理 4 对于迭代过程 $x_{k+1}=\varphi(x_k)$ 及正整数 $p$ ，如果 $\varphi^{(p)}(x)$ 在所求根 $x^*$ 的邻域连续，且
$\varphi'(x^*)=\varphi''(x^*)=...=\varphi^{p-1}(x^*)\mbox{，}\varphi^{p}(x^*) \neq 0$ 则该迭代过程在点 $x^*$ 的邻域内时 $p$ 阶收敛的

3.5 Aitken加速方法

$x'_{k+1}=x_k-\frac{(x_{k+1}-x_k)^2}{x_k-2x_{k+1}+x_{k+2}}$

4 牛顿法

优点：收敛速度快
缺点：对初值的选取要求较高

4.1 基本思路

对于非线性方程 $f(x)=0$ ，设 $x_0$ 是一个初始近似根（可由逐步搜索法确定）
，函数 $f(x)$ 在 $x_0$ 处的泰勒展开为
$f(x)=f(x_0)+f'(x_0)(x-x_0)+...+\frac{f^{(n)}(x_0)}{n!}(x-x_0)^n$
用一阶泰勒展开近似 $f(x)$ ，即有
$f(x) \approx f(x_0)+f'(x_0)(x-x_0)$
于是，方程 $f(x)$ 在点 $x_0$ 附近可近似表示为 $f(x_0)+f'(x_0)(x-x_0)=0$ ，将它的根 $x_1=x_0-\frac{f(x_0)}{f'(x_0)}$ 作为原方程 $f(x)$ 的一个近似新根。重复上述过程得迭代格式 $x_{k+1}=x_k-\frac{f(x_k)}{f'(x_k)}$ 这个方法叫做 牛顿迭代法，简称 牛顿法。

4.2 计算步骤

（1）选取初始近似值 $x_0$ ，允许误差 $\varepsilon_1,\varepsilon_2$ ，计算 $f_0=f(x_0),f_0'=f'(x_0)$ ；
（2）按公式 $x_1=x_0-\frac{f_0}{f'_0}$ 迭代一次，得到新的近似值 $x_1$ ，计算 $f_1=f(x_1),f'_1=f'(x_1)$ ；
（3）如果 $x_1$ 满足 $|\delta|<\varepsilon_1$ 或 $|f_1|<\varepsilon_2$ ，则终止迭代格式，以 $x_1$ 作为所求的根；否则转步骤4。其中
$\delta=\left\{ \begin{aligned} & |x_1-x_0| ,\mbox{当}|x_1|<C \\ & \frac{|x_1-x_0|}{x_1} ,\mbox{当}|x_1| \geq C\\ \end{aligned} \right.$ 其中 $C$ 是取绝对值误差或相对误差的控制常数，一般可取 $C=1$
（4）如果迭代次数达到预先指定的次数 $N$ ，或者 $f/_1=0$ ，则方法失败；否则以 $(x_1,f_1,f'_1)$ 代替 $(x_0,f_0,f'_0)$ 转步骤（2）继续迭代

4.3 简化牛顿法与牛顿下山法

简化牛顿法
也称平行弦法。其迭代公式为 $x_{k+1}=x_k-Cf(x_k),C\neq 0,k=0,1,...$ 迭代函数 $\varphi(x)=x-Cf(x)$ ，一般取 $C=\frac{1}{f'(x_0)}$
牛顿下山法
牛顿法收敛性依赖初值 $x_0$ 的选取。若 $x_0$ 偏离所求根 $x^*$ 较远，则牛顿法可能发散。
为了防止出现发散的情况，我们对迭代过程再附加一项要求，即具有单调性： $|f(x_{k+1})|<|f(x_k)|$ 满足这项要求的方法称为下山法。
我们将牛顿法与下山法结合起来使用，即在下山法保证函数值稳定下降的前提下，用牛顿法加快收敛速度。我们对迭代法的计算结果 $x’_{k+1}=x_k-\frac{f(x_k)}{f’(x_k)}$ 与前一项的近似值 $x_k$ 的适当加权平均作为新的改进值 $x_{k+1}=\lambda x’_{k+1}+(1-\lambda)x_k$ 其中 $\lambda(0<\lambda\le 1)$ 称为下山因子，上式可写为 $x_{k+1}=x_k-\lambda \frac{f(x_k)}{f’(x_k)}$ 称为 牛顿下山法。选择下山因子从 $\lambda=1$ 开始，逐次将 $\lambda$ 减半进行试算，直到能使得下降条件成立为止，再开始牛顿迭代即可求得近似解。

5 弦截法

优点：计算量比牛顿法小
缺点：收敛速度较牛顿法稍慢

5.1 基本思路

设 $x_k,x_{k-1}$ 是 $f(x)=0$ 的近似根，我们利用 $f(x_k),f(x_{k+1})$ 构造一次插值多项式 $p_1(x)$ ，并用 $p_1(x)=0$ 的根作为 $f(x)=0$ 的心近似根，由于 $p_1(x)=f(x_k)+\frac{f(x_k)-f(x_{k-1})}{x_k-x_{k-1}}(x-x_k)$ 因此有 $x_{k+1}=x_k-\frac{f(x_k)}{f(x_k)-f(x_{k-1})}(x_k-x_{k-1})$ 这样导出的公式可看作牛顿法 $x_{k+1}=x_k-\frac{f(x)}{f’(x_k)}$ 中的导数 $f’(x)$ 用差商 $\frac{f(x_k)-f(x_{k-1})}{x_k-x_{k-1}}$ 取代的结果