第七章非线性方程求根
一、重点内容提要 （一）问题简介 求单变量函数方程
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*)?fx'(?*)?...fx?(*f)0x,?( *)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时,容易证
明,f'(x*)?0,
?''(x*)?f''(x*)?0f'(x*),由定理7.4知,牛顿迭代法是平方收敛的,且
ek?1f''(x*)?k??e22f'(x*) (7.14) k
lim重根情形的牛顿迭代法 当x*是f(x)?0的m重根(m?2)时,迭代函数
?(x)?x?f(x)f'(x)在x*处的导数
?'(x*)?1?1?0m,且|?'(x*)|?1.所以牛顿迭代法求重根只是线性收敛.若
x*的重数m知道,则迭代式
xk?1??xk?m
f(xk),k?0,1,2,...f'(xk) (7.15)
求重根二阶收敛.当m未知时,x*一定是函数
?(x)?f(x)f'(x)的单重零点,此时迭代式
xk?1?xk??(xk)f(xk)f'(xk)?xk??'(xk)[f'(xk)]?f(xk)f''(xk) (7.16)
k?0,1,2,...也是二阶收敛的.
xk?1?xk?简化牛顿法 如下迭代法
f(xk),k?0,1,2,...f'(x0)
称为简化牛顿法或平行弦法.
牛顿下山法 为防止迭代不收敛,可采用牛顿下山法.具体方法见教材. 4.弦截法
将牛顿迭代法(7.13)中的
f'(xk)用f(x)在xk?1,xk处的一阶差商来代替,即可得弦截法
xk?1?xk? 定理7.6假设
f(xk)(xk?xk?1)f(xk)?f(xk?1) (7.17)
f(x)在其零点x*的邻域?:|x?x*|??内具有二阶连续导数,且对任意x??x0,x1??,,则当邻域?充分小时,弦截法(7.17)将按阶
有f'(x)?0,又初值
p?1?5?1.61822收敛到x*.这里p是方程????1?0的正根.
5.抛物线法
弦截法可以理解为用过根.若已知
(xk?1,f(xk?1)),(xk?f(xk))两点的直线方程的根近似替f(x)?0的
0三个近似根的
?2f(x?)xk,
xk?1,xk?2用过
(xk,fk(x?1)k)x,?(x,1fk(kx)x(,()0的根,所得f()x)??)kf,的抛物线方程的根近似代替
的迭代法称为抛物线法,也称密勒(Muller)法. 当
f(x)在x*的邻近有三阶连续导数,f'(x*)?0,则抛物线法局部收敛,且收敛阶为
p?1.839?1.84.
三、常考题型及典型题精解例7-1 证明方程x3?x?1?0在[1,2]上有一个实根x*,并用二分法求这个根,要求|xk-x*|?10-3.若要求|xk-x*|?10-6,需二分区间[1,2]多少次?解 设f(x)=x3?x?1,则f(1)=-1<0,f(2)=5>0,故方程f(x)=0在[1,2]上有根x*.又因f'(x)=3x2-1,所以当x?[1,2]时,f'(x)>0,即f(x)=0在[1,2]上有惟一实根x*.用二分法计算结果如表7-1所示. 表7-1 k 0 1 2 3 4 5 6 7 8 9
ak 1 1 1.25 1.25 1.3125 1.3125 1.3125 1.3204 1.3243 1.3243 bk 2 1.5 1.5 1.375 1.375 1.13438 1.3282 1.3282 1.3282 1.3263 xk 1.5 1.25 1.375 1.3125 1.3438 1.3282 1.3204 1.3243 1.3263 1.3253 f(xk)的符号 + - + - + + - - + + 此时x9=1.3253满足|x9-x*|?似值.1?0.977?10-3?10-3,可以作为x*的近1021?10-6即可,解得k+1?19.932,k+12即只需把[1,2]二分20次就能满足精度要求. 若要求|xk-x*|?10?6,只需|xk-x*|?例7-2 已知函数方程(x-2)ex=1,(1)确定有根区间[a,b];(2)构造不动点迭代公式使之对任意初始近似x0?[a,b],迭代方法均收敛;(3)用所构造的公式计算根的近似值,要求|xk?xk?1|?10?3.