Cht7非线性方程求根

1、11 1 方程求根与方程求根与二分法二分法第第7 7章章 非线性方程求根非线性方程求根一、引言一、引言. ,)(,(1.1) 0)( baCxfRxxf的求根问题，其中考虑单变量非线性方程非线性方程的分两类：. 01 : )., 1 , 0(R, 0, 0 , . 1301110 xxniaaaxaxaxainnnn如其中代数方程. 0 : , . 2xex如超越方程2.)(* . ,|*)(|0),(*)()( )(重零点的为则称为正整数其中可以分解为如果mxfxmxgxgxxxfxfm. 0*)(, 0*)(*)(*)( )() 1(xfxfxfxfmm此时, 0)()(,)(bfafba

2、Cxf若 则可用搜索法求有根区间.0 的有根区间求方程xex例1例1 x 1 0 1 2f(x)的符号 + +求根问题的三个方面：存在性，分布，精确化。存在性，分布，精确化。3二、二分法二、二分法二分法简述., ;,)()( .,)()( . 2/ )(, 0)()(0111010000 xbaabbxaxfafxxfxfbaxbfaf否则同号，则与若假若不然，停止那么输出的零点，是假如取设,11kkbababa故 *,2/ )(xbaxkkk(1.3) .2/ )(2/ )(|*|1kkkkababxxba2ba 4.25 . 1 , 0 . 1 01 3位小数点后内的一个实根，准确到在求

3、xx 例2例2k 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 + + + 二分法优、缺点； 用途。52 2 迭代法及其收敛性迭代法及其收敛性一、不动点迭代一、不动点迭代(2.1) ).( 0)(xxxf 化为等价形式将非线性方程.)(*; ) *(*0*)( 不动点不动点的一个为函数称xxxxxf ).(,010 xxx可以得到给定初始近似值 .)(2.2) ., 2 , 1 , 0 ),( 1为迭代函数称式如此反

4、复，构造迭代公xkxxkk6.)2 . 2()(*)(*(2.2)*,lim )2 . 2(,0不动点迭代法不动点迭代法为故称的不动点，是收敛，且则称迭代公式有极限得到的序列由如果对任何初值xxxxxxbaxkkk.几何意义是一种逐次逼近法；隐式化为显式，迭代法：说明说明7迭代法的几何意义 交点的横坐标 *x( )( )yxxg xyg xy=x2x0 x1x8迭代法需解决的三个问题迭代函数的构造由迭代函数产生的解序列的收敛性序列的收敛速度和误差估计9.*5 . 101 3xxx附近的根在求 例3例3 )., 2 , 1 , 0( , 15 . 11310kxxxkk，）解：（kxk01234

5、5671.51.357211.330861.325881.324941.324761.324731.32472. ,39.12,375. 2 , 5 . 1, 1 (2) 21031xxxxxkk10.*,)(2.4 |;| )()(| , , 10 (2) ,)( , (1) , ,)( xbaxyxLyxbayxLbaxbaxbaCx上存在唯一的不动点在那么）（都有使得常数都有并且如果迭代函数定理1定理1二、不动点的存在性与迭代法的收敛性二、不动点的存在性与迭代法的收敛性*,)(2.2) ,1 0 xxbax的不动点均收敛于迭代序列对任意初值的条件下在定理定理2定理2并有误差估计(2.5)

