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

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

2、坐標(biāo)（圖7-3). 0)(xf*x)( xfy x 設(shè) 是根 的某個近似值，過曲線 上橫坐標(biāo)為 的點 引切線，并將該切線與 軸的交點的橫坐標(biāo) 作為 的新的近似值. kx*x)( xfy kxkPx1kx*x圖7-33注意到切線方程為 ).)()(kkkxxxfxfy這樣求得的值 必滿足(1），從而就是牛頓公式（2）的計算結(jié)果. 由于這種幾何背景，牛頓法亦稱切線法切線法.1kx 牛頓法（2）的收斂性，可直接由上節(jié)定理得到，對（2）其迭代函數(shù)為 ,)()()(xfxfxxg由于 .)()()()(2xfxfxfxg 假定 是 的一個單根，即 ，則由上式知 ，于是依據(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計算結(jié)果表 所給方程（3.4）實際上是方程 的等價形式. 若用不動點迭代到同一精度要迭代28次，

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

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

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

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

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

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

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

11、.對 用牛頓法，其迭代函數(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取初值 ，計算結(jié)果如表7-7. 5.10 x414213

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

13、),(),(1kkxfxf)(kxf 1 弦截法弦截法 設(shè) 是 的近似根，利用 構(gòu)造一次插值多項式 ，并用 的根作為新的近似根 . 由于 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)為 的點分別記為 ，則弦線 的斜率等于差商值 , 其方)( xfy 1,kkxx1

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

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

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

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

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

19、nTn),f,(fF,R),x,(xx11.0)(xF（6.2） 當(dāng) ，且 中至少有一個是自變量2n),1(nifi 的非線性函數(shù)時，稱方程組（6.1）為非線非線性方程組性方程組. ),1(nixi31 非線性方程組求根問題是前面介紹的方程（即 ）求根的直接推廣，只要把前面介紹的單變量函數(shù) 看成向量函數(shù) 則可將單變量方程求根方法推廣到方程組（6.2）. 1n)( xf)( xF 若已給出方程（6.2）的一個近似根 ，將函數(shù) 的分量 在 用多元函數(shù)泰勒展開，并取其線性部分，則可表示為 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秩 修改法：對 作適當(dāng)修改得到取待定則有另一，從擬方程可得故，由用法求利用（ ）和（ ）求再由，求，.37其中 ( 0 )( 0 )( 0 )1000( 0 )(1)( 0 )0(1)( 0 )(1)( 0 )-111(1)( 0 )(1)1,(),(),(),3()()04()()(5)()(xfxAfxHAsHfxxxssfxfxyfxfxHAxxfxf計 算 過 程 ：（ ） 選 取計 算=(2)計 算=-=當(dāng)在 容 許 誤 差 范 圍 內(nèi)時 停 止 計 算 。（ ） 計