数值分析课件-(第7章).ppt

1、机动上页下页首页结束工科研究生公共课程数学系列 内容提要内容提要7.1 方程求根与二分法方程求根与二分法7.2 迭代法及其收敛性迭代法及其收敛性7.3 牛顿法牛顿法7.4 弦截法弦截法机动上页下页首页结束工科研究生公共课程数学系列 7.1 方程求根与方程求根与二分法二分法一、引言一、引言.b,aC)x(f,Rx 0)x(f 的求根问题，其中的求根问题，其中考虑单变量非线性方程考虑单变量非线性方程非线性方程的分类非线性方程的分类.0ex :.2.01xx :).n,1,0i(Ra,0a,0axaxaxa .1x3i0n1n1n1n0 如如超越方程超越方程如如其中其中代数方程代数方程机动上页下页首

2、页结束工科研究生公共课程数学系列 32 11.138.841.770 xxx例如求方程的有根区间搜搜索索法法求求有有根根区区间间。则则可可用用若若。此此时时重重零零点点。的的为为则则称称为为正正整整数数其其中中可可以以分分解解为为如如果果,0)b(f)a(f,b,aC)x(f0*)x(f,0*)x(f*)x(f*)x(f m)x(f*x .m ,|*)x(g|0),x(g*)xx()x(f )x(f)m()1m(m 由此可知方程的有根区间为由此可知方程的有根区间为1,2 3,4 5,61,2 3,4 5,6求根问题的三个方面：存在性，分布，精确化。求根问题的三个方面：存在性，分布，精确化。x

3、0 1 2 3 4 5 6f(x)的符号 +机动上页下页首页结束工科研究生公共课程数学系列 0000101110()()0,()/2.()(),.()(),;,f af bxabf xf xxf af xax bbaa bx设取假如是的零点，那么输出停止 假若不然，若与同号，则否则。11110111(1),(2)x,x=,x=,22-(3)-,22kkkkkkkka ba bababbab ab ab ababa二分过程中有三个量在变：（区间、近似根、区间长度）二、二分法0 xyX*x0aby=f(x)a1b1机动上页下页首页结束工科研究生公共课程数学系列 3()101.0,1.5-2.f x

4、xx 求在内的一个实根，准确到小数点后位例例7 17 1 1k|*|()/2()/2()/2*().xxkkkkkkkxxbab axabxkk收敛性分析：因故有,因此，只要二分的足够多次（即 充分大），便有，这里 为预定的精度。机动上页下页首页结束工科研究生公共课程数学系列 k ak bk xkf(xk)符号0123456 1.0 1.25 1.31251.3203 1.5 1.3751.34381.3281 1.25 1.375 1.3125 1.3438 1.3281 1.3203 1.3242 +005.0 xx6k66*度度），便便能能达达到到预预定定的的精精次次（只只要要二二分分机

5、动上页下页首页结束工科研究生公共课程数学系列。的的一一个个为为函函数数称称化化为为等等价价形形式式将将非非线线性性方方程程不不动动点点)x(*x;)*x(*x0*)x(f )x(x 0)x(f 二分法的优点是算法简单，且总是收敛的，缺点是二分法的优点是算法简单，且总是收敛的，缺点是收收敛太慢敛太慢,故一般不单独将其用于求根，只用其为根求故一般不单独将其用于求根，只用其为根求得一个较好的近似值。得一个较好的近似值。7.2 迭代法迭代法一、不动点迭代与不动点迭代法一、不动点迭代与不动点迭代法机动上页下页首页结束工科研究生公共课程数学系列 0101,()(),0,1,2,.2.2 ()kkxxxxx

6、kx给定初始近似值可以得到如此反复，构造迭代公式（）称为迭代函数。上述迭代法是一种逐次逼近法，其基本思想是将隐式方上述迭代法是一种逐次逼近法，其基本思想是将隐式方程归结为一组显示的计算公式，就是说，迭代过程实质上是程归结为一组显示的计算公式，就是说，迭代过程实质上是一个逐步显示的过程。一个逐步显示的过程。0,2.2 lim()()2.2kkkxa bxxxxxx如果对任何，由式（）得到的序列有极限则称迭代方程收敛，且为的不动点，称式（）为不动点迭代法。机动上页下页首页结束工科研究生公共课程数学系列 3 101.5-*xxx求在附近的根。例例7 7 2 2k xkkxkkxk0121.51.35

7、7211.3308634 51.325881.32494 1.324766781.324731.324721.32472),2,1,0k(1xx1xx13k1k3 据据此此建建立立迭迭代代公公式式式式）将将方方程程改改写写成成下下列列形形解解：（即即为为所所求求的的根根。实实际际上上已已满满足足方方程程完完全全相相同同，可可以以认认为为与与结结果果787xxx机动上页下页首页结束工科研究生公共课程数学系列 331012(2)xx-1 11.5,2.375,12.39,.kkxxxxx另一种等价形式建立迭代公式迭代初值仍取则有 继续迭代下去已经没有必要，因为结果显然会越来越大，继续迭代下去已经没

8、有必要，因为结果显然会越来越大，不可能趋于某个极限。这种不收敛的迭代过程称作是发散的。不可能趋于某个极限。这种不收敛的迭代过程称作是发散的。一个发散的迭代过程，纵使进行了千百次迭代，其结果也毫一个发散的迭代过程，纵使进行了千百次迭代，其结果也毫无价值。因此，迭代格式形式不同，有的收敛，有的发散，只无价值。因此，迭代格式形式不同，有的收敛，有的发散，只有收敛的迭代过程才有意义，为此要研究不动点的存在性及迭有收敛的迭代过程才有意义，为此要研究不动点的存在性及迭代法的收敛性。代法的收敛性。即即为为所所求求的的根根。实实际际上上已已满满足足方方程程完完全全相相同同，可可以以认认为为与与结结果果787x

9、xx机动上页下页首页结束工科研究生公共课程数学系列 的的不不动动点点。即即为为即即使使在在由由连连续续函函数数性性质质可可知知存存且且满满足足显显然然定定义义函函数数因因上上存存在在不不动动点点。在在，显显然然或或若若性性。证证明明：先先证证不不动动点点存存在在)x(x),x(x0,)x(f)b,a(x0b)b()b(f,0a)a()a(f,b,aC)x(fx)x()x(f,b)x(ab,a)x(b)b(a)a(二、不动点的存在性与迭代法的收敛性二、不动点的存在性与迭代法的收敛性.*xb,a)x(2.4|;yx|L|)y()x(|,b,ay,x ,1L0 (2),b,a)x(,b,ax (1)

10、,b,aC)x(上上存存在在唯唯一一的的不不动动点点在在那那么么）（都都有有使使得得常常数数都都有有并并且且设设迭迭代代函函数数 定定理理1 1机动上页下页首页结束工科研究生公共课程数学系列 代代替替。可可用用它它表表明明定定理理中中的的条条件件有有则则由由中中值值定定理理可可知知对对有有且且对对任任意意，在在使使用用时时如如果果中中的的条条件件和和定定理理对对定定理理2.7)(2)b,a(,y-xL)yx)()y()x(b,ay,x2.7)(1L)x(b,axb,aC)x(221010 。的的不不动动点点只只能能是是唯唯一一的的引引出出矛矛盾盾。故故得得则则由由的的不不动动点点，都都是是及及

11、再再证证唯唯一一性性。设设)x(xxxxL)x()x(xx2.4)x(b,axx2121121122 机动上页下页首页结束工科研究生公共课程数学系列 2/331333321-(x)x1(x)(x1),31 11,2(x)()1,3 412(x)3211(x)x1(x)3x1 2(x)1在例7 2中，当时，在区间中，又因故定理 中条件 成立。所以迭代法收敛。而当时，在区间，中不满足定理条件。(2.5)|(2.2).|1|*,)(,1010 xxLLxxxxbaxkk的的不不动动点点均均收收敛敛于于迭迭代代序序列列对对任任意意初初值值的的条条件件下下在在定定理理定定理理2 2机动上页下页首页结束工

12、科研究生公共课程数学系列 具具有有足足够够精精度度。足足够够小小即即可可保保证证近近似似值值次次计计算算结结果果的的偏偏差差由由此此可可见见，只只要要相相邻邻两两将将其其化化为为而而不不便便于于实实际际应应用用。可可由由于于含含有有信信息息但但它它次次数数原原则则上上可可用用于于确确定定迭迭代代误误差差估估计计式式kkkkkkxxxxxLxx|.|1|*111|L,(2.5).|11|*|,|1|*,*,0)(;1|)(|,10,)(,)(10101kkkkkxxLxxxxLLxxxbaxxbaxfLxbaxLbaxbaxbaCx|4)|3)(2.2)2)1)(2)(1),均收敛于均收敛于迭代

