Chapter 2 一元方程的求解 | Solutions of Equations in One Variable

约 1520 个字 5 张图片 预计阅读时间 8 分钟

2.0 停机程序 | Stopping procedure

我们可以选择一个精度要求$ϵ$，逐步迭代，直到满足下列条件之一：

1. $|x_{i+1}-x_i|<ϵ$
2. $|f(x_{i+1})|<ϵ$
3. $\frac{|x_{i+1}-x_i|}{|x_{i+1}|}<ϵ$

如果$|x_{i+1}-x_i|$收敛于0而序列本身发散 ，1号会失效。

也有可能$f(x)$与0很接近，但是$x_n$与$x$差别很大，2号也不行了。

3号条件是能运用的最好的停机准则，因为它最接近测试相对误差。

2.1 二分法 | Bisection Method

为什么要用a+(b-a)/2，而不用(b+a)/2？

1. 因为a和b可能是很大的数，相加可能会溢出。
2. 因为a和b可能是很小的数，相加可能会产生舍入误差。用此方法可以确保a+(b-a)/2落在a和b之间。
3. 例如，用截断保留2位有效数字，a=0.91，b=0.93，(a+b)/2=1.8/2=0.9，而a+(b-a)/2=0.91+(0.93-0.91)/2=0.92。

2.2 不动点迭代 | Fixed-Point Iteration

不动点的存在性和唯一性的充分条件：

a. $g\in C[a,b]$且$g(x)\in [a,b],\mathrm{\forall }x\in [a,b]$，则$g$在$[a,b]$上有不动点。

b. $|g^{\prime }(x)|\le k<1,\mathrm{\forall }x\in (a,b)$，则该不动点是唯一的。

则对于任意$p_0\in [a,b]$，不动点迭代序列$p_{n+1}=g(x_n)$收敛于不动点。

且我们有误差限$|p_n-p|\le \frac{k^n}{1-k}|p_1-p_0|$，这将收敛速率和一阶导数的界联系起来。

误差界分析

$$\begin{array}{rl}|p_{n+1}-p_n|& =|g(p_n)-g(p_{n-1})|=|g^{\prime }(\xi )||p_n-p_{n-1}|\le k|p_n-p_{n-1}|\\ & \le k^2|p_{n-1}-p_{n-2}|\le \dots \le k^n|p_1-p_0|\end{array}$$

$$\begin{array}{rl}|p_n-p|& =|p_n-p_{n-1}+p_{n-1}-p_{n-2}+\dots +p_1-p_0|\\ & \le |p_n-p_{n-1}|+|p_{n-1}-p_{n-2}|+\dots +|p_1-p_0|\\ & \le (k^{n-1}+k^{n-2}+\dots +1)|p_1-p_0|\\ & =\frac{k^n-1}{k-1}|p_1-p_0|\le \frac{k^n}{1-k}|p_1-p_0|\end{array}$$

2.3 牛顿迭代法 | Newton's Method

就是用切线逼近零点，然后求切线与x轴的交点，作为下一个点，如此往复。

$$x_{n+1}=x_n-\frac{f(x_n)}{f^{\prime }(x_n)}$$

定理：设$f\in C^2[a,b]$，如果$p\in [a,b]$满足$f(p)=0$且$f^{\prime }(p)\ne 0$，则存在$\delta >0$，使得对任何初始值$p_0\in (p-\delta ,p+\delta )$，牛顿迭代法产生收敛于$p$的序列$\{p_n{\}}_{n=1}^{\mathrm{\infty }}$。

证明：

牛顿迭代法的收敛性取决于初始近似值的选择。

2.4 迭代法的误差分析 | Error Analysis for Iterative Methods

假设$\{p_n{\}}_{n=0}^{\mathrm{\infty }}$收敛于$p$，其中对$\mathrm{\forall }{p}_n\ne p$。如果存在正数$\lambda$和$\alpha$，使得

$$\underset{n\to \mathrm{\infty }}{lim}\frac{|p_{n+1}-p|}{|p_n-p{|}^{\alpha }}=\lambda$$

则称$\{p_n{\}}_{n=0}^{\mathrm{\infty }}$是$\alpha$阶收敛的(converges to p of order α)，$\lambda$称为渐进误差常数(asymptotic error constant)。

一般具有高阶收敛性的序列收敛速度更快。

• 如果$\alpha =1$，则该序列是线性收敛的(linearly convergent)。

• 如果$\alpha =2$，则该序列是二次收敛的(quadratically convergent)。

不动点法

不动点法的收敛阶和渐进误差常数：

$$\begin{array}{rl}{p}_{n+1}-p=g(p_n)-g(p)=g^{\prime }(\xi )(p_n-p)& \Rightarrow \frac{|p_{n+1}-p|}{|p_n-p|}=|g^{\prime }(\xi )|\\ & \Rightarrow \underset{n\to \mathrm{\infty }}{lim}\frac{|p_{n+1}-p|}{|p_n-p|}=\underset{n\to \mathrm{\infty }}{lim}|g^{\prime }(\xi )|=|g^{\prime }(p)|\end{array}$$

