第三節(jié)牛頓迭代法

1、1一一 牛頓法及其收斂性牛頓法及其收斂性 牛頓法是一種線性化方法，其基本思想是將非線性方程 逐步歸結(jié)為某種線性方程來(lái)求解.0)(xf 設(shè)已知方程 有近似根 （假定 )，將函數(shù) 在點(diǎn) 展開(kāi)，有 0)(xfkx0)(kxf)( xfkx),)()()(kkkxxxfxfxf于是方程 可近似地表示為 0)(xf.0)()(kkkxxxfxf（1）這是個(gè)線性方程，記其根為 ，則 的計(jì)算公式為 1kx1kx10.4 牛頓迭代法牛頓迭代法2),1 ,0()()(1kxfxfxxkkkk（2）這就是牛頓牛頓(Newton)(Newton)法法. 牛頓法的幾何解釋. 方程 的根 可解釋為曲線 與 軸的交點(diǎn)的橫

2、坐標(biāo)（圖7-3). 0)(xf*x)( xfy x 設(shè) 是根 的某個(gè)近似值，過(guò)曲線 上橫坐標(biāo)為 的點(diǎn) 引切線，并將該切線與 軸的交點(diǎn)的橫坐標(biāo) 作為 的新的近似值. kx*x)( xfy kxkPx1kx*x圖7-33注意到切線方程為 ).)()(kkkxxxfxfy這樣求得的值 必滿足(1），從而就是牛頓公式（2）的計(jì)算結(jié)果. 由于這種幾何背景，牛頓法亦稱切線法切線法.1kx 牛頓法（2）的收斂性，可直接由上節(jié)定理得到，對(duì)（2）其迭代函數(shù)為 ,)()()(xfxfxxg由于 .)()()()(2xfxfxfxg 假定 是 的一個(gè)單根，即 ，則由上式知 ，于是依據(jù)可以斷定，牛頓法在根 的鄰近至少

3、是平方收斂的. )( xf*x0*)(,0*)(xfxf0*)( xg*x4又因 ,*)(*)(*)(xfxfxg 故 可得 .*)(2*)(*)(*lim21xfxfxxxxkkk （3.3） 例例7.3.1 7.3.1 用牛頓法解方程 .01 xxe（3.4） 解解 這里牛頓公式為 ,11kxkkkxexxxk取迭代初值 ，迭代結(jié)果列于表7-5中. 5.00 x.!*)()(1pxgeeppkk.!*)()(1pxgeeppkk556714.0356716.0257102.015.0057kxk計(jì)算結(jié)果表 所給方程（3.4）實(shí)際上是方程 的等價(jià)形式. 若用不動(dòng)點(diǎn)迭代到同一精度要迭代28次，

4、可見(jiàn)牛頓法的收斂速度是很快的.xex6 對(duì)于給定的正數(shù) ，應(yīng)用牛頓法解二次方程 C,02 Cx可導(dǎo)出求開(kāi)方值 的計(jì)算程序 C).(211kkkxCxx（3.5）這種迭代公式對(duì)于任意初值 都是收斂的. 00 x 事實(shí)上，對(duì)（3.5）式施行配方手續(xù)，易知 .)(21;)(212121CxxCxCxxCxkkkkkk二二 牛頓法應(yīng)用舉例牛頓法應(yīng)用舉例7以上兩式相除得 .211CxCxCxCxkkkk據(jù)此反復(fù)遞推有 .20011kCxCxCxCxkk（3.6）記 ,00CxCxq整理（3.6）式，得 8.1222kkqqCCxk 對(duì)任意 ，總有 ，故由上式推知，當(dāng) 時(shí) ，即迭代過(guò)程恒收斂. 00 x1

5、qkCxk723805.104723805.103723837.102750000.10110067kxk計(jì)算結(jié)果表 解解 取初值 ，對(duì) 按（3.5）式迭代3次便得到精度為 的結(jié)果（見(jiàn)表7-6). 100 x115C610 由于公式（3.5）對(duì)任意初值 均收斂，并且收斂的速度很快，因此可取確定的初值如 編成通用程序. 00 x10 x例例7.3.2 7.3.2 求 . 1159 三三 簡(jiǎn)化牛頓法與牛頓下山法簡(jiǎn)化牛頓法與牛頓下山法 牛頓法的牛頓法的優(yōu)點(diǎn)優(yōu)點(diǎn) 收斂快，牛頓法的牛頓法的缺點(diǎn)缺點(diǎn) 一 每步迭代要計(jì)算 及 ，計(jì)算量較大且有時(shí) 計(jì)算較困難， 二是初始近似 只在根 附近才能保證收斂，如 給的

6、不合適可能不收斂. )(kxf)(kxf )(kxf 0 x*x0 x10 為克服這兩個(gè)缺點(diǎn)，通?？捎孟率龇椒? （1） 簡(jiǎn)化牛頓法，也稱平行弦法. 其迭代公式為 .,1 ,0)(1CxCfxxkkk（3.7）迭代函數(shù) ).()(xCfxx 若在根 附近成立 ，即取 ，則迭代法（3.7）局部收斂.*x1)(1)(xfCx2)(0 xfC11 在（3.7）中取 ，則稱為簡(jiǎn)化牛頓法簡(jiǎn)化牛頓法，這類方法計(jì)算量省，但只有線性收斂，其幾何意義是用平行弦與 軸交點(diǎn)作為 的近似. 如圖7-4所示. )(10 xfCx*x圖7-412 （2 2） 牛頓下山法牛頓下山法. . 牛頓法收斂性依賴初值 的選取. 如

7、果 偏離所求根 較遠(yuǎn)，則牛頓法可能發(fā)散.0 x0 x*x 例如，用牛頓法求方程 .013 xx（3.8）在 附近的一個(gè)根 . 5.1x*x 設(shè)取迭代初值 ，用牛頓法公式 5.10 x131231kkkkkxxxxx（3.9）計(jì)算得 .32472.1,32520.1,34783.1321xxx迭代3次得到的結(jié)果 有6位有效數(shù)字. 3x13 但如果改用 作為迭代初值，則依牛頓法公式（3.9）迭代一次得 6.00 x.9.171x這個(gè)結(jié)果反而比 更偏離了所求的根 . 6.00 x32472.0* x 為了防止迭代發(fā)散，對(duì)迭代過(guò)程再附加一項(xiàng)要求，即具有單調(diào)性： .)()(1kkxfxf（3.10）滿足

8、這項(xiàng)要求的算法稱下山法下山法. 將牛頓法與下山法結(jié)合起來(lái)使用，即在下山法保證函數(shù)值穩(wěn)定下降的前提下，用牛頓法加快收斂速度. 將牛頓法的計(jì)算結(jié)果 14)()(1kkkkxfxfxx與前一步的近似值 適當(dāng)加權(quán)平均作為新的改進(jìn)值 kx,)1(11kkkxxx（3.11）其中 稱為下山因子，（3.11）即為 )10(),1 ,0()()(1kxfxfxxkkkk（3.12）(3.12)稱為牛頓下山法牛頓下山法. 選擇下山因子時(shí)從 開(kāi)始，逐次將 減半進(jìn)行試算，直到能使下降條件（3.10）成立為止. 1 若用此法解方程（3.8），當(dāng) 時(shí)由（3.9）求得6.00 x15 ，它不滿足條件（3.10）.9.17

9、1x 通過(guò) 逐次取半進(jìn)行試算，當(dāng) 時(shí)可求得 . 此時(shí)有 ，而顯然 . 32/1140625.11x656643.0)(1xf384.1)(0 xf)()(01xfxf 由 計(jì)算 時(shí) , 均能使條件（3.10）成立. 計(jì)算結(jié)果如下 ： 1x,32xx1.0000086.0)(,32472.1;00667.0)(,32628.1;1866.0)(,36181.1443322xfxxfxxfx 即為 的近似. 一般情況只要能使條件（3.10）成立，則可得到 ，從而使 收斂.4x*x0)(limkkxfkx16四四 重根情形重根情形 設(shè) ，整數(shù) ，則 為方程 的 重根，此時(shí)有 )(*)()(xxxxf

10、m0*)(,2xm*x0)(xfm.0*)(,0*)(*)(*)()1(xfxfxfxfmm只要 仍可用牛頓法（3.2）計(jì)算，此時(shí)迭代函數(shù) 0)(kxf)()()(xfxfxxg的導(dǎo)數(shù)為 011*)(mxg且 ，所以牛頓法求重根只是線性收斂. 1*)( xg17,)()()(xfxfmxxg則 . 用迭代法 0*)( xg),1 ,0()()(1kxfxfmxxkkkk（3.13）求 重根，則具有2階收斂，但要知道 的重?cái)?shù) . mm*x 構(gòu)造求重根的迭代法，還可令 ，若 是 的 重根，則 )(/)()(xfxfx*x0)(xfm,)(*)()()(*)()(xxxxmxxxx若取故 是 的單根

11、.對(duì) 用牛頓法，其迭代函數(shù)為 *x0)(x)(x18.)()()()()()()()(2xfxfxfxfxfxxxxxg 從而可構(gòu)造迭代法 ),1 ,0()()()()()(21 kxfxfxfxfxfxxkkkkkkk（3.14）它是二階收斂的. 例例7.3.3 7.3.3 方程 的根 是二重根，用上述三種方法求根. 04424xx2* x 解解 先求出三種方法的迭代公式： （1） 牛頓法 .4221kkkkxxxx19 （2） 用（3.13）式 .2221kkkkxxxx （3） 用（3.14）式 .2)2(221kkkkkxxxxx取初值 ，計(jì)算結(jié)果如表7-7. 5.10 x414213

12、562.1414213562.14254976191414215686.1436607143.12411764706.1416666667.1458333333.1132177321xxxxkk）方法（）方法（）方法（三種方法數(shù)值結(jié)果表20 計(jì)算三步，方法（2）及（3）均達(dá)到10位有效數(shù)字，而用牛頓法只有線性收斂，要達(dá)到同樣精度需迭代30次. 21五五 弦截法與拋物線法弦截法與拋物線法 用牛頓法求方程（1.1）的根，每步除計(jì)算 外還要算 ，當(dāng)函數(shù) 比較復(fù)雜時(shí)，計(jì)算 往往較困難，為此可以利用已求函數(shù)值 來(lái)回避導(dǎo)數(shù)值 的計(jì)算. )(kxf)(kxf )( xf)( xf

13、),(),(1kkxfxf)(kxf 1 弦截法弦截法 設(shè) 是 的近似根，利用 構(gòu)造一次插值多項(xiàng)式 ，并用 的根作為新的近似根 . 由于 1,kkxx0)(xf)(),(1kkxfxf)(1xp0)(1xp1kx).()()()(111kkkkkkxxxxxfxfxfxp（5.1）22因此有 ).()()()(111kkkkkkkxxxfxfxfxx（5.2）（5.2）可以看做牛頓公式 )()(1kkkkxfxfxx中的導(dǎo)數(shù) 用差商 取代的結(jié)果.)(kxf 11)(kkkkxxxfxf 幾何意義. 曲線 上橫坐標(biāo)為 的點(diǎn)分別記為 ，則弦線 的斜率等于差商值 , 其方)( xfy 1,kkxx1

14、,kkPP1kkPP11)(kkkkxxxfxf23程是).()()(11kkkkkkxxxxxfxfxfy因之，按（5.2)式求得的 實(shí)際上是弦線 與 軸交點(diǎn)的橫坐標(biāo). 這種算法因此而稱為弦截法弦截法. 1kx1kkPPx表7-524 弦截法與切線法（牛頓法）都是線性化方法，但兩者有本質(zhì)的區(qū)別. 切線法在計(jì)算 時(shí)只用到前一步的值 ，而弦截法（5.2），在求 時(shí)要用到前面兩步的結(jié)果 ，因此使用這種方法必須先給出兩個(gè)開(kāi)始值 .1kxkx1kx1,kkxx01, xx 例例7.3.4 7.3.4 用弦截法解方程 .01)(xxexf 解解 設(shè)取 作為開(kāi)始值，用弦截法求得的結(jié)果見(jiàn)表7-8，比較例7.

15、3.1牛頓法的計(jì)算結(jié)果可以看出，弦截法的收斂速度也是相當(dāng)快的. 6.0,5.010 xx56714.0456709.0356532.026.015.0087kxk計(jì)算結(jié)果表 實(shí)際上，弦截法具有超線性的收斂性. 25 定理定理6 6 假設(shè) 在根 的鄰域 內(nèi)具有二階連續(xù)導(dǎo)數(shù)，且對(duì)任意 有 ，又初值 ，那么當(dāng)鄰域充分小時(shí)，弦截法（5.2）將按階 收斂到根 . 這里 是方程 的正根. )( xf*x*:xxx0)( xf10, xx618.1251p*xp012262 2 拋物線法拋物線法 設(shè)已知方程 的三個(gè)近似根 ，以這三點(diǎn)為節(jié)點(diǎn)構(gòu)造二次插值多項(xiàng)式 ，并適當(dāng)選取 的一個(gè)零點(diǎn) 作為新的近似根，這樣確定

16、的迭代過(guò)程稱拋物線法拋物線法，亦稱密勒（密勒（MllerMller）法）法. 21,kkkxxx0)(xf)(2xp)(2xp1kx 在幾何上，這種方法的基本思想是用拋物線 與 軸的交點(diǎn) 作為所求根 的近似位置（圖7-6). )(2xpy 1kxx*x圖7-627插值多項(xiàng)式 ).)(,)(,)()(12112kkkkkkkkkxxxxxxxfxxxxfxfxp有兩個(gè)零點(diǎn)： ,)(4)(22121kkkkkkkxxxfxfxfxx（5.3）式中 ).(,1211kkkkkkkxxxxxfxxf 問(wèn)題是該如何確定 ，假定在 三個(gè)近似根中， 更接近所求的根 ，為了保證精度，選 （5.3）中較接近 的

17、一個(gè)值作為新的近似根 . 為此，只要取根式前的符號(hào)與 的符號(hào)相同. 1kx21,kkkxxxkx*xkx1kx28例例7.3.5 7.3.5 用拋物線法求解方程 .01)(xxexf 解解 設(shè)用表7-8的前三個(gè)值 56532.0,6.0,5.0210 xxx作為開(kāi)始值，計(jì)算得 .21418.2,83373.2,68910.2,005031.0)(,093271.0)(,175639.0)(0121201210 xxxfxxfxxfxfxfxf故 .75694.2)(,1201212xxxxxfxxf代入（5.3）式求得 .56714.0,)(4)(201222223xxxfxfxfxx29 以

18、上計(jì)算表明，拋物線法比弦截法收斂得更快. 在一定條件下可以證明，對(duì)于拋物線法，迭代誤差有下列漸近關(guān)系式 .*)(6*)(42.01840.1xfxfeekk 可見(jiàn)拋物線法也是超線性收斂的，其收斂的階 ,收斂速度比弦截法更接近于牛頓法. 840.1p 從（5.3）看到，即使 均為實(shí)數(shù)， 也可以是復(fù)數(shù)，所以拋物線法適用于求多項(xiàng)式的實(shí)根和復(fù)根. 21,kkkxxx1kx307.6 7.6 解非線性方程組的牛頓迭代法解非線性方程組的牛頓迭代法 考慮方程組 ,0),(,0),(111nnnxxfxxf（6.1）其中 均為 的多元函數(shù). nff,1),(1nxx 用向量記號(hào)記 , (6.1）就可寫(xiě)成 Tn

19、nTn),f,(fF,R),x,(xx11.0)(xF（6.2） 當(dāng) ，且 中至少有一個(gè)是自變量2n),1(nifi 的非線性函數(shù)時(shí)，稱方程組（6.1）為非線非線性方程組性方程組. ),1(nixi31 非線性方程組求根問(wèn)題是前面介紹的方程（即 ）求根的直接推廣，只要把前面介紹的單變量函數(shù) 看成向量函數(shù) 則可將單變量方程求根方法推廣到方程組（6.2）. 1n)( xf)( xF 若已給出方程（6.2）的一個(gè)近似根 ，將函數(shù) 的分量 在 用多元函數(shù)泰勒展開(kāi)，并取其線性部分，則可表示為 Tknkkxxx),()()(1)()( xF),1)(nixfi)( kx).)()()()()()(kkkx

20、xxFxFxF令上式右端為零，得到線性方程組 ),()()()()(kkkxFxxxF（6.3）32其中 nnnnnnxxfxxfxxfxxfxxfxxfxxfxxfxxfxF)()()()()()()()()()(212221212111（6.4）稱為 的雅可比雅可比(Jacobi)(Jacobi)矩陣矩陣. )( xF 求解線性方程組（6.3）并記解為 ，則得 )1(kx)., 1 , 0()()()(1)()()1(kxFxFxxkkkk（6.5）這就是解非線性方程組（6.2）的牛頓迭代法牛頓迭代法. 33 例例12 12 求解方程組 .052),(,032),(222121221211

21、xxxxfxxxxf給定初值 , 用牛頓法求解. Tx)0.1,5.1()0( 解解 先求雅可比矩陣 .1422821)(,2421)(1212121xxxxxFxxxF由牛頓法（6.5）得 ,5)()(23214228212)(22)(1)(2)(1)(1)(2)(1)(2)()1(kkkkkkkkkkxxxxxxxxxx34即 ).,1 ,0(,)4(25128)(2)(,453)(2)()(1)(2)(2)(2)(12)(12)(2)(2)1(2)(1)(2)(2)(2)(12)(12)(2)(1)1(1kxxxxxxxxxxxxxxxxxxkkkkkkkkkkkkkkkkkk由 逐次迭

22、代得到 Tx)0.1,5.1()0(,)755983.0,488034.1(,)755952.0,488095.1(,)75.0,5.1()3()2()1(TTTxxx 的每一位都是有效數(shù)字. )3(x35v擬Newton方程(1)11(1)(0)(1)(0)(2)(1)1(1)111()(1),()()()(2)AfxAsysxxyf xf xAxxA f xANewton取滿足其中，若 可逆，就可取的選擇多樣化，每一種選擇都確定一種方法，都稱為擬法。36v1.0110101000010(0)(1)(2)(0)(2)(3)01,-=(3),.(-) =,(),()(4),42,(),TTTT

23、TBroydenAAA AusuA A s us sNewtonAA syA syA sthenus syA s sAAs sxNewtonxxAfxxx秩 修改法：對(duì) 作適當(dāng)修改得到取待定則有另一，從擬方程可得故，由用法求利用（ ）和（ ）求再由，求，.37其中 ( 0 )( 0 )( 0 )1000( 0 )(1)( 0 )0(1)( 0 )(1)( 0 )-111(1)( 0 )(1)1,(),(),(),3()()04()()(5)()(xfxAfxHAsHfxxxssfxfxyfxfxHAxxfxf計(jì) 算 過(guò) 程 ：（ ） 選 取計(jì) 算=(2)計(jì) 算=-=當(dāng)在 容 許 誤 差 范 圍 內(nèi)時(shí) 停 止 計(jì) 算 。（ ） 計(jì)