13、序列迭代序列对任意初值对任意初值上有唯一的根上有唯一的根在在方程方程那么那么都有都有使得使得都有都有并且并且如果迭代函数如果迭代函数推论推论机动上页下页首页结束工科研究生公共课程数学系列 320122322312 x-x-10 x1.5 11 (1)7-3 1,1;(2)1,111(3),11 kkkkkkxxxxxxxxxxxx 为求在附近的一个根，设奖方程改写成下列等价形式，并建立相应的迭代公式：迭代公式迭代公式迭代公式试分析每种迭代公式的收敛性，并选取一种公式求出具有四位有效数例字的近似根。上上整整体体收收敛敛。在在故故迭迭代代式式，时时当当来来考考察察，的的邻邻域域取取解解6.1,3.

14、1 1113.1226.1,3.1 11)(6.1,3.1 5.1213320kkxxLxxxxx (x)(1)1.61.3 :机动上页下页首页结束工科研究生公共课程数学系列 3222/322/32313/21(2)1.3,1.6(x)1x1.3,1.6221.6(x)0.52213(1)3(1 1.3)1 1.3,1.6111(3)(x),()1,2(1)2(1.6 1)11 1(2)L(2)kkkkxxLxxxxxxxx当时故在上整体收敛。故发散。由于的 较小，故取中迭代公式计算。要求结果具*313310,1 101211 100.5 1021.5 kkkkkLxxxxLLxxLx有四位有

15、效数字 因，故只需取计算结果见 下表机动上页下页首页结束工科研究生公共课程数学系列 k xk k xk 1 2 31.4842480341.4727057301.468817314 4 5 6 1.4670479731.4662430101.465876820.1x05.取取初初值值kxxk 10 e10 x-20(1)0 1(2)x(2-e)/10,x07 4-.比较求的根到三位小数所需的计算量：在区间，内用二分法；用迭代法取初值例3656110,1.4662xxxx由于故可取机动上页下页首页结束工科研究生公共课程数学系列 迭迭代代计计算算结结果果如如下下上上整整体体收收敛敛。取取在在时时，

16、当当具具有有三三位位有有效效数数字字。用用二二分分法法计计算算，此此时时故故因因解解：,0 x0.5,0)e2(101)x(,5.0,0)x(0.5,0 x)2(xx,1021000030517.021xx,1x0,0)1(f,0)0(f,1,0 x)1(0 x14*41514k k xk k xk 1 2 30.10.0894829080.090639135 4 5 6 0.090512616 0.090526468 0.090524951精精确确到到三三位位小小数数。故故此此时时64-566xx,102100000720.0 xxL1Lxx 机动上页下页首页结束工科研究生公共课程数学系列.

17、,:.,均均收收敛敛对对于于任任意意初初值值迭迭代代过过程程于于是是依依据据定定理理可可以以断断定定是是因因为为这这总总有有对对于于任任意意此此外外成成立立于于任任意意使使对对的的某某个个邻邻域域存存在在由由连连续续函函数数性性质质证证明明是是局局部部收收敛敛的的则则迭迭代代法法且且的的某某邻邻域域内内有有连连续续在在的的不不动动点点为为迭迭代代函函数数设设RxxxxxxxLxxxxRxRxLxRxxxRxxxxxxkk01)()()()()(.1)(*:*)2.2(,1|*)(|*)(,)(*定定理理3 3.*xb,axk局局部部收收敛敛性性附附近近考考察察收收敛敛性性，称称为为点点。应应用

18、用上上经经常常只只在在不不动动不不容容易易由由定定理理作作出出判判断断局局收收敛敛性性；上上的的收收敛敛性性通通常常称称为为全全在在迭迭代代序序列列三、局部收敛性与收敛阶三、局部收敛性与收敛阶局局部部收收敛敛。法法则则称称迭迭代代且且收收敛敛到到产产生生的的序序列列迭迭代代对对任任意意的的某某个个邻邻域域如如果果存存在在有有不不动动点点设设)2.2(*,)2.2(,:*,0(x)xRxRxxxRxxk定定义义1 1机动上页下页首页结束工科研究生公共课程数学系列.0*)x()x31(21)x()x3x(21x4 ;134.0231*)x(2x1)x()3x(41xx3;1*)x(x3)x(x3x

19、2;1132*)x(1x2)x(3xxx12kk1k2kk1k2k1kk2k1k ，）（，）（，）（，）（2 30*3-.xx只用四则运算不用开方求方程的根例例7 57 5kxk迭代法(1)迭代法(2)迭代法(3)迭代法(4)0123?x0 x1 x2 x3?23987?21.521.5?21.751.734751.732631?21.751.7321431.732051?机动上页下页首页结束工科研究生公共课程数学系列.p*x,0*)x(0*)x(*)x(*)x(,p*x)x(x)x()p()1p(阶阶收收敛敛的的附附近近是是那那么么迭迭代代过过程程在在，并并且且连连续续导导数数阶阶邻邻近近具

20、具有有的的根根在在如如果果迭迭代代函函数数 定定理理4 4.2p1p1p .p ,C,Ceelim*,xxe*,x)x(x pk1kkkkk1k时时为为平平方方收收敛敛超超线线性性收收敛敛；当当时时为为当当时时迭迭代代法法为为线线性性收收敛敛；特特别别地地，当当收收敛敛阶阶则则称称迭迭代代过过程程为为是是不不等等于于零零的的常常数数若若误误差差收收敛敛于于设设迭迭代代过过程程 定定义义2 2阶收敛阶收敛该迭代法为该迭代法为知知由定理由定理，而，而的的，而迭代法，而迭代法，故它只是线性收敛的，故它只是线性收敛的的的中，迭代法中，迭代法例例平方收敛平方收敛时时当当迭代法线性收敛迭代法线性收敛时时特

21、别地，当特别地，当 2 4 4.,02,032)(0)()4(0)()3(,0*)(,0*)(;1|*)(|pxxxxxx机动上页下页首页结束工科研究生公共课程数学系列 222222322,(-8)22(-8)0222(-8)0 2-80()2-8(1)0,(2)0,()0(1,2)()610()yxyxyxRyyyxxxxxxf xxxfff xfxxf x 解:的导数由确定的函数 的导数满足，由两曲线相切的条件，可得 即令，则在内有实根。又，故13108 (),()(),(1,2)2kkxxxxx仅有一个根，构造迭代公式2222(-8)7-6.RyxyxRR当 取适当值时，曲线与相切，试用

22、迭代法求切点横坐标的近似值，要求不少于四位有效数字，且不必求例机动上页下页首页结束工科研究生公共课程数学系列 223301,21()2,1 81 1()()()1626 31.5,xxxxLx 则当时，故迭代收敛。取计算结果如下表。k xk|xk-xk-1|0123 1.5 1.481248 1.482671 1.4825630.0187520.0014230.000108333231101.48312LxxxxxxL由于，故可取，即可保证两曲线切点的横坐标的近似值具有四位有效数字。机动上页下页首页结束工科研究生公共课程数学系列(4.1),0)xx)(x(f)x(f 0)x(f ),xx)(x

23、(f)x(f)x(fTaylor,0)x(f,x0)x(f:kkkkkkkk 近近似似表表示示为为于于是是展展开开做做并并假假定定近近似似根根的的设设已已知知方方程程线线性性化化牛牛顿顿迭迭代代公公式式的的推推导导、.4.2 .)x(f)x(fxx ,xkkk1k1k牛牛顿顿迭迭代代法法这这就就是是）（则则有有计计算算公公式式记记 其根为7.3 牛顿法牛顿法一、一、牛顿法及其收敛性牛顿法及其收敛性机动上页下页首页结束工科研究生公共课程数学系列 1()-1 10.5kxxkkkkf xxexexxxx解：牛顿公式为：-取迭代初值，迭代结果列于下表.-1xxe 用牛顿法解方程 例例 7 77 7k

24、xkkxk010.50.57102230.567160.56714机动上页下页首页结束工科研究生公共课程数学系列 22224.()(),()()()()()()()1,()()(*)(*)0(*)(*)0(*)(*),(*)(*)()()0(*)0f xxxfxfxf x fxf x fxxfxfxfxfxfxfxfxxfxfxxf xxx 牛顿迭代公式的几何意义牛顿迭代法的局部收敛性当是的单根时，。此时牛顿法是二阶收敛的。机动上页下页首页结束工科研究生公共课程数学系列 0k 1kk2k 1kk2k 1kk1C0,x(x)2x1xC(x-C)2x1 xC(xC)2xx证明：对式配方，易知20

25、,5-0011CxCx对于给定正数应用牛顿法解二次方程证明迭代公式对于任意初值都是收敛的，并求.例例7 7 8 8二、牛顿法应用举例二、牛顿法应用举例机动上页下页首页结束工科研究生公共课程数学系列 21120000220210,1,kkkkkkkkkkkxCxCxCxCxCxCxCxCxCqxCqxCCqxqkxC 以上两式相除得据此反复递推有记整理上式，得对任意总有故由上式推知，当时即迭代过程恒收敛。机动上页下页首页结束工科研究生公共课程数学系列 的的结结果果。精精度度为为次次便便得得到到。迭迭代代初初值值取取利利用用60kk1k10301x ,115C)xC x(21 x kxk012 3

26、 41010.75000010.723837 10.723805 10.723805机动上页下页首页结束工科研究生公共课程数学系列 1111()()()(1),0,1,2,()1,kkkkkkkkkkkf xxxf xf xxxxxxkf x(2)将牛顿法与下山法结合起来使用。牛顿法的计算结果与前一步的近似值x的适当加权平均作为新的改进值，加入下山因子的迭代公式称为牛顿下山法。选择下山因子时从开始逐次将1()().kkf xf x折半直到满足三、简化牛顿法与牛顿下山法三、简化牛顿法与牛顿下山法1010 ()0,0,1,2,.-()()1()1,0()21,()()()kkkkkkxxCf xC

27、kxx cf xxCfxCfxxCfxf xxxfx(1)构造迭代公式迭代函数（）.若即时在根 附近成立 迭代法局部收敛。当取时，迭代公式 称为简化牛顿法。机动上页下页首页结束工科研究生公共课程数学系列 3000 101.5*.1.50.60.6xxxxxx 如、再求在附近的根：依次用牛顿法，简化牛顿法，牛顿下山法计算结果如下：例例 解解kxkxkxk f(xk)012341.51.347831.325201.324720.617.9发散0.6 -1.3841.140625 -0.6566431.36181 0.18661.32628 0.006671.32472 0.0000086机动上页下

28、页首页结束工科研究生公共课程数学系列 1,()(*)()(),(*)().()()/()*()mkkkkmf xxxg xf xxxmfxxf xfxxf xm重根情形，牛顿法不是平方收敛，(1)可将迭代法改为仍平方收敛(2)可令，若是的 重根，则(*)()(),(*)()(*)()*()0.xxg xxmg xxxg xxx故是的单根四、重根情形四、重根情形机动上页下页首页结束工科研究生公共课程数学系列.(4.14),)x(f)x(f)x(f)x(f)x(fxx )x(kk2kkkk1k仍仍平平方方收收敛敛用用牛牛顿顿法法得得对对 422121212 440*2.21 422 (*)2(2)

29、3 (*).2-9kkkkkkkkkkkkkxxxxxxxxxxxxxxxx用上述三种方法求的二重根：（）牛顿法；（）；（）计算结果如下：7 7 例例解解机动上页下页首页结束工科研究生公共课程数学系列).xx(xx)x(f)x(f)x(f )xx(x,x f )x(f )x(p xx .1)x(f).x(f)x(f,0)x(fk0k0kkk0kk10kkkk ，得得到到线线性性插插值值函函数数为为插插值值节节点点和和以以单单点点弦弦截截法法的的迭迭代代法法。下下面面介介绍绍避避免免求求要要计计算算外外还还每每步步除除计计算算程程用用牛牛顿顿法法求求解解非非线线性性方方kxk(1)(2)(3)0

30、123x0 x1x2x31.51.4583333331.4366071431.4254976191.51.4166666671.4142156861.4142135621.51.4117647061.4142114381.4142135627.4 弦截法弦截法机动上页下页首页结束工科研究生公共课程数学系列).xx()x(f)x(f)x(fxx )x(fxx)x(f)x(f0k0kkk1kk0k0k ，同样得，同样得代替导数代替导数在牛顿法中用差商在牛顿法中用差商.)xx()x(f)x(f)x(fxx 0)x(p0k0kkk1k1称称为为单单点点弦弦截截法法，得得到到令令 .1*)x(0 ,*)

31、x(f1 0)x*x()x(f*)x(f 0)x(f*)x(f*)x(f1*)x(.00 x*x)x(f*)x(f0200 线线性性收收敛敛的的可可以以证证明明单单点点弦弦截截法法是是机动上页下页首页结束工科研究生公共课程数学系列.xx)x(f)x(f)x(f.)xx()x(f)x(f)x(fxx 0)x(p)xx(xx)x(f)x(f)x(f )x(p xx .21kk1kkk1kk1kkkk1k1k1kk1kkk11kk而而得得到到或或在在牛牛顿顿法法中中取取称称为为两两点点弦弦截截法法，得得到到令令，得得到到线线性性插插值值函函数数为为插插值值节节点点和和以以两两点点弦弦截截法法 .线线

32、性性收收敛敛可可以以证证明明两两点点弦弦截截法法超超机动上页下页首页结束工科研究生公共课程数学系列.*x618.1p,x,x ,0)x(fx|*xx:|*x)x(f 625110收收敛敛到到按按阶阶充充分分小小时时，两两点点弦弦截截法法那那么么当当又又初初值值有有连连续续导导数数，且且对对任任意意内内具具有有二二阶阶的的邻邻域域在在根根假假设设 定定理理1111 10.e1 (-)eekkkxxkkkkkxxkkxexxxxxxx 用两点弦截法求方程 的根解：两点弦截法公式为，例例7 7 1 10 0kxkkxk0120.50.60.56532340.567090.56714机动上页下页首页结束工科研究生公共课程数学系列 知识结构图七方程近似求根基本概念（单根、重根、有根区间、不动点、收敛阶）求根方法二分法及其收敛性不动点迭代法及其收敛性定理（不动点迭代法的加速技巧）牛顿迭代法及其收敛性插值型迭代法（多点迭代）弦截法抛物线法机动上页下页首页结束工科研究生公共课程数学系列