6、 . |1|*| 01xxLLxxkk. |11|*| 1kkkxxLxx还有11. |11|*| 4) |,|1|*| 3) *,(2.2) , 2) *,0)( 1) ; 1| )(|, , 10 (2) ,)( , (1) , ,)( 10101kkkkkxxLxxxxLLxxxbaxxbaxfLxbaxLbaxbaxbaCx均收敛于迭代序列对任意初值上有唯一的根在方程那么都有使得都有并且如果迭代函数推论推论. 12 ; 11 1,2 3131kkkkxxxx）内考查：在12三、局部收敛性与收敛阶三、局部收敛性与收敛阶.*,局部收敛性附近考察收敛性，称为点。应用上经常只在不动不容易由定理

7、作出判断局收敛性；上的收敛性通常称为全在迭代序列xbaxk. *),(*(2.2)*,( ),*,( 0则称迭代序列局部收敛均收敛于迭代序列使得如果xxxUxxU定义1定义1.)2 . 2( , 1|*)(| ,*)(,)(* 是局部收敛的则迭代法且内有连续导数的某邻域在的不动点为迭代函数若 xxxxx定理3定理313. 3*03 2xx的根用不同方法求方程例4例4 ; 1132*)(12)(3121xxxxxxkkk，）（ ; 1*)(3)(3221xxxxxkk，）（ ;134. 0231*)(21)() 3(41321xxxxxxkkk，）（. 0*)()31 (21)()3(214 2

8、1xxxxxxkkk，）（kxk迭代法(1) 迭代法(2) 迭代法(3)迭代法(4)0123 ? x0 x1 x2 x3 ?23987?21.521.5?21.751.734751.732631?21.751.7321431.732051?14.211 . , ,lim*,*,)( 11时为平方收敛超线性收敛；当时为当时迭代法为线性收敛；特别地，当收敛阶则称迭代过程为是不等于零的常数若误差收敛于设迭代过程ppppCCeexxexxxpkkkkkkk定义2定义2.*, 0*)(0*)(*)(*)( ,*)()( )() 1(阶收敛的附近是那么迭代过程在，并且连续导数阶邻近具有的根在如果迭代函数p

9、xxxxxpxxxxpp 定理4定理4. ,0*)( , 0*)(; ,1|*)(|0平方收敛时当迭代法线性收敛时特别地，当 xxx153 3 迭代收敛的加速方法迭代收敛的加速方法一、埃特金加速收敛方法一、埃特金加速收敛方法),( 01xx由迭代公式校正一次得对于收敛的迭代过程，).( 12xx再校正一次得则变化不大如果 ,)( ,)(Lxx(3.1) *).-(*)()(*),-(*)()(*112001xxLxxxxxxLxxxx* 1021xxxxxxxx16,*2202022121xxxxxxxxxxx.2)( 222* 0122010012210220100200122102xxxx

10、xxxxxxxxxxxxxxxxxxxxx)( )( :Aitken)(1212kkkkxxxx加速迭代方法于是得到埃特金* 1021xxxxxxxxkkkkkkkxxxxxxx122112)( (3.2) ./)( 22kkkxxx17 Aitken 加速：加速：xyy = xy = g(x)x*x0P(x0, x1)x1x2x P(x1, x2)2212012()2xxxxxxx一般地，有：一般地，有：2112()2KKKKKKKxxxxxxx01021232343,(),( ), ,(), ,( ),.xxg xxg xxxg xxxg x比比 收敛得略快。收敛得略快。 Kx Kx18二

11、、斯蒂芬森迭代法二、斯蒂芬森迭代法迭代法蒂芬森加速技巧结合，得到斯把不动点迭代与埃特金)(Steffensen(3.3) ), 2 , 1 , 0( 2)(),( ),(21kxyzxyxxyzxykkkkkkkkkkk (3.4) ), 2 , 1 , 0( )( 1其中代法改写为另一种不动点迭kxxkk(3.5) .)(2)()()( 2xxxxxxx19Steffensen迭代格式几何解释 20.2)3 . 3()(*1) *( ,)()(* .)(*,)(* 阶收敛的是迭代法的不动点，且斯蒂芬森为，则存在的不动点，设为反之，的不动点为则的不动点为若xxxxxxxxxx 定理5定理5.

12、1 01 313kkxxxx的迭代将斯蒂芬森法用于解 例5例5.,)3 . 3( .1331有收敛结果计算现用发散指出：例kkxx解解kxkykzk0123451.51.416291.355651.329851.324801.324722.375001.840921.491401.347101.3251812.39655.238882.317281.444351.32714说明说明: (2.2)不收敛,(3.3)可能收敛; (2.2)线性收敛,(3.3)平方收敛!21.4 , 303 2中的解在求方程xex 例6例6ln3ln2 构造迭代法，)(3lnln2：1kkxxxgxx取对数得解解.2

13、,4 , 3)(,4 , 3 , 132)(max ,2)( 43迭代收敛由定理当xxxxxx.73307. 3 , 5 . 3 160 xx则进行加速若用,)3 . 3(kxkykzk0123.53.734443.733073.604143.733813.662023.73347224 4 牛顿法牛顿法一、牛顿法及其收敛性一、牛顿法及其收敛性.牛顿迭代公式的推导:线性化展开做并假定近似根的设已知方程Taylorxfxxfkk, 0)(,0)( ),)()()( kkkxxxfxfxf(4.1) , 0)()( 0)( kkkxxxfxfxf近似表示为于是.4.2 .)()( ,其根为11牛顿

14、迭代法牛顿迭代法这就是）（则有计算公式记kkkkkxfxfxxx23.义牛顿迭代公式的几何意.性牛顿迭代法的局部收敛,)()()( xfxfxx ,)()()()()()()(1)( 222xfxfxfxfxfxfxfx ,*)(*)(*)(0*)(*)(0*)(*)(*)( 42xfxfxfxfxfxfxfx ）（4.3 . *)(2*)( *)(*lim 21xfxfxxxxkkk 图7-324二、牛顿法应用举例二、牛顿法应用举例.01 的根用牛顿法求方程xxe例7例7. 5 . 0 ), 2 , 1 , 0( 1 01xkxexxxkxkkkk取初值解：牛顿迭代公式为kxk01230.5

15、0.571020.567160.56714，应用牛顿法解二次方程对于给定正数0 , 2CxC例例8 8;115并求.0:0迭代公式皆收敛对证明x(4.5) ). (212 21kkkkkkxCxxCxxx解：. 01 ,1150 xC初值取kxk012341010.75000010.72383710.72380510.72380525).(211kkkxCxx（4.5）这种迭代公式对于任意初值 都是收敛的. 00 x 事实上，对（4.5）式施行配方手续，易知 .)(21;)(212121CxxCxCxxCxkkkkkk以上两式相除得 .211CxCxCxCxkkkk据此反复递推有 .200kC

16、xCxCxCxkk（4.6）26记 ,00CxCxq整理（4.6）式，得 .1222kkqqCCxk 对任意 ，总有 ，故由上式推知，当 时 ，即迭代过程恒收敛. 00 x1qkCxk27三、简化牛顿法与牛顿下山法三、简化牛顿法与牛顿下山法 ., 2 , 1 , 0, 0 )( 1kCxCfxxkkk构造迭代公式.,2)(0 1, )(1)(公式局部收敛时即当xfCxfCx(4.7) .)()( 01xfxfxxkkk简化牛顿法：)(10 xfC图7-428 （2 2） 牛顿下山法牛顿下山法. . 牛顿法收敛性依赖初值 的选取. 如果 偏离所求根 较远，则牛顿法可能发散.0 x0 x*x 例如

17、，用牛顿法求方程 .013 xx（4.8）在 附近的一个根 . 5.1x*x 设取迭代初值 ，用牛顿法公式 5.10 x131231kkkkkxxxxx（4.9）计算得 .32472.1,32520.1,34783.1321xxx迭代3次得到的结果 有6位有效数字. 3x29 但如果改用 作为迭代初值，则依牛顿法公式（4.9）迭代一次得 6.00 x.9.171x这个结果反而比 更偏离了所求的根 . 6.00 x32472.1* x 为了防止迭代发散，对迭代过程再附加一项要求，即具有单调性： .)()(1kkxfxf（4.10）满足这项要求的算法称下山法下山法. 将牛顿法与下山法结合起来使用，

18、即在下山法保证函数值稳定下降的前提下，用牛顿法加快收敛速度. 将牛顿法的计算结果 30)()(1kkkkxfxfxx与前一步的近似值 适当加权平均作为新的改进值 kx,)1(11kkkxxx（4.11）其中 称为下山因子，（4.11）即为 )10(),1 ,0()()(1kxfxfxxkkkk（4.12）(4.12)称为牛顿下山法牛顿下山法. 选择下山因子时从 开始，逐次将 减半进行试算，直到能使下降条件（4.10）成立为止. 1 若用此法解方程（4.8），当 时由（4.9）求得6.00 x31 ，它不满足条件（4.10）.9.171x 通过 逐次取半进行试算，当 时可求得 . 此时有 ，而显

19、然 . 32/1140625.11x656643.0)(1xf384.1)(0 xf)()(01xfxf 由 计算 时 , 均能使条件（4.10）成立. 计算结果如下 ： 1x,32xx1.0000086.0)(,32472.1;00667.0)(,32628.1;1866.0)(,36181.1443322xfxxfxxfx 即为 的近似. 一般情况只要能使条件（4.10）成立，则可得到 ，从而使 收敛.4x*x0)(limkkxfkx32四、重根情形四、重根情形.(4.13) ,)()( )(*)()(,1仍平方收敛可将迭代法改为，牛顿法不是平方收敛重根情形kkkkmxfxfmxxxgxx

20、xfm.0)(*,)(*)()()(*)()( )(*)(/ )()(的单根是故重根，则的是，若还可令xxxgxxxmgxgxxxmxfxxfxfx33.(4.14) ,)()()()()( )(21仍平方收敛用牛顿法得对kkkkkkkxfxfxfxfxfxxx . 2*044 924xxx的二重根用上述三种方法求 例例；）牛顿法：（kkkkxxxx42 121解解；）（kkkkxxxx22 )13. 4( 221.2)2( (4.14) 3221kkkkkxxxxx）（计算结果如下： 34kxk(1)(2)(3)0123x0 x1x2x31.51.4583333331.4366071431.

21、4254976191.51.4166666671.4142156861.4142135621.51.4117647061.4142114381.41421356235)()()()( )( 1111kkkkkkkkxxxxxfxfxfxpxx，得到线性插值函数为插值节点和以.)()()()( 0)(1111称为弦截法，得到令kkkkkkkxxxfxfxfxxxp.)()()(11而得到或在牛顿法中取kkkkkxxxfxfxf.几何意义5 弦截法与抛物线法弦截法与抛物线法的迭代法。下面介绍避免求要计算外还每步除计算程用牛顿法求解非线性方)( ).()(, 0)(kkkxfxfxfxf36).()

