數(shù)值計算課件——第二章非線性方程的數(shù)值解法

1、第二章第二章 非線性方程的數(shù)值解法非線性方程的數(shù)值解法非線性方程求解的基本問題：非線性方程求解的基本問題：根的個數(shù)；根的位置根的個數(shù)；根的位置。對于非線性方程，由于對于非線性方程，由于f(x)的多樣性，求其根尚無一的多樣性，求其根尚無一般的解析方法可以使用般的解析方法可以使用。求解方程的根，一般有兩種情形求解方程的根，一般有兩種情形：求出在給定范圍內(nèi)的某個根求出在給定范圍內(nèi)的某個根求出方程的全部根，而根的數(shù)目和位置事先不知道求出方程的全部根，而根的數(shù)目和位置事先不知道 本章介紹幾種方程求根的方法。這些方法大部分是要已本章介紹幾種方程求根的方法。這些方法大部分是要已知根的范圍，而且在此范圍內(nèi)只有

2、一個根知根的范圍，而且在此范圍內(nèi)只有一個根。求非線性方程根的一些常用方法：求非線性方程根的一些常用方法：區(qū)間分割法（逐步搜索法、區(qū)間分割法（逐步搜索法、 二分法）二分法）迭代法迭代法牛頓法牛頓法割線法割線法2.1區(qū)間搜索法區(qū)間搜索法預(yù)備知識：預(yù)備知識：方程的根：單根、重根。方程的根：單根、重根。 根的存在性定理：根的存在性定理：定理：定理：若若 f 在在a, b上連續(xù)，且上連續(xù)，且 f (a) f (b) 0，則，則 f 在在 (a, b) 上必有一根；若上必有一根；若 f 在在a, b上上連續(xù)且單調(diào)連續(xù)且單調(diào)則則 f 在在 (a, b) 上上有且僅有有且僅有一根。一根。定理定理 函數(shù)函數(shù) f

3、 (x)對于對于x* 有有f (x*) =0，但，但 則稱則稱 為方程的單根。如果有為方程的單根。如果有 但但 ，則稱，則稱 是方程是方程 的的 m重根。重根。 *()0fx*1)*()()()0mf xfxfx（()*()0mfx*x2.1.1逐步搜索法逐步搜索法思路：思路：先把區(qū)間先把區(qū)間a,b均分均分為為N等分，從初始值等分，從初始值x0=a開始，步長開始，步長h（ba）/N來增值。每跨一步進行一次根的搜索。來增值。每跨一步進行一次根的搜索。計算速度慢，一般用于確定根的位置計算速度慢，一般用于確定根的位置例：例：求連續(xù)函數(shù)求連續(xù)函數(shù) f(x) 在有根區(qū)間在有根區(qū)間a,b上的根。上的根。2

4、.1.2 二分法二分法思路思路：二分法的基本思想二分法的基本思想 就是逐步就是逐步對分對分區(qū)間區(qū)間,經(jīng)過對根的搜經(jīng)過對根的搜索，將有根區(qū)間的長度縮小到充分小，從而求出滿足精度的索，將有根區(qū)間的長度縮小到充分小，從而求出滿足精度的根根 的近似值。的近似值。二分法的步驟：二分法的步驟： 在有根區(qū)間在有根區(qū)間 取中點取中點 ，計算函數(shù)，計算函數(shù)值值 ，若，若 ，就得到方程的實根，就得到方程的實根 ，否則檢查否則檢查 與與 是否同號，如同號，說明待是否同號，如同號，說明待求的根求的根 在在 的右側(cè)，這時令的右側(cè)，這時令 ；如；如 在在 的左側(cè)，這時令的左側(cè)，這時令 ，這樣新的有根區(qū)間，這樣新的有根區(qū)間

5、 的長度為的長度為 之半。之半。 bax 210 2baf02 baf2*bax 0 xf af*x0 xbbxa 101,*x0 x011,xbaa 11,baba,ba,二分法二分法abx0 x1a1x*b1 11,ba 11,ba 11121bax *x1x 22,ba kkbababa,11 kkba , 11,ba ababkkk 21二分法二分法 kkkbax 21,210 xxx*x誤差誤差 分析分析： ababxxkkkk 1*2121 kxx* kkkbax 21*x二分法二分法優(yōu)點：優(yōu)點：簡單，簡單， 對對f (x) 要求不高要求不高(只要連續(xù)即可只要連續(xù)即可) .用二分法

