非線性方程的數(shù)值解法

1、第二章第二章 非線性方程的數(shù)值解法非線性方程的數(shù)值解法 /* Numerical Solutions of Nonlinear Equations*/本章主要內(nèi)容：本章主要內(nèi)容：1 1、二分法、二分法2 2、不動(dòng)點(diǎn)迭代的構(gòu)造及其收斂性判定、不動(dòng)點(diǎn)迭代的構(gòu)造及其收斂性判定（重點(diǎn)）（重點(diǎn)）3 3、Newton和和Steffensen迭代迭代（重點(diǎn)）（重點(diǎn)）4 4、割線法、割線法5 5、非線性方程組的迭代解法、非線性方程組的迭代解法歷史背景歷史背景 代數(shù)方程的求根問(wèn)題是一個(gè)古老的數(shù)學(xué)問(wèn)題。理論上，代數(shù)方程的求根問(wèn)題是一個(gè)古老的數(shù)學(xué)問(wèn)題。理論上， 次代數(shù)方程在復(fù)數(shù)域內(nèi)一定有次代數(shù)方程在復(fù)數(shù)域內(nèi)一定有

2、個(gè)根個(gè)根( (考慮重?cái)?shù)考慮重?cái)?shù)) )。早在。早在1616世紀(jì)世紀(jì)就找到了三次、四次方程的求根公式，但直到就找到了三次、四次方程的求根公式，但直到1919世紀(jì)才證明大世紀(jì)才證明大于等于于等于5 5次的一般代數(shù)方程式不能用代數(shù)公式求解，而對(duì)于超次的一般代數(shù)方程式不能用代數(shù)公式求解，而對(duì)于超越方程就復(fù)雜的多，如果有解，其解可能是一個(gè)或幾個(gè)，也可越方程就復(fù)雜的多，如果有解，其解可能是一個(gè)或幾個(gè)，也可能是無(wú)窮多個(gè)。一般也不存在根的解析表達(dá)式。因此需要研究能是無(wú)窮多個(gè)。一般也不存在根的解析表達(dá)式。因此需要研究數(shù)值方法求得滿足一定精度要求的根的近似解。數(shù)值方法求得滿足一定精度要求的根的近似解。 nn求方程求

3、方程 幾何意義幾何意義0( )f x 基本定理基本定理2 1 .Th 如果函數(shù)如果函數(shù) 在在 上連續(xù)，且上連續(xù)，且則至少有一個(gè)數(shù)則至少有一個(gè)數(shù) 使得使得 ，若同時(shí)，若同時(shí) 的一階的一階導(dǎo)數(shù)導(dǎo)數(shù) 在在 內(nèi)存在且保持定號(hào)，即內(nèi)存在且保持定號(hào)，即 ( (或或 ) )則這樣的則這樣的 在在 內(nèi)唯一。內(nèi)唯一。 ( )f x , a b( ) ( )0f a f b ( )0f ( )fx ( )0fx , a b( )f x , a b0( )fx abx*( )yf x oxy1 1 二分法二分法 /* Bisection Method */原理：原理：若若 f Ca, b，且，且 f (a) f (

4、b) 0，則，則 f 在在 (a, b) 上至上至少有一實(shí)根。少有一實(shí)根。基本思想：基本思想：逐步將區(qū)間分半，通過(guò)判別區(qū)間端點(diǎn)函數(shù)值的符號(hào)，逐步將區(qū)間分半，通過(guò)判別區(qū)間端點(diǎn)函數(shù)值的符號(hào)，進(jìn)一步搜索有根區(qū)間，將有根區(qū)間縮小到充分小，從而求進(jìn)一步搜索有根區(qū)間，將有根區(qū)間縮小到充分小，從而求 出滿足給定精度的根出滿足給定精度的根 的近似值。的近似值。x )(xfy aboxy x 21bax 1b 2112xba 2a 3a 1a32xba 2b3b11,a b22,a b33,a b以此類推以此類推終止法則？終止法則？abx1x2abWhen to stop?11xxkk 2()kf x 或或不能

5、保證不能保證 x 的精的精度度x* 2xx* 二分法算法二分法算法給定區(qū)間給定區(qū)間a,b ，求，求f(x)=0 在該區(qū)間上的根在該區(qū)間上的根x. .輸入輸入: : a和和b; ; 容許誤差容許誤差 TOL; ; 最大對(duì)分次數(shù)最大對(duì)分次數(shù) Nmax.輸出輸出: 近似根近似根 x.Step 1 Set k = 1;Step 2 Compute x=f(a+b)/2);Step 3 While ( k Nmax) do steps 4-6 Step 4 If |x| TOL , STOP; Output the solution x. Step 5 If x*f(a)0 , Set b=x; Els

