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

一牛頓法及其收斂性牛頓法是一種線(xiàn)性化方法，其基本思想是將非線(xiàn)性方程逐步歸結(jié)為某種線(xiàn)性方程來(lái)求解.設(shè)已知方程有近似根（假定)，將函數(shù)在點(diǎn)展開(kāi)，有于是方程可近似地表示為（1）這是個(gè)線(xiàn)性方程，記其根為，則的計(jì)算公式為10.4牛頓迭代法1一牛頓法及其收斂性牛頓法是一種線(xiàn)性化方法，其基本（2）這就是牛頓(Newton)法.牛頓法的幾何解釋.方程的根可解釋為曲線(xiàn)與軸的交點(diǎn)的橫坐標(biāo)（圖7-3).設(shè)是根的某個(gè)近似值，過(guò)曲線(xiàn)上橫坐標(biāo)為的點(diǎn)引切線(xiàn)，并將該切線(xiàn)與軸的交點(diǎn)的橫坐標(biāo)作為的新的近似值.圖7-32（2）這就是牛頓(Newton)法.牛頓法的幾何解注意到切線(xiàn)方程為這樣求得的值必滿(mǎn)足(1），從而就是牛頓公式（2）的計(jì)算結(jié)果.由于這種幾何背景，牛頓法亦稱(chēng)切線(xiàn)法.牛頓法（2）的收斂性，可直接由上節(jié)定理得到，對(duì)（2）其迭代函數(shù)為由于假定是的一個(gè)單根，即，則由上式知，于是依據(jù)可以斷定，牛頓法在根的鄰近至少是平方收斂的.

3注意到切線(xiàn)方程為這樣求得的值必滿(mǎn)足(1），從而就又因故可得（3.3）

例7.3.1用牛頓法解方程（3.4）

解這里牛頓公式為取迭代初值，迭代結(jié)果列于表7-5中.4又因故可得（所給方程（3.4）實(shí)際上是方程的等價(jià)形式.若用不動(dòng)點(diǎn)迭代到同一精度要迭代28次，可見(jiàn)牛頓法的收斂速度是很快的.5所給方程（3.4）實(shí)際上是方程的等價(jià)形對(duì)于給定的正數(shù)，應(yīng)用牛頓法解二次方程可導(dǎo)出求開(kāi)方值的計(jì)算程序（3.5）這種迭代公式對(duì)于任意初值都是收斂的.事實(shí)上，對(duì)（3.5）式施行配方手續(xù)，易知二牛頓法應(yīng)用舉例6對(duì)于給定的正數(shù)，應(yīng)用牛頓法解二次方程可導(dǎo)出求開(kāi)以上兩式相除得據(jù)此反復(fù)遞推有（3.6）記整理（3.6）式，得7以上兩式相除得據(jù)此反復(fù)遞推有（3.6）記整理（3.6）對(duì)任意，總有，故由上式推知，當(dāng)時(shí)，即迭代過(guò)程恒收斂.

解取初值，對(duì)按（3.5）式迭代3次便得到精度為的結(jié)果（見(jiàn)表7-6).由于公式（3.5）對(duì)任意初值均收斂，并且收斂的速度很快，因此可取確定的初值如編成通用程序.例7.3.2求.8對(duì)任意，總有，故由上式推知，三簡(jiǎn)化牛頓法與牛頓下山法牛頓法的優(yōu)點(diǎn)收斂快，牛頓法的缺點(diǎn)

一每步迭代要計(jì)算及，計(jì)算量較大且有時(shí)計(jì)算較困難，二是初始近似只在根附近才能保證收斂，如給的不合適可能不收斂.9三簡(jiǎn)化牛頓法與牛頓下山法牛頓法的優(yōu)點(diǎn)收斂快，9為克服這兩個(gè)缺點(diǎn)，通?？捎孟率龇椒?（1）簡(jiǎn)化牛頓法，也稱(chēng)平行弦法.其迭代公式為（3.7）迭代函數(shù)若在根附近成立，即取，則迭代法（3.7）局部收斂.10為克服這兩個(gè)缺點(diǎn)，通?？捎孟率龇椒?（1）在（3.7）中取，則稱(chēng)為簡(jiǎn)化牛頓法，這類(lèi)方法計(jì)算量省，但只有線(xiàn)性收斂，其幾何意義是用平行弦與軸交點(diǎn)作為的近似.如圖7-4所示.圖7-411在（3.7）中取，則稱(chēng)為簡(jiǎn)化牛（2）牛頓下山法.牛頓法收斂性依賴(lài)初值的選取.如果偏離所求根較遠(yuǎn)，則牛頓法可能發(fā)散.例如，用牛頓法求方程（3.8）在附近的一個(gè)根.設(shè)取迭代初值，用牛頓法公式（3.9）計(jì)算得迭代3次得到的結(jié)果有6位有效數(shù)字.12（2）牛頓下山法.牛頓法收斂性依賴(lài)初但如果改用作為迭代初值，則依牛頓法公式（3.9）迭代一次得這個(gè)結(jié)果反而比更偏離了所求的根.為了防止迭代發(fā)散，對(duì)迭代過(guò)程再附加一項(xiàng)要求，即具有單調(diào)性：（3.10）滿(mǎn)足這項(xiàng)要求的算法稱(chēng)下山法.將牛頓法與下山法結(jié)合起來(lái)使用，即在下山法保證函數(shù)值穩(wěn)定下降的前提下，用牛頓法加快收斂速度.將牛頓法的計(jì)算結(jié)果13但如果改用作為迭代初值，則依牛頓法公與前一步的近似值適當(dāng)加權(quán)平均作為新的改進(jìn)值（3.11）其中稱(chēng)為下山因子，（3.11）即為（3.12）(3.12)稱(chēng)為牛頓下山法.選擇下山因子時(shí)從開(kāi)始，逐次將減半進(jìn)行試算，直到能使下降條件（3.10）成立為止.若用此法解方程（3.8），當(dāng)時(shí)由（3.9）求得14與前一步的近似值適當(dāng)加權(quán)平均作為新的改進(jìn)值（3.11，它不滿(mǎn)足條件（3.10）.通過(guò)逐次取半進(jìn)行試算，當(dāng)時(shí)可求得.此時(shí)有，而顯然.由計(jì)算時(shí),均能使條件（3.10）成立.計(jì)算結(jié)果如下：即為的近似.一般情況只要能使條件（3.10）成立，則可得到，從而使收斂.15，它不滿(mǎn)足條件（3.10）.通過(guò)四重根情形

設(shè)，整數(shù)，則為方程的重根，此時(shí)有只要仍可用牛頓法（3.2）計(jì)算，此時(shí)迭代函數(shù)的導(dǎo)數(shù)為且，所以牛頓法求重根只是線(xiàn)性收斂.16四重根情形設(shè)則.用迭代法（3.13）求重根，則具有2階收斂，但要知道的重?cái)?shù).構(gòu)造求重根的迭代法，還可令，若是的重根，則若取故是的單根.對(duì)用牛頓法，其迭代函數(shù)為17則.用迭代法（3.13）求從而可構(gòu)造迭代法（3.14）它是二階收斂的.

