第七章 非线性方程求根
一、重点内容提要 （一）问题简介 求单变量函数方程
f(x)?0 (7.1)
的根是指求x*（实数或复数），使得f(x*)?0.称x*为方程(7.1)的根,也称x*为函数f(x)mf(x)?(x?x*)g( x)f(x)的零点.若可以分解为
其中m为正整数,g(x)满足g(x)?0,则x*是方程(7.1)的根.当m=1时,称x*为单根;当m>1时,称x*为m重根.若g(x)充分光滑,x*是方程(7.1)的m重根,则有
(m?1)(m)f(x*)?f'(x*)?...?f(x*)?0,f(x*)?0
若f(x)在[a,b]上连续且f(a)f(b)?0,则方程(7.1)在(a,b)内至少有一个实根,称[a,b]为方程(7.1)的有根区间.有根区间可通过函数作图法或逐次搜索法求得.
(二)方程求根的几种常用方法 1.二分法
设f(x)在[a,b]上连续,f(a)f(b)?0,则f(x)?0在(a,b)内有根x*.再设f(x)?0在(a,b)内
1x0?(a0?b0)a?a,b0?b,计算f(x0).若f(x0)?0则x*?x,结束计2仅有一个根.令0和
算;若
f(a0)f(x0)?0,则令a1?x0,b1?b,得新的有根区间[a1,b1];若f(a0)f(x0)?0,则令
1b?a?(b0?a0)11a1?a0,b1?x0[a,b][a,b]?[a,b]1100112,得新的有根区间.,.再令1x1?(a1?b)1f(x1),同上法得出新的有根区间[a2,b2],如此反复进行,可得一有根区2计算
间套
...?[an,bn]?[an?1,bn?1]?...?[a0,b0]
11an?x*?bn,n?0,1,2,...,bn?an?(bn?1?a?1)?...?n(b0?a0)22且. 1lim(bn?an)?0,limxn?lim(an?bn)?x*n??n??2故 n??
因此,
xn?1(an?bn)2可作为f(x)?0的近似根,且有误差估计
2.迭代法
|xn?x*|?1(b?a)2n?1 (7.2)
将方程式(7.1)等价变形为 x??(x) (7.3)
若要求x*满足f(x*)?0则x*??(x*);反之亦然.称x*为函数?(x)的一个不动点.求方程(7.1)的根等价于求?(x)的不动点由式(7.3)产生的不动点迭代关系式(也称简单迭代法)为
xk?1??(xk)k,?0,1, 2... (7.4)
xk?1??(xk),k?0,1,2...,由式(7.4)产生的序列?xk?有
函数?(x)称为迭代函数.如果对任意极限
limxk?x*k??
则称不动点迭代法(7.4)收敛.
定理7.1(不动点存在性定理)设?(x)?C[a,b]满足以下两个条件: 1.对任意x?[a,b]有a??(x)?b;
2.存在正常数L?1,使对任意x,y?[a,b],都有|?(x)??(y)|?|x?y| (7.5) 则?(x)在[a,b]上存在惟一的不动点x*.
定理7.2(不动点迭代法的全局收敛性定理)设?(x)?C[a,b]满足定理7.1中的两个条件,则对任意
x0?[a,b],由(7.4)式得到的迭代序列?xk?收敛.到?(x)的不动点,并有误差估计式
|xk?x*|?L|xk?xk?1|1?L (7.6)
Lk|xk?x*|?|xk?xk?1|1?L和 (7.7)
定理7.3(不动点迭代法的局部收敛性定理)设x*为?(x)的不动点,?'(x)在x*的某个邻域连续,且|?'(x)|?1,则迭代法(7.4)局部收敛.
收敛阶的概念 设迭代过程(7.4)收敛于方程x??(x)的根x*,如果迭代误差
ek?xk?x*当k??时成产下列渐近关系式
ek?1?C(常数C?0)e k (7.8)
则称该迭代过程是p阶收敛的.特别地,p=1时称线性收敛,p>1时称超线性收敛,p=2时称平方
收敛.
(K)?(x)在所求根x*的邻近连续,并且 定理7.4(收敛阶定理)对于迭代过程(7.4),如果
?'(x*)??''(x*)?...??(p?1)(x*)?0?(p)(x*)?0
则该迭代过程在点x*的邻近是收敛的,并有
(7.9)
lim
ek?11(p)??(x*)k??epp!k (7.10)
斯蒂芬森(Steffensen)迭代法 当不动点迭代法(7.4)只有线性收敛阶,甚至于不收敛时,可用斯
蒂芬森迭代法进行加速.具体公式为
yk??(xk),zk??(yk)(yk?xk)2xk?1?xk?zk?2yk?xkk?0,1,2,... (7.11)
此法也可写成如下不动点迭代式
xk?1??(xk),k?0,1,2,...(?(x)?x)2?(x)?x??(?(x))?2?(x)?x (7.12)
定理7.5(斯蒂芬森迭代收敛定理) 设x*为式(7.12)中设?''(x)存在,?'(x*)?1,则x*是
?(x)的不动点,则x*是?(x)的不动点;
?(x)的不动点,则斯蒂芬森迭代法(7.11)是2阶收敛的.
3.牛顿迭代法
牛顿迭代法是一种特殊的不动点迭代法,其计算公式为
xk?1?xk? 其迭代函数为
f(xk),k?0,1,2,...f'(xk) (7.13)
?(x)?x?
f(x)f'(x)
牛顿迭代法的收敛速度 当f(x*)?0,f'(x*)?0,f''(x*)?0时,容易证