6、e Set a=x; Step 6 Set k=k+1; Compute x=f(a+b)/2);Go To Step 3 ;Step 7 Output the solution of equation: x; STOP. 11111 222, ,kkkkkabxxxbak 且3、 12lnlnlnbak 由二分法的過(guò)程可知：由二分法的過(guò)程可知：4、對(duì)分次數(shù)的計(jì)算公式：對(duì)分次數(shù)的計(jì)算公式： 11,kka ba bab 0,kkkkf af bxab 1、 111122kkkkkbababa 2、 1112kkxxba 令令誤差誤差 分析分析2 2 .Th解解：211 510 ,.;ab，12l

7、n()lnlnban 21 5 11012ln( .)lnln 4.645n例例1 1：用二分法求方程用二分法求方程 在區(qū)間在區(qū)間 上的上的根，誤差限為根，誤差限為 ，問(wèn)至少需對(duì)分多少次？，問(wèn)至少需對(duì)分多少次？310 xx 1 1 5 , . 210 簡(jiǎn)單簡(jiǎn)單; 對(duì)對(duì)f (x) 要求不高要求不高(只要連續(xù)即可只要連續(xù)即可) .無(wú)法求復(fù)根及無(wú)法求復(fù)根及偶重根偶重根收斂慢收斂慢 用二分法求根，最好先給出用二分法求根，最好先給出 f (x) 草圖以確定根的大草圖以確定根的大概位置?；蛴盟阉鞒绦颍瑢⒏盼恢谩；蛴盟阉鞒绦颍瑢, b分為若干小區(qū)間，對(duì)每一分為若干小區(qū)間，對(duì)每一個(gè)滿足個(gè)滿足 f (ak)f

8、 (bk) 0 的區(qū)間調(diào)用二分法程序，可找出區(qū)的區(qū)間調(diào)用二分法程序，可找出區(qū)間間a, b內(nèi)的多個(gè)根，且不必要求內(nèi)的多個(gè)根，且不必要求 f (a)f (b) 0 。優(yōu)點(diǎn)優(yōu)點(diǎn)缺點(diǎn)缺點(diǎn)2 迭代法的理論迭代法的理論 /* Theory of Iteration Method*/f (x) = 0 x = g (x)（迭代函數(shù)）（迭代函數(shù)）等價(jià)變換等價(jià)變換思思路路從一個(gè)初值從一個(gè)初值 x0 出發(fā)，計(jì)算出發(fā)，計(jì)算 x1 = g(x0), x2 = g(x1), , xk+1 = g(xk), 若若 收斂，即存在收斂，即存在 x* 使得使得 ，且，且 g 連續(xù)，則由連續(xù)，則由 可可知知 x* = g(x*

9、)，即，即x* 是是 g 的不動(dòng)點(diǎn)，也就是的不動(dòng)點(diǎn)，也就是f 的根。的根。 0kkx*limxxkk kkkkxgx limlim1看起來(lái)很簡(jiǎn)單，令人看起來(lái)很簡(jiǎn)單，令人有點(diǎn)不相信，那么問(wèn)有點(diǎn)不相信，那么問(wèn)題是什么呢？題是什么呢？如何判定這種方法如何判定這種方法是收斂的呢？是收斂的呢？f (x) 的根的根x g (x) 的不動(dòng)點(diǎn)的不動(dòng)點(diǎn)x 10 1 2(), , ,(*)kkxg xk 一、不動(dòng)點(diǎn)迭代一、不動(dòng)點(diǎn)迭代 /*Fixed-Point Iteration*/xyy = xxyy = xxyy = xxyy = xx*x*x*x*y=g(x)y=g(x)y=g(x)y=g(x)x0p0 x

