迭代法的一般理论

非线性方程的数值方法

张瑞
中国科学技术大学数学科学学院

迭代法的基础理论

非线性问题是实际问题中经常遇到的问题。非线性方程的求根是其中一个重要的课题。

  • 方程$\sin(x)-\frac12=0$在$\mathbb{R}$上有无穷多个根。
  • 方程$e^x-\cos(\pi x)-1=0$在$(0,1)$上有一个根，但没法用初等函数表达出来。
  • 方程$\begin{cases} y=x^2+c \\ x=y^2+c \end{cases}$的根的情况跟$c$的值有关
    • $c=0$，方程有2个根$x=0,1$
    • $c=\frac14$，方程有1个根$x=\frac12$
    • $c=-1$，方程有3组解$x=-1, 0, \frac{1+\sqrt 5}2$

非线性问题相比较于线性问题要复杂得多，至今没有很好的理论来给出根的存在性判定。

现有的理论，非线性问题在局部的性质有一些结论。因此数值上，也只能在局部求解非线性方程的根。

这种方法通常是迭代法，预先给出根的初始估计值，然后不断地逼近根。

迭代法

定义 1.
设有方程$f(x)=0$的等价形式

\[x=\phi(x) \]

由根附近的某初值$x_0$开始，作序列

\[x_{n+1}=\phi(x_n), n=0,1,2,\cdots \]

若$\phi(x)$连续，且

\[\lim_{n\to\infty}x_n=\alpha \]

则有$\alpha=\phi(\alpha)$，即$\alpha$是方程的根。这种求根方法称为迭代方法。

例 1. 求$x=10^x-2$

解. 方法1： 作格式

\[x_{n+1}=10^{x_n}-2 \]

取$x_0=1$，有

\[x_1=8, x_2=10^8-2 \]

序列无限增大，不收敛。这时，称迭代不收敛。

方法2：作格式

\[x_{n+1}=\lg(x_n+2) \]

取初值$x_0=1$，有

\[\begin{aligned} x_1=0.4771, x_2=0.3939, x_3=0.3791, x_4=0.3764, \\ x_5=0.3759, x_6=0.3758, x_7=0.3758, \cdots \end{aligned} \]

序列收敛。可以得到根的近似值为$0.3758$

收敛定理

定理 1.
函数$\phi(x)$在$[a,b]$上连续，$(a,b)$内可导，且满足

  1. 当$x\in[a,b]$时，$\phi(x)\in[a,b]$
  2. 当$x\in(a,b)$时，$|\phi'(x)|\leq L<1$，$L$为常数。

则有

  1. 在$[a,b]$上，方程$x=\phi(x)$有且仅有一根，记为$\alpha$；
  2. 对$\forall x_0\in[a,b]$，由迭代格式
    \[x_{n+1}=\phi(x_n), n=0,1,2,\cdots \]
    产生的序列$\{x_n\}$收敛到$\alpha$。
  3. 有误差估计$\displaystyle|\alpha-x_n|\leq\frac{L^n}{1-m}|x_1-x_0|$

证明. (1) 存在性。

令$F(x)=x-\phi(x)$，则有

\[F(a)=a-\phi(a)<0, F(b)=b-\phi(b)>0 \]

由连续函数的介值性，存在至少一个$\xi\in[a,b]$满足

\[F(\xi)=0 \]

即，$\phi(\xi)=\xi$

唯一性：

若有$\alpha,\beta$都满足$\phi(x)=x$，则有