例7.3.3方程的根是二重根，用上述三種方法求根.

解先求出三種方法的迭代公式：（1）牛頓法18從而可構(gòu)造迭代法（3.14）它是二階收斂的.例7.3.（2）用（3.13）式（3）用（3.14）式取初值，計(jì)算結(jié)果如表7-7.19（2）用（3.13）式（3）用（3.1計(jì)算三步，方法（2）及（3）均達(dá)到10位有效數(shù)字，而用牛頓法只有線(xiàn)性收斂，要達(dá)到同樣精度需迭代30次.20計(jì)算三步，方法（2）及（3）均達(dá)到10位有效數(shù)字，2五弦截法與拋物線(xiàn)法用牛頓法求方程（1.1）的根，每步除計(jì)算外還要算，當(dāng)函數(shù)比較復(fù)雜時(shí)，計(jì)算往往較困難，為此可以利用已求函數(shù)值來(lái)回避導(dǎo)數(shù)值的計(jì)算.1弦截法

設(shè)是的近似根，利用構(gòu)造一次插值多項(xiàng)式，并用的根作為新的近似根.由于（5.1）21五弦截法與拋物線(xiàn)法用牛頓法求方程（1.1）的根，因此有（5.2）（5.2）可以看做牛頓公式中的導(dǎo)數(shù)用差商取代的結(jié)果.幾何意義.曲線(xiàn)上橫坐標(biāo)為的點(diǎn)分別記為，則弦線(xiàn)的斜率等于差商值,其方22因此有（5.2）（5.2）可以看做牛頓公式中的導(dǎo)數(shù)程是因之，按（5.2)式求得的實(shí)際上是弦線(xiàn)與軸交點(diǎn)的橫坐標(biāo).這種算法因此而稱(chēng)為弦截法.表7-523程是因之，按（5.2)式求得的實(shí)際上是弦線(xiàn)弦截法與切線(xiàn)法（牛頓法）都是線(xiàn)性化方法，但兩者有本質(zhì)的區(qū)別.切線(xiàn)法在計(jì)算時(shí)只用到前一步的值，而弦截法（5.2），在求時(shí)要用到前面兩步的結(jié)果，因此使用這種方法必須先給出兩個(gè)開(kāi)始值.

