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

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

第3頁，課件共40頁，創(chuàng)作于2023年2月又因故可得（3.3）

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

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

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

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

設(shè)，整數(shù)，則為方程的重根，此時有只要仍可用牛頓法（3.2）計算，此時迭代函數(shù)的導(dǎo)數(shù)為且，所以牛頓法求重根只是線性收斂.第16頁，課件共40頁，創(chuàng)作于2023年2月則.用迭代法（3.13）求重根，則具有2階收斂，但要知道的重數(shù).構(gòu)造求重根的迭代法，還可令，若是的重根，則若取故是的單根.對用牛頓法，其迭代函數(shù)為第17頁，課件共40頁，創(chuàng)作于2023年2月從而可構(gòu)造迭代法（3.14）它是二階收斂的.

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

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

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

例7.3.4用弦截法解方程

解設(shè)取作為開始值，用弦截法求得的結(jié)果見表7-8，比較例7.3.1牛頓法的計算結(jié)果可以看出，弦截法的收斂速度也是相當(dāng)快的.實際上，弦截法具有超線性的收斂性.第24頁，課件共40頁，創(chuàng)作于2023年2月

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

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

第32頁，課件共40頁，創(chuàng)作于2023年2月

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

解先求雅可比矩陣由牛頓