因此，如果$g^{\prime }(p)\ne 0$，则不动点迭代法是线性收敛的，且渐进误差常数为$|g^{\prime }(p)|$。

牛顿迭代法

牛顿迭代法的收敛阶和渐进误差常数：

由泰勒展开：

$$\begin{array}{rl}0& =f(p)=f(p_n)+f^{\prime }(p_n)(p-p_n)+\frac{f^{″}(\xi )}{2}(p-p_n{)}^2\\ & \Rightarrow p=p_n-\frac{f(p_n)}{f^{\prime }(p_n)}-\frac{f^{″}(\xi )}{2f^{\prime }(p_n)}(p-p_n{)}^2\\ & \Rightarrow \underset{n\to \mathrm{\infty }}{lim}\frac{|p_{n+1}-p|}{|p_n-p{|}^2}=\underset{n\to \mathrm{\infty }}{lim}\frac{|f^{″}(\xi )|}{2|f^{\prime }(p_n)|}=\frac{|f^{″}(p)|}{2|f^{\prime }(p)|}\end{array}$$

因此，牛顿迭代法是二次收敛的，且渐进误差常数为$\frac{|f^{″}(p)|}{2|f^{\prime }(p)|}$。

不动点法的多重根情况

如果$p$是$g(x)$的不动点，存在正整数$m$，使得$g^{\prime }(p)=g^{″}(p)=\dots =g^{(m-1)}(p)=0$，且$g^{(m)}(p)\ne 0$，则称$p_n=g(p_{n-1})$以阶$m$收敛于$p$，渐进误差常数为$\frac{|g^{(m)}(p)|}{m!}$。

$$\begin{array}{rl}{p}_{n+1}& =g(p_n)=g(p)+g^{\prime }(p)(p_n-p)+\frac{g^{″}(\xi )}{2}(p_n-p{)}^2+\dots +\frac{g^{(m)}(\xi )}{m!}(p_n-p{)}^m\\ & \Rightarrow \underset{n\to \mathrm{\infty }}{lim}\frac{|p_{n+1}-p|}{|p_n-p{|}^m}=\underset{n\to \mathrm{\infty }}{lim}\frac{|g^{(m)}(\xi )|}{m!}=\frac{|g^{(m)}(p)|}{m!}\end{array}$$

牛顿法的多重根情况

如果$p$是$f$的$m$重零点，则有$f(x)=(x-p{)}^{m}q(x)$，记$g(x)=x-\frac{f(x)}{f^{\prime }(x)}$，牛顿法即为 $p_n=g(p_{n-1})$

$$\begin{array}{rl}{g}^{\prime }(x)& =1-\frac{f^{\prime }(x{)}^2-f(x)f^{″}(x)}{(f^{\prime }(x){)}^2}\\ & =\frac{f(x)f^{″}(x)}{(f^{\prime }(x){)}^2}\\ & =\frac{(x-p{)}^{m}q(x)(m(m-1)(x-p{)}^{m-2}q(x)+2m(x-p{)}^{m-1}{q}^{\prime }(x)+q^{″}(x)(x-p{)}^m)}{(m(x-p{)}^{m-1}q(x)+q^{\prime }(x)(x-p{)}^m{)}^2}\\ & =\frac{(x-p{)}^{2m-2}q(x)(m(m-1)q(x)+2m(x-p)q^{\prime }(x)+q^{″}(x)(x-p{)}^2)}{(x-p{)}^{2m-2}(mq(x)+q^{\prime }(x)(x-p){)}^2}\\ & =\frac{q(x)(m(m-1)q(x)+2m(x-p)q^{\prime }(x)+q^{″}(x)(x-p{)}^2)}{(mq(x)+q^{\prime }(x)(x-p){)}^2}\end{array}$$

所以

$$g^{\prime }(p)=\frac{q(p)m(m-1)q(p)}{(mq(p){)}^2}=1-\frac{1}{m}<1$$

由不动点法的迭代情况可知，此时为线性收敛，不为二次收敛。

牛顿法多重根下的优化

定义

$$\mu (x)=\frac{f(x)}{f^{\prime }(x)}$$

如果$p$是$f$ 的$m$重零点，$f(x)=(x-p{)}^{m}q(x)$，则

$$\mu (x)=\frac{(x-p{)}^{m}q(x)}{m(x-p{)}^{m-1}q(x)+q^{\prime }(x)(x-p{)}^m}=\frac{(x-p)q(x)}{mq(x)+q^{\prime }(x)(x-p)}$$

又$q(p)\ne 0$，且

$$\frac{q(p)}{mq(p)+q^{\prime }(p)(p-p)}=\frac{1}{m}\ne 0$$

