迭代法的一般理论 |
您所在的位置:网站首页 › 一般迭代法求方程的根 › 迭代法的一般理论 |
迭代法的一般理论
非线性方程的数值方法
张瑞
中国科学技术大学数学科学学院
[email protected]
迭代法的基础理论
非线性问题是实际问题中经常遇到的问题。非线性方程的求根是其中一个重要的课题。 方程$\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)$内可导,且满足 当$x\in[a,b]$时,$\phi(x)\in[a,b]$ 当$x\in(a,b)$时,$|\phi'(x)|\leq L0$,使得 \[\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 |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |