數(shù)值分析- 非線性方程求根

1、1 1 方程求根與方程求根與二分法二分法第第7 7章章 解非線性方程的迭代法解非線性方程的迭代法一、引言一、引言. ,)(,(1.1) 0)( baCxfRxxf的求根問題，其中考慮單變量非線性方程非線性方程的分兩類：. 01 : )., 1 , 0(R, 0, 0 , . 1301110 xxniaaaxaxaxainnnn如其中代數(shù)方程. 0 : , . 2xex如超越方程.)(* . ,|*)(|0),(*)()( )(重零點的為則稱為正整數(shù)其中可以分解為如果mxfxmxgxgxxxfxfm. 0*)(, 0*)(*)(*)( )() 1(xfxfxfxfmm此時, 0)()(,)(bf

2、afbaCxf若 則可用搜索法求有根區(qū)間.0 的有根區(qū)間求方程xex例1例1 x 1 0 1 2f(x)的符號 + + 方程根的數(shù)值計算大致可分三個步驟進行: (1) 判定根的存在性。 (2)確定根的分布范圍,即將每一個根用區(qū)間隔離開來。 (3)根的精確化,即根據(jù)根的初始近似值按某種方法逐步精確化,直至滿足預(yù)先要求的精度為止。 設(shè)f(x)為定義在某區(qū)間上的連續(xù)函數(shù),方程(1.1)存在實根。雖然方程(1.1)的根的分布范圍一般比較復雜,但我們不難將函數(shù)f(x)的定義域分成若干個只含一個實根的區(qū)間。 例如考慮方程 x2-2x-1=0 由圖7.1所示,該方程的一個負實根在-1和0之間,另一個正實根在

3、2和3之間。 圖 7.1 這樣,我們總可以假設(shè)方程(1.1)在(a,b)內(nèi)有且僅有一個單實根x*。由連續(xù)函數(shù)的介值定理知 f(a)f(b)0 若數(shù)值b-a較小,那么我們可在(a,b)上任取一點x0作為方程的初始近似根。 例如,方程 f(x)=x3-x-1=0 由于f(1)0,f(1.5)0,又f(x)在區(qū)間(1,1.5)上單調(diào)連續(xù),故可知在(1,1.5)內(nèi)有且僅有一個實根。于是可取某個端點或區(qū)間內(nèi)某一個點的值作為根的初始近似值。 設(shè)函數(shù)f(x)在區(qū)間a,b上單調(diào)連續(xù),且 f(a)f(b)0 則方程(1.1)在區(qū)間(a,b)內(nèi)有且僅有一個實根x。二、二分法二、二分法二分法簡述., ;,)()(

4、.,)()( . 2/ )(, 0)()(0111010000 xbaabbxaxfafxxfxfbaxbfaf否則同號，則與若假若不然，停止那么輸出的零點，是假如取設(shè),11kkbababa故 *,2/ )(xbaxkkk(1.3) .2/ )(2/ )(|*|1kkkkababxx 11()2kkxxba(1.3) 對于確定的精度,從式(1.3)易求得需要二等分的次數(shù)k。 二分法具有簡單和易操作的優(yōu)點。其計算步驟如下,框圖如圖7.2所示。 1.計算步驟 輸入有根區(qū)間的端點a,b及預(yù)先給定的精度; (a+b)/2 x; 若f(a)f(x)0,則x=b,轉(zhuǎn)向;否則x=a,轉(zhuǎn)向。 若b-a,則輸出

5、方程滿足精度的根x,結(jié)束;否則轉(zhuǎn)向。2. 計算框圖 (見下頁）例1 求方程 f(x)=x3-x-1=0在區(qū)間(1,1.5)內(nèi)的根。要求用四位小數(shù)計算,精確到小數(shù)點后兩位。解 這里a=1,b=1.5，取區(qū)間(1,1.5)的中點01(1 1.5)1.252x 圖 7.2 由于f(1)0,f(1.25)0,則令 a1=1.25, b1=1.5得到新的有根區(qū)間(1.25,1.5) 取x6=1.3242，誤差限| x6-x*|0.5/(27)0.005,故x6即為所求近似根，實際上根x*=1.324717二分法優(yōu)點：計算簡單，收斂性有保證； 缺點：收斂不夠快，特別是精度要求高時，工作量大，而且不能夠求復

6、根及雙重根。2 2 迭代法迭代法一、不動點迭代一、不動點迭代(2.1) ).( 0)(xxxf 化為等價形式將非線性方程.)(*; ) *(*0*)( 不動點不動點的一個為函數(shù)稱xxxxxf ).(,010 xxx可以得到給定初始近似值 .)(2.2) ., 2 , 1 , 0 ),( 1為迭代函數(shù)稱式如此反復，構(gòu)造迭代公xkxxkk.)2 . 2()(*)(*(2.2)*,lim )2 . 2(,0不動點迭代法不動點迭代法為故稱的不動點，是收斂，且則稱迭代公式有極限得到的序列由如果對任何初值xxxxxxbaxkkk.幾何意義是一種逐次逼近法；隱式化為顯式，迭代法：說明說明.*5 . 101

7、3xxx附近的根在求 例3例3 )., 2 , 1 , 0( , 15 . 11310kxxxkk，）解：（kxk012345671.51.357211.330861.325881.324941.324761.324731.32472雖然迭代法的基本思想很簡單,但效果并不總是令人滿意的。對于上例,若按方程寫成另一種等價形式 x=x3-1 (29) 建立迭代公式 xk+1=x3k-1, k=0,1,2,仍取初始值x0=1.5, 則迭代結(jié)果為 x1=2.375 x2=12.3976這種不收斂的迭代過程稱作是發(fā)散的。如下圖：.*,)(2.4 |;| )()(| , , 10 (2) ,)( , (1

8、) , ,)( xbaxyxLyxbayxLbaxbaxbaCx上存在唯一的不動點在那么）（都有使得常數(shù)都有并且如果迭代函數(shù)定理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) , ,)( 10101kkkkkxxLxxxxLL

9、xxxbaxxbaxfLxbaxLbaxbaxbaCx均收斂于迭代序列對任意初值上有唯一的根在方程那么都有使得都有并且如果迭代函數(shù)推論推論. 12 ; 11 1,2 3131kkkkxxxx）散性：內(nèi)考查如下迭代法的斂在三、局部收斂性與收斂階三、局部收斂性與收斂階.*,局部收斂性附近考察收斂性，稱為點。應(yīng)用上經(jīng)常只在不動不容易由定理作出判斷局收斂性；上的收斂性通常稱為全在迭代序列xbaxk. *),(*(2.2)*,( ),*,( 0則稱迭代序列局部收斂均收斂于迭代序列使得如果xxxUxxU定義1定義1.)2 . 2( , 1|*)(| ,*)(,)(* 是局部收斂的則迭代法且內(nèi)有連續(xù)導數(shù)的某

10、鄰域在的不動點為迭代函數(shù)若 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?.211 . , ,

11、lim*,*,)( 11時為平方收斂超線性收斂；當時為當時迭代法為線性收斂；特別地，當收斂階則稱迭代過程為是不等于零的常數(shù)若誤差收斂于設(shè)迭代過程ppppCCeexxexxxpkkkkkkk定義2定義2.*, 0*)(0*)(*)(*)( ,*)()( )() 1(階收斂的附近是那么迭代過程在，并且連續(xù)導數(shù)階鄰近具有的根在如果迭代函數(shù)pxxxxxpxxxxpp 定理4定理4. ,0*)( , 0*)(; ,1|*)(|0平方收斂時當?shù)ň€性收斂時特別地，當 xxx3 3 迭代收斂的加速方法迭代收斂的加速方法一、埃特金加速收斂方法一、埃特金加速收斂方法),( 01xx由迭代公式校正一次得對于收斂

12、的迭代過程，).( 12xx再校正一次得則變化不大如果 ,)( ,)(Lxx(3.1) *).-(*)()(*),-(*)()(*112001xxLxxxxxxLxxxx* 1021xxxxxxxx,*2202022121xxxxxxxxxxx.2)( 222* 0122010012210220100200122102xxxxxxxxxxxxxxxxxxxxxxxxx)( )( :Aitken)(1212kkkkxxxx加速迭代方法于是得到埃特金* 1021xxxxxxxxkkkkkkkxxxxxxx122112)( (3.2) ./)( 22kkkxxx二、斯蒂芬森迭代法二、斯蒂芬森迭代法迭

13、代法蒂芬森加速技巧結(jié)合，得到斯把不動點迭代與埃特金)(Steffensen(3.3) ), 2 , 1 , 0( 2)(),( ),(21kxyzxyxxyzxykkkkkkkkkkk (3.4) ), 2 , 1 , 0( )( 1其中代法改寫為另一種不動點迭kxxkk(3.5) .)(2)()()( 2xxxxxxx.2)3 . 3()(*1) *( ,)()(* .)(*,)(* 階收斂的是迭代法的不動點，且斯蒂芬森為，則存在的不動點，設(shè)為反之，的不動點為則的不動點為若xxxxxxxxxx 定理5定理5. 1 01 313kkxxxx的迭代將斯蒂芬森法用于解 例5例5.,)3 . 3(

14、.1331有收斂結(jié)果計算現(xiàn)用發(fā)散指出：例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 構(gòu)造迭代法，)(3lnln2：1kkxxxgxx取對數(shù)得解解.2,4 , 3)(,4 , 3 , 132)(max ,2)( 43迭代收斂由定理當xx

15、xxxx.73307. 3 , 5 . 3 160 xx則進行加速若用,)3 . 3(kxkykzk0123.53.734443.733073.604143.733813.662023.733474 4 牛頓法牛頓法一、牛頓法及其收斂性一、牛頓法及其收斂性.牛頓迭代公式的推導:線性化展開做并假定近似根的設(shè)已知方程Taylorxfxxfkk, 0)(,0)( ),)()()( kkkxxxfxfxf(4.1) , 0)()( 0)( kkkxxxfxfxf近似表示為于是.4.2 .)()( ,其根為11) )牛頓迭代法(牛頓迭代法(切線法這就是）（則有計算公式記kkkkkxfxfxxx 牛頓法是

16、非線性方程線性化的方法。其計算步驟為: 給出初始近似根x0及精度。 計算 若x1-x0,則轉(zhuǎn)向;否則,轉(zhuǎn)向。 輸出滿足精度的根x1,結(jié)束。 牛頓法的計算框圖見圖7.4。 0010()()f xxxfx圖 7.4 .義牛頓迭代公式的幾何意.性牛頓迭代法的局部收斂,)()()( xfxfxx ,)()()()()()()(1)( 222xfxfxfxfxfxfxfx ,*)(*)(*)(0*)(*)(0*)(*)(*)( 42xfxfxfxfxfxfxfx ）（4.3 . *)(2*)( *)(*lim 21xfxfxxxxkkk 二、牛頓法應(yīng)用舉例二、牛頓法應(yīng)用舉例.0 的根用牛頓法求方程xex

17、例7例7. 5 . 0 ), 2 , 1 , 0( 1 01xkxexxxkxkkkk取初值解：牛頓迭代公式為kxk01230.50.571020.567160.56714，應(yīng)用牛頓法解二次方程對于給定正數(shù)0 , 2CxC例例8 8;115并求.00迭代公式皆平方收斂證明x(4.5) ). (212 21kkkkkkxCxxCxxx解：. 01 ,1150 xC初值取kxk012341010.75000010.72383710.72380510.723805三、簡化牛頓法與牛頓下山法三、簡化牛頓法與牛頓下山法 ., 2 , 1 , 0, 0 )( 1kCxCfxxkkk構(gòu)造迭代公式.,2)(0

18、 1, )(1)(公式局部收斂時即當xfCxfCxg(4.7) .)()( 01xfxfxxkkk簡化牛頓法：)(10 xfCkkkxxx)1 (11(4.12) , 2 , 1 , 0,)()( 1kxfxfxxkkkk牛頓下山法：. )()( 1,1kkxfxf逐次折半直到滿足其中下山因子.*5 . 101 33xxx附近的根在再求、 例例，計算結(jié)果如下：，折半，簡化牛頓法，：依次用牛頓法32/116 . 06 . 05 . 1000 xxx解解kxkxkxk f(xk)012341.51.347831.325201.324720.617.9發(fā)散0.6 -1.3841.140625 -0.

19、6566431.36181 0.18661.32628 0.006671.32472 0.0000086四、重根情形四、重根情形.(4.13) ,)()( )(*)()(,1仍平方收斂可將迭代法改為，牛頓法不是平方收斂重根情形kkkkmxfxfmxxxgxxxfm.0)(*,)(*)()()(*)()( )(*)(/ )()(的單根是故重根，則的是，若還可令xxxgxxxmgxgxxxmxfxxfxfx.(4.14) ,)()()()()( )(21仍平方收斂用牛頓法得對kkkkkkkxfxfxfxfxfxxx . 2*044 924xxx的二重根用上述三種方法求 例例；）牛頓法：（kkkkx

20、xxx42 121解解；）（kkkkxxxx22 )13. 4( 221.2)2( (4.14) 3221kkkkkxxxxx）（計算結(jié)果如下： kxk(1)(2)(3)0123x0 x1x2x31.51.4583333331.4366071431.4254976191.51.4166666671.4142156861.4142135621.51.4117647061.4142114381.4142135625 5 弦截法弦截法的迭代法。下面介紹避免求要計算外還每步除計算程用牛頓法求解非線性方)( ).()(, 0)(kkkxfxfxfxf單點弦截法 . 1).()()()( )(, )( )( 00010kkkkkkkkxxxxxfxfxfxxxxfxfxpxx，得到線性插值函數(shù)為插值節(jié)點和以.)()()()( 0)(0011稱為單點弦截法，得到令xxxfxfxfxxxpkk