第7章非线性方程组的解法

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

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

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

4、*(2.2)*,lim )2 . 2(,0不动点迭代法不动点迭代法为故称的不动点，是收敛，且则称迭代公式有极限得到的序列由如果对任何初值xxxxxxbaxkkk.几何意义是一种逐次逼近法；隐式化为显式，迭代法：说明说明.*5 . 101 3xxx附近的根在求 例3例3 )., 2 , 1 , 0( , 15 . 11310kxxxkk，）解：（kxk012345671.51.357211.330861.325881.324941.324761.324731.32472. ,39.12,375. 2 , 5 . 1, 1 (2) 21031xxxxxkk.*,)(2.4 |;| )()(| ,

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

6、101kkkkkxxLxxxxLLxxxbaxxbaxfLxbaxLbaxbaxbaCx均收敛于迭代序列对任意初值上有唯一的根在方程那么都有使得都有并且如果迭代函数推论推论. 12 ; 11 1,2 3131kkkkxxxx）内考查：在三、局部收敛性与收敛阶三、局部收敛性与收敛阶.*,局部收敛性附近考察收敛性，称为点。应用上经常只在不动不容易由定理作出判断局收敛性；上的收敛性通常称为全在迭代序列xbaxk. *),(*(2.2)*,( ),*,( 0则称迭代序列局部收敛均收敛于迭代序列使得如果xxxUxxU定义1定义1.)2 . 2( , 1|*)(| ,*)(,)(* 是局部收敛的则迭代法且

7、内有连续导数的某邻域在的不动点为迭代函数若 xxxxx定理3定理3. 3*03 2xx的根求方程只用四则运算不用开方例4例4 ; 1132*)(12)(3121xxxxxxkkk，）（ ; 1*)(3)(3221xxxxxkk，）（ ;134. 0231*)(21)() 3(41321xxxxxxkkk，）（. 0*)()31 (21)()3(214 21xxxxxxkkk，）（kxk迭代法(1) 迭代法(2) 迭代法(3)迭代法(4)0123 ? x0 x1 x2 x3 ?23987?21.521.5?21.751.734751.732631?21.751.7321431.732051?.2

8、11 . , ,lim*,*,)( 11时为平方收敛超线性收敛；当时为当时迭代法为线性收敛；特别地，当收敛阶则称迭代过程为是不等于零的常数若误差收敛于设迭代过程ppppCCeexxexxxpkkkkkkk定义2定义2.*, 0*)(0*)(*)(*)( ,*)()( )() 1(阶收敛的附近是那么迭代过程在，并且连续导数阶邻近具有的根在如果迭代函数pxxxxxpxxxxpp 定理4定理4. ,0*)( , 0*)(; ,1|*)(|0平方收敛时当迭代法线性收敛时特别地，当 xxx作业作业: P290, 2,4.3 3 迭代收敛的加速方法迭代收敛的加速方法一、埃特金加速收敛方法一、埃特金加速收敛

9、方法),( 01xx由迭代公式校正一次得对于收敛的迭代过程，).( 12xx再校正一次得则变化不大如果 ,)( ,)(Lxx(3.1) *).-(*)()(*),-(*)()(*112001xxLxxxxxxLxxxx* 1021xxxxxxxx,*2202022121xxxxxxxxxxx.2)( 222* 0122010012210220100200122102xxxxxxxxxxxxxxxxxxxxxxxxx)( )( :Aitken)(1212kkkkxxxx加速迭代方法于是得到埃特金* 1021xxxxxxxxkkkkkkkxxxxxxx122112)( (3.2) ./)( 22k

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

11、将斯蒂芬森法用于解 例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)平方收敛!.4 , 303 2中的解在求方程xex 例6例6ln3ln2 构造迭代法，)(3lnln2：1kkxxxgxx取对数得解解.2,4 , 3)(,4 , 3 , 13

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

13、kkkkxfxfxxx.义牛顿迭代公式的几何意.性牛顿迭代法的局部收敛,)()()( xfxfxx ,)()()()()()()(1)( 222xfxfxfxfxfxfxfx ,*)(*)(*)(0*)(*)(0*)(*)(*)( 42xfxfxfxfxfxfxfx ）（4.3 . *)(2*)( *)(*lim 21xfxfxxxxkkk 二、牛顿法应用举例二、牛顿法应用举例.0 的根用牛顿法求方程xex例7例7. 5 . 0 ), 2 , 1 , 0( 1 01xkxexxxkxkkkk取初值解：牛顿迭代公式为kxk01230.50.571020.567160.56714，应用牛顿法解二次

14、方程对于给定正数0 , 2CxC例例8 8;115并求.00迭代公式皆平方收敛证明x(4.5) ). (212 21kkkkkkxCxxCxxx解：. 01 ,1150 xC初值取kxk012341010.75000010.72383710.72380510.723805三、简化牛顿法与牛顿下山法三、简化牛顿法与牛顿下山法 ., 2 , 1 , 0, 0 )( 1kCxCfxxkkk构造迭代公式.,2)(0 1, )(1)(公式局部收敛时即当xfCxfCxg(4.7) .)()( 01xfxfxxkkk简化牛顿法：)(10 xfCkkkxxx)1 (11(4.12) , 2 , 1 , 0,)