22、()(11kkkkkkxxxxxfxfxfy图7-537 弦截法与切线法（牛顿法）都是线性化方法，但两者有本质的区别. 切线法在计算 时只用到前一步的值 ，而弦截法（5.2），在求 时要用到前面两步的结果 ，因此使用这种方法必须先给出两个开始值 .1kxkx1kx1,kkxx01, xx 例例10 10 用弦截法解方程 .01)(xxexf 解解 设取 作为开始值，用弦截法求得的结果见表7-8，比较例7牛顿法的计算结果可以看出，弦截法的收敛速度也是相当快的. 6.0,5.010 xx56714.0456709.0356532.026.015.0087kxk计算结果表 实际上，弦截法具有超线性的

23、收敛性. 38.收敛可以证明弦截法超线性.*618. 1, , 0)(|*:|*)( 625110 xpxxxfxxxxxf收敛到按阶充分小时，两点弦截法那么当又初值有连续导数，且对任意内具有二阶的邻域在根假设定理定理39 7.5.2 7.5.2 抛物线法抛物线法 设已知方程 的三个近似根 ，以这三点为节点构造二次插值多项式 ，并适当选取 的一个零点 作为新的近似根，这样确定的迭代过程称抛物线法抛物线法，亦称密勒（密勒（MllerMller）法法. 21,kkkxxx0)(xf)(2xp)(2xp1kx 在几何上，这种方法的基本思想是用抛物线 与 轴的交点 作为所求根 的近似位置（图7-6).