例7.3.4用弦截法解方程

解設(shè)取作為開(kāi)始值，用弦截法求得的結(jié)果見(jiàn)表7-8，比較例7.3.1牛頓法的計(jì)算結(jié)果可以看出，弦截法的收斂速度也是相當(dāng)快的.實(shí)際上，弦截法具有超線(xiàn)性的收斂性.24弦截法與切線(xiàn)法（牛頓法）都是線(xiàn)性化方法，但兩者

定理6假設(shè)在根的鄰域內(nèi)具有二階連續(xù)導(dǎo)數(shù)，且對(duì)任意有，又初值，那么當(dāng)鄰域Δ充分小時(shí)，弦截法（5.2）將按階收斂到根.這里是方程的正根.25定理6假設(shè)在根的鄰域2拋物線(xiàn)法設(shè)已知方程的三個(gè)近似根，以這三點(diǎn)為節(jié)點(diǎn)構(gòu)造二次插值多項(xiàng)式，并適當(dāng)選取的一個(gè)零點(diǎn)作為新的近似根，這樣確定的迭代過(guò)程稱(chēng)拋物線(xiàn)法，亦稱(chēng)密勒（Müller）法.在幾何上，這種方法的基本思想是用拋物線(xiàn)與軸的交點(diǎn)作為所求根的近似位置（圖7-6).圖7-6262拋物線(xiàn)法設(shè)已知方程的三插值多項(xiàng)式有兩個(gè)零點(diǎn)：（5.3）式中問(wèn)題是該如何確定，假定在三個(gè)近似根中，更接近所求的根，為了保證精度，選（5.3）中較接近的一個(gè)值作為新的近似根.為此，只要取根式前的符號(hào)與的符號(hào)相同.27插值多項(xiàng)式有兩個(gè)零點(diǎn)：（5.3）式中問(wèn)題是該如例7.3.5用拋物線(xiàn)法求解方程

解設(shè)用表7-8的前三個(gè)值作為開(kāi)始值，計(jì)算得故代入（5.3）式求得28例7.3.5用拋物線(xiàn)法求解方程解設(shè)用表7-以上計(jì)算表明，拋物線(xiàn)法比弦截法收斂得更快.在一定條件下可以證明，對(duì)于拋物線(xiàn)法，迭代誤差有下列漸近關(guān)系式可見(jiàn)拋物線(xiàn)法也是超線(xiàn)性收斂的，其收斂的階,收斂速度比弦截法更接近于牛頓法.從（5.3）看到，即使均為實(shí)數(shù)，也可以是復(fù)數(shù)，所以?huà)佄锞€(xiàn)法適用于求多項(xiàng)式的實(shí)根和復(fù)根.29以上計(jì)算表明，拋物線(xiàn)法比弦截法收斂得更快.7.6解非線(xiàn)性方程組的牛頓迭代法考慮方程組（6.1）其中均為的多元函數(shù).用向量記號(hào)記,(6.1）就可寫(xiě)成（6.2）當(dāng)，且中至少有一個(gè)是自變量的非線(xiàn)性函數(shù)時(shí)，稱(chēng)方程組（6.1）為非線(xiàn)性方程組.307.6解非線(xiàn)性方程組的牛頓迭代法考慮方程組非線(xiàn)性方程組求根問(wèn)題是前面介紹的方程（即）求根的直接推廣，只要把前面介紹的單變量函數(shù)看成向量函數(shù)則可將單變量方程求