10、1p1 x0p0 x1p1 x0p0 x1p1x0p0 x1p1幾何意義幾何意義例例2： 已知方程已知方程 在在 上有一個(gè)根（正根）上有一個(gè)根（正根）324100 xx1 2 , 下面選取下面選取5 5種迭代格式：種迭代格式：1 1、32410 xxxx 即即32410( )g xxxx 2 2、23410 xx 1321102xx 1321102g xx即即3 3、即即2104xxx 12104xxx 12104g xxx4 4、即即12104xx 12104g xx 5 5、即即xxxxxx83104223( )( )( )f xg xxfx 取取01 5 .x 計(jì)算結(jié)果如下：計(jì)算結(jié)果如下

11、：123840875673246972010275 10.xxxx 法法1 11234451113484013673813649613652613751713652251365230013.xxxxxxx 法法4 412123081650299691865086.( .)xxx 法法3 3123445112912869514025413454613751713751713751713651378211365230013.xxxxxxxx 法法2 2123413733313652613652300141365230013.xxxx 法法5 5Lipschitz條件成條件成立的充分條件立的充分條件

12、2 3 .Th 考慮方程考慮方程 x = g(x), 若若( I ) 當(dāng)當(dāng) x a, b 時(shí)，時(shí)， g(x) a, b；( II ) 0 L 1 使得使得 對(duì)對(duì) x a, b 成立。成立。則任取則任取 x0 a, b，由，由 xk+1 = g(xk) 得到的序列得到的序列 收斂收斂于于g(x) 在在a, b上的唯一不動(dòng)點(diǎn)。并且有誤差估計(jì)式：上的唯一不動(dòng)點(diǎn)。并且有誤差估計(jì)式： 0kkx|11|*|1kkkxxLxx 101|*|kkLxxxxL ( k = 1, 2, )且存在極限且存在極限 *lim1xgxxxxkkk 1( )g xL ( )g x 連續(xù)時(shí)連續(xù)時(shí)證明：證明： g(x) 在在a

13、, b上存在不動(dòng)點(diǎn)？上存在不動(dòng)點(diǎn)？令令xxgxf )()(bxga )(,0)()( aagaf0)()( bbgbf)(xf有根有根 不動(dòng)點(diǎn)唯一？不動(dòng)點(diǎn)唯一？反證：若不然，設(shè)還有反證：若不然，設(shè)還有 ，則，則)(xgx ),*( )()(*)(xxgxgxg xx*在在和和之間。之間。 *xx0)(1)( gxx*而而xxg*1| )(| 當(dāng)當(dāng)k 時(shí)，時(shí)， xk 收斂到收斂到 x* ？ |*|kxx|*| )(| )(*)(|111 kkkxxgxgxg0|*|.|*|01 xxLxxLkk L 越越 收斂越快收斂越快可用可用 來(lái)來(lái)控制收斂精度控制收斂精度|1kkxx ?|11|*|1kkk

14、xxLxx |*|*|*|*|11kkkkkkxxLxxxxxxxx ?|1|*|01xxLLxxkk |.| )(| )()(|011111xxLxxLxxgxgxgxxkkkkkkkkkk 1lim()?kkkxxg xxx *)(*)*)(lim*lim1xgxxxxgxxxxkkkkkkk 小小條件條件 ( II ) 可改為可改為 在在a, b 滿足滿足Lipschitz條件條件,定理結(jié)論仍然成立定理結(jié)論仍然成立(定理定理2.3)。 算法算法: : 不動(dòng)點(diǎn)迭代不動(dòng)點(diǎn)迭代給定初始近似值給定初始近似值 x0 ，求，求x = g(x) 的解的解. .輸入輸入: : 初始近似值初始近似值 x0

15、; ; 容許誤差容許誤差 TOL; ; 最大迭代次數(shù)最大迭代次數(shù) Nmax.輸出輸出: 近似解近似解 x 或失敗信息或失敗信息.Step 1 Set i = 1;Step 2 While ( i Nmax) do steps 3-6Step 3 Set x = g(x0); /* 計(jì)算計(jì)算 xi */Step 4 If | x x0 | 1)(1)階收斂的方法，階收斂的方法，改用改用Stefensen迭代方法優(yōu)點(diǎn)不多。迭代方法優(yōu)點(diǎn)不多。取取01 5.x 計(jì)算結(jié)果如下：計(jì)算結(jié)果如下：12341361886136522813652301365230.xxxx 法法2 2原原迭迭代代次次數(shù)數(shù)2912