24、 )(2xpy 1kxx*x图7-640插值多项式 ).)(,)(,)()(12112kkkkkkkkkxxxxxxxfxxxxfxfxp有两个零点： ,)(4)(22121kkkkkkkxxxfxfxfxx（5.3）式中 ).(,1211kkkkkkkxxxxxfxxf 问题是该如何确定 ，假定在 三个近似根中， 更接近所求的根 ，为了保证精度，选 （5.3）中较接近 的一个值作为新的近似根 . 为此，只要取根式前的符号与 的符号相同. 1kx21,kkkxxxkx*xkx1kx41 例例11 11 用抛物线法求解方程 .01)(xxexf 解解 设用表7-8的前三个值 56532.0,6.

25、0,5.0210 xxx作为开始值，计算得 .21418.2,83373.2,68910.2,005031.0)(,093271.0)(,175639.0)(0121201210 xxxfxxfxxfxfxfxf故 .75694.2)(,1201212xxxxxfxxf代入（5.3）式求得 .56714.0,)(4)(201222223xxxfxfxfxx42 以上计算表明，抛物线法比弦截法收敛得更快. 在一定条件下可以证明，对于抛物线法，迭代误差有下列渐近关系式 .*)(6*)(42.01840.1xfxfeekk 可见抛物线法也是超线性收敛的，其收敛的阶 ,收敛速度比弦截法更接近于牛顿法. 840.1p 从（5.3）看到，即使 均为实数， 也可以是复数，所以抛物线法适用于求多项式的实根和复根. 21,kkkxxx1kx43 7.6 7.6 解非线性方程组的牛顿迭代法解非线性方程组的牛顿迭代法 考虑方程组 ,0),(,0),(111nnnxxfx