第2章非線性方程(組)的數(shù)值解法2

1、第第 2 章章基礎(chǔ)教學(xué)部數(shù)學(xué)教研室基礎(chǔ)教學(xué)部數(shù)學(xué)教研室 彭彭 曉曉 華華2.4 迭代收斂的加速法迭代收斂的加速法加快收斂速度，減少計(jì)算量，是數(shù)值計(jì)算的重要課題加快收斂速度，減少計(jì)算量，是數(shù)值計(jì)算的重要課題 構(gòu)造一個更快收斂構(gòu)造一個更快收斂kx( )xx0 x埃特金埃特金加速方法可用于加快一已知收斂序列加速方法可用于加快一已知收斂序列 的收斂速度，的收斂速度， kx的序列的序列kx設(shè)設(shè) 是一個線性收斂的序列，收斂于方程是一個線性收斂的序列，收斂于方程 的根的根 .kxx 第一次校正：第一次校正： 設(shè)設(shè) 是根是根 的某個預(yù)測值，的某個預(yù)測值， x迭代公式可使迭代公式可使 校正為校正為10()xx0

2、 x由微分中值定理由微分中值定理,有有 100()()( )()xxxxxx 2.4.1埃特金加速法埃特金加速法 其方法是通過收斂較慢的已知序列其方法是通過收斂較慢的已知序列由于在較小的有根區(qū)間內(nèi)，由于在較小的有根區(qū)間內(nèi)， 的變化不大，取的變化不大，取 則有則有( )x0 x其中其中 介于介于 與與 之間之間.( )xL10()xxL xx 第二次校正：第二次校正： x對對 值再校正一次值再校正一次21()xx1x由于由于 21()xxL xxL將其與將其與 上面的式子聯(lián)立，消去 得 .0121xxxxxxxx數(shù)值分析數(shù)值分析解非線性方程（組）解非線性方程（組）解出解出 ，得到，得到一次埃特金