16、34513368751363130136522013652301365230.xxxxx 法法3 3原原來(lái)來(lái)不不收收斂斂12345670934944100503310754631145492121343712757711325977.xxxxxxx 法法1 18910111355744136458213652271365230.xxxx 原原來(lái)來(lái)不不收收斂斂返回返回0()()f xg xx4 牛頓法牛頓法 /* Newton - Raphson Method */一、牛頓迭代公式的推導(dǎo)一、牛頓迭代公式的推導(dǎo)1、待定參數(shù)法待定參數(shù)法不動(dòng)點(diǎn)迭代的不動(dòng)點(diǎn)迭代的關(guān)鍵關(guān)鍵是構(gòu)造滿足是構(gòu)造滿足收斂條件收斂

17、條件的的迭代函數(shù)迭代函數(shù) ( )g x一種一種自然的選擇自然的選擇是令是令0( )( )()g xxcf xc為了加速不動(dòng)點(diǎn)迭代的收斂過(guò)程，應(yīng)盡可能使迭代函數(shù)為了加速不動(dòng)點(diǎn)迭代的收斂過(guò)程，應(yīng)盡可能使迭代函數(shù) 在在 處有處有更多階導(dǎo)數(shù)等于零更多階導(dǎo)數(shù)等于零（定理（定理2.52.5）。）。 ( )g xxx 1()cfx 1()()g xcfx 令令0 110()() ()()()()()g xh xf xh xfxh xfx 10()()()h xfxfx 現(xiàn)設(shè)現(xiàn)設(shè)( )( ) ( )g xxh x f x10( )( )( )h xfxfx 取取0()g x 滿足滿足因此，選取迭代函數(shù)因此，選