6、求根，最好先給出用二分法求根，最好先給出 f (x) 草圖以確定根的大草圖以確定根的大概位置?；蛴盟阉鞒绦颍瑢⒏盼恢??；蛴盟阉鞒绦?，將a, b分為若干小區(qū)間，對每一分為若干小區(qū)間，對每一個滿足個滿足 f (ak)f (bk) 0 的區(qū)間調(diào)用二分法程序，可找出區(qū)的區(qū)間調(diào)用二分法程序，可找出區(qū)間間a, b內(nèi)的多個根，內(nèi)的多個根，二分法二分法二分法特點：二分法特點：缺點缺點：收斂慢（：收斂慢（ 等比級數(shù)等比級數(shù)） 無法求復(fù)根及偶重根無法求復(fù)根及偶重根 21對于給定的精度對于給定的精度 ,可估計二分法所需的步數(shù)可估計二分法所需的步數(shù) k ： 12lglglg21 abkabk求方程求方程f(xf(x)

7、=0)=0的根的二分法算法的根的二分法算法).(21)4(;endwhile.,;,0)()()2);(),(21)1|)3(;3,10)()()2(;,:)1(baxbxbaelsexabathenxfafifxfbaxbawhileelsebathenbfafifbaba 輸出輸出計算計算令令時做時做步步轉(zhuǎn)第轉(zhuǎn)第值值輸入輸入重新重新步步返回第返回第值及精度控制量值及精度控制量的的有根區(qū)間有根區(qū)間輸入輸入 2.2 2.2 簡單迭代法簡單迭代法2.2.1 2.2.1 迭代原理迭代原理2.2.2 2.2.2 迭代的收斂性迭代的收斂性2.2.3 2.2.3 迭代的收斂速度迭代的收斂速度2.2.4

8、2.2.4 迭代的加速迭代的加速2.2 簡單迭代法簡單迭代法f (x) = 0 x = (x)等價變換等價變換f (x) 的根的根 (x) 的不動點的不動點思思路路從一個初值從一個初值 x0 出發(fā)出發(fā), ,計算計算 x1 = (x0), x2 = (x1), , xk+1 = (xk), 若若 收斂，即存在收斂，即存在 x* 使得使得 ，只要，只要 連續(xù)，則連續(xù)，則 ，也就是也就是 x* = (x* )，即，即x* 是是 的根，也就是的根，也就是f 的根。的根。若若 xk發(fā)散，則迭代發(fā)散，則迭代 法失敗。法失敗。kx*limxxkk kkkkxx limlim12.2.1迭代法原理：迭代法原理

9、：3331101xxxxxx 迭代法迭代法：是一種逐次逼近的方法。是一種逐次逼近的方法。它是它是用某個用某個固定公式反復(fù)校正根的近似值，使之逐步精確，最后固定公式反復(fù)校正根的近似值，使之逐步精確，最后得到滿足精度要求的結(jié)果。得到滿足精度要求的結(jié)果。 xk+1 = (xk) 稱為稱為迭代格式，迭代格式， (x) 稱為稱為迭代函數(shù)迭代函數(shù)x0 x0 稱為稱為迭代初值迭代初值, , 數(shù)列數(shù)列 稱為稱為迭代序列迭代序列 kx 迭代法迭代法思想思想：將隱式方程將隱式方程 的求根問題歸的求根問題歸結(jié)為計算一組顯式結(jié)為計算一組顯式xk+1 = (xk) ，也就是說，迭代過程是，也就是說，迭代過程是一個逐步顯

10、式化的過程。一個逐步顯式化的過程。x = (x)例題例題 例2.2.1 試用迭代法求方程 在區(qū)間(1，2)內(nèi)的實根。 解：由 建立迭代關(guān)系 k=10,1,2,3.計算結(jié)果如下:31xx01)(3xxxf311kkxx例題例題n精確到小數(shù)點后五位5102132472. 1x例題n但如果由 建立迭代公式 仍取 ，則有 ， 顯然結(jié)果越來越大， 是發(fā)散序列1x3x,.2 , 1131kxxkk 5 . 10 x 2.3751x 12.392x kx 簡單迭代法的幾何意義：把求方程( ) 0f x 的根的問題， 轉(zhuǎn)化為求( )yxyx兩曲線的交點問題，交點的橫坐標就是方程的根*x。 xyy = xxyy

11、 = xxyy = xxyy = xx*x*x*x*y= (x)y= (x)y= (x)y= (x)x0p0 x1p1 x0p0 x1p1 x0p0 x1p1x0p0 x1p1簡單迭代法簡單迭代法收斂定理收斂定理 考慮方程考慮方程 x =(x), (x)在在a, b上連續(xù)上連續(xù), 若若( I ) 對所有對所有 x a, b ，有，有 (x) a, b；( II ) 存在存在 0 L 1 ，使所有使所有 x a, b 有有| (x) | L 1 。則：則：1）方程）方程x = (x)在在a, b上的解上的解x*存在且唯一。存在且唯一。 2）任取）任取 x0 a, b，由迭代過程，由迭代過程 xk

12、+1 = (xk) 收斂于收斂于x*簡單迭代法簡單迭代法推論推論 驗后誤差估計：驗后誤差估計：|1|*|1 kkkxxLLxx|1|*|01xxLLxxkk 誤差估計式：誤差估計式：驗前誤差估計：驗前誤差估計：證明：證明： (x) 在在a, b上有根？上有根？令令xxx )()( bxa )( ,0)()( aaa 0)()( bbb )(x 有根有根 根唯一？根唯一？反證：若不然，設(shè)還有反證：若不然，設(shè)還有 ，則，則)(xx ),*( )()(*)(xxxx xx*在在和和之間。之間。 *xx0)(1)( xx* 而而xx*1| )(| 當當k 時，時， xk 收斂到收斂到 x* ？ |*|

13、kxx|*| )(| )(*)(|11 kkxxxx 0|*|.|*|01 xxLxxLkk 3 簡單迭代法簡單迭代法 xx 有根有根L1| )1 (1 kkkxxLxxL?|1|*|1 kkkxxLLxx|)|*(| |*|111 kkkkkkkkxxxxLxxxxLxxLxx ?|1|*|01xxLLxxkk | | )(| )()(|2121211 kkkkkkkkxxLxxxxxx 可用可用 來來控制收斂精度控制收斂精度|1 kkxxL 越越 收斂越快收斂越快小小定理條件非必要條件，對某些問題在區(qū)間定理條件非必要條件，對某些問題在區(qū)間a, b上上不不滿足滿足| (x) | L 1 ，迭

14、代也收斂。，迭代也收斂。 實際應(yīng)用中還是用此定理判斷收斂性，當不滿足收實際應(yīng)用中還是用此定理判斷收斂性，當不滿足收斂條件時，改變迭代公式使之滿足。斂條件時，改變迭代公式使之滿足。3 簡單迭代法簡單迭代法|1 .|1|1|*|012121xxLLxxLLxxLLxxkkkkkk 2.2.3 迭代法局部收斂性迭代法局部收斂性1 *x bax, bax, *:xx kkxx 1 0 x kkxx 1*x*x*x*x 1* x *:xx 1 Lx *xxxx *xx x *xxxxLxx kkxx 1 0 x x xx *x 1* x kkxx 1由于在實際應(yīng)用中根由于在實際應(yīng)用中根 x* 事先不知道

15、，故條件事先不知道，故條件 | (x* )| 1無法驗證。但已知根的初值無法驗證。但已知根的初值x0在根在根 x*鄰域，又根據(jù)鄰域，又根據(jù) (x)的的連續(xù)性，則可采用連續(xù)性，則可采用 | (x0 )| 1 來代替來代替| (x* )| 1，判斷迭代的收斂性。，判斷迭代的收斂性。 *x kkxx 1 xx *xxekk 1 pp 0 ccceepkkk 1limkxp10 , 1 cp2 p1 pc*x kkxx 1p xp 0, 0*1* xxxxpp *xQ: 如何實際確定收斂階？如何實際確定收斂階？例題n例：例： 證明函數(shù) 在區(qū)間1，2上滿足迭代收斂條件。n證明：31)x(x上嚴格單調(diào)增函

16、數(shù)。是區(qū)間所以因為,)(2 , 1 0) 1(31)x(32baxxx例題 2 , 1 1431|) 1(31| )(|332xLxx又23)2(12) 1 (33，而）。滿足條件（，所以即1)(2 , 1 )2(),1 (x）。滿足條件（所以2)(x滿滿足足收收斂斂原原理理。在在故故2 , 1 1)x(3 x 例題n若取迭代函數(shù) ， 不滿足收斂定理，故不能肯定 收斂到方程的根。 1)x(3 x2 , 1 3|3| )(|2xxx因為,.1 , 0)(1nxxnn Aitken 加速：加速：簡單迭代法簡單迭代法xyy = xy = (x)x*x0P(x0, x1)x1x2x P(x1, x2)

17、012202201220102)(2)(xxxxxxxxxxxxx 一般地，有：一般地，有：KKKKKKKxxxxxxx 12212)(.),(,),(,),(),(,34123012010 xxxxxxxxxxx 比比 收斂得略快。收斂得略快。 Kx Kx Steffensen 加速：加速：.,),(), (,),(),(,01201012010 xxxxxxxxxxx 2.3 2.3 牛頓迭代法牛頓迭代法2.3.1 2.3.1 迭代公式的建立迭代公式的建立2.3.2 2.3.2 牛頓迭代法的收斂情況牛頓迭代法的收斂情況2.3.3 2.3.3 牛頓迭代法的修正法牛頓迭代法的修正法2.3 牛頓

18、法牛頓法原理：原理：將非線性方程線性化將非線性方程線性化 Taylor 展開展開取取 x0 x*，將將 f (x)在在 x0 做一階做一階Taylor展開展開:20000)(! 2)()()()(xxfxxxfxfxf ， 在在 x0 和和 x* 之之間間 。將將 (x* x0)2 看成高階小量，則有：看成高階小量，則有：)*)()(*)(0000 xxxfxfxf )()(*000 xfxfxx 線性化線性化xyx*x0 x1)()(1kkkkxfxfxx 迭代公式迭代公式： )()(xfxfxx 迭代函數(shù)迭代函數(shù)：牛頓切線法牛頓切線法2.3.2牛頓切線法的收斂情況牛頓切線法的收斂情況 定理

19、定理 （局部收斂性局部收斂性）設(shè)函數(shù)設(shè)函數(shù) 在包含在包含 的某鄰的某鄰域內(nèi)有域內(nèi)有 階連續(xù)導(dǎo)數(shù)，階連續(xù)導(dǎo)數(shù)， 是方程是方程 的的單根單根，則當初值則當初值 充分接近充分接近 時，牛頓切線法收斂，且至時，牛頓切線法收斂，且至少為二階收斂。并有少為二階收斂。并有*xk12kkxx*f ( x*)lim( xx*)2 f ( x*) xf 2 p*x 0 xf0 x*x這里這里單根單根意味著：意味著：f ( x*)0 牛頓切線法牛頓切線法2.3.2牛頓迭代法的收斂情況牛頓迭代法的收斂情況 定理定理設(shè)函數(shù)設(shè)函數(shù) 滿足滿足 且且 在在 鄰域連續(xù)，則牛頓迭代法在鄰域連續(xù)，則牛頓迭代法在 收斂，且至少為二收

20、斂，且至少為二階收斂。并有階收斂。并有f ( x*)0, f ( x )0, *)(2*)(*)(*lim21xfxfxxxxkkk xf*xf ( x )*x牛頓切線法牛頓切線法證明：證明：牛頓法牛頓法 事實上是一種特殊的不動點迭代事實上是一種特殊的不動點迭代 其中其中 ，則，則)()()(xfxfxx 10*)(*)(*)(*)(2xfxfxfx 收斂收斂由由 Taylor 展開：展開：2)*(!2)()*)()(*)(0kkkkkxxfxxxfxfxf 2)*()(! 2)()()(*kkkkkkxxxffxfxfxx 1 kx)(2)(*)(*21kkkkxffxxxx 只要只要f (

21、x*) 0在在單根單根 附近收斂快附近收斂快 k 12kkxx*f ( x*)lim( xx*)2 f ( x*) 牛頓切線法牛頓切線法牛頓法收斂性依賴于牛頓法收斂性依賴于x0 的選取。的選取。x*x0 x0 x0具有具有局部恒收斂性局部恒收斂性，收斂性依賴于，收斂性依賴于初值初值 的選取。的選取。收斂性好收斂性好（至少平方收斂）（至少平方收斂）每次計算要計算導(dǎo)數(shù)，每次計算要計算導(dǎo)數(shù)，效率不高效率不高牛頓法特點：牛頓法特點：例題例題例1: 用Newton法求 的近似解。（取8位有效數(shù)字）。解：由零點定理。0cos)(xxxf內(nèi)有根。在)2, 0(0cosxx迭代公式得及由Newtonxxfsi

22、n1)(,.1 , 0sin1cos1nxxxxxnnnnn例題085133739. 0739085133. 0739085133. 0739085178. 0;73936133. 044*43210 xxxxxxx故取得取例題n例2: 用Newton法計算 。解：220)(2aaxxf其中迭代公式得及由Newtonxxf2)(,.1 , 0)2(212221nxxxxxxnnnnnn。有十位有效數(shù)的近似值是已的精確值相比，。與，則取332102414213562. 1414215686. 11.416666675 . 1xxxxx牛頓迭代法算法框圖牛頓迭代法算法框圖Newton迭代法算法迭代

23、法算法。輸出）轉(zhuǎn)（做輸入1101001001000:)4(;2) 3;)2;/) 1|while(3);();()2(;,) 1 (xendwhilexxffxxfxffxffx牛頓切線法改進牛頓切線法改進牛頓法的改進與推廣牛頓法的改進與推廣 改進一：改進一：重根時的收斂速度及改進：重根時的收斂速度及改進：Q1: 若若 ，牛頓法牛頓法是否仍收斂？是否仍收斂？0*)( xf設(shè)設(shè) x* 是是 f 的的 n 重根，則：重根，則： 且且 。)(*)()(xqxxxfn 0*)( xq因為因為牛頓法事實上是一種特殊的不動點迭代，牛頓法事實上是一種特殊的不動點迭代，其中其中 ，則，則)()()(xfxfx

24、x 22f ( x*)f ( x*) f ( x*)|( x*)|1f ( x*) 111n A1: 有局部收斂性，收斂慢（有局部收斂性，收斂慢（線性收斂線性收斂）。）。Q2: 如何加速重根的收斂？如何加速重根的收斂？)()( )(xfxfxx A2: 修正修正迭代格式（迭代格式（平方收斂平方收斂）n n證明過程證明過程見書見書p42 改進二：改進二： 牛頓牛頓下山法下山法擴大初值范圍的修正牛頓法擴大初值范圍的修正牛頓法： 原理原理：若由若由 xk 得到的得到的 xk+1 不能使不能使 | f | 減小，則在減小，則在 xk 和和 xk+1 之間找一個更好的點之間找一個更好的點 ，使得，使得

25、。1 kx)()(1kkxfxf xkxk+1,)1(1kkxx 1, 0 )()()1 ()()(1kkkkkkkkxfxfxxxfxfxx 通過適當選取的通過適當選取的 保證函數(shù)值能單調(diào)下降保證函數(shù)值能單調(diào)下降牛頓切線法改進牛頓切線法改進下山法：下山法：迭代過程中保證函數(shù)值單調(diào)下降，即迭代過程中保證函數(shù)值單調(diào)下降，即)()(1kkxfxf 牛頓下山法：牛頓下山法：將牛頓法與下山法結(jié)合使用的算法將牛頓法與下山法結(jié)合使用的算法 下山因子下山因子牛頓牛頓下山法幾點討論下山法幾點討論實用中從實用中從 = 1開始反復(fù)將開始反復(fù)將 減半計算。一旦單調(diào)下降則稱減半計算。一旦單調(diào)下降則稱“下山成功下山成功

26、”。反之則稱。反之則稱“下山失敗下山失敗”，需另選初值，需另選初值x0計算。計算。牛頓切線法改進牛頓切線法改進當當 1時。牛頓下山法只有線性收斂速度，但對初值的選時。牛頓下山法只有線性收斂速度，但對初值的選取卻可放的很寬。常用牛頓下山法選取初值。取卻可放的很寬。常用牛頓下山法選取初值。實用中常用牛頓下山法選取初值。為加快收斂速度，轉(zhuǎn)入牛實用中常用牛頓下山法選取初值。為加快收斂速度，轉(zhuǎn)入牛頓法來求解根的精確值。頓法來求解根的精確值。牛頓法每一步要計算牛頓法每一步要計算 f 和和 f ，相當于，相當于2個函數(shù)值，且有些個函數(shù)值，且有些導(dǎo)數(shù)難求。為了避開導(dǎo)數(shù)的計算，用導(dǎo)數(shù)難求。為了避開導(dǎo)數(shù)的計算，用

27、差商差商代替代替導(dǎo)數(shù)。導(dǎo)數(shù)。x0切線切線 割線割線 切線斜率切線斜率 割線斜率割線斜率00)()()(xxxfxfxfkkk 2.42.4弦截法弦截法 ：x2x100)()(xxxfxfkk )()()()(001xxxfxfxfxxkkkkk kkkkxfxfxx1 用用割線斜率割線斜率（差商）替換（差商）替換切線斜率切線斜率，代入牛頓法迭代公式：，代入牛頓法迭代公式：上式中，固定弦的一個端點（上式中，固定弦的一個端點（x x0 0, ,f f( (x0) )），而另一端點變動，），而另一端點變動，稱為稱為單點弦法。單點弦法。2.4.1 2.4.1 單點弦法單點弦法：單點弦法幾何意義單點弦法

28、幾何意義*0*00*0f ( x )f ( x )( x )1( xx )1f ( x )f ( x )f ( x )xx 因為因為f(xf(x* *) ) = 0 = 0，故求導(dǎo)數(shù)得，故求導(dǎo)數(shù)得所以所以0 0 (x(x* *) ) 1 1，所以，所以單點弦法單點弦法僅為僅為線性收斂線性收斂。單點弦法收斂速度單點弦法收斂速度：00f ( x )( x )x( xx )f ( x )f ( x ) 迭代函數(shù)迭代函數(shù)：*0*0f ( x )f ( x )xx *x當初值當初值x x0 0充分接近充分接近 時時很接近很接近f(xf(x* *) )2.4.2 2.4.2 雙點弦法雙點弦法：為了加快收斂

29、速度為了加快收斂速度，弦的兩個端點都在變動，稱為弦的兩個端點都在變動，稱為雙點弦法雙點弦法或稱或稱快速弦截法?？焖傧医胤ā５鷷r需要迭代時需要2個初值個初值 xk 和和 xk1。 111 kkkkkkkxxxfxfxfxx雙點弦法迭代公式雙點弦法迭代公式：雙點弦法幾何意義雙點弦法幾何意義P1P2雙點弦法收斂速度雙點弦法收斂速度： 雙點弦截法的收斂性與牛頓迭代法一樣，即在雙點弦截法的收斂性與牛頓迭代法一樣，即在根的某個鄰域內(nèi)，根的某個鄰域內(nèi)，f(xf(x) )有直至二階的連續(xù)導(dǎo)數(shù)，且有直至二階的連續(xù)導(dǎo)數(shù)，且f(xf(x* *) ) 0 0，具有局部收斂性，同時在鄰域任取初，具有局部收斂性，同時在鄰域任取初值值x0 x0、x1x1，迭代均收斂。，迭代均收斂。 可以證明，雙點弦截法具有超線性斂速度，可以證明，雙點弦截法具有超線性斂速度，收斂的階為：收斂的階為： 1151.6182 用用Newton法和弦截法解下面方程的根，并比較法和弦截法解下面方程的根，并比較0133xx13)(3xxxf設(shè)33)(2xxf由由Newton法法由弦截法由弦截法)()()()(111kkkkkkkxxxfxfxfxx)()(1kkkkxfxfxx331323kkkkxxxxx0=0.5;x1