\[\alpha-\beta=\phi(\alpha)-\phi(\beta)=\phi'(\xi)(\alpha-\beta) \]

所以

\[|\alpha-\beta|=|\phi'(\xi)||\alpha-\beta|\leq L |\alpha-\beta| \]

由$L<1$，则有

\[|\alpha-\beta|=0 \]

即，$\alpha=\beta$。

(2) 设$\alpha=\phi(\alpha)$，则

\[x_{n+1}-\alpha=\phi(x_n)-\phi(\alpha)=\phi'(\xi)(x_n-\alpha) \]

所以

\[|x_{n+1}-\alpha|=|\phi'(\xi)(x_n-\alpha)|\leq L|x_n-\alpha| \]

这样，

\[\begin{aligned} |x_{n+1}-\alpha|&\leq L|x_n-\alpha|\leq L^2|x_{n-1}-\alpha| \\ &\leq L^3|x_{n-2}-\alpha|\leq ... \\ &\leq L^{n+1}|x_0-\alpha| \end{aligned} \]

由$0<L<1$，数列$x_n$收敛到$\alpha$。

(3) 由

\[x_{n+1}-x_n=\phi(x_n)-\phi(x_{n-1})=\phi'(\xi)(x_n-x_{n-1}) \]

可得

\[|x_{n+1}-x_n|=|\phi'(\xi)(x_n-x_{n-1})|\leq L |x_n-x_{n-1}| \]

这样，有

\[\begin{aligned} |x_{n+1}-x_n|&\leq L |x_n-x_{n-1}|\leq L^2 |x_{n-1}-x_{n-2}| \\ &\leq L^3 |x_{n-2}-x_{n-3}|\leq\cdots \\ &\leq L^{n} |x_{1}-x_{0}| \end{aligned} \]

对任意自然数$p$，有

\[\begin{aligned} |x_{n+p}-x_n|\leq&|x_{n+p}-x_{n+p-1}|+|x_{n+p-1}-x_{n+p-2}|\\ &+\cdots+|x_{n+1}-x_n| \\ \leq &(L^{n+p-1}+L^{n+p-2}+\cdots L^n)|x_1-x_0| \\ = & \frac{L^n-L^{n+p}}{1-L}|x_1-x_0| \\ < & \frac{L^n}{1-L}|x_1-x_0| \end{aligned} \]

令$p\to\infty$，则有

\[|\alpha-x_n|\leq\frac{L^n}{1-L}|x_1-x_0| \]
  • 定理只是给出了判定迭代收敛的一个充分条件。
  • 但要构造满足定理条件的等价形式也不容易做到。
  • $x^*$是方程$f(x)=0$的根。若有$|\phi'(x^*)|<1$，则存在$x^*$的领域$(x^*-\delta, x^*+\delta)$，其上成立$|\phi'(x)|<L<1$。这样，若初值$x_0$（或迭代序列中的某个值）落在领域内，就可以得到收敛的迭代序列了。
  • 经常使用条件$\phi'(x^*)|<1$是否成立，来判定一个迭代格式能否收敛。
  • 前面的定理可以看到，$L$越小，收敛速度越快。
  • 同时，前面的定理也表明，随着迭代的进行，$x_n$会越来越靠近根， 因而判定$|\phi'(x)|\leq L$的取值范围也会减小，从而$L$也会不断变化，
  • 因此，$L$的大小并不适合判定收敛的快慢。

定义 2.
迭代序列$\{x_n\}$收敛到$\alpha$，且$e_k=\alpha-x_k\neq 0$，若存在常数$r\geq 1$和常数$c>0$，使得

\[\lim_{k\to\infty}\frac{|e_{k+1}|}{|e_k|^r}=c \]

成立，则称迭代格式是r阶收敛的。

$r=1$时，称格式是线性收敛的。$r>1$时，称为超线性收敛。$r=2$时，称为平方收敛。

定理 2.
设$\alpha$满足$\alpha=\phi(\alpha)$，整数$n>1$，$\phi(x)$在$\alpha$附近具有$n$阶连续导数，且

\[\phi^{(k)}(\alpha)=0, k=1,2,\cdots,n-1; \phi^{(n)}(\alpha)\neq 0 \]

则迭代格式

\[x_{k+1}=\phi(x_k), k=0,1,2,\cdots \]

是$n$阶收敛的，且有

\[\lim_{k\to\infty}\frac{|e_{k+1}|}{|e_k|^n}=\frac{|\phi^{(n)}(\alpha)|}{n!} \]

证明. 由Taylor公式

\[\begin{aligned} \phi(x_k)=&\phi(\alpha)+\phi'(\alpha)(x_k-\alpha)+\cdots\\ &+\frac{\phi^{(n-1)}(\alpha)}{(n-1)!}(x_k-\alpha)^{n-1} +\frac{\phi^{(n)}(\xi)}{n!}(x_k-\alpha)^{n} \\ =&\phi(\alpha)+\frac{\phi^{(n)}(\xi)}{n!}(x_k-\alpha)^{n} \end{aligned} \]

则有

\[|e_{k+1}|=|\phi(x_k)-\phi(\alpha)|=\frac{|\phi^{(n)}(\xi)|}{n!}|e_k|^n \]

例 2. 为求方程$x^3+2x-5-0$在$[1,2]$内的根，产生如下的迭代格式

\[x_{k+1}=\sqrt[3]{5-2x_k} \]

给出该格式的收敛性和收敛阶。

解. 由题知，

\[\phi(x)=\sqrt[3]{5-2x} \]

在区间$[1,2]$内，有

\[|\phi'(x)|=|\frac13\frac{-2}{(5-2x)^{\frac23}}|\leq\frac23<1 \]

所以，迭代格式是收敛的。

在根$\alpha$处，有

\[\phi'(\alpha)=-\frac{2}{3(5-2x)^{\frac23}}=\frac{-2}{3\alpha^2}\neq 0 \]

格式是线性收敛的。

Steffensen加速收敛

若格式是线性收敛的，即有

\[\lim_{k\to\infty}\frac{x_{k+1}-\alpha}{x_k-\alpha}=c \]

则，当$k$充分大时，有

\[x_{k+1}-\alpha\approx c(x_k-\alpha), x_{k+2}-\alpha \approx c(x_{k+1}-\alpha) \]

因此

\[\frac{x_{k+2}-\alpha}{x_{k+1}-\alpha}\approx\frac{x_{k+1}-\alpha}{x_k-\alpha} \]

这样，可以得到

\[\alpha\approx x_k-\frac{(x_{k+1}-x_k)^2}{x_{k+2}-2x_{k+1}+x_k} \]

得到的表达式作为$\alpha$近似值，会比$x_{k+1}$, $x_{k+2}$更好。

定义 3.
若有迭代格式$x_{k+1}=\phi(x_k)$，则格式

\[\begin{cases} y_k=\phi(x_k), z_k=\phi(y_k) \\ x_{k+1}=x_k-\frac{(y_k-x_k)^2}{z_k-2y_k+x_k} \end{cases} , k=0,1,2,\cdots \]

称为史蒂芬森加速迭代法(Steffensen)。

定理 3.
设$\alpha=\phi(\alpha)$，$\phi(x)$在包含$\alpha$的某个开区间内具有连续的二阶导数， 并且$\phi'(\alpha)\neq 1$，则如上的迭代格式至少二阶收敛。

例 3. 将Steffensen加速应用到解$x=10^x-2$方程的两种格式中。

  1. $x_{n+1}=10^{x_n}-2$
  2. $x_{n+1}=\lg(x_n+2)$

解. 

用Steffensen加速  x= log_{10}(x+2)
0 0.5
1 0.375935526659935
2 0.37581208772453945
3 0.3758120875934263
4 0.3758120875934263
迭代收敛
不收敛格式的Steffen加速  x=10^x-2 
0 0.5
1 0.459030642738056
2 0.4177856359561663
3 0.3878203271079459
4 0.3768844259181736
5 0.37582092149660973
6 0.37581208819484646
7 0.3758120875934263
8 0.37581208759342627
迭代收敛

目录

本节读完

例 4.

4.