數(shù)值分析第7章4-6節(jié))

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

2、交點(diǎn)的橫坐標(biāo))( xfy x圖7-3（圖7-3). 3 設(shè) 是根 的某個近似值，過曲線 上橫坐標(biāo)為 的點(diǎn) 引切線，并將該切線與 軸的交點(diǎn)的橫坐標(biāo) 作為 的新的近似值. kx*x)( xfy kxkPx1kx*x 注意到切線方程為 ).)()(kkkxxxfxfy這樣求得的值 必滿足（4.1），從而就是牛頓公式（4.2）的計(jì)算結(jié)果. 1kx 由于這種幾何背景，牛頓法也稱切線法切線法. 由定理4，可以直接得到牛頓法的收斂性.),1 ,0()()(1kxfxfxxkkkk（4.2）.0)()(kkkxxxfxf（4.1）4,)()()(xfxfxx由于 .)()()()(2xfxfxfx 假定 是

3、的一個單根，)( xf*x即 ，0*)(,0*)(xfxf則由上式知，0*)( x (4.2)的迭代函數(shù)為 在根 的鄰近是平方收斂的. *x于是依據(jù)定理4可以斷定，牛頓法 又因 ,*)(*)(*)(xfxfx ),1 ,0()()(1kxfxfxxkkkk（4.2）5故由（2.9）可得 .*)(2*)(*)(*lim21xfxfxxxxkkk （4.3） 例例7 7.01exx（4.4） 解解,1e1kxkkkxxxxk取迭代初值 ，迭代結(jié)果列于表7-5中. 5.00 x用牛頓法解方程 這里牛頓公式為 所給方程（4.4）實(shí)際上是方程 的等價形式. xx e.!*)()(1pxeeppkk（2.

4、9）656714.0356716.0257102.015.00kxk計(jì)算結(jié)果5表7 牛頓法的計(jì)算步驟： 步驟步驟1 1 準(zhǔn)備準(zhǔn)備選定初始近似值 ，0 x).(00 xff 步驟步驟2 2 迭代迭代0001/ ffxx迭代一次，得新的近似值 ，1x).(),(1111xffxff 若用不動點(diǎn)迭代到同一精度 可見牛頓法的收斂速度是很快的.要迭代17次.),(00 xff計(jì)算 按公式 計(jì)算 7則終止迭代，以 作為所求的根；1x 此處 是允許誤差，而 21,，時當(dāng)時當(dāng)CxxxxCxxx1101101其中 是取絕對誤差或相對誤差的控制常數(shù)，C.1C 步驟步驟4 4 修改修改 如果迭代次數(shù)達(dá)到預(yù)先指定的次

5、數(shù) ，N 步驟步驟3 3 控制控制如果 滿足 或 ，1x121f否則轉(zhuǎn)步驟4. 一般可取8或者 ，則方法失敗；01f 否則以 代替 轉(zhuǎn)步驟2繼續(xù)迭代.),(111ffx),(000ffx9 7.4.2 牛頓法應(yīng)用舉例牛頓法應(yīng)用舉例 對于給定的正數(shù) ，應(yīng)用牛頓法解二次方程 C,02 Cx可導(dǎo)出求開方值 的計(jì)算程序 C).(211kkkxCxx（4.5）這種迭代公式對于任意初值 都是收斂的. 00 x 事實(shí)上，對（4.5）式施行配方手續(xù)，易知 ;)(2121CxxCxkkk10以上兩式相除得 .211CxCxCxCxkkkk據(jù)此反復(fù)遞推有 .20011kCxCxCxCxkk（4.6）記 ,00Cx

6、Cxq.)(2121CxxCxkkk11.1222kkqqCCxk 對任意 ，00 x總有 ，1q時 ，Cxk723805.104723805.103723837.102750000.101100kxk計(jì)算結(jié)果6表7 解解取初值 ，對100 x 按（4.5）式迭代3次115C便得到精度為 的結(jié)果610 例例8 8 求 . 115整理（4.6）式，得 故由上式推知，即迭代過程恒收斂. k當(dāng)（見表7-6). .20011kCxCxCxCxkk（4.6）).(211kkkxCxx（4.5）12 由于公式（4.5）對任意初值 均收斂，并且收斂的速度很快，因此可取確定的初值,如 編成通用程序. 00 x

7、10 x).(211kkkxCxx（4.5）13 7.4.3 簡化牛頓法與牛頓下山法簡化牛頓法與牛頓下山法 牛頓法的優(yōu)點(diǎn)是收斂快，缺點(diǎn)一是每步迭代要計(jì)算 及 ，計(jì)算量較大且有時 計(jì)算較困難，)(kxf)(kxf )(kxf 為克服這兩個缺點(diǎn)，通常可用下述方法. （1 1） 簡化牛頓法，簡化牛頓法，.,)(101CxCfxxkkk，（4.7）迭代函數(shù) ).()(xCfxx 二是初始近似 只在根 附近才能保證收斂，如0 x*x0 x給的不合適可能不收斂. 其迭代公式為 也稱平行弦法.14 若在根 附近成立 ，即取*x1)(1)(xfCx,2)(0 xfC則迭代法（4.7）局部收斂. 在（4.7）中

8、取 ，則稱為簡化牛頓法簡化牛頓法，)(10 xfC這類方法計(jì)算量省，但只有線性收斂， 其幾何意義是用平行弦與 軸交點(diǎn)作為 的近似. x*x 如圖7-4所示. 圖7-4即 )()(01xfxfxxkkk.,1 ,0)(1CxCfxxkkk（4.7）.,1 ,0)(1CxCfxxkkk（4.7）15 （2 2） 牛頓下山法牛頓下山法. . 牛頓法收斂性依賴初值 的選取. 0 x 如果 偏離所求根 較遠(yuǎn)，則牛頓法可能發(fā)散.0 x*x 例如，用牛頓法求方程 .013 xx（4.8）在 附近的一個根 . 5.1x*x 設(shè)取迭代初值 ，用牛頓法公式 5.10 x131231kkkkkxxxxx（4.9）計(jì)

9、算得 16.32472.1,32520.1,34783.1321xxx迭代3次得到的結(jié)果 有6位有效數(shù)字. 3x 但如果改用 作為迭代初值，則依牛頓法公式（4.9）迭代一次得 6.00 x.9.171x這個結(jié)果反而比 更偏離了所求的根 . 6.00 x32472.0* x 為了防止迭代發(fā)散，對迭代過程再附加一項(xiàng)要求，即具有單調(diào)性： .)()(1kkxfxf（4.10）滿足這項(xiàng)要求的算法稱下山法下山法. 131231kkkkkxxxxx（4.9）17 將牛頓法與下山法結(jié)合起來使用，即在下山法保證函數(shù)值穩(wěn)定下降的前提下，用牛頓法加快收斂速度. 將牛頓法的計(jì)算結(jié)果 )()(1kkkkxfxfxx與前

10、一步的近似值 適當(dāng)加權(quán)平均作為新的改進(jìn)值 kx,)1(11kkkxxx（4.11）其中 稱為下山因子，)0(),1 ,0()()(1kxfxfxxkkkk（4.12）(4.12)稱為牛頓下山法牛頓下山法. （4.11）即為 18 選擇下山因子時從 開始，逐次將 減半進(jìn)行試算，1 若用此法解方程（4.8），當(dāng) 時由（4.9）求得6.00 x直到能使下降條件（4.10）成立為止. ，它不滿足條件（4.10）.9.171x 通過 逐次取半進(jìn)行試算，當(dāng) 時可求得32/1,140625. 11x此時有 ，656643.0)(1xf顯然 . )()(01xfxf384.1)(0 xf而 由 計(jì)算 時 ,

11、均能使條件（4.10）成立. 計(jì)算結(jié)果如下 ： 1x,32xx1.)()(1kkxfxf（4.10）131231kkkkkxxxxx（4.9）.013 xx（4.8）.)()(1kkxfxf（4.10）.)()(1kkxfxf（4.10）19;1866.0)(,36181.122xfx 即為 的近似. 4x*x則可得到 ，從而使 收斂.0)(limkkxfkx一般情況只要能使條件（4.10）成立，;00667.0)(,32628.133xfx.0000086.0)(,32472.144xfx.)()(1kkxfxf（4.10）20 7.4.4 重根情形重根情形 設(shè) ，整數(shù) ，)(*)()(xg

12、xxxfm0*)(,2xgm則 為方程 的 重根，*x0)(xfm.0*)(,0*)(*)(*)()1(xfxfxfxfmm只要 仍可用牛頓法（4.2）計(jì)算，此時迭代函數(shù) 0)(kxf)()()(xfxfxx的導(dǎo)數(shù)為 ，011mx*)(此時有 且 ，所以牛頓法求重根只是線性收斂. 1*)( x),1 ,0()()(1kxfxfxxkkkk（4.2）21,)()()(xfxfmxx則 . 0*)( x),1 ,0()()(1kxfxfmxxkkkk（4.13）求 重根，則具有2階收斂，但要知道 的重?cái)?shù) . mm*x 構(gòu)造求重根的迭代法，還可令 ，)(/)()(xfxfx若 是 的 重根，則 *x

13、0)(xfm,)(*)()()(*)()(xgxxxmgxgxxx若取 用迭代法 22)()()(xxxx從而可構(gòu)造迭代法 ),1 ,0()()()()()(21 kxfxfxfxfxfxxkkkkkkk（4.14）它是2階收斂的. 故 是 的單根. *x0)(x對它用牛頓法，其迭代函數(shù)為 .)()()()()(2xfxfxfxfxfx 23 例例9 9方程 的根 是二重根，04424xx2* x 解解 （1） 牛頓法 .42844423241kkkkkkkkkxxxxxxxxx用上述三種方法求根. 先求出三種方法的迭代公式： （2） 用（4.13）式 .22,221kkkkxxxxm （3）

14、 用（4.14）式 .2)2(221kkkkkxxxxx取初值 ，計(jì)算結(jié)果如表7-7. 5.10 x),1 ,0()()(1kxfxfmxxkkkk（4.13）),1 ,0()()()()()(21 kxfxfxfxfxfxxkkkkkkk,44)(24xxxf24414213562141421356214254976191341421143814142156861436607143124117647061416666667145833333311321.xxxxkk方法（3）方法（2）方法（1）三種方法數(shù)值結(jié)果7表7 從結(jié)果看出，經(jīng)過三步計(jì)算，方法（2）及（3）均達(dá)到10位有效數(shù)字，而由于牛

15、頓法只有線性收斂，所以要達(dá)到同樣精度需迭代30次. 257.5 弦截法與拋物線法弦截法與拋物線法 當(dāng)函數(shù) 比較復(fù)雜時，計(jì)算 往往較困難，)( xf)(xf 值 的計(jì)算. )(kxf 為此可以利用已求函數(shù)值 來回避導(dǎo)數(shù)),(),(1kkxfxf還要算 .)(kxf 用牛頓法求方程 的根，每步除計(jì)算 外，)(kxf0)(xf26 7.5.1 弦截法弦截法 設(shè) 是 的近似根，1,kkxx0)(xf利用 )(),(1kkxfxf構(gòu)造一次插值多項(xiàng)式 ，并用 的根作為新的近似根 . )(1xp0)(1xp1kx，)()()()(kkkkkkxxxxxfxfxfxp111（5.1） 由于 因此有 ，)()(

16、)()(111kkkkkkkxxxfxfxfxx（5.2）27（5.2）可以看作將牛頓公式 )()(1kkkkxfxfxx中的導(dǎo)數(shù) 用差商 取代的結(jié)果.)(kxf 11)(kkkkxxxfxf 接著討論幾何意義. 曲線 上橫坐標(biāo)為 的點(diǎn)分別記為 ，)( xfy 1,kkxx1,kkPP則弦線 的斜率等于差商值 , 1kkPP11)(kkkkxxxfxf28).()()(11kkkkkkxxxxxfxfxfy按（5.2)式求得的 實(shí)際上是弦線 與 軸交點(diǎn)的橫坐標(biāo). 1kx1kkPPx表7-5這種算法因此而稱為弦截法弦截法. 其方程為).()()()(111kkkkkkkxxxfxfxfxx（5.

17、2）29 而弦截法（5.2），在求 時要用到前面兩步的結(jié)果 ，1kx1,kkxx 弦截法與切線法（牛頓法）都是線性化方法，但兩者有本質(zhì)的區(qū)別. 切線法在計(jì)算 時只用到前一步的值 .kx1kx因此使用這種方法必須先給出兩個開始值 .01, xx 例例1010.01e)(xxxf 解解56714.0456709.0356532.026.015.00kxk計(jì)算結(jié)果8表7 用弦截法解方程 設(shè)取 作為6.0,5.010 xx開始值，用弦截法求得的結(jié)果見表7-8，).()()()(111kkkkkkkxxxfxfxfxx（5.2）30 實(shí)際上，弦截法具有超線性的收斂性. 比較例7牛頓法的計(jì)算結(jié)果可以看出，

18、弦截法的收斂速度也是相當(dāng)快的. 定理定理6 6這里 是方程 的正根. 618.1251p012假設(shè) 在根 的鄰域 內(nèi))(xf*x*:xx且對任意 有 ，x0)( xf,10 xx具有二階連續(xù)導(dǎo)數(shù)，那么當(dāng)鄰域充分小時，又初值階收斂到根 . *xp弦截法（5.2）將按).()()()(111kkkkkkkxxxfxfxfxx（5.2）31 7.5.2 拋物線法拋物線法 設(shè)已知方程 的三個近似根 ，21,kkkxxx0)(xf 幾何上，這種方法的基本思想是用拋物線與 軸的交點(diǎn) 作為所求根 的近似位置（圖7-6). 1kxx*x圖7-6以這三點(diǎn)為節(jié)點(diǎn)構(gòu)造二次插值多項(xiàng)式 ,)(2xp 的一個零點(diǎn) 作為新

19、的近似根，)(2xp1kx并適當(dāng)選取 這樣確定的迭代過程稱為拋拋物線法物線法，也稱密勒（密勒（Mller）法）法.32插值多項(xiàng)式 )(,)(,)()(12112kkkkkkkkkxxxxxxxfxxxxfxfxp有兩個零點(diǎn)： ,)(4)(22121kkkkkkkxxxfxfxfxx（5.3）式中 ).(,1211kkkkkkkxxxxxfxxf 問題是該如何確定 .1kx 假定在 三個近似根中， 更接近所求的根 .21,kkkxxxkx*x33 為了保證精度，選（5.3）中較接近 的一個值作為新的近似根 . kx1kx 為此，只要取根式前的符號與 的符號相同. 例例1111.01e)(xxxf

20、用拋物線法求解方程 解解設(shè)用表7-8的前三個值 56532.0,6.0,5.0210 xxx作為開始值，計(jì)算得 ,093271.0)(,175639.0)(10 xfxf,005031.0)(2xf,68910.2,01xxf,)(4)(22121kkkkkkkxxxfxfxfxx（5.3）567140456709035653202601500.kxk計(jì)算結(jié)果8表734故 .75694.2)(,1201212xxxxxfxxf代入（5.3）式求得 .56714.0,)(4)(201222223xxxfxfxfxx,83373.2,12xxf.21418.2,012xxxf 以上計(jì)算表明，拋物線

21、法比弦截法收斂得更快. 在一定條件下可以證明，對于拋物線法，迭代誤差有下列漸近關(guān)系式 .*)(6*)(42.01840.1xfxfeekk ,)(4)(22121kkkkkkkxxxfxfxfxx（5.3）35可見拋物線法也是超線性收斂的，其收斂的階 ,840.1p 從（5.3）看到，即使 均為實(shí)數(shù)， 也可以是復(fù)數(shù)，所以拋物線法適用于求多項(xiàng)式的實(shí)根和復(fù)根. 21,kkkxxx1kx收斂速度比弦截法更接近于牛頓法. ,)(4)(22121kkkkkkkxxxfxfxfxx（5.3）367.6 解非線性方程組的牛頓迭代法解非線性方程組的牛頓迭代法 考慮方程組 ,0),(,0),(111nnnxxf

22、xxf（6.1）其中 均為 的多元函數(shù). nff,1),(1nxx 用向量記號記 , T1T1R),(,),(nnnffxxFx0.)(xF（6.2）(6.1）就可寫成 37 非線性方程組求根問題是前面介紹的方程（即 ）求根的直接推廣.1n 若已給出方程（6.2）的一個近似根 ，T1),()()()(knkkxxx將函數(shù) 的分量 在 用多元函數(shù))( xF),)(nifi1x)(kx 的非線性函數(shù)時，稱方程組（6.1）為非線非線性方程組性方程組. ), 1(nixi 當(dāng) ，且 中至少有一個是自變量2n), 1(nifi 只要把前面介紹的單變量函數(shù) 看成向量函數(shù))( xf，)( xF則可將單變量方程求根方法推廣到方程組（6.2）. 泰勒展開，并取其線性部分，則可表示為 .0)(xF（6.2）38令上式右端為零，得到線性方程組 ),()()()()(kkkxFxxx