3、加速：一次埃特金加速： x對于初始近似值對于初始近似值 ，首先計(jì)算，首先計(jì)算 10()xx0 x然后，可用上式右端作為然后，可用上式右端作為 的新近似值，記做的新近似值，記做 1x再計(jì)算再計(jì)算 .22021100210210()22x xxxxxxxxxxxx21()xxx這就是一次埃特金加速過程這就是一次埃特金加速過程.數(shù)值分析數(shù)值分析解非線性方程（組）解非線性方程（組）埃特金加速算法：埃特金加速算法： 對于更一般的情形對于更一般的情形 ，首先由，首先由 計(jì)算計(jì)算 12,kkxxkx由此得到埃特金加速迭代公式：由此得到埃特金加速迭代公式：然后作一次加速然后作一次加速 .12121121()(

4、)(),0,1,2kkkkkkkkkkkxxxxxxxxkxxx21121()2kkkkkkkxxxxxxx可以證明，可以證明，*1*lim0kkkxxxx它表明序列它表明序列 的收斂速度比的收斂速度比 的收斂速度快的收斂速度快.，kxkx【注注】 當(dāng)?shù)^程收斂很慢時(shí)，一般可當(dāng)?shù)^程收斂很慢時(shí)，一般可用埃特金法加速，但有時(shí)埃特金法加速可用埃特金法加速，但有時(shí)埃特金法加速可能失敗，例如當(dāng)能失敗，例如當(dāng) 起伏很大、初值起伏很大、初值 與根與根 有較大的距離時(shí)，埃特金加速就有較大的距離時(shí)，埃特金加速就可能失敗可能失敗.0 x( )xx2.4.2 斯蒂芬森迭代法斯蒂芬森迭代法(Steffensen

5、s Method)：如果把埃特金加速技巧與不動點(diǎn)迭代結(jié)合如果把埃特金加速技巧與不動點(diǎn)迭代結(jié)合，則可得到如下的斯蒂芬森迭代法則可得到如下的斯蒂芬森迭代法 (),()kkkkyxzy1(),0,1,kkxxk21(),0,1,2kkkkkkkyxxxkzyx實(shí)際上公式（實(shí)際上公式（2.18）是將不動點(diǎn)迭代法計(jì)算兩步合）是將不動點(diǎn)迭代法計(jì)算兩步合并成一步得到的，可將它寫成另一種不動點(diǎn)迭代并成一步得到的，可將它寫成另一種不動點(diǎn)迭代2 ( )( )( ( )2 ( )xxxxxxx 其中其中對不動點(diǎn)迭代（對不動點(diǎn)迭代（2.19）有以下局部收斂性定理）有以下局部收斂性定理.（2.18）（2.19）（2.2

6、0）【定理定理6】若若 為上式定義的迭代函數(shù)為上式定義的迭代函數(shù) 的不動點(diǎn)，則的不動點(diǎn)，則 *x( )x則則 為為 的不動點(diǎn)的不動點(diǎn).反之，若反之，若 為為 的不動點(diǎn)，設(shè)的不動點(diǎn)，設(shè) *x( )x*x( )x( )x存在，存在， 則則 是是 的不動點(diǎn)，且該斯蒂芬森迭的不動點(diǎn)，且該斯蒂芬森迭代法是代法是2階收斂的階收斂的. *()1x*x( )x例例2-11用斯蒂芬森迭代法求解方程用斯蒂芬森迭代法求解方程 3( )10f xxx 解例解例2-7中已指出迭代中已指出迭代 是發(fā)散的是發(fā)散的.311kkxx現(xiàn)在利用斯蒂芬森迭代計(jì)算，仍取現(xiàn)在利用斯蒂芬森迭代計(jì)算，仍取 計(jì)算結(jié)計(jì)算結(jié)果見表果見表2-6.

7、3( )1xx表表2-6例例2-11迭代值迭代值計(jì)算表明它是收斂的，這說明即使原不動計(jì)算表明它是收斂的，這說明即使原不動點(diǎn)迭代法不收斂，用斯蒂芬森迭代法仍可點(diǎn)迭代法不收斂，用斯蒂芬森迭代法仍可能收斂能收斂.至于原來已收斂的不動點(diǎn)迭代法，至于原來已收斂的不動點(diǎn)迭代法，由定理由定理6可知它可達(dá)到可知它可達(dá)到2階收斂階收斂.更進(jìn)一步還更進(jìn)一步還可知若原迭代法為可知若原迭代法為 階收斂，則斯蒂芬森階收斂，則斯蒂芬森迭代法為迭代法為 階收斂階收斂.1.324721.324725 51.327141.327141.325181.325181.324801.324804 41.444351.444351.3

8、47101.347101.328951.328953 32.317282.317281.491401.491401.355651.355652 25.238885.238881.840921.840921.416291.416291 112.396612.39662.375002.375001.51.50 0kykzkxkp1p 例例2-12用斯蒂芬森迭代法求方程用斯蒂芬森迭代法求方程01)(xxexf在在 附近的一個根附近的一個根.0.5x 在例在例7中，迭代過程中，迭代過程 1(0 ,1,)kxkxek解方程的精確解為解方程的精確解為0.56714392.x 取初值取初值 ，迭代計(jì)算到，迭

9、代計(jì)算到 .00 .5x1 80 .5 6 7 1 4 0 7x利用斯蒂芬森迭代計(jì)算，結(jié)果見表利用斯蒂芬森迭代計(jì)算，結(jié)果見表2-7.由表由表2-7可知，經(jīng)可知，經(jīng)過過2次迭代次迭代.且且 *51 80 .41 0 xx1 80 .5 6 7 1 4 3 3 1x*720 .21 0 xx加速效果較好加速效果較好.數(shù)值分析數(shù)值分析解非線性方程（組）解非線性方程（組）kkxkykz0.5671433120.567297860.566870790.5676238810.545239210.606530660.50表2-7例2-12迭代值 運(yùn)行結(jié)果表明迭代成功，達(dá)到精度要求運(yùn)行結(jié)果表明迭代成功，達(dá)到精

10、度要求.迭代終止條迭代終止條件為：前后兩次迭代結(jié)果之差是否滿足精度，共迭代計(jì)件為：前后兩次迭代結(jié)果之差是否滿足精度，共迭代計(jì)算算3次；對比例次；對比例2-8，利用不動點(diǎn)迭代計(jì)算了，利用不動點(diǎn)迭代計(jì)算了18次；顯然次；顯然Steffensen方法收斂更快方法收斂更快. 思考：在埃特金加速或斯蒂芬森加速法的基礎(chǔ)上思考：在埃特金加速或斯蒂芬森加速法的基礎(chǔ)上是否能找到更好的收斂速度加速法？是否能找到更好的收斂速度加速法？ 不動點(diǎn)迭代一般理論告訴我們，構(gòu)造不動點(diǎn)迭代一般理論告訴我們，構(gòu)造好的迭代函數(shù)可使收斂速度提高好的迭代函數(shù)可使收斂速度提高.然而迭然而迭代函數(shù)的構(gòu)造方法又各不相同、方法多代函數(shù)的構(gòu)造方

11、法又各不相同、方法多樣樣.能否找到一種迭代方法能否找到一種迭代方法, ,既結(jié)構(gòu)簡單既結(jié)構(gòu)簡單, ,收斂速度快收斂速度快, ,又不存在發(fā)散的問題？牛頓又不存在發(fā)散的問題？牛頓迭代法就是這樣一種方法。迭代法就是這樣一種方法。2.5.1 牛頓迭代法牛頓迭代法 基本思想是：基本思想是：將非線性函數(shù)將非線性函數(shù)f f( (x x) )逐步線性化逐步線性化, , 從而將非線性方程從而將非線性方程f f( (x x)=0)=0近似地轉(zhuǎn)化為線性方程近似地轉(zhuǎn)化為線性方程求解。求解。即把非線性方程逐步線性化即把非線性方程逐步線性化.方程方程 的根的根 ，幾何意義是曲線，幾何意義是曲線與與 軸的交點(diǎn)軸的交點(diǎn).求曲線

12、與求曲線與 軸的交點(diǎn)沒有普遍的公式，軸的交點(diǎn)沒有普遍的公式，但直線與但直線與 軸的交點(diǎn)容易計(jì)算。軸的交點(diǎn)容易計(jì)算。0)(xf*xxxx( )yf x( )yf x( )0f x 基本方法：基本方法：用函數(shù)用函數(shù)的切線近似曲線的切線近似曲線 ( )yf x，從而用切線方程的根逐步代替從而用切線方程的根逐步代替的根的根。牛頓迭代法的原理：牛頓迭代法的原理： 2)(21)()()(kkkkkxxxfxxxfxfxf忽略高次項(xiàng)忽略高次項(xiàng), ,用其線性部分作為函數(shù)用其線性部分作為函數(shù)f(x)f(x)的近似，的近似， )()()(kkkxxxfxfxf 設(shè)設(shè) 的根的根 , ,則有則有 , ,即即 0)(x

13、f*x0)(*xf0)()(*kkkxxxfxf)()(*kkkxfxfxx)()(1kkkkxfxfxx)2,1 ,0(k將右端取為將右端取為 , ,即即 是比是比 更接近于更接近于 的近似值的近似值 1kx1kxkx*x 對于方程對于方程 , ,設(shè)其近似根為設(shè)其近似根為 , ,函數(shù)函數(shù) 可在可在 附近作泰勒展開附近作泰勒展開 0)(xfkxkx( )f x線性化方法：線性化方法：xyx*x00100()()fxxxfxx 1x 2000()()()yf xfxxx1211()()fxxxfx牛頓法也稱為切線法牛頓法也稱為切線法 牛頓迭代法的牛頓迭代法的幾何解釋幾何解釋111( )( )()

14、yf xfxxx（1）（2）()()()kkkyf xfxxx1()()kkkkfxxxfx17)(/ )()(xfxfxx( ),xx)(1kkxx)(x牛頓迭代法的收斂性：牛頓迭代法的收斂性：，則有，則有從而牛頓迭代就是不動點(diǎn)迭代從而牛頓迭代就是不動點(diǎn)迭代因此可以通過考察因此可以通過考察迭代法的收斂性及收斂速度迭代法的收斂性及收斂速度. .如果取如果取的性質(zhì)，來討論的性質(zhì)，來討論定理定理7 7 設(shè)設(shè) 是方程是方程 的單根的單根, , 且且f f( (x x) )在在 的某鄰域內(nèi)有連續(xù)的二階導(dǎo)數(shù)的某鄰域內(nèi)有連續(xù)的二階導(dǎo)數(shù), , 則牛頓法在則牛頓法在 附近附近局部收斂局部收斂, , 且至少且至

15、少二階收斂二階收斂, , 有有 *x0)(xf*x*x*1122*()limlim2()kkkkkkxxfxefxexx 1 1、局部收斂：局部收斂：若在若在x的某個鄰域的某個鄰域內(nèi)的每一點(diǎn)，迭代均收斂，稱這種形式的收斂為內(nèi)的每一點(diǎn)，迭代均收斂，稱這種形式的收斂為局部收斂局部收斂.:Rxx【定理定理4】 （局部收斂性）（局部收斂性）設(shè)設(shè) )(x在在x的鄰近連續(xù)，的鄰近連續(xù)，1)(x且且則迭代過程則迭代過程)(1kkxx在在x鄰近具有局部收斂性鄰近具有局部收斂性. .復(fù)習(xí)：復(fù)習(xí)：定義定義 （收斂階）（收斂階）：設(shè)迭代過程：設(shè)迭代過程 收斂于收斂于 的的根根 , ,記迭代誤差記迭代誤差若存在常數(shù)若

16、存在常數(shù)p p（p1p1）和和c c（c0c0），），使使 )(1kkxx)(xx*xkkxxe*ceepkkk1lim則稱序列則稱序列 是是p p 階收斂的階收斂的, ,c c 稱漸近誤差常數(shù)。稱漸近誤差常數(shù)。 kx2 2、迭代法的收斂速度、迭代法的收斂速度特別地特別地, , 時(shí)稱為線性收斂時(shí)稱為線性收斂, , 時(shí)稱為平方收斂。時(shí)稱為平方收斂。 時(shí)稱為超線性收斂。時(shí)稱為超線性收斂。 1p 2p 1p 3 3、定理定理5 5 設(shè)迭代過程設(shè)迭代過程 , , 若若 在所求根在所求根 的鄰域連續(xù)且的鄰域連續(xù)且 則迭代過程在則迭代過程在 鄰域是鄰域是 階收斂階收斂的。的。)(1kkxx)()(xp*x

17、0)(, 0)()()(*)(*) 1(* xxxxpp*xp21)(xf)(/ )()(xfxfxx)(1kkxx2)(/)()()(xfxfxfx 223( )( )( )( )( ) /( )2 ( )( ) /( )xf x fxfx fxfxf x fxfx*x0)(xf()0,f x0)(xf0)(/ )()(, 0)( xfxfxx.定理定理7的的證明：證明：（1） 對于對于，取，取則牛頓迭代過程為則牛頓迭代過程為注意到注意到由于由于是是的單根，即的單根，即所以有所以有由由定理定理4知，迭代過程是局部收斂的知，迭代過程是局部收斂的.且由且由定理定理5知，知，迭代過程在點(diǎn)迭代過程在

18、點(diǎn)*x鄰近是鄰近是2階收斂的階收斂的.22)(x*xkxx 22( *)()( *)( *)(*)(*)2!1( *)( *)/( *)(*) .2kkkkxxxxxxxxxfxfxxx1(),kkxx)(*xx21)()(2/ )( xxxfxfxxkk21)(2/ )( xxxfxfxxkk（2） 將將在在處作泰勒展開并代入處作泰勒展開并代入，有，有注意到注意到，得到，得到因此有因此有*1122*()limlim2()kkkkkkxxfxefxexx 證畢證畢 ?0)(0 xf 1000)()(xxfxfx ?01 xx 開 始 輸 入 x0,N 1 k k+ 1 k x1 x0 輸 出

19、x1 輸 出 迭 代 失 敗 標(biāo) 志 結(jié) 束 n k N ? n n y 輸 出 奇 異 標(biāo) 志 y y 牛頓迭代法算法實(shí)現(xiàn)牛頓迭代法算法實(shí)現(xiàn)數(shù)值分析數(shù)值分析例2-13 用求 x=e-x的根,=10-4解：因 f (x)= x ex 1 , f (x)=ex ( x+1) 建立迭代公式nxnnnxxnnnxexxxeexxxnnn 1)1 (11取x0=0.5,逐次計(jì)算得 x1=0.57102, x2=0.56716， x3=0.56714與例2-8相比，牛頓法的收斂速度快。的根的根, ,要求要求20 xxe51| 10kkxx1ln(2)kkxx迭代格式一：迭代格式一：迭代格式二：迭代格式二

20、：121kkxkkkxxexxe取初值取初值x x0 00.00.0, ,計(jì)算如下：計(jì)算如下：對迭代格式一對迭代格式一: : the iterative number is 27, the numerical solution is 0.442852706對迭代格式二對迭代格式二: : the iterative number is 3, the numerical solution is 0.442854401例例2-12-14 4 用用NewtonNewton法求方程法求方程26例2-13 用牛頓迭代法計(jì)算22( )02f xxaa其中迭代公式得及由Newtonxxf2)(21212()0

21、,1,.22nnnnnnxxxxnxx012331.51.41666667,1.4142156861.4142135622xxxxx取，則，。與的精確值相比， 是已有十位有效數(shù)字的的近似值。解：*x0 x*x【注】【注】 牛頓迭代過程在牛頓迭代過程在鄰近，否則，可能不收斂鄰近，否則，可能不收斂. .如下圖所示如下圖所示最好選在最好選在鄰近具有平方收斂速度鄰近具有平方收斂速度. .牛頓迭代法的優(yōu)點(diǎn)：快速收斂性，算法簡單、容易實(shí)現(xiàn)牛頓迭代法的優(yōu)點(diǎn)：快速收斂性，算法簡單、容易實(shí)現(xiàn). .牛頓迭代法的缺點(diǎn)：牛頓迭代法的缺點(diǎn)：(2)(2)每步迭代要計(jì)算每步迭代要計(jì)算)(kxf及及)(kxf 計(jì)算量較大且有

22、時(shí)計(jì)算量較大且有時(shí)計(jì)算較困難。計(jì)算較困難。 )(kxf （1 1）因?yàn)榫植渴諗啃裕猿踔担┮驗(yàn)榫植渴諗啃?，所以初值Newton法的收斂性依賴于法的收斂性依賴于x0 的選取。的選取。x*x0 x0 x0 為克服這兩個缺點(diǎn)，通?？捎孟率龇椒榭朔@兩個缺點(diǎn)，通?？捎孟率龇椒?2.5.2 2.5.2 簡化牛頓法與簡化牛頓法與牛頓下山法牛頓下山法 0( )2Cfx*x1 1、簡化牛頓法：、簡化牛頓法：1(),kkkxxCf x( )( )xxCf x( )1( )1xCfx簡化牛頓法也稱簡化牛頓法也稱平行弦法平行弦法，其迭代公式為，其迭代公式為迭代函數(shù)迭代函數(shù)即取即取0,C , 1 , 0k若若 在