18、取迭代函數(shù)( )( )( )f xg xxfx Newton Raphson迭代格式迭代格式10 1 2(), , ,()kkkkf xxxkfx 稱之為稱之為牛頓牛頓拉夫森拉夫森方法，簡(jiǎn)稱方法，簡(jiǎn)稱牛頓法牛頓法原理：原理：將非線性方程將非線性方程線性化線性化取取 x0 x*，將將 f (x)在在 x0 做一階做一階Taylor展開(kāi)展開(kāi):20000)(! 2)()()()(xxfxxxfxfxf ， 在在 x0 和和 x 之間之間2、Taylor展開(kāi)法展開(kāi)法/* Taylors expansion Method */將將 (x* x0)2 看成看成高階小量高階小量，則有：，則有：)*)()(*

19、)(0000 xxxfxfxf )()(*000 xfxfxx xyx*x010 1 2(), , ,()kkkkf xxxkfx 只要只要 f C1，每一步迭代都有，每一步迭代都有 而且而且 ，則，則 x*就是就是 f 的根。的根。limkkxx 0()kf x 1x000()()()yf xfxxx 與與x軸交點(diǎn)的橫坐標(biāo)軸交點(diǎn)的橫坐標(biāo)1x2x無(wú)開(kāi)方運(yùn)算，又無(wú)除法運(yùn)算。無(wú)開(kāi)方運(yùn)算，又無(wú)除法運(yùn)算。例例1 1：寫(xiě)出求寫(xiě)出求 的的Newton迭代格式；迭代格式； 寫(xiě)出求寫(xiě)出求 的的Newton迭代格式迭代格式, ,要求公式中既要求公式中既0()a a 10()aa 解：解：等價(jià)于求方程等價(jià)于求方程

20、 的正根的正根200( )()f xxaa2110 1 222()(), , ,()kkkkkkkkkf xxaaxxxxkfxxx 2( )fxx 解法一：解法一：等價(jià)于求方程等價(jià)于求方程 的正根的正根2100( )()()f xxaa12( )()fxxa 21112()()()()kkkkkkkxf xaxxxfxxa 110 1 22(), , ,kxka 32( )fxx 解法二：解法二：等價(jià)于求方程等價(jià)于求方程 的正根的正根2100( )()f xaax21312()()kkkkkkkaf xxxxxfxx 2130 1 22(), , ,kkxaxk Th2.7 （局部收斂性局部

21、收斂性） 設(shè)設(shè) x* 為方程為方程 f (x) =0的根，在包含的根，在包含x*的某個(gè)開(kāi)區(qū)間內(nèi)的某個(gè)開(kāi)區(qū)間內(nèi) 連續(xù)，連續(xù)， 且且 ，則存在，則存在 x* 的鄰域的鄰域 ，使得任取初值使得任取初值 ，由，由Newtons Method產(chǎn)生的序列產(chǎn)生的序列 以不低于以不低于二階二階的收斂速度收斂于的收斂速度收斂于x*，且，且( *),Bxxx *)(0 xBx ( )fx 0( )fx kx122*( *)lim(*)( *)kkkxxfxxxfx 122*( *)lim(*)( *)kkkxxfxxxfx 221( )( )( )( )( )fxf x fxgxfx 證明：證明：Newtons

22、Method 事實(shí)上是一種事實(shí)上是一種特殊的不動(dòng)點(diǎn)迭代特殊的不動(dòng)點(diǎn)迭代 其中其中 ，則，則)()()(xfxfxxg fxf xgxfx2( *)( *)( *)0( *) 收斂收斂由由 Taylor 展開(kāi)：展開(kāi)：2)*(!2)()*)()(*)(0kkkkkxxfxxxfxfxf 2)*()(! 2)()()(*kkkkkkxxxffxfxfxx 1 kx122*()( *)()kkkkxxfxxfx 在在單根單根 /*simple root */ 附近收斂快附近收斂快 只要只要 ，則令，則令 可得結(jié)論?？傻媒Y(jié)論。 k0()fx Th2.5有根有根根唯一根唯一產(chǎn)生的序列產(chǎn)生的序列單調(diào)有單調(diào)有

23、界界保證收斂保證收斂證明：證明：因?yàn)橐驗(yàn)閒 C2a, b，由（，由（1）和（）和（2）知）知f (x) 在在a, b內(nèi)有內(nèi)有唯一唯一根根x 下面由條件（下面由條件（1）、（）、（2）分）分4種情況討論：種情況討論：000( ),( ); , ,( )f af bxa bfx 000( ),( ); , ,( )f af bxa bfx 000( ),( ); , ,( )f af bxa bfx 000( ),( ); , ,( )f af bxa bfx 僅證明僅證明第一種第一種情況，其它情況類似討論情況，其它情況類似討論Th2.8 （收斂的充分條件收斂的充分條件）設(shè)設(shè)f (x) =0 且且

24、f C2a, b，若，若(1) f (a) f (b) 0；(2) 在整個(gè)在整個(gè)a, b上上 不變號(hào)且不變號(hào)且 ；(3) 選取選取 x0 a, b 使得使得 ；則則Newtons Method產(chǎn)生的序列產(chǎn)生的序列 xk 收斂于方程的根收斂于方程的根 ,f 0( )fx 000()()f xfx x 且且122*( *)lim(*)( *)kkkxxfxxxfx 由中值定理，由中值定理， 使得使得 , a b 0( )( )( )f bf afba 因此因此0( ) , fxxa b 即即 在在 上單調(diào)遞增上單調(diào)遞增( )f x , a b由由0000 , ,()()xa bf xfx 00()

