第6章 解非線性方程的迭代法20171121

1、1 1 方程求根與二分法方程求根與二分法 第第7 7章章 解非線性方程的迭代法解非線性方程的迭代法 一、引言一、引言 . ,)(, (1.1) 0)( baCxfRx xf 的求根問題，其中 考慮單變量非線性方程 非線性方程的分兩類： . 01 : )., 1 , 0(R, 0 , 0 , . 1 3 0 1 1 10 xxniaa axaxaxa i nn nn 如其中 代數(shù)方程 . 0 : , . 2 x ex如超越方程 .)(* . ,|*)(|0 ),(*)()( )( 重零點(diǎn)的為則稱為正整數(shù)其中 可以分解為如果 mxfxmxg xgxxxf xf m . 0*)(, 0*)(*)(*

2、)( )() 1( xfxfxfxf mm 此時 , 0)()(,)(bfafbaCxf若 則可用搜索法求有根區(qū)間. .0 的有根區(qū)間求方程 x ex例例1 1 x 1 0 1 2 f(x)的符號 + + 求根問題的三個方面：存在性，分布，精確化。 二、二分法二、二分法 二分法簡述. ., ;,)()( ., )()( . 2/ )(, 0)()( 011 1010 0 00 xbaa bbxaxfaf x xfxfbaxbfaf 否則 同號，則與若 假若不然，停止那么輸出 的零點(diǎn)，是假如取設(shè) , 11 kk bababa故 *,2/ )(xbax kkk (1.3) .2/ )(2/ )(|

3、*| 1 k kkk ababxx .2 5 . 1 , 0 . 1 01 3 位小數(shù)點(diǎn)后 內(nèi)的一個實(shí)根，準(zhǔn)確到在求 xx 例例2 2 k ak bk xkf(xk)符號 0 1 2 3 4 5 6 1.0 1.25 1.3125 1.3203 1.5 1.375 1.3438 1.3281 1.25 1.375 1.3125 1.3438 1.3281 1.3203 1.3242 + + + 二分法優(yōu)、缺點(diǎn)； 用途。 2 2 迭代法迭代法 一、不動點(diǎn)迭代一、不動點(diǎn)迭代 (2.1) ).( 0)( xx xf 化為等價形式將非線性方程 .)(* ; ) *(*0*)( 不不動動點(diǎn)點(diǎn)的一個為函數(shù)

4、稱xx xxxf ).(, 010 xxx可以得到給定初始近似值 .)( (2.2) ., 2 , 1 , 0 ),( 1 為迭代函數(shù)稱 式如此反復(fù)，構(gòu)造迭代公 x kxx kk 6 迭代過程的幾何表示 ( )yx y x O x* x2 x1 x0 x y 0 P 1 Q 2 P * P 2 Q ( ) ( ) yx xx xy 交點(diǎn)即為真根 .)2 . 2( )(*)(*(2.2) *,lim )2 . 2(, 0 不動點(diǎn)迭代法不動點(diǎn)迭代法為故稱 的不動點(diǎn)，是收斂，且則稱迭代公式 有極限得到的序列由如果對任何初值 xxx xx xbax k k k .幾何意義 是一種逐次逼近法；隱式化為顯

5、式，迭代法 ：說明說明 .*5 . 101 3 xxx附近的根在求 例例3 3 kxk 0 1 2 3 4 5 6 7 1.5 1.35721 1.33086 1.32588 1.32494 1.32476 1.32473 1.32472 . ,39.12,375. 2 , 5 . 1, 1 (2) 210 3 1 xxxxx kk )., 2 , 1 , 0( , 15 . 11 3 10 kxxx kk ，）解：（ .*,)( 2.4 |;| )()(| , , 10 (2) ,)( , (1) , ,)( xbax yxLyx bayxL baxbax baCx 上存在唯一的不動點(diǎn)在那么

6、 ）（ 都有使得常數(shù) 都有 并且如果迭代函數(shù) 定理1定理1 二、不動點(diǎn)的存在性與迭代法的收斂性二、不動點(diǎn)的存在性與迭代法的收斂性 *,)(2.2) ,1 0 xx bax 的不動點(diǎn)均收斂于 迭代序列對任意初值的條件下在定理 定理2定理2 并有誤差估計(jì) (2.5) . | 1 |*| 01 xx L L xx k k . | 1 1 |*| 1kkk xx L xx 還有 . | 1 1 |*| 4) |,| 1 |*| 3) *,(2.2) , 2) *,0)( 1) ; 1| )(|, , 10 (2) ,)( , (1) , ,)( 1 01 0 1 kkk k k xx L xx xx

7、L L xx xbax xbaxf LxbaxL baxbax baCx 均收斂于迭代序列對任意初值 上有唯一的根在方程 那么 都有使得 都有 并且如果迭代函數(shù) 推論推論 . 12 ; 11 1,2 3 1 3 1 kkkk xxxx）內(nèi)考查：在 三、局部收斂性與收斂階三、局部收斂性與收斂階 . * , 局部收斂性附近考察收斂性，稱為 點(diǎn)。應(yīng)用上經(jīng)常只在不動不容易由定理作出判斷 局收斂性；上的收斂性通常稱為全在迭代序列 x baxk . *),(* (2.2)*,( ),*,( 0 則稱迭代序列局部收斂均收斂于 迭代序列使得如果 xx xUxxU 定定義義1 1 .)2 . 2( , 1|*)

8、(| , *)(,)(* 是局部收斂的則迭代法且內(nèi)有連續(xù)導(dǎo)數(shù) 的某鄰域在的不動點(diǎn)為迭代函數(shù)若 x xxxx 定定理理3 3 . 3*03 2 xx的根求方程只用四則運(yùn)算不用開方例例4 4 ; 1132*)(12)(31 2 1 xxxxxx kkk ，）（ ; 1*)( 3 )( 3 2 2 1 x x x x x k k ，）（ ;134. 0 2 3 1*)( 2 1)() 3( 4 1 3 2 1 x x xxxx kkk ，）（ . 0*)() 3 1 ( 2 1 )() 3 ( 2 1 4 2 1 x x x x xx k kk ，）（ kxk迭代法(1) 迭代法(2) 迭代法(3)

9、迭代法(4) 0 1 2 3 ? x0 x1 x2 x3 ? 2 3 9 87 ? 2 1.5 2 1.5 ? 2 1.75 1.73475 1.732631 ? 2 1.75 1.732143 1.732051 ? .2 11 . , ,lim *,*,)( 1 1 時為平方收斂超線性收斂；當(dāng) 時為當(dāng)時迭代法為線性收斂；特別地，當(dāng)收斂 階則稱迭代過程為是不等于零的常數(shù)若 誤差收斂于設(shè)迭代過程 p pp pCC e e xxexxx p k k k kkkk 定義2定義2 .* , 0*)(0*)(*)(*)( , *)()( )() 1( 階收斂的附近是那么迭代過程在 ， 并且連續(xù)導(dǎo)數(shù) 階鄰

10、近具有的根在如果迭代函數(shù) px xxxx pxxxx pp 定理4定理4 . ,0*)( , 0*)( ; ,1|*)(|0 平方收斂時當(dāng) 迭代法線性收斂時特別地，當(dāng) xx x 不講不講3 3 迭代收斂的加速方法迭代收斂的加速方法 一、埃特金加速收斂方法一、埃特金加速收斂方法 ),( 01 xx 由迭代公式校正一次得對于收斂的迭代過程， ).( 12 xx再校正一次得 則變化不大如果 ,)( ,)(Lxx (3.1) *).-(*)()(* *),-(*)()(* 112 001 xxLxxxx xxLxxxx * * * * 1 0 2 1 xx xx xx xx ,*2 2 0202 2

11、1 2 1 xxxxxxxxxxx . 2 )( 2 2 2 * 012 2 01 0 012 2 102 2 01002 0 012 2 102 xxx xx x xxx xxxxxxxx x xxx xxx x )( )( :Aitken)( 12 1 2 kk kk xx xx 加速迭代方法于是得到埃特金 * * * * 1 0 2 1 xx xx xx xx kkk kk kk xxx xx xx 12 2 1 1 2 )( (3.2) ./)( 22 kkk xxx 二、斯蒂芬森迭代法二、斯蒂芬森迭代法 迭代法 蒂芬森加速技巧結(jié)合，得到斯把不動點(diǎn)迭代與埃特金 )(Steffensen

12、 (3.3) ), 2 , 1 , 0( 2 )( ),( ),( 2 1 k xyz xy xx yzxy kkk kk kk kkkk (3.4) ), 2 , 1 , 0( )( 1 其中 代法改寫為另一種不動點(diǎn)迭 kxx kk (3.5) . )(2)( )( )( 2 xxx xx xx .2)3 . 3( )(*1) *( ,)()(* .)(*,)(* 階收斂的是迭代法的不動點(diǎn)，且斯蒂芬森 為，則存在的不動點(diǎn)，設(shè)為 反之，的不動點(diǎn)為則的不動點(diǎn)為若 xxxxxx xxxx 定定理理5 5 . 1 01 3 1 3 kk xxxx的迭代將斯蒂芬森法用于解 例5例5 .,)3 . 3(

13、 .13 3 1 有收斂結(jié)果計(jì)算現(xiàn)用發(fā)散指出：例 kk xx解解 kxkykzk 0 1 2 3 4 5 1.5 1.41629 1.35565 1.32985 1.32480 1.32472 2.37500 1.84092 1.49140 1.34710 1.32518 12.3965 5.23888 2.31728 1.44435 1.32714 說明說明: (2.2)不收斂,(3.3)可能收斂; (2.2)線性收斂,(3.3)平方收斂! .4 , 303 2 中的解在求方程 x ex 例6例6 ln3ln2 構(gòu)造迭代法，)(3lnln2： 1 kk xx xgxx取對數(shù)得解解 .2 ,4

14、 , 3)(,4 , 3 , 1 3 2 )(max , 2 )( 43 迭代收斂由定理 當(dāng) xxx x x x .73307. 3 , 5 . 3 160 xx 則進(jìn)行加速若用,)3 . 3( kxkykzk 0 1 2 3.5 3.73444 3.73307 3.60414 3.73381 3.66202 3.73347 作業(yè)P290,2 4 4 牛頓法牛頓法 一、牛頓法及其收斂性一、牛頓法及其收斂性 .牛頓迭代公式的推導(dǎo):線性化 展開做并假定近似根 的設(shè)已知方程 Taylorxfx xf kk , 0)(, 0)( ),)()()( kkk xxxfxfxf (4.1) , 0)()(

15、0)( kkk xxxfxf xf近似表示為于是 . 4.2 . )( )( ,其根為 1 1 牛牛頓頓迭迭代代法法這就是 ）（ 則有計(jì)算公式記 k k kk k xf xf xx x 22 Newton 法的幾何解釋 1 1010 x (0) () /() yx xxf xfx 與軸交點(diǎn)為第二個近似根： 000 00 0 ,() ( ) ()()() f xxx f x yfxxf xx 當(dāng)在取定后（在真根附近），過 作的切線，則切線方程： x0 x1 (x0，f(x0) 當(dāng)當(dāng)x*是是f(x)的單根時的單根時 ,( *)( *)f xfx 00即即 .義牛頓迭代公式的幾何意 .性牛頓迭代法的

16、局部收斂 , )( )( )( xf xf xx , )( )()( )( )()()( 1)( 22 2 xf xfxf xf xfxfxf x , *)( *)( *)( 0*)(*)(0*)(*)( *)( 4 2 xf xf xf xfxfxfxf x ）（4.3 . *)(2 *)( *)( * lim 2 1 xf xf xx xx k k k 二、牛頓法應(yīng)用舉例二、牛頓法應(yīng)用舉例 .0 的根用牛頓法求方程 x ex例例7 7 . 5 . 0 ), 2 , 1 , 0( 1 0 1 x k x ex xx k x k kk k 取初值 解：牛頓迭代公式為 kxk 0 1 2 3 0

17、.5 0.57102 0.56716 0.56714 ，應(yīng)用牛頓法解二次方程對于給定正數(shù)0 , 2 CxC例例8 8 ;115并求 .0 0 迭代公式皆平方收斂證明x (4.5) ). ( 2 1 2 2 1 k k k k kk x C x x Cx xx 解： . 01 ,115 0 xC初值取 kxk 0 1 2 3 4 10 10.750000 10.723837 10.723805 10.723805 2 1 0 123 4 00 1 2 100100 Heron 17x4 4.124.1231064.1231056256177 4.1231056256176605498214098

18、56 nn n CxC C xx x C xxx x 例：用牛頓法，找一個計(jì)算平方根的方法。 解：設(shè)，考慮方程。 牛頓法： 古老公式：公元年間古希臘工程師、 建筑師。 上述公式常被用來計(jì)算平方根的子程序。 例：，僅列出正確數(shù)字，則 28（位有效?。?三、簡化牛頓法與牛頓下山法三、簡化牛頓法與牛頓下山法 ., 2 , 1 , 0, 0 )( 1 kCxCfxx kkk 構(gòu)造迭代公式 .,2)(0 1, )(1)(公式局部收斂時即當(dāng)xfCxfCxg (4.7) . )( )( 0 1 xf xf xx k kk 簡化牛頓法： )( 1 0 xf C kkk xxx)1 ( 11 (4.12) ,

19、2 , 1 , 0, )( )( 1 k xf xf xx k k kk 牛頓下山法： . )()( 1, 1kk xfxf 逐次折半直到滿足其中下山因子 .*5 . 101 3 3 xxx附近的根在再求、 例例 ，計(jì)算結(jié)果如下：，折半 ，簡化牛頓法，：依次用牛頓法 32/11 6 . 06 . 05 . 1 000 xxx解解 kxkxkxk f(xk) 0 1 2 3 4 1.5 1.34783 1.32520 1.32472 0.6 17.9 發(fā)散 0.6 -1.384 1.140625 -0.656643 1.36181 0.1866 1.32628 0.00667 1.32472 0

20、.0000086 . 1 )( 2 的根山法求討論用牛頓法和牛頓下： x x xf 思考思考 .，11, 1,0 )1 ( 1 )1 ( 2)1 ( )( 000 22 2 22 2 xxx x x x xxx xf注： 四、重根情形四、重根情形 ,( )(*)( ) m mf xxxg x 重重根根情情形形，牛牛頓頓法法不不是是平平方方收收斂斂， () , (4.13) () . k kk k f x xxm fx 1 可可將將迭迭代代法法改改為為 仍仍平平方方收收斂斂 .0)(* , )(*)()( )(*)( )( )(*)(/ )()( 的單根是故 重根，則的是，若還可令 xx xgx

21、xxmg xgxx x mxfxxfxfx . (4.14) , )()()( )()( )( 2 1 仍平方收斂 用牛頓法得對 kkk kk kk xfxfxf xfxf xx x . 2*044 9 24 xxx的二重根用上述三種方法求 例例 ；）牛頓法：（ k k kk x x xx 4 2 1 2 1 解解 ；）（ k k kk x x xx 2 2 )13. 4( 2 2 1 . 2 )2( (4.14) 3 2 2 1 k kk kk x xx xx）（計(jì)算結(jié)果如下： 1 1 k kk k x xx x 2 2 4 （ ）牛牛頓頓法法； ；）（ k k kk x x xx 2 2

22、)13. 4( 2 2 1 . 2 )2( (4.14) 3 2 2 1 k kk kk x xx xx）（ kxk(1)(2)(3) 0 1 2 3 x0 x1 x2 x3 1.5 1.458333333 1.436607143 1.425497619 1.5 1.416666667 1.414215686 1.414213562 1.5 1.411764706 1.414211438 1.414213562 5 5 弦截法弦截法 . 1兩兩點(diǎn)點(diǎn)弦弦截截法法 )( )()( )( )( 1 1 1 1 k kk kk k kk xx xx xfxf xfxp xx ，得到線性插值函數(shù)為插值節(jié)

23、點(diǎn)和以 . )( )()( )( 0)( 1 1 1 1 稱為兩點(diǎn)弦截法 ， ，得到令 kk kk k kk xx xfxf xf xx xp . )()( )( 1 1 而得到或在牛頓法中取 kk kk k xx xfxf xf .幾何意義 .線性收斂可以證明兩點(diǎn)弦截法超 .* 618. 1 , , 0)( |*:|*)( 6 2 51 10 x p xxxfx xxxxf 收斂到 按階充分小時，兩點(diǎn)弦截法那么當(dāng) 又初值有連續(xù)導(dǎo)數(shù)，且對任意 內(nèi)具有二階的鄰域在根假設(shè) 定定理理 .01)( 的根用兩點(diǎn)弦截法求方程 x xexf 例10例10 kxk 0 1 2 3 4 0.5 0.6 0.56

24、532 0.56709 0.56714 . 2單單點(diǎn)點(diǎn)弦弦截截法法 ).( )()( )( )(, )( )( 0 0 01 0 k k k k kkk k xx xx xfxf xf xxxxfxfxp xx ，得到線性插值函數(shù)為插值節(jié)點(diǎn)和以 . )( )()( )( 0)( 0 0 1 1 稱為單點(diǎn)弦截法 ， ，得到令 xx xfxf xf xx xp k k k kk )( )()( 0 0 ，同樣得代替導(dǎo)數(shù)在牛頓法中用差商 k k k xf xx xfxf ).( )()( )( 0 0 1 xx xfxf xf xx k k k kk .幾何意義 .線性收斂的可以證明單點(diǎn)弦截法是這是

25、因?yàn)椋?, *)( 1 0)*( )(*)( 0)(*)(*)( 1*)( 0 0 * )(*)( 0 2 0 0 xx xfxf xf xx xfxf xfxfxf x . 1*)( 0 x 拋物線法 . 3 )(, )(,)( )( , 121 12 21 kkkkk kkkk kkk xxxxxxxf xxxxfxfxp xxx，得到插值函數(shù)為插值節(jié)點(diǎn)和以 ).(, ,)(4 )(2 0)( 1211 21 1 2 kkkkkkk kkkk k kk xxxxxfxxf xxxfxf xf xx xp 式中 ， ，得到兩個零點(diǎn)：令 . ,)(4)sgn( )(2 21 1 kkkk k kk xxxfxf xf xx .*840. 1xp收斂到拋物線法按階 6 6 解非線性方程組的迭代法解非線性方程組的迭代法 . 0),( , 0),( , 0),( 21 212 211 nn n n xxxf xxxf xxxf 考慮非線性方程組 .)( OXF 利用向量記號寫為 . ,*)( ,* .)( 為非線性方程組的解則稱使得 若存在上向量值函數(shù)是定義在某區(qū)域這里 *D RD n XOXFX XF ).( XGX 考慮等價的方程