15、()( 1kxfxfxxkkkk牛顿下山法：. )()( 1,1kkxfxf逐次折半直到满足其中下山因子.*5 . 101 33xxx附近的根在再求、 例例，计算结果如下：，折半，简化牛顿法，：依次用牛顿法32/116 . 06 . 05 . 1000 xxx解解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.1)( 2的根山法求讨论用牛顿法和牛顿下：xxxf思考思考.，11, 1,0)1 (

16、1)1 (2)1 ()(000222222xxxxxxxxxxf注：四、重根情形四、重根情形.(4.13) ,)()( )(*)()(,1仍平方收敛可将迭代法改为，牛顿法不是平方收敛重根情形kkkkmxfxfmxxxgxxxfm.0)(*,)(*)()()(*)()( )(*)(/ )()(的单根是故重根，则的是，若还可令xxxgxxxmgxgxxxmxfxxfxfx.(4.14) ,)()()()()( )(21仍平方收敛用牛顿法得对kkkkkkkxfxfxfxfxfxxx . 2*044 924xxx的二重根用上述三种方法求 例例；）牛顿法：（kkkkxxxx42 121解解；）（kkkk

17、xxxx22 )13. 4( 221.2)2( (4.14) 3221kkkkkxxxxx）（计算结果如下： kxk(1)(2)(3)0123x0 x1x2x31.51.4583333331.4366071431.4254976191.51.4166666671.4142156861.4142135621.51.4117647061.4142114381.414213562作业作业: P291, 12,15.5 5 弦截法弦截法的迭代法。下面介绍避免求要计算外还每步除计算程用牛顿法求解非线性方)( ).()(, 0)(kkkxfxfxfxf单点弦截法 . 1).()()()( )(, )( )

18、( 00010kkkkkkkkxxxxxfxfxfxxxxfxfxpxx，得到线性插值函数为插值节点和以.)()()()( 0)(0011称为单点弦截法，得到令xxxfxfxfxxxpkkkkk )()()(00，同样得代替导数在牛顿法中用差商kkkxfxxxfxf).()()()( 001xxxfxfxfxxkkkkk.几何意义.线性收敛的可以证明单点弦截法是这是因为，,*)(1 0)*()(*)(0)(*)(*)(1*)( 00*)(*)(0200 xxxfxfxfxxxfxfxfxfxfx. 1*)( 0 x两点弦截法 . 2)()()()( )( 1111kkkkkkkkxxxxxfx

19、fxfxpxx，得到线性插值函数为插值节点和以.)()()()( 0)(1111称为两点弦截法，得到令kkkkkkkxxxfxfxfxxxp.)()()(11而得到或在牛顿法中取kkkkkxxxfxfxf.几何意义.线性收敛可以证明两点弦截法超.*618. 1, , 0)(|*:|*)( 625110 xpxxxfxxxxxf收敛到按阶充分小时，两点弦截法那么当又初值有连续导数，且对任意内具有二阶的邻域在根假设定理定理.01)( 的根用两点弦截法求方程xxexf 例10例10kxk012340.50.60.565320.567090.56714抛物线法 . 3)(, )(,)( )( ,121

20、1221kkkkkkkkkkkkxxxxxxxfxxxxfxfxpxxx，得到插值函数为插值节点和以).(,)(4)(2 0)(12112112kkkkkkkkkkkkkkxxxxxfxxfxxxfxfxfxxxp式中，得到两个零点：令.,)(4)sgn()(2 211kkkkkkkxxxfxfxfxx.*840. 1xp收敛到抛物线法按阶6 6 解非线性方程组的解非线性方程组的迭代法迭代法 . 0),(, 0),(, 0),( 21212211nnnnxxxfxxxfxxxf考虑非线性方程组 .)( OXF利用向量记号写为. ,*)( ,* .)(为非线性方程组的解则称使得若存在上向量值函数是定义在某区域这里*DRDnXOXFXXF).( XGX 考虑等价的方程组., ,)()( ),1 , 0(