25、f x0 xx 01000()()f xxxxfx 另一方面，由另一方面，由Taylor展開(kāi)得展開(kāi)得2000012( )()()()( )()!f xf xfxxxfxx 介于介于 、 之間之間 x0 x20000102()()()()( )()!f xf xfxxxfxx 20000012()( )()()()f xfxxxxfxfx 210012( )()()fxxxfx 1xx 0 x 重復(fù)以上過(guò)程，可得（重復(fù)以上過(guò)程，可得（歸納法歸納法）1kkxxx （自己證）（自己證）因此，數(shù)列因此，數(shù)列 單調(diào)下降且有下界單調(diào)下降且有下界 kxx 令令limkkxl 1()( )limlim()(

26、)kkkkkkf xf lxxllfxfl 0( )f llx 由由Taylor展開(kāi)得展開(kāi)得212( )()()()()()!kkkkkf xf xfxxxfxx 2102()()()()()()!kkkkkf xf xfxxxfxx 212()()()()!()kkkkkkf xfxxxxfxfx 2112()()!()kkkkfxxxxfx 122*( *)lim(*)( *)kkkxxfxxxfx Newtons Method 收斂性依賴于收斂性依賴于x0 的選取。的選取。x*x0 x0 x0Th2.9 （收斂的另一充分條件收斂的另一充分條件）設(shè)設(shè) 在在a, b上連續(xù)，上連續(xù)， (1)

27、f (a) f (b) 0；(2) 在整個(gè)在整個(gè)a, b上上 且且 ；(3) ，則對(duì)則對(duì) ，Newtons Method產(chǎn)生的序列產(chǎn)生的序列 xk 收斂于方收斂于方程程 在在a, b內(nèi)內(nèi)的唯一實(shí)根的唯一實(shí)根 。( )fx 0( )fx x 且且0( )fx ( )( )f abaf a ( )( )f bbaf b 0 , xa b 0( )f x ab( )( )()yf afaxa ( )( )f axafa ( )( )f afa ( )( )f bxbfb ( )yf x ( )( )f bfb x ( )( )()yf bfbxb Th2.9中條件中條件（3）的的幾何意義幾何意義保證