23、根在根附近成立，則附近成立，則迭代法（迭代法（2.222.22）局部收斂）局部收斂. .（2.222.22）)(10 xfCx*x在（在（2.222.22）中?。┲腥∵@類方法計(jì)算量省，但只有線性收斂，其幾何意義是這類方法計(jì)算量省，但只有線性收斂，其幾何意義是 用平行弦與用平行弦與 軸交點(diǎn)交點(diǎn)作為 的近似，如圖的近似，如圖2-6所示所示.，則稱為，則稱為簡化牛頓法簡化牛頓法，31 圖圖2-6 簡化牛頓法幾何示意簡化牛頓法幾何示意32013 xx5 . 1x*x5 . 10 x131231kkkkkxxxxx34783. 11x32520. 12x32472. 13x3x6 . 00 x9 .17

24、1x6 . 00 x32472. 1*x例例2-12-14 4在在附近的一個根附近的一個根.解解 1 1） 設(shè)取迭代初值設(shè)取迭代初值，牛頓法公式為，牛頓法公式為迭代迭代3 3次得到的結(jié)果次得到的結(jié)果有有6 6位有效數(shù)字位有效數(shù)字. .作為迭代初值，則依牛頓法公式（作為迭代初值，則依牛頓法公式（2.232.23）迭代一次得）迭代一次得. .這個結(jié)果反而比這個結(jié)果反而比更偏離了所求的根更偏離了所求的根計(jì)算得計(jì)算得2 2） 如果改用如果改用用牛頓法求解方程用牛頓法求解方程33通常通常, ,牛頓迭代法的收斂性依賴于初始值的選取牛頓迭代法的收斂性依賴于初始值的選取, ,如果初始值如果初始值偏離所求的根比

25、較遠(yuǎn)偏離所求的根比較遠(yuǎn), ,則牛頓法可能發(fā)散。為了防止迭代發(fā)散則牛頓法可能發(fā)散。為了防止迭代發(fā)散, ,我們對牛頓迭代法的迭代過程再附加一項(xiàng)要求我們對牛頓迭代法的迭代過程再附加一項(xiàng)要求, ,即具有單調(diào)性即具有單調(diào)性)()(1kkxfxf滿足這項(xiàng)要求的算法稱下山法。滿足這項(xiàng)要求的算法稱下山法。2、牛頓下山法、牛頓下山法牛頓下山法原理：牛頓下山法原理：將牛頓迭代法與下山法結(jié)合起來將牛頓迭代法與下山法結(jié)合起來使用使用, ,即在下山法保證函數(shù)值下降的前提下即在下山法保證函數(shù)值下降的前提下, ,用牛頓用牛頓迭代法加快收斂速度。把這一算法稱為牛頓下山法。迭代法加快收斂速度。把這一算法稱為牛頓下山法。即即)(

26、)(1kkkkxfxfxx其中其中(01)(01)為下山因子為下山因子 1()()kkkkf xxxfx11(1)kkkxxx牛頓法計(jì)算的結(jié)果：牛頓法計(jì)算的結(jié)果：與前一步的近似值與前一步的近似值x xk k適當(dāng)加權(quán)平均作為新的改進(jìn)值適當(dāng)加權(quán)平均作為新的改進(jìn)值 下山因子的選擇是個逐步探索的過程，設(shè)從下山因子的選擇是個逐步探索的過程，設(shè)從=1開始反復(fù)將開始反復(fù)將減半進(jìn)行試算減半進(jìn)行試算, 即逐次取即逐次取為為,21,21, 12)()(1kkxfxf下山因子的選擇：下山因子的選擇：從中挑選下山因子，直至找到其中某個從中挑選下山因子，直至找到其中某個使單調(diào)性條件使單調(diào)性條件成立，則稱成立，則稱“下山

27、成功下山成功”，否則，否則“下山失敗下山失敗”，這時(shí)需另選初值重算。這時(shí)需另選初值重算。363211140625. 11x656643. 0)(1xf384. 1)(0 xf)()(01xfxf1x,32xx136181. 12x1866. 0)(2xf32628. 13x00667. 0)(3xf32472. 14x0000086. 0)(4xf4x*x例例1414中取中取逐次取半進(jìn)行計(jì)算，逐次取半進(jìn)行計(jì)算，時(shí)可求得時(shí)可求得，此時(shí)，此時(shí)而而，顯然，顯然由由計(jì)算計(jì)算時(shí)時(shí)均能使下降條件成立，計(jì)算結(jié)果如下：均能使下降條件成立，計(jì)算結(jié)果如下：，即為即為的近似的近似. .通過通過當(dāng)當(dāng)1x由由計(jì)算計(jì)算6

28、 . 00 x，它不滿足下降條件。，它不滿足下降條件。37lim()0,kkf xkx1一般情況只要使下降條件成立，則可一般情況只要使下降條件成立，則可從而使從而使牛頓下山法是目前方程求根的一個牛頓下山法是目前方程求根的一個速度雖然沒有牛頓法快，但它對初速度雖然沒有牛頓法快，但它對初值的選取范圍放寬很多值的選取范圍放寬很多. .收斂收斂. .有效方法，當(dāng)有效方法，當(dāng)時(shí)，時(shí)，得到得到它的收斂它的收斂382.5.3 割線法割線法)(kxf )(kxf )(kxf )(xf牛頓迭代法的收斂速度很快，但是每迭代一次，都要計(jì)算牛頓迭代法的收斂速度很快，但是每迭代一次，都要計(jì)算的值，如果出現(xiàn)的值，如果出現(xiàn)

29、接近于零，可能接近于零，可能不為零，但當(dāng)不為零，但當(dāng)時(shí)，導(dǎo)數(shù)的計(jì)算工作量也較大時(shí)，導(dǎo)數(shù)的計(jì)算工作量也較大. .通常希望避免計(jì)算導(dǎo)數(shù)，通常希望避免計(jì)算導(dǎo)數(shù)，而導(dǎo)出一個類似牛頓迭代的公式而導(dǎo)出一個類似牛頓迭代的公式. .導(dǎo)致溢出導(dǎo)致溢出. .既使既使較復(fù)雜較復(fù)雜1kxkkxx,1割線法（割線法（Secant MethodSecant Method）原理）原理：時(shí)，由前面算出的時(shí)，由前面算出的兩點(diǎn)的割線斜率代替導(dǎo)數(shù)，可得兩點(diǎn)的割線斜率代替導(dǎo)數(shù)，可得在牛頓迭代中，為避免計(jì)算導(dǎo)數(shù)，用經(jīng)過兩點(diǎn)的割線在牛頓迭代中，為避免計(jì)算導(dǎo)數(shù)，用經(jīng)過兩點(diǎn)的割線來代替切線，即求來代替切線，即求39)(/ )(1kkkkxf

30、xfxx)()()()(111kkkkkkkxxxfxfxfxx代入牛頓迭代公式代入牛頓迭代公式中，有中，有割線法迭代公式割線法迭代公式. )(xfy )(,(),(,(111kkkkkkxfxpxfxp)() 1()()(1kkkkkkxxxxxfxfxfy0y1,kx其割線方程為其割線方程為，割線與割線與的交點(diǎn)記為的交點(diǎn)記為則得到割線法迭代公式則得到割線法迭代公式. .割線法又稱為弦截法、割線法又稱為弦截法、弦線法弦線法. .過兩點(diǎn)過兩點(diǎn)割線法的幾何意義割線法的幾何意義：迭代公式的導(dǎo)數(shù)是曲線迭代公式的導(dǎo)數(shù)是曲線的割線（弦線）的斜率，的割線（弦線）的斜率，11)()()(kkkkkxxxfx

31、fxf40圖圖2-7 割線法幾何示意割線法幾何示意41)(xf*x0)(* xf10,xx*x618. 1*618. 0*1)(/ )(xxxfxfxxkk kkxx,11kk618. 1p如果如果在零點(diǎn)在零點(diǎn)附近有附近有，且初始值，且初始值充分接近充分接近，則割線法的迭代過程是收斂的，其收斂速度為，則割線法的迭代過程是收斂的，其收斂速度為其中其中分別是第分別是第次和第次和第【注注】 割線法具有超線性收斂速度，其收斂階為割線法具有超線性收斂速度，其收斂階為連續(xù)的二階導(dǎo)數(shù)，連續(xù)的二階導(dǎo)數(shù)，次迭代近似值次迭代近似值. .割線法的收斂性：割線法的收斂性：4205 . 0sinxx)()sin(sin

32、)(5 . 0sin1111kkkkkkkkkkxxxxxxxxxx用割線法求方程用割線法求方程解解 割線法迭代公式為割線法迭代公式為在在1.51.5附近的一個根附近的一個根. .保留四位有效數(shù)字。保留四位有效數(shù)字。6 . 1, 4 . 110 xx,4919426. 12 . 0)9854497. 09995736. 0(2 . 09995736. 01 . 16 . 1)4 . 16 . 1 ()4 . 1sin6 . 1(sin)4 . 16 . 1 (5 . 06 . 1sin6 . 16 . 12x49730. 1,49702. 143xx取初始值取初始值迭代計(jì)算，得到迭代計(jì)算，得到

33、.例例2-12-15 5 4301xxe6 . 0, 5 . 010 xx56714. 0,56709. 0,56532. 0432xxx用割線法求方程用割線法求方程在在0.50.5附近附近. .用割線法迭代計(jì)算，得到用割線法迭代計(jì)算，得到比較比較例例2-12-13 3牛頓牛頓法的計(jì)算結(jié)果可以看出，法的計(jì)算結(jié)果可以看出，割線法的收斂速度也是相當(dāng)快的割線法的收斂速度也是相當(dāng)快的. .解解 取初始值取初始值的根的根例例2-12-16 6 40.5671432x 例例2-12-13 3中中44)()()(*xgxxxfm0)(*xg*x0)(xf2m*(1)*()()()0,mf xfxfx0)(*

34、)(xfm0)(kxf)()()(xfxfxx011)(*mx1)(* x2.5.4 2.5.4 求重根的修正牛頓法求重根的修正牛頓法，整數(shù)，整數(shù)，則則為方程為方程的的重根，此時(shí)有重根，此時(shí)有只要只要仍可用牛頓法計(jì)算，此時(shí)迭代函數(shù)仍可用牛頓法計(jì)算，此時(shí)迭代函數(shù)的導(dǎo)數(shù)為的導(dǎo)數(shù)為且且，所以牛頓法求重根只是線性收斂，所以牛頓法求重根只是線性收斂. .設(shè)設(shè)m45)()()(xfxfmxx0)(* x)()(1kkkkxfxfmxx, 1 , 0km*xm一、一、求重根的修正牛頓法求重根的修正牛頓法1 1，則，則因此利用迭代法因此利用迭代法, ,求求重根，具有重根，具有2 2階收斂階收斂. .應(yīng)用該方法

35、的應(yīng)用該方法的的重?cái)?shù)的重?cái)?shù). .選取選取 （2.282.28）前提是：要知道前提是：要知道46)(/ )()(xfxfx*x0)(xfm)()()()()()(*xgxxxmgxgxxx二、二、求重根的修正牛頓法求重根的修正牛頓法2 2若若是是的的重根，則重根，則，（，（2.292.29）構(gòu)造求重根的迭代法，還可令構(gòu)造求重根的迭代法，還可令*x0)(x)()()()()()()()(2xfxfxfxfxfxxxxx )()()()()(21kkkkkkkxfxfxfxfxfxx , 1 , 0k故故是是的單根的單根. .對它用牛頓法，其迭代函數(shù)為對它用牛頓法，其迭代函數(shù)為從而可構(gòu)造迭代法從而可

36、構(gòu)造迭代法，它是二階收斂的它是二階收斂的. .方法方法1）方法方法2）方法方法3）11.4583333331.4166666671.41176470621.4366071431.4142156861.41421143831.4254976191.4142135621.414213562kkx1x2x3x表表2-8三種方法數(shù)值結(jié)果三種方法數(shù)值結(jié)果計(jì)算三步，方法計(jì)算三步，方法2）及方法）及方法3）均達(dá)到）均達(dá)到10位有效數(shù)字，而用位有效數(shù)字，而用牛頓法只有線性收斂，要達(dá)到同樣精度需要迭代牛頓法只有線性收斂，要達(dá)到同樣精度需要迭代30次次.48【注】【注】 求重根的修正牛頓法求重根的修正牛頓法1需要

37、已知根的重?cái)?shù)，需要已知根的重?cái)?shù)，因此不實(shí)用因此不實(shí)用.求重根的修正牛頓法求重根的修正牛頓法2需要求函數(shù)的二需要求函數(shù)的二階導(dǎo)數(shù)，并且當(dāng)所求根為單根時(shí)，不能改善本來已階導(dǎo)數(shù)，并且當(dāng)所求根為單根時(shí)，不能改善本來已經(jīng)二次收斂的牛頓法經(jīng)二次收斂的牛頓法.對于實(shí)際問題，往往事先并對于實(shí)際問題，往往事先并不知道所求根是否是重根，需要通過試算來判斷，不知道所求根是否是重根，需要通過試算來判斷，如當(dāng)牛頓法收斂很慢時(shí)通常為重根如當(dāng)牛頓法收斂很慢時(shí)通常為重根.小結(jié)：小結(jié)：)(/ )()(xfxfxx一、牛頓迭代法：一、牛頓迭代法：1 1、牛頓迭代函數(shù)：、牛頓迭代函數(shù)：2 2、牛頓迭代公式：、牛頓迭代公式：1()(

38、)kkkkfxxxfx3 3、牛頓迭代收斂性：、牛頓迭代收斂性：定理定理7 7 設(shè)設(shè) 是方程是方程 的單根的單根, , 且且f f( (x x) )在在 的某鄰域內(nèi)有連續(xù)的二階導(dǎo)數(shù)的某鄰域內(nèi)有連續(xù)的二階導(dǎo)數(shù), , 則牛頓法在則牛頓法在 附近附近局部收斂局部收斂, , 且至少且至少二階收斂二階收斂, , 有有 *x0)(xf*x*x*1122*()limlim2()kkkkkkxxfxefxexx 0( )2Cfx*x1 1、簡化牛頓法：、簡化牛頓法：1(),kkkxxCf x( )( )xxCf x( )1( )1xCfx迭代公式：迭代公式：迭代函數(shù)：迭代函數(shù)：即取即取0,C , 1 , 0k

39、若若 在根在根附近成立，則附近成立，則迭代法（迭代法（2.222.22）局部收斂）局部收斂. .)(10 xfC在（在（2.222.22）中取）中取，則稱為，則稱為簡化牛頓法簡化牛頓法，二、簡化牛頓法與牛頓下山法二、簡化牛頓法與牛頓下山法5104424 xx2*xkkkkxxxx4221kkkkxxxx22212)2(221kkkkkxxxxx5 . 10 x例例1 17 7方程方程的根的根是二重根，用上述三種方法求根是二重根，用上述三種方法求根. .2 2） 用（用（2.282.28）式：）式：3 3） 用（用（2.292.29）式：）式：取初值取初值，計(jì)算結(jié)果如表，計(jì)算結(jié)果如表2-8.2-8.解解先求出三種方法的迭代公式先求出三種方法的迭代公式. .1 1） 牛頓法：牛頓法： 將牛頓迭代法與下山法結(jié)合起來使用將牛頓迭代法與下山法結(jié)合起來使用, ,即在下山即在下山法保證函數(shù)值下降的前提下法保證函數(shù)值下降的前提下, ,用牛頓迭代法加快收斂用牛頓迭代法加快收斂速度。把這一算法稱為牛頓下山法。即速度。把這一算法稱為牛頓下山法。即)()(1kkkkxfxfxx其中其中(01)(01)為下山因子為下山因子 1()()kkkkf xxxfx11(1)kkkxxx牛頓法計(jì)算的結(jié)果：牛頓法計(jì)算的結(jié)果：