所以$p$是$\mu (x)$的单根，那么我们对$\mu$应用牛顿迭代法，就有

$$\begin{array}{rl}{p}_{n+1}=g(p_n)& =p_n-\frac{\mu (p_n)}{{\mu }^{\prime }(p_n)}\\ & =p_n-\frac{\frac{f(p_n)}{f^{\prime }(p_n)}}{\frac{f^{\prime }(p_n)f^{\prime }(p_n)-f(p_n)f^{″}(p_n)}{(f^{\prime }(p_n){)}^2}}\\ & =p_n-\frac{f(p_n)f^{\prime }(p_n)}{f^{\prime }(p_n{)}^2-f(p_n)f^{″}(p_n)}\end{array}$$

这就是让有多重根的牛顿法二次收敛的方法。

1. 要求二阶导
2. 分母由两个接近于0的数相减，会引起严重的舍入误差。

2.5 加速收敛 | Accelerating Convergence

二次收敛是很少可以得到的，我们在日常中总会碰到线性收敛。为了考虑如何加速线性收敛序列的收敛速度，下面介绍——AITKEN${\mathrm{\Delta }}^2$方法。

AITKEN${\mathrm{\Delta }}^2$方法

$\mathrm{\Delta }$

对于给定的序列，向前差分(forward difference)定义为$\mathrm{\Delta }{p}_n=p_{n+1}-p_n$，对于更高的幂，我们有${\mathrm{\Delta }}^k{p}_n=\mathrm{\Delta }({\mathrm{\Delta }}^{k-1}{p}_n)$，比如${\mathrm{\Delta }}^2{p}_n=\mathrm{\Delta }(\mathrm{\Delta }{p}_n)=\mathrm{\Delta }(p_{n+1}-p_n)=(p_{n+2}-p_{n+1})-(p_{n+1}-p_n)$

假设$\{p_n{\}}_{n=0}^{\mathrm{\infty }}$是线性收敛的，其极限为$p$。

为了便于构造比$\{p_n{\}}_{n=0}^{\mathrm{\infty }}$收敛更快的序列$\{{\hat{p}}_n{\}}_{n=0}^{\mathrm{\infty }}$，我们假设$p_n-p,p_{n+1}-p,p_{n+2}-p$的符号一致，又假设$n$足够大，有

$$\frac{p_{n+1}-p}{p_n-p}\approx \frac{p_{n+2}-p}{p_{n+1}-p}$$

从而

$$p_{n+1}^2-2p_{n+1}p+p^2\approx p_{n+2}{p}_n-(p_n+p_{n+2})p+p^2$$

解出$p$，得到

$$p\approx \frac{p_{n+2}{p}_n-p_{n+1}^2}{p_{n+2}-2p_{n+1}+p_n}\approx p_n-\frac{(p_{n+1}-p_n{)}^2}{p_{n+2}-2p_{n+1}+p_n}$$

于是，我们可以构造序列$\{{\hat{p}}_n{\}}_{n=0}^{\mathrm{\infty }}$，其中

$${\hat{p}}_n=p_n-\frac{(p_{n+1}-p_n{)}^2}{p_{n+2}-2p_{n+1}+p_n}=p_n-\frac{(\mathrm{\Delta }{p}_n{)}^2}{{\mathrm{\Delta }}^2{p}_n}$$

这样定义序列的方法就是AITKEN${\mathrm{\Delta }}^2$法

为什么说更快？

可以证明

$$\underset{n\to \mathrm{\infty }}{lim}\frac{\widehat{p_n}-p}{p_n-p}=0$$

怎么迭代？

其实还是用序列本身的迭代法，不过在计算值的时候采取了AITKEN${\mathrm{\Delta }}^2$法。

构造按如下顺序：

$$\begin{gathered} p_0,p_1=g(p_0),p_2=g(p_1) \\ \widehat{p_0}=\{{\mathrm{\Delta }}^2\}(p_0) \\ {p}_3=g(p_2) \\ \widehat{p_1}=\{{\mathrm{\Delta }}^2\}(p_1) \\ ⋮ \end{gathered}$$

Steffensen 方法

这个方法假设$\widehat{p_0}$比$p_2$更好地逼近$p$，从而把上述过程第三行的不动点迭代应用到$\widehat{p_0}$上

$$\begin{gathered} p_0^{(0)},p_1^{(0)}=g(p_0^{(0)}),p_2^{(0)}=g(p_1^{(0)}) \\ {p}_0^{(1)}=\{{\mathrm{\Delta }}^2\}(p_0^{(0)}) \\ {p}_1^{(1)}=g(p_0^{(0)}) \\ ⋮ \end{gathered}$$

算法如下：

注意${\mathrm{\Delta }}^2{p}_n$可能为0，如果发生，则终止并选取$p_2^{(n-1)}$为近似解。

我们一般要求$g^{\prime }(p)\ne 0$，则在邻域内Steffensen法是二次收敛的