第七章非线性方程求根
（一）问题简介 求单变量函数方程
f(x)?0 (7.1)
的根是指求x*（实数或复数），使得f(x*)?0.称x*为方程(7.1)的根,也称x*为函数f(x)?的零点.若f(x)可以分解为 f(x)?(xx*)g( xm其中m为正整数,g(x)满足g(x)?0,则x*是方程(7.1)的根.当m=1时,称x*为单根;当m>1时,称x*为m重根.若g(x)充分光滑,x*是方程(7.1)的m重根,则有 f(x*)?f'(x*)?...?f(m?1)(x*)?0,f(m)(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)内
x0?12(a0?b0)仅有一个根.令算;若
a0?a,b0?b,计算和
f(x0).若
f(x0)?0则x*?x,结束计
,则令
f(a0)f(x0)?0,则令
a1?x0,b1?b,得新的有根区间
[a1,b1];若
f(a0)f(x0)?012a1?a0,b1?x0,得新的有根区间
[a1,b1].
[a0,b0]?[a1,b1],
b1?a1?(b0?a0).再令
x1?12(a1?b)1计算
f(x1),同上法得出新的有根区间
[a2,b2],如此反复进行,可得一有根区
间套
...?[an,bn]?[an?1,bn?1]?...?[a0,b0]12
12n且
an?x*?bn,n?0,1,2,...,bn?an?(bn?1?a?1)?...?(b0?a0).
故
lim(bn?an)?0,limxn?limn??n??12n??(an?bn)?x*
因此,
xn?12(an?bn)可作为f(x)?0的近似根,且有误差估计
12n?1 2.迭代法
|xn?x*|?(b?a) (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...函数?(x)称为迭代函数.如果对任意极限
limxk?x*k??,由式(7.4)产生的序列
?xk?有
则称不动点迭代法(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*|?L?xk?收敛.到?(x)的不动点,并有误差估计式
|xk?xk?1|
1?LLk (7.6)
和
|xk?x*|?1?L|xk?xk?1| (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)
ek (7.8)
则称该迭代过程是p阶收敛的.特别地,p=1时称线性收敛,p>1时称超线性收敛,p=2时称平方收敛.
定理7.4(收敛阶定理)对于迭代过程(7.4),如果??'(x*)??''(x*)?...???(p)(p?1)(K)(x)在所求根x*的邻近连续,并且
(x*)?0(x*)?0 (7.9)
则该迭代过程在点x*的邻近是收敛的,并有
limek?1epk
k???1p!?(p)(x*) (7.10)
斯蒂芬森(Steffensen)迭代法 当不动点迭代法(7.4)只有线性收敛阶,甚至于不收敛时,可用斯蒂芬森迭代法进行加速.具体公式为
yk??(xk),zk??(yk)xk?1?xk?(yk?xk)2zk?2yk?xkk?0,1,2,... (7.11)
此法也可写成如下不动点迭代式
xk?1??(xk),k?0,1,2,...?(x)?x?(?(x)?x)2?(?(x))?2?(x)?x (7.12)
?(x)定理7.5(斯蒂芬森迭代收敛定理) 设x*为式(7.12)中的不动点,则x*是?(x)的不动点;?(x)设?''(x)存在,?'(x*)?1,则x*是的不动点,则斯蒂芬森迭代法(7.11)是2阶收敛的.
3.牛顿迭代法
牛顿迭代法是一种特殊的不动点迭代法,其计算公式为
xk?1?xk?f(xk)f'(xk),k?0,1,2,... 其迭代函数为
?(x)?x?f(x)f'(x) (7.13)
牛顿迭代法的收敛速度 当f(x*)?0,f'(x*)?0,f''(x*)?0时,容易证
明,f'(x*)?0,
?''(x*)?f''(x*)f'(x*)?0,由定理7.4知,牛顿迭代法是平方收敛的,且
f''(x*)limek?1ek2
k???2f'(x*) (7.14)
?(x)?x?f(x)f'(x)重根情形的牛顿迭代法 当x*是f(x)?0的m重根(m?2)时,迭代函数
?'(x*)?1?1m?0在x*处的导数
,且|?'(x*)|?1.所以牛顿迭代法求重根只是线性收敛.若
x*的重数m知道,则迭代式
xk?1??xk?mf(xk)f'(xk),k?0,1,2,... (7.15)
?(x)?f(x)f'(x)的单重零点,此时迭代式
求重根二阶收敛.当m未知时,x*一定是函数
xk?1?xk??(xk)?'(xk)?xk?f(xk)f'(xk)[f'(xk)]?f(xk)f''(xk) k?0,1,2,...也是二阶收敛的.
xk?1?xk?f(xk)f'(x0),k?0,1,2,... (7.16)
简化牛顿法 如下迭代法
称为简化牛顿法或平行弦法.
牛顿下山法 为防止迭代不收敛,可采用牛顿下山法.具体方法见教材. 4.弦截法
将牛顿迭代法(7.13)中的
xk?1?xk?f'(xk)xx用f(x)在k?1,k处的一阶差商来代替,即可得弦截法
(xk?xk?1)f(xk)f(xk)?f(xk?1) 定理7.6假设
f(x) (7.17)
在其零点x*的邻域?:|x?x*|??内具有二阶连续导数,且对任意x??x0,x1??有f'(x)?0,又初值
p?1?25?1.618,,则当邻域?充分小时,弦截法(7.17)将按阶
收敛到x*.这里p是方程????1?0的正根.
25.抛物线法
弦截法可以理解为用过根.若已知
(xk,fk(xk?1,f(xk?1)),(xk?f(xk))两点的直线方程的根近似替f(x)?0的
xkf(x?)的三个近似根
k,
xk?1,
xk?2用过
(x?1)k)x,?1(fx,?2(kx)?)kf,x(,()0f()x)?的抛物线方程的根近似代替的根,所得
的迭代法称为抛物线法,也称密勒(Muller)法. 当
f(x)在x*的邻近有三阶连续导数,f'(x*)?0,则抛物线法局部收敛,且收敛阶为
p?1.839?1.84.
二、知识结构图
三、常考题型及典型题精解例7-1 证明方程x?x?1?0在[1,2]上有一个实根x*,并用二分法求这个根,要求|xk-x*|?10.若要求|xk-x*|?10,需二分区间[1,2]多少次?解 设f(x)=x?x?1,则f(1)=-1<0,f(2)=5>0,故方程f(x)=0在[1,2]上有根x*.又因f'(x)=3x-1,所以当x?[1,2]时,f'(x)>0,即f(x)=0在[1,2]上有惟一实根x*.用二分法计算结果如表7-1所示.23-3-63
表7-1 k 0 1 2 3 4 5 6 7 8
ak bk xk f(xk)的符号 1 1 1.25 1.25 1.3125 1.3125 1.3125 1.3204 1.3243 2 1.5 1.5 1.375 1.375 1.13438 1.3282 1.3282 1.3282 1.5 1.25 1.375 1.3125 1.3438 1.3282 1.3204 1.3243 1.3263 + - + - + + - - +
9 1.3243 1.3263 1.3253 + 此时x9=1.3253满足|x9-x*|?似值.1210?0.977?10-3?10,可以作为x*的近-3 若要求|xk-x*|?10,只需|xk-x*|??612k+1?10即可,解得k+1?19.932,-6即只需把[1,2]二分20次就能满足精度要求.例7-2 已知函数方程(x-2)e=1,(1)确定有根区间[a,b];(2)构造不动点迭代公式使之对任意初始近似x0?[a,b],迭代方法均收敛;(3)用所构造的公式计算根的近似值,要求|xk?xk?1|?10.?3x
x解 (1)令f(x)=(x-2)e-1,由于f(2)=-1<0,f(3)=e-1>0,因此区间[2,3]是方程f(x)=0的一个有根区间.又因f'(x)=(x-1)e,limf(x)=+?,limf(x)=-1,x???x???xxf'(1)=-e-1<0,当x>1时f(x)单增,x<1时f(x)单减,故f(x)=0在(-?,+?)内有且仅有一根x*,即x*?[2,3].(2)将(x-2)e=1等价变形为x=2+ex?x1
,x?[2,3].则?(x)=2+e.由于当?x?2xx?[2,3]时2??(x)?3,|?'(x)|=|-e|?e<1故不动点迭代法xk+1=2+e?xk,k=0,1,2,...,对?x0?[2,3]均收敛.进行迭代计算,结果如表7-2所示.(3)取x0=2.5,利用xk+1=2+e?xk
表7-2 k 0 1 2 3 4 xk |xk?xk?1| 2.5 2.082084999 2.124670004 2.119472387 2.120094976 0.417915001 0.042585005 0.0005197617 0.000622589
此时x4已满足误差要求,即x*?x4?2.120094976.例7?3 考虑求解方程2cosx?3x?12?0的迭代公式 xk+1=4+23cosxk,k=0,1,2,... (1)试证:对任意初始近似x0?R,该方法收敛;(2)取x0=4,求根的近似值xk+1,要求|xk+1-xk|?10;(3)所给方法的收敛阶是多少?解 (1)由迭代公式知,迭代函数?(x)=4+x?(??,??).由于?(x)的值域介于(4-|?'(x)|=|-23sinx|?23?12323cosx,23)之间,且-3)与(4+故根据定理7.1,7.2知,?(x)在(??,??)内存在惟一的不动点x*,且对?x0?R,迭代公式得到的序列?xk?收敛于x*.(2) 取x0=4,迭代计算结果如表7-3所示.
|xk?xk?1| 表7-3 k 0 1 2 3 4 5 此时
x5xk 4 3.564237587 3.391995168 3.354124827 3.348333384 3.347529903 0.435762413 0.172242419 0.037870341 0.005791443 0.000803481 已满足误差要求，即
x*?x5?3.347529903
（3）由于?'(x*)?0.136323129?0，故根据定理7 .4知方法是线性收敛的，并且有
limek?1ek??'(x*)k??。
2例7-4 对于迭代函数?(x)?x?C(x?2)，试讨论： （1）当C为何值时，
xk?1??(xk)(k?0,1,2,...)产生的序列
?xk?收敛于2；
（2）C为何值时收敛最快？
C??12，
?122，计算?(x)的不动点2，要求
（3）分别取
|xk?1?xk|?102?5
解： （1）?(x)?x?C(x?2)，?'(x)?1?2Cx，根据定理7.3，当
?12?C?0|?'(2)|?|1?22C|?1，亦即
时迭代收敛。
C??122时迭代至少是二阶收敛的，
（2）由定理7.4知，当?'(2)?1?22C?0，即收敛最快。
C?12,?1（3）分别取
22，并取x0?1.2，迭代计算结果如表7-4所示。
表7-4 k xk(C??12 )k xk(C??122 )0 1 6 12 13 此时都达到
1.2 1.48 1.413369586 1.414209303 1.414215327 0 1 2 3 4 1.2 1.397989899 1.414120505 1.414213559 1.414213562 |xk?1?xk|?10?5.事实上2?1.414213562...,
例7-5 给定初值
x0?0,2a以及迭代公式
xk?1?xk(2?axk),k?0,1,2,...,常数a?0
证明: (1)该迭代函数是二阶收敛的;(2)该迭代产生的序列
|1?ax0|?1?xk?收敛的充要条件是
．
?()?a111解: (1) 显然,迭代函数为?(x)?x(2?ax),且
1a,即a是?(x)的不动点.又
?'()?0?''()??2a?0?'(x)?2(1?ax),?''(x)??2a,所以aa,，由定理7.4知，
limek?1ek21迭代是二阶收敛的，且
k???12?''()??aa1．
（２）因
ek?xk?1a?1a1ark(axk?1)，令
rk?axk?1，则
xk?1?xk(1?rk),ek?
然而
rk?axk?1?axk?1(1?rk?1)?1 故
?(rk?1?1)(1?rk?1)?1??rk?12
rk??r2k?1??rk?2?...??r4k20
ek?1ark??1ar02k
limrk?0k??由此可知
limek?0k??等价于，而k??limrk?0又等价于
|r0|?1，即
|1?ax0|?1．
注 （１）的结论也可以直接用二阶收敛函数的定义去证明．另外，本题迭代式实际上
f(x)?a?1x使用牛顿迭代法而得．
是对
3?(x)?x?x,x?0为?(x)的一个不动点,验证迭代xk?1??(xk)对任意x0?0不例7-6 对
收敛,但改用斯蒂芬森迭代却是收敛的,并说明斯蒂芬森迭代计算?(x)的不动点x?0时的收敛阶.
解 由于?'(x)?1?3x,当x?0时|?'(x)|?1,且有
|xk?1?0|?|?(xk)?0|?|?'(?)(xk?0)|?xx?0,L?1,介于k与0之间,若0,迭代不收敛.
2若改用斯蒂芬森迭代(7 .12),可得 ?'(0)?23,根据定理7.3,斯蒂芬森迭代法收敛.
2xk?1??(xk),?(x)?x?xx?3x?3
42?'(0)??03由于,故用斯蒂芬森迭代计算不动点x?0时,收敛阶p?1.(请读者注意,这一
结论与定理7.5的结论是否矛盾?) 例7-7 当R取适当值时,曲线
y?x2与
y?(x?8)?R222相切,试用迭法求切点横坐标的近
似值,要求不少于四位有效数字,且不必求R. 解
y?x2的导数y'?2x,由y?(x?8)?R确定的函数y的导数满足
222
2yy'?2(x?8)?0,由两曲线相切的条件,可得
2?x?2x?2(x?8)?0
2即 2x?x?8?0
令f(x)?2x?x?8,则f(1)?0,f(2)?0,f(x)?0在(1,2)内有实根.又
f'(x)?6x?1?0,故f(x)?0仅有一个根,构造迭代公式 xk?1??(xk),?(x)?(8?x21332)3,x?(1,2),
则当x?[1,2]时,1??(x)?2.
18?x?311|?'(x)|?|?()|?L?()3?16263
22故迭代收敛.取
x0?1.5,计算结果如表7-5所示.
k 表7-5 k xk |xk?xk?1| xk |xk?xk?1| 0 1 |x3?x*|?1.5 1.481248 0.018752 2 3 1.482671 1.482563 0.001423 0.000108?12?10?3L1?L由于
|x3?x2|?12?10?3,故可取
x*?x3?1.483,即可保证两曲线切点的横
坐标的近似值具有四位有效数字.
例7-8 曲线y?x?0.51x?1与y?2.4x?1.89在点(1.6,1)附近相切,试用牛顿迭代法求切点的横坐标的近似值
xk?132,使
|xk?1?xk|?102?5.
解 两曲线的导数分别为
2y'?3x?0.51和y'?4.8x,两曲线相切,导数相等,故有
3x?4.8x?0.51?0 令
f(x)?3x?4.8x?0.512,则f(1)?0,f(2)?0,故区间[1,2]是f(x)?0的有根区间.又
当x?[1,2]时,f'(x)?6x?4.8?0,因此f(x)?0在[1,2]上有惟一实根x*.对f(x)应用牛顿迭代法,得计算公式
xk?1?xk?3xk?4.8xk?0.516xk?4.82,k?0,1,2,...
x?2由于f''(x)?6?0,故取0迭代计算一定收敛,计算结果如表7-6所示.
表7-6 k xk k xk 0 1 2 继续计算仍得
x6?1.732.0 2.293055556 1.817783592 3 4 5 1.706815287 1.700025611 1.7 ,故x*?1.7.
2注 本题也可令x?0.51x?1?2.4x?1.89,解得切点横坐标满足方程
f(x)?x?2.4x?51x?2.89?0,用有重根时的牛顿迭代法(7.15)式计算,此时m?2.仍
32取
x0?2,经四步可得x*?1.7.
例7-9(牛顿迭代法收敛定理)设f(x)在[a,b]上具有二阶连续导数,且满足条件 (1)f(a)f(b)?0;
(2)在[a,b]上f'(x)?0,f''(x)?0; (3)
x0?[a,b]满足
f(x0)f''(x0)?0.
f(x)?0在[a,b]内的惟一实根x*,并且是平方
则由牛顿迭代法产生的序列收敛的.
?xk?单调收敛于
证明 因f(x)在[a,b]上连续,由条件(1)知,方程f(x)?0在(a,b)内有根x*.又由于条件(2)知f'(x)在[a,b]上恒正或恒负,所以f(x)在[a,b]上严格单调,因而x*是f(x)?0在(a,b)内的惟一实根.
条件(1),(2)共有四种情形:
(1)f(a)?0,f(b)?0,f'(x)?0,f''(x)?0,?x?[a,b]; (2)f(a)?0,f(b)?0,f'(x)?0,f''(x)?0,?x?[a,b]; (3)f(a)?0,f(b)?0,f'(x)?0,f''(x)?0,?x?[a,b];
(4)f(a)?0,f(b)?0,f'(x)?0,f''(x)?0,?x?[a,b]. 仅就(1)进行定理证明,其余三种情况的证明方法是类似的. 由
x0?[a,b],f(x0)f''(x0)?0可知
f(x0)?0x?x*,再由f'(x)?0知f(x)单增且0.又由
牛顿迭代法知
x1?x0?f(x0)f'(x0)?x0 又台劳展开得 其中
?0
12!f(x)?f(x0)?f'(x0)(x?x0)?f''(?0)(x?x0)2
介于x与
x0之间.利用f(x*)?0,得
12*f(x0)?f'(x0)(x*?x0)?x*?x0?x1?f(x0)f'(x0)*f''(?0)(x*?x0)?0(x*?x0)?2*2?1f''(?0)2f'(x0)21f''(?0)2f'(x0)(x*?x0)
x?x0由f'(x)?0,f''(x)?0以及前面证明的1,有
一般地,设
x*?x1?x0
f(xk)?0x*?xk?xk?1,则必有
?xk且
xk?1?xk?f(xk)f'(xk)
同样由台劳公式
12!f(x)?f(xk)?f'(xk)(x?xk)?f''(?k)(x?xk)2
及f(x*)?0,得
f(xk)?f'(xk)(x*?xk)?x*?xk?xk?1?f(xk)f'(xk)*12*f''(?k)(x*?xk)?0(x*?xk)?2*2?1f''(?k)2f'(xk)21f''(?k)2f'(xk)(x*?xk)?xk?1?xk
?llimxkxk??x*根据归纳法原理知,数列单调下降有下界,因此有极限.设k??.对迭代式
xk?1?xk?f(xk)f'(xk)两端取k??的极限,并利用f(x).f'(x)的连续性知f(l)?0,即
l?x*.
limxk?1?x*(xk?x*)2由上述证明知,有关系式
k???1f''(x*)2f'(x*),即对于单根,牛顿迭代法是平方收敛的.
f(x*)?0,f'(x*)?0,f''(x*)?0,?xk?例7-10 设函数f(x)具有二阶连续导数,是由牛顿
迭代法产生的序列,证明
limxk?1?xk(xk?xk?1)2
k????f''(x*)2f'(x*)
解 牛顿迭代法为
xk?1?xk?f(xk)f'(xk),k?0,1,2,...
xk?1?xk??f(xk)f'(xk)故
2xk?1?xkf(xk)?f'(xk?1)??????2(xk?xk?1)f'(xk)?f(xk?1)??f(xk)?f(x*)[f(xk?1)?f(x*)]f'(?k)[f'(xk?1)]222[f'(xk?1)]f'(xk)(xk?x*)2?? 其中
?kf'(xk)[f'(?k?1)](xk?1?x*)2
介于
xk与x*之间,
xk?1?xk?k?1介于
xk?1与x*之间,根据式(7.14)得
22lim?k??(xk?xk?1)2??limf'(?k)[f'(xk?1)]xk?x*2k??f'(xk)[f'(?k?1)](xk?1?x*)?1f''(x*)2f'(x*)
(m?2),?xk?例7-11 设f(x)具有连续的m阶导数,x*是f(x)?0的m重根是由牛顿迭
代法产生的序列,证明
limxk?1?x*xk?x*xk?1?xkxk?xk?1?1?1m1m;(1)
k??
;lim(2)
k???1?
limxk?1?xkxk?1?2xk?xk?1(3)
k???m.
证明 (1)因x*是f(x)?0的m重根,则f(x)可以表示成
x) f(x)?(x?x*)h(x),h(?
m所以
f'(x)?mx(?xm?1*)hx(?)x?(xh*x)mh*x)?'()
(x?x*)m?1m[hx(?)x?(x'()]
xk?1?xk?f(xk)f'(xk)由牛顿迭代法得
(xk?x*)hx(kmxk?1?x*?xk?x*?)(xk?x*)m?1[mh(xk)?(xk?x*)h'(xk)]???h(xk)(xk?x*)?1??mh(x)?(x?x*)h'(x)kkk??
故
limxk?1?x*xk?x*?1?1m (2)
xk?1?xkxk?xk?1?mk??
f(xk)f'(xk?1)f(xk?1)f'(xk)m?m?1(xk?x*)h(xk)(xk?1?x*)[mh(xk?1)?(xk?1?x*)h'(xk?1)]m?1(xk?1?x*)h(xk?1)(xk?x*)[mh(xk)?(xk?x*)h'(xk)]??xk?x*??h(xk)?mh(xk?1)?(xk?1?x*)h'(xk?1)????xk?1?x*??h(xk?1)?mh(xk)?(xk?x*)h'(xk)?
利用h(x*)?0及(1)的结论得
limxk?1?xkxk?xk?1?1?1m;
k??
f(x)f'(x)的导函数
?(x)?x?(3)先证明牛顿迭代函数
?'(x)?1?1m(x?x*)
因x*是f(x)的m重零点,则由假设,f(x)具有m阶连续导数,得
f(x*)?f且
f(x)?f'(x)?f''(x)?1x'(?*)?.f..(m?1)x?(*f)m(0x,?)( *)0m!f1(m)(?1)(x?x*)f(m)m(m?1)!1(m?2)!(?2)(x?x*)m?1f(m)(?3)(x?x*)m?2 其中
?1,?2,?3
介于x与x*之间,故有
f(x)f''(x)[f'(x)]2?'(x*)?lim 而
n?x*?limm?1fm(m)(?1)f(m)(m)(?3)2n?x*[f(?2)]?1?1m
xk?1?xkxk?1?2xk?xk?1?xk?1?xk(xk?1?xk)?(xk?xk?1)?11??'(?k)?xk?1?xk
所以
xk?1?xk??'(?k)(xk?1?xk)xk?1?xkxk?1?2xk?xk?11
1limk???lim11??'(?k)k???1?(1?1m?m)
?'(x*)?1?
注 结论(1)和
m都表明牛顿迭代法求重根时仅为线性收敛.结论(3)可以用来计
算重根数m.
例7-12 考虑下列修正的牛顿公式(单点斯蒂芬森方法)
xk?1?xk?f(xk)f(xk?f(xk))?f(xk)2
设f(x)有二阶连续导数,f(x*)?0,f'(x*)?0,试证明该方法是二阶收敛的. 证明 将
f(xk?f(xk))f(kx))?在
xk处作台劳展开,得
1f'k(x)fk(x?)2
f(xk?f(kx?)?f''(f)k
2x()其中?介于
xk与
xk?f(xk)之间,于是
f(xk?f(xk))?f(xk)?f'(xk)f(xk)?xk?1?x*?xk?x*?f(xk)f'(xk)?1212f''(?)f(xk)2
由于x*是f(x)?0的单根,故
f''(?)f(xk)
f(x)?(x?x*)h(x),h(x*)?0 所以
f'(xk)?h(xk)?(xk?x*)h'(xk)xk?1?x*?xk?x*?(xk?x*)h(xk)h(xk)?(xk?x*)h'(xk)?12f''(?)f(xk)?????h(xk)(xk?x*)?1???1?h(xk)?(xk?x*)h'(xk)?f''(?)f(xk)??2?1??h'(xk)?f''(?)h(xk)??2??1??h(xk)?(xk?x*)h'(xk)?f''(?)h(xk)??2??
(xk?x*)2
故
h'(x*)??1h(x*)f''(x*)2h(x*)limxk?1?x*(xk?x*)2
k??
即迭代法是二阶收敛的.
四、学习效果测试题及答案
1、证明方程e?10x?2?0在(0,1)内有一个实根x*,并用二分法求这个根.若要求
x|xn?x*|?10?6,需二分区间[0,1]多少次?
?3(答案:当
|xn?x*|?10时
x*?x9?0.090820313对分次数k?1?20.)
2xx??(xk)x?[a,b]2、对方程3x?e?0,确定[a,b]及?(x),使k?1对任意0均收敛,并求出方
程的各个根,误差不超过10. (答
?4
[a,b]?[?1,0],?(x)??13xe2,x*??0.458962267案:(1)
[a,b]?[1,0],?(x)?13x2;(2)
e,x*?0.910007572;(3)
2[a,b]?[3,4],?(x)?ln(3x),x*?3.733079028)
3、建立一个迭代公式计算2?(答案:
xk?1?2?2?...,分析迭代的收敛性,取x0?0,计算x6.
2?xk,k?0,1,2,...,x6?1.999397637.)
4、试分别采用
?1(x)?2?lnx|和
?2(x)?e|?10?8x?2的斯蒂芬森迭代法求方程x?lnx?2在区间
xk?xk?1xk(2,??)内的根x*,要求
.
和
x5?3.146193262(答案:取
x0?3,其解分别为
42x4?3.146193220.)
5、由方程f(x)?x?4x?4?0求二重根x*?|x?xk|?10(7.15),(7.16)计算x*,要求k?1?82,试用牛顿法(7.13),有重根时的牛顿法
.
(答案:三种方法均取
x0?1.5,分别得
)
?6x24?1.414213568,x3?1.414213562,x3?1.414213562.32f(x)?x?2x?10x?20?0的根,要求|xk?1?xk|?10Leonardo6、用弦切法求方程
.
(答案:取
x0?1,x2?2,用式(7.17)得
3x5?1.368808108x0?2.)
|xk?1?xk|?10?67、用抛物线法求解方程x?3x?1?0在(答案:取
附近的根,要求
)
.
x0?1,x2?2,x3?2.5,x*?x6?1.879385242.xx8、试构造一个求方程e?x?2根的收敛的迭代格式,要求说明收敛理由,并求根的近似值k,|xk?xk?1|?12?10?3使.
xk?1??(xk)?ln(2?xk)(答案:有根区间[0,1],不动点迭代式
x0?0.5,x*?x14?0.442671724,取
x*?x3?0.442854401..另外,也可用牛顿迭代法求解得)
9、试确定常数p,q,r,使迭代公式
a25xk?1?pxk?q
xk
3产生的序列收敛到a,并使其收敛阶尽可能高.
p?q?59,r??139,且?'''(a)?0,此时迭代法三阶收敛.)
(答案:利用定理7.4可得
10、?(x)?x?p(x)f(x)?q(x)f(x),试确定函数p(x)和q(x),使求解f(x)?0且以?(x)为迭代函数的迭代法至少三阶收敛.
p(x)?1f'(x),q(x)?1f''(x)32(答案:利用定理(7.4)可得 五、课后习题全解
2[f'(x)].)
1、用二分法求方程x?x?1?0的正根,要求误差小于0.05.
解 设f(x)?x?x?1,f(1)??1?0,f(2)?1?0,故[1,2]为f(x)的有根区间.又
0?x?12时,f(x)单增,当
x?12时f(x)单增.而
22f'(x)?2x?1,故当
15f()??,f(0)??124,由单调性知f(x)?0的惟一正根x*?(1,2).根据二分法的误差估
1?0.05计式(7.2)知要求误差小于0.05,只需2k?1,解得k?1?5.322,故至少应二分6次.具体
计算结果见表7-7.
表7-7 k ak bk xk f(xk)的符号 0 1 2 3 4 5 - 即
1 1.5 1.5 1.5 1.5625 1.59375 2 2 1.75 1.625 1.625 1.625 1.5 1.75 1.625 1.5625 1.59375 1.609375 - + + - - - x*?x5?1.609375.
32x?1.52、为求x?x?1?0在0附近的一个根,设将方程改写成下列等价形式,并建立相应
的迭代公式:
x?1?1x,迭代公式
2xk?1?1?1xk2(1);
1232xk?1?(1?xk)3x?1?x(2),迭代公式;
x?21x?1,迭代公式
xk?1?1xk?1(3). 试分析每种迭代公式的收敛性,并选取一种公式求出具有四位有效数字的近似根. 解 取
x0?1.5的邻域[1.3,1.6]来考察.
?(x)?1?1x2(1)当x?[1.3,1.6]时,
xk?1?1?1xk2?[1.3,1.6],|?'(x)|?|?2x3|?21.33?L?1,故迭代公式
在[1.3,1.6]上整体收敛.
(2)当x?[1.3,1.6]时
?(x)?(1?x)|?'(x)|?23121/3?[1.3,1.6]2|x(1?x)32|?231.62?L?0.522?1 故
xk?1?(1?xk)32(1?1.3)32
在[1.3,1.6]上整体收敛.
?12(x?1)3/2?(x)?1x?1,|?'(x)|?||?12(1.6?1)?1xk?1?1xk?1(3)故发散.
由于(2)的L叫小,故取(2)中迭代式计算.要求结果具有四位有效数字,只需 即
取
x0?1.5|xk?x*|?L1?L|xk?xk?1|?12?10?3
?3|xk?xk?1|?1?LL?12?10?3?0.5?10
计算结果见表7-8.
x kx k 表7-8 k k 1 2 3
1.481248034 1.472705730 1.468817314 4 5 6 1.467047973 1.466243010 1.465876820
由于
|x6?x5|?12?10?3,故可取
x*?x6?1.466.
3、比较求e?10x?2?0的根到三位小数所需的计算量: (1)在区间[0,1]内用二分法;
xk?1?2?e10xkx(2)用迭代法,取初值
x0?0.
解 (1)因x*?[0,1],f(0)?0,f(1)?0,故0?x*?1,用二分法计算结果见表7-9. 表7-9 k ak bk xk f(xk)的符号1 2k?1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 |x14?x*|?0 0 0 0 0.0625 0.0625 0.0778125 0.0859375 0.08984375 0.08984375 0.08984375 0.090332031 0.090332031 0.090454101 0.090515136 1 0.5 0.25 0.125 0.125 0.09375 0.09375 0.09375 0.09375 0.091796875 0.090820312 0.090820312 0.090576171 0.090576171 0.090576171 0.5 0.25 0.125 0.0625 0.09375 0.078125 0.0859375 0.08984375 0.091796875 0.090820312 0.090332031 0.090576171 0.090454101 0.090515136 0.090545653 + + + - + - - - + + - + - - + 0.5 0.25 0.125 0.0625 0.03125 0.015625 0.0078125 0.00390625 0.001953125 0.000976562 0.000488281 0.00024414 0.00012207 0.000061035 0.000030517 1215?0.000030517?12此时
?10,x*?x14?4具有三位有效数字.
(2)当x?[0,0.5]时,
xk?1?110(2?ek)x?(x)?[0,0.5],|?'(x)|?110|?e|?L?0.825x,故迭代试
在[0,0.5]上整体收敛.取
x0?0,迭代计算结果如表7-10所示.
表7-10 k 1 2
0.1 0.089482908 xkk 4 5 xk 0.090512616 0.090526468
3
|x6?x*|?L1?L0.090639135 6 0.090524951 此时
|x6?x5|?0.00000720?12?10?4,故
x*?x6精确到三位小数.
0???2M4、给定函数f(x),设对一切x,f'(x)存在且0?m?f'(x)?M,证明对于范围内的任意定数?,迭代过程
xk?1?xk??f(xk)均收敛于f(x)?0的根x*.
证明 由于f'(x)?0,f(x)为单增函数,故方程f(x)?0的根x*是惟一的(假定方程有根
x*).迭代函数?(x)?x??f(x),|?'(x)|?|1??f'(x)|,.由0?m?f'(x)?M及
0???20??m??f'(x)??M?2,?1?1??M?M得,1??f'(x)?1??m?1,故
|?'(x)|?L?max{|1??m|,|1??M|}?1,由此可得
|xk?x*|?L|xk?1?x*|?...?L|x0?x*|?0(k??)k
即k??limk?x*.
?55、用斯蒂芬森迭代法计算第2题中(2)的近似根,精确到10.
1解 记第2题中(2)的迭代函数
?2(x)?(1?x)22?3(x)?1x?1,利用迭
,(3)的迭代函数为
代式(7.11),计算结果见表7-11. 表7-11 k 0 1 2 3
加速?（x）的结果xk2 k 0 1 2 3 4 加速?（x）的结果xk3 1.5 1.465558485 1.465571233 1.465571232 1.5 1.467342286 1.465576085 1.465571232 1.465571232
6、设?(x)?x?p(x)f(x)?q(x)f(x),试确定函数p(x)和q(x),使求解f(x)?0且以?(x)为迭代函数的迭代法至少三阶收敛.
2解 要求
xk?1??(xk)三阶收敛到f(x)?0的根x*,根据定理7.4,应有
?(x*)?x*,?'(x*)?0,?''(x*)?0.于是由
x*?x*?p(x*)f(x*?)q(x（*)f）x=*x*2?'(x*?)?1px(*f)x'(?*)0(f*)x?''(q*)x2f(x*?)[2 得
?''x(*?)?p2x'(f*)x'?(*p)x
'(*)]0p(x*)?1f'(x*),q(x*)?1f''(x*)3 故取
p(x)?2[f'(x*)]
1f'(x),q(x)?1f''(x)3
2[f'(x)]
即迭代至少三阶收敛.
3f(x)?x?3x?1?0在x0?2附近的根.根的准确值x*?1.87938524...,7、用下列方法求
要求计算结果准确到四位有效数字.
(1)用牛顿法; (2)用弦截法,取
x0?2,x1?1.9;
.
2(3)用抛物线法,取
x0?1,x1?3,x2?22解 f(1)?0,f(2)?0,f(x)?3x?3?3(x?1)?0,f''(x)?6x?0,对?x?[1,2]. (1)取
x0?2,用牛顿迭代法
xk?3xk?13xk?323xk?1?xk??2xk?13(xk?1)23
12?10?3计算得
x1?1.888888889,x2?1.879451567,|x2?x*|?,故
x*?x2?1.879451567.
(2)取
x2?2,x1?1.9,利用弦截法
xk?1?xk?(xk?xk?1)f(xk)f(xk)?f(xk?1)
12?10?3得,
x2?1.981093936,x3?1.880840630,x4?1.879489903,|x4?x*|?,故取
x*?x4?1.879489903.
(3)
x0?1,x1?3,x2?2.抛物线法的迭代式为
2f(xk)xk?1?xk?w?sign(w)w?4f(xk)f[xk,xk?1,xk?2]2w?f[xk,xk?1]?f[xk,xk?1,xk?2](xk?xk?1)
已达四位有效数字.
迭代结果为:
x3?1.953967549,x4?1.87801539,x5?1.8793868668、分别用二分法和牛顿迭代法求x?tanx?0的最小正根.
tanx?x?13x?...?3x2k?1解 显然x*?0满足x?tanx?0.另外当|x|较小时,
x?(0,2k?1?...,故
?当
2时,tanx?x,因此,方程x?tanx?0的最小正根应在2)(?3?,2)内.
f(x)?x?tanx,x?(?3?2,2)记
,容易算得f(4)?2.842...?0,f(4.6)??4.26...?0,因此
[4,4.6]是f(x)?0的有限区间. 对于二分法,计算结果见表7-12. 表7-12 k 0 1 2 3 4 5 6 7 8 9
ak bk xk f(xk)的符号 4.0 4.3 4.45 4.45 4.4875 4.4875 4.4875 4.4921875 4.4921875 4.493359375 4.6 4.6 4.6 4.525 4.525 4.50625 4.496875 4.496875 4.49453125 4.49453125 4.3 4.45 4.525 4.4875 4.50625 4.496875 4.4921875 4.49453125 4.493359375 4.493445313 + + - + - - + - + -
此时
|x9?x*|?1210?11024?10?3.
f'(x)??(tanx)?0,f''(x)??2tanx21cosx2?0若用牛顿迭代法求解,由于迭代计算结果如表7-13所示. 表7-13 ,故取
x0?4.6,
k 1 2 3 xk k 4 5 6 4.545732122 4.506145588 4.49417163 4.493412197 4.493409458 4.493409458 xk所以x?tanx?0的最小正根为x*?4.493409458. 9、研究求a的牛顿公式
xk?1?12(xk?axk),x0?0
证明对一切且序列是递减的.
xk?12(xk?1?axk?1)证法一 用数列的办法,因
xk?12(xk?1?axk?1)?2x0?0由知
xk?0,且
a,k?1,2,3,....又由
a?1,?k?1xk?1 故
xk?1?xkxk?12?2a
a.根据单调原理知,?xk?有极限.易证起极限为a.
a.对f(x)?x?,即kk?1单减有下界2?证法二 设f(x)?x?a(a?0).易知f(x)?0在[0,??)内有惟一实根x*?应用牛顿迭代法,得
xk?1?xk?f(xk)f'(xk)x0?a?12(xk??axk),k?0,1,2,...
利用例7-9的结论知,当时,
limx?a,且k??ka?x?时,kk?0单减有下界.当
x0?(0,a)
x1?12(x0??ax0)?12[x0?ax0]?2a?a
x1
?x?此时,从起,kk?1单减有下界10、对于f(x)?0的牛顿公式
Rk?a,且极限为a. f(xk)f'(xk)xk?1?xk?,证明
xk?xk?1(xk?1?xk?2)2
?f''(x*)
收敛到
2f'(x*),这里x*为f(x)?0的根.
证明见例7-10.
11、用牛顿迭代法和求重根的牛顿迭代法(7.15)和(7.16)(书中式(4.13),(4.14))计算方程
f(x)?(sinx?x2)?02?5的一个近似根,准确到10,初始值
x0??2.
f(x)?(sinx?x2)2解
的根x*为2重根,即
x2)(cosx?1)f'(x)?2(sinx?
用牛顿法迭代公式为
(sinxk?xk?1?xk?2(sinx?sinxk?xk?xkx2xk22
)2)(cosx?12?)
x0?2,k?0,1,3,...2cosxk?1
?2,则x1?1.785398,x2?1.844562,...,迭代到
?5令
x20?1.895494,|x*?1.89549|?10.
用求重根的迭代公式(7.15),迭代迭代公式为
sinxk?xk?1?xk?cosxk?xk2,k?0,1,2,...12
x0?
?2,则x1?2.000000,x2?1.900996,x3?1.895512,x4?1.895494,x5?1.895494.
取
四次迭代达到上面
x20的结果.
若用公式(7.16),则有
xk?1?xk?f(xk)f'(xk)[f'(xk)]?f(xk)f''(xk)2
12)xk2)将f(x),f'(x)及
f''(x)?2(cosx?12)?2sinx(sinx?xk2122x)代入上述迭代公式,得
(sinxk?xk?1?xk?(cosxk?122)(cosxk?
x0?)?sinxk(sinxk?
?2,得x1?1.801749,x2?1.889630,x3?1.895474,x4?1.895494,x5?1.895494.
取
结果与公式(7.15)的相同.
33x?a?012、应用牛顿迭代法于方程,导出求立方根a的迭代公式,并讨论其收敛性.
32解 设f(x)?x?a,f'(x)?3x,f''(x)?6x,牛顿迭代公式为
xk?1?xk?xk?a3xk23?2xk?a3xk23,k?0,1,2,...
当x?0,f'(x)?0,f''(x)?0;当x?0时,f'(x)?0,f''(x)?0,,因此,对于a?0,当
x0?3a时
f(x0)f''(x0)?03xk??,根据例7-9的结论知,牛顿序列收敛到3a.当x0?(0,a)时,
x1?3a?2x0?a3x023?3a?(3a?x0)3x022(3a?2x0)?0,x1?3a
x1
3xk??从起,牛顿序列收敛到3a. x?对于a?0,当0x0?(3a,0)a?0时
f(x0)f''(x0)?0,.由牛顿法产生的序列
?xk?单增趋于3a.当
时,
x1?3a?(3a?x0)3x022(3a?2x0)?0,x1?3a 之后迭代也收敛. 当a?0时,迭代式变为
xk?1?xk?xk32 该迭代对任何
x0?R3xk?23xk
均收敛,但收敛速度是线性的.
f(x)?1?ax2?013、应用牛顿法于方程
f(x)?1?ax2,导出求a的迭代公式,并用此公式求115的值.
,f'(x)?2ax3,x?0解 ,所以牛顿迭代公式有
1?xk?1?xk?axk322axk?12xk(3?xka2),k?0,1,2,...
f''(x)?6ax4
?0易知.故取
x0?(0,a)时,迭代收敛.
x?9对于115,取0,迭代计算,得
x1?10.33043478,x2?10.70242553,x3?10.7237414,
x4?10.72380529,x5?10.72380529
故115?10.72380529.
f(x)?1?axn14、应用牛顿法于方程f(x)?x?a?0和并求
nn?0,分别导出求a的迭代公式,
nlima?xk?1k2
k??(na?x) nn?1解 对于f(x)?x?a,f'(x)?nxxk?1?xk?xk?anxkn?1n,因此牛顿迭代法为
axkn?1?1n[(n?1)xk?],k?0,1,2,... 根据定理7.4知
(?(na)?nn?1na2)1n?12nlim(na?xk?1)(na?xk)
k????a
f(x)?1?axn,f'(x)?naxn?1对于
xk?1?xk?,牛顿法公式为
xkanf(xk)f'(xk)?xkn[(n?1)?],k?0,1,2,...
根据定理7.4知
(?(na)??nnn?1na?)1n?12nlima?xk?12
15、证明迭代公式
k??(na?xk)a
xk?1?xk(xk?3a)3xk?a22
a,求
x是计算a的三阶方法.假定初值0充分靠近根x*?lima?xk?1(a?xk)2
k??2
xk?1??(xk)?(x)?x(x?3a)3x?a2证明 记由?(x)的定义,有
,则迭代式为
且?(a)?a. (3x?a)?(x)?x(x?3a) 对上式两端连续求导三次,得
6x?(x)?(3x?a)?'(x)?3x?3a6?(x)?12x?'(x)?(3x?a)?''(x)?6x22222 代x?18?'(x)?18x?''(x)?(3x?a)?'''(x)?62
a依次入上三式,并利用?(a)?a,得
?'(a)?0,?''(a)?0,?'''(a)?32a?0
所以由定理7.4知,迭代公式是求a的三阶方法且
lima?xk?1(a?xk)2
k???31??3!2a4a1
16、用牛顿法解方程组
22??x?y?4?22x?y?1??
取(x(0),y(0)T)?(1.6,1.2).
2222T解 记
f1(x,y)?x?y?4,f2(x,y)?x?y?1,则
?4x??1??4y??1?2xF'(x,y)???2x2y??1,[F'(x,y)]??2y? 牛顿迭代法为
?1?4x???1??4y
?f1(x(k),y(k))??x(k?1)??x(k)?(k)(k)?1?(k?1)???(k)??[F'(x,y)]?(k)(k)?f(x,y)?yy????2 ?
代入初值(x
(0),y(0)T)?(1.6,1.2),迭代计算,得
T0?0x0?x(1)??1.581250??,?(1????)1.2250000?0y0y????8?3x0?x(3)??1.581138??,?(3????)1.2247447y1y??8?? ?(2)???(?2)???(4)1.581?13834?1.224?7448981.581?38830?1.22444871?7
???(?4)???