28、數(shù)列保證數(shù)列 單調(diào)遞增且有上界單調(diào)遞增且有上界 kxx 證明仿證明仿照照Th2.9改進(jìn)與推廣（改進(jìn)與推廣（補(bǔ)充補(bǔ)充） /* improvement and generalization */ 重根重根 /* multiple root */ 加速收斂法：加速收斂法：Q1: 若若 ，Newtons Method 是否仍收斂？是否仍收斂？0*)( xf設(shè)設(shè) x* 是是 f 的的 n 重根，則：重根，則： 且且 。( )()( )nf xxxq x ()0q x 因?yàn)橐驗(yàn)?Newtons Method 事實(shí)上是一種特殊的不動(dòng)點(diǎn)迭代，事實(shí)上是一種特殊的不動(dòng)點(diǎn)迭代，其中其中 ，則，則)()()(xfxf

29、xxg 22*)(*)(*)(*)(1|*)(|xfxfxfxfxg111 nA1: 有局部收斂性，但重?cái)?shù)有局部收斂性，但重?cái)?shù) n 越高越高，收斂，收斂越慢越慢。Q2: 如何如何加速加速重根情況時(shí)的收斂速度？重根情況時(shí)的收斂速度？A2: 將求將求 f 的的重根轉(zhuǎn)化重根轉(zhuǎn)化為求另一函數(shù)的為求另一函數(shù)的單根單根。令，則令，則 f 的重根的重根 = = 的單根。的單根。)()()(xfxfx 求復(fù)根求復(fù)根 /* Finding Complex Roots */ Newton 公式中的自變量可以是公式中的自變量可以是復(fù)數(shù)復(fù)數(shù)記記 z = x + i y, z0 為初值，同樣有為初值，同樣有)()(1k

30、kkkzfzfzz kkkkkkDiCzfBiAzf )(,)(設(shè)設(shè)代入公式，令代入公式，令實(shí)、虛部對(duì)應(yīng)相等實(shí)、虛部對(duì)應(yīng)相等，可得，可得;221kkkkkkkkDCDBCAxx .221kkkkkkkkDCCBDAyy 5 弦割法與拋物線法弦割法與拋物線法 /* Secant Method and Parabola Method */x0 x1割線割線 /* secant line */切線斜率切線斜率 割線斜率割線斜率11()()()kkkkkf xf xfxxx 111()()()()kkkkkkkf xxxxxf xf x 需要需要2個(gè)初值個(gè)初值 x0 和和 x1。Newtons Met

31、hod 每一步要計(jì)算每一步要計(jì)算 f 和和 ，為了避免計(jì)算導(dǎo)，為了避免計(jì)算導(dǎo)數(shù)值，現(xiàn)用數(shù)值，現(xiàn)用 f 的值近似的值近似 ，從而得到，從而得到弦割法弦割法（割線法割線法）。）。f f x2一、弦割法一、弦割法Th2.10 局部收斂性局部收斂性 設(shè)設(shè) 表示區(qū)間表示區(qū)間 ， x*為方程為方程 f (x) =0的根，的根， 函數(shù)函數(shù)f (x)在在 中有中有足夠階連續(xù)導(dǎo)數(shù)足夠階連續(xù)導(dǎo)數(shù)， 且且 滿足滿足 ,xxI0 I則對(duì)則對(duì) ，由割線法產(chǎn)生的序列，由割線法產(chǎn)生的序列 都收斂于都收斂于x*，且，且(i) (ii) (iii) 0( );fxxI 2( ),;( )fMIf 1dM 01,xxI kx其中

32、其中11limkqqkkeKe 2*(),()fxKfx 1151 6182().q 收斂速度介于收斂速度介于Newton and Bisection 之間之間 Corollary(推論推論) 設(shè)設(shè) x* 為方程為方程 f (x) =0的一個(gè)根，的一個(gè)根， ， 且且 在在 x* 的附近連續(xù)，則的附近連續(xù)，則 使得使得 由由Secant Method產(chǎn)生的序列產(chǎn)生的序列 都收斂于都收斂于x*。01,x xxx ( )fx 0()fx kx0, 例例1 證明方程證明方程 在區(qū)間在區(qū)間 內(nèi)有內(nèi)有唯一唯一根根 ，且，且使得對(duì)任意的初始值使得對(duì)任意的初始值 ，由，由割線法割線法產(chǎn)生的序產(chǎn)生的序列列 都收

33、斂于都收斂于 。 cosxx 02, x 0 01,xxxx kxx 證明：證明：令令( )cosf xxx 0022( )()ff 1002( )sin, ,fxxx 方程方程存在存在根根方程存在方程存在唯一唯一根根0()fx 且且( )cosfxx 在在 附近連續(xù)附近連續(xù)x 由由推論推論知，由知，由割線法割線法產(chǎn)生的序列產(chǎn)生的序列 都收斂于都收斂于 。 x kx xk-2Muller方法的思想來(lái)源于方法的思想來(lái)源于弦割法弦割法: :利用利用3個(gè)已知點(diǎn)構(gòu)造一條拋物個(gè)已知點(diǎn)構(gòu)造一條拋物線線, ,取其與取其與x軸的交點(diǎn)構(gòu)造下一次迭代值軸的交點(diǎn)構(gòu)造下一次迭代值. .x*二、拋物線法二、拋物線法(M

34、uller)幾何圖示幾何圖示xkxk-1xk+1( )f x2( )px Muller方法的具體實(shí)現(xiàn)方法的具體實(shí)現(xiàn): :設(shè)已知三個(gè)點(diǎn)設(shè)已知三個(gè)點(diǎn)22(,(),kkxf x 11(,(),kkxf x (,().kkxf x則過(guò)上述三個(gè)點(diǎn)的則過(guò)上述三個(gè)點(diǎn)的拋物線方程拋物線方程為為: :12221212121()()()()( )()()()()()()kkkkkkkkkkkkkkxxxxxxxxp xf xf xxxxxxxxx 2121()()()()()kkkkkkkxxxxf xxxxx 取該拋物線與取該拋物線與x軸的交點(diǎn)作為下一次迭代值軸的交點(diǎn)作為下一次迭代值, ,即即210()kpx 然后取新的相鄰的三次迭代值重復(fù)上述過(guò)程然后取新的相鄰的三次迭代值重復(fù)上述過(guò)程, ,即為即為Muller方法方法. Muller方法中拋物線根的計(jì)算方