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

第三節(jié)牛頓迭代法1第一頁(yè)，共四十頁(yè)，2022年，8月28日（2）這就是牛頓(Newton)法.牛頓法的幾何解釋.方程的根可解釋為曲線與軸的交點(diǎn)的橫坐標(biāo)（圖7-3).設(shè)是根的某個(gè)近似值，過(guò)曲線上橫坐標(biāo)為的點(diǎn)引切線，并將該切線與軸的交點(diǎn)的橫坐標(biāo)作為的新的近似值.圖7-3第二頁(yè)，共四十頁(yè)，2022年，8月28日注意到切線方程為這樣求得的值必滿足(1），從而就是牛頓公式（2）的計(jì)算結(jié)果.由于這種幾何背景，牛頓法亦稱切線法.牛頓法（2）的收斂性，可直接由上節(jié)定理得到，對(duì)（2）其迭代函數(shù)為由于假定是的一個(gè)單根，即，則由上式知，于是依據(jù)可以斷定，牛頓法在根的鄰近至少是平方收斂的.

第三頁(yè)，共四十頁(yè)，2022年，8月28日又因故可得（3.3）

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

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

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

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

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

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

解先求出三種方法的迭代公式：（1）牛頓法第十八頁(yè)，共四十頁(yè)，2022年，8月28日（2）用（3.13）式（3）用（3.14）式取初值，計(jì)算結(jié)果如表7-7.第十九頁(yè)，共四十頁(yè)，2022年，8月28日計(jì)算三步，方法（2）及（3）均達(dá)到10位有效數(shù)字，而用牛頓法只有線性收斂，要達(dá)到同樣精度需迭代30次.第二十頁(yè)，共四十頁(yè)，2022年，8月28日五弦截法與拋物線法用牛頓法求方程（1.1）的根，每步除計(jì)算外還要算，當(dāng)函數(shù)比較復(fù)雜時(shí)，計(jì)算往往較困難，為此可以利用已求函數(shù)值來(lái)回避導(dǎo)數(shù)值的計(jì)算.1弦截法

設(shè)是的近似根，利用構(gòu)造一次插值多項(xiàng)式，并用的根作為新的近似根.由于（5.1）第二十一頁(yè)，共四十頁(yè)，2022年，8月28日因此有（5.2）（5.2）可以看做牛頓公式中的導(dǎo)數(shù)用差商取代的結(jié)果.幾何意義.曲線上橫坐標(biāo)為的點(diǎn)分別記為，則弦線的斜率等于差商值,其方第二十二頁(yè)，共四十頁(yè)，2022年，8月28日程是因之，按（5.2)式求得的實(shí)際上是弦線與軸交點(diǎn)的橫坐標(biāo).這種算法因此而稱為弦截法.表7-5第二十三頁(yè)，共四十頁(yè)，2022年，8月28日弦截法與切線法（牛頓法）都是線性化方法，但兩者有本質(zhì)的區(qū)別.切線法在計(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í)際上，弦截法具有超線性的收斂性.第二十四頁(yè)，共四十頁(yè)，2022年，8月28日

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

解設(shè)用表7-8的前三個(gè)值作為開(kāi)始值，計(jì)算得故代入（5.3）式求得第二十八頁(yè)，共四十頁(yè)，2022年，8月28日以上計(jì)算表明，拋物線法比弦截法收斂得更快.在一定條件下可以證明，對(duì)于拋物線法，迭代誤差有下列漸近關(guān)系式可見(jiàn)拋物線法也是超線性收斂的，其收斂的階,收斂速度比弦截法更接近于牛頓法.從（5.3）看到，即使均為實(shí)數(shù)，也可以是復(fù)數(shù)，所以拋物線法適用于求多項(xiàng)式的實(shí)根和復(fù)根.第二十九頁(yè)，共四十頁(yè)，2022年，8月28日7.6解非線性方程組的牛頓迭代法考慮方程組（6.1）其中均為的多元函數(shù).用向量記號(hào)記,(6.1）就可寫成（6.2）當(dāng)，且中至少有一個(gè)是自變量的非線性函數(shù)時(shí)，稱方程組（6.1）為非線性方程組.第三十頁(yè)，共四十頁(yè)，2022年，8月28日非線性方程組求根問(wèn)題是前面介紹的方程（即）求根的直接推廣，只要把前面介紹的單變量函數(shù)看成向量函數(shù)則可將單變量方程求根方法推廣到方程組（6.2）.若已給出方程（6.2）的一個(gè)近似根，將函數(shù)的分量在用多元函數(shù)泰勒展開(kāi)，并取其線性部分，則可表示為令上式右端為零，得到線性方程組（6.3）第三十一頁(yè)，共四十頁(yè)，2022年，8月28日其中（6.4）稱為的雅可比(Jacobi)矩陣.求解線性方程組（6.3）并記解為，則得（6.5）這就是解非線性方程組（6.2）的牛頓迭代法.

第三十二頁(yè)，共四十頁(yè)，2022年，8月28日

例12求解方程組給定初值,用牛頓法求解.

解先求雅可比矩陣由牛頓