牛頓法及其收斂性課件

牛頓法及其收斂性課件1第一頁(yè)，共三十一頁(yè)，編輯于2023年，星期日（4.2）這就是牛頓(Newton)法.

牛頓法的幾何解釋.

方程的根可解釋為曲線與軸的交點(diǎn)的橫坐標(biāo)（圖7-3).

設(shè)是根的某個(gè)近似值，過曲線上橫坐標(biāo)為的點(diǎn)引切線，并將該切線與軸的交點(diǎn)的橫坐標(biāo)作為的新的近似值.圖7-32第二頁(yè)，共三十一頁(yè)，編輯于2023年，星期日注意到切線方程為這樣求得的值必滿足(4.1），從而就是牛頓公式（4.2）的計(jì)算結(jié)果.由于這種幾何背景，牛頓法亦稱切線法.

牛頓法（4.2）的收斂性，可直接由定理4得到，對(duì)（4.2）其迭代函數(shù)為由于假定是的一個(gè)單根，即，則由上式知，于是依據(jù)定理4可以斷定，牛頓法在根的鄰近是平方收斂的.3第三頁(yè)，共三十一頁(yè)，編輯于2023年，星期日又因故由（2.9）可得（4.3）

例7用牛頓法解方程（4.4）

解這里牛頓公式為取迭代初值，迭代結(jié)果列于表7-5中.4第四頁(yè)，共三十一頁(yè)，編輯于2023年，星期日

所給方程（4.4）實(shí)際上是方程的等價(jià)形式.若用不動(dòng)點(diǎn)迭代到同一精度要迭代17次，可見牛頓法的收斂速度是很快的.

牛頓法的計(jì)算步驟：

步驟1準(zhǔn)備選定初始近似值，計(jì)算

步驟2迭代按公式迭代一次，得新的近似值，計(jì)算

步驟3控制如果滿足或，則終5第五頁(yè)，共三十一頁(yè)，編輯于2023年，星期日止迭代，以作為所求的根；否則轉(zhuǎn)步驟4.此處是允許誤差，而其中是取絕對(duì)誤差或相對(duì)誤差的控制常數(shù)，一般可取

.

步驟4修改如果迭代次數(shù)達(dá)到預(yù)先指定的次數(shù)，或者，則方法失?。环駝t以代替轉(zhuǎn)步驟2繼續(xù)迭代.6第六頁(yè)，共三十一頁(yè)，編輯于2023年，星期日7.4.2牛頓法應(yīng)用舉例

對(duì)于給定的正數(shù)，應(yīng)用牛頓法解二次方程可導(dǎo)出求開方值的計(jì)算程序（4.5）這種迭代公式對(duì)于任意初值都是收斂的.

事實(shí)上，對(duì)（4.5）式施行配方手續(xù)，易知7第七頁(yè)，共三十一頁(yè)，編輯于2023年，星期日以上兩式相除得據(jù)此反復(fù)遞推有（4.6）記整理（4.6）式，得8第八頁(yè)，共三十一頁(yè)，編輯于2023年，星期日

對(duì)任意，總有，故由上式推知，當(dāng)時(shí)，即迭代過程恒收斂.

解取初值，對(duì)按（4.5）式迭代3次便得到精度為的結(jié)果（見表7-6).

由于公式（4.5）對(duì)任意初值均收斂，并且收斂的速度很快，因此可取確定的初值如編成通用程序.

例8求.9第九頁(yè)，共三十一頁(yè)，編輯于2023年，星期日7.4.3簡(jiǎn)化牛頓法與牛頓下山法

牛頓法的優(yōu)點(diǎn)是收斂快，缺點(diǎn)一是每步迭代要計(jì)算及，計(jì)算量較大且有時(shí)計(jì)算較困難，二是初始近似只在根附近才能保證收斂，如給的不合適可能不收斂.

為克服這兩個(gè)缺點(diǎn)，通?？捎孟率龇椒?

（1）簡(jiǎn)化牛頓法，也稱平行弦法.其迭代公式為（4.7）迭代函數(shù)

若在根附近成立，即取，則迭代法（4.7）局部收斂.10第十頁(yè)，共三十一頁(yè)，編輯于2023年，星期日

在（4.7）中取，則稱為簡(jiǎn)化牛頓法，這類方法計(jì)算量省，但只有線性收斂，其幾何意義是用平行弦與軸交點(diǎn)作為的近似.如圖7-4所示.圖7-411第十一頁(yè)，共三十一頁(yè)，編輯于2023年，星期日

（2）牛頓下山法.

牛頓法收斂性依賴初值的選取.如果偏離所求根較遠(yuǎn)，則牛頓法可能發(fā)散.

例如，用牛頓法求方程（4.8）在附近的一個(gè)根.

設(shè)取迭代初值，用牛頓法公式（4.9）計(jì)算得迭代3次得到的結(jié)果有6位有效數(shù)字.12第十二頁(yè)，共三十一頁(yè)，編輯于2023年，星期日

但如果改用作為迭代初值，則依牛頓法公式（4.9）迭代一次得這個(gè)結(jié)果反而比更偏離了所求的根.

為了防止迭代發(fā)散，對(duì)迭代過程再附加一項(xiàng)要求，即具有單調(diào)性：（4.10）滿足這項(xiàng)要求的算法稱下山法.

將牛頓法與下山法結(jié)合起來(lái)使用，即在下山法保證函數(shù)值穩(wěn)定下降的前提下，用牛頓法加快收斂速度.

將牛頓法的計(jì)算結(jié)果13第十三頁(yè)，共三十一頁(yè)，編輯于2023年，星期日與前一步的近似值適當(dāng)加權(quán)平均作為新的改進(jìn)值（4.11）其中稱為下山因子，（4.11）即為（4.12）(4.12)稱為牛頓下山法.

選擇下山因子時(shí)從開始，逐次將減半進(jìn)行試算，直到能使下降條件（4.10）成立為止.

若用此法解方程（4.8），當(dāng)時(shí)由（4.9）求得14第十四頁(yè)，共三十一頁(yè)，編輯于2023年，星期日

，它不滿足條件（4.10）.

通過逐次取半進(jìn)行試算，當(dāng)時(shí)可求得

.此時(shí)有，而顯然.

由計(jì)算時(shí),均能使條件（4.10）成立.計(jì)算結(jié)果如下：

即為的近似.一般情況只要能使條件（4.10）成立，則可得到，從而使收斂.15第十五頁(yè)，共三十一頁(yè)，編輯于2023年，星期日7.4.4重根情形

設(shè)，整數(shù)，則為方程的重根，此時(shí)有只要仍可用牛頓法（4.2）計(jì)算，此時(shí)迭代函數(shù)的導(dǎo)數(shù)為且，所以牛頓法求重根只是線性收斂.若取16第十六頁(yè)，共三十一頁(yè)，編輯于2023年，星期日則.用迭代法（4.13）求重根，則具有2階收斂，但要知道的重?cái)?shù).

構(gòu)造求重根的迭代法，還可令，若是的重根，則故是的單根.對(duì)它用牛頓法，其迭代函數(shù)為17第十七頁(yè)，共三十一頁(yè)，編輯于2023年，星期日從而可構(gòu)造迭代法（4.14）它是二階收斂的.

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

解先求出三種方法的迭代公式：

（1）牛頓法18第十八頁(yè)，共三十一頁(yè)，編輯于2023年，星期日

（2）用（4.13）式

（3）用（4.14）式取初值，計(jì)算結(jié)果如表7-7.19第十九頁(yè)，共三十一頁(yè)，編輯于2023年，星期日

計(jì)算三步，方法（2）及（3）均達(dá)到10位有效數(shù)字，而用牛頓法只有線性收斂，要達(dá)到同樣精度需迭代30次.20第二十頁(yè)，共三十一頁(yè)，編輯于2023年，星期日7.5弦截法與拋物線法

用牛頓法求方程（1.1）的根，每步除計(jì)算外還要算，當(dāng)函數(shù)比較復(fù)雜時(shí)，計(jì)算往往較困難，為此可以利用已求函數(shù)值來(lái)回避導(dǎo)數(shù)值的計(jì)算.

7.5.1弦截法

設(shè)是的近似根，利用構(gòu)造一次插值多項(xiàng)式，并用的根作為新的近似根.由于（5.1）21第二十一頁(yè)，共三十一頁(yè)，編輯于2023年，星期日因此有（5.2）（5.2）可以看做牛頓公式中的導(dǎo)數(shù)用差商取代的結(jié)果.

幾何意義.

曲線上橫坐標(biāo)為的點(diǎn)分別記為，則弦線的斜率等于差商值,其方22第二十二頁(yè)，共三十一頁(yè)，編輯于2023年，星期日程是因之，按（5.2)式求得的實(shí)際上是弦線與軸交點(diǎn)的橫坐標(biāo).這種算法因此而稱為弦截法.表7-523第二十三頁(yè)，共三十一頁(yè)，編輯于2023年，星期日

弦截法與切線法（牛頓法）都是線性化方法，但兩者有本質(zhì)的區(qū)別.

切線法在計(jì)算時(shí)只用到前一步的值，而弦截法（5.2），在求時(shí)要用到前面兩步的結(jié)果，因此使用這種方法必須先給出兩個(gè)開始值.

例10用弦截法解方程

解設(shè)取作為開始值，用弦截法求得的結(jié)果見表7-8，比較例7牛頓法的計(jì)算結(jié)果可以看出，弦截法的收斂速度也是相當(dāng)快的.

實(shí)際上，弦截法具有超線性的收斂性.24第二十四頁(yè)，共三十一頁(yè)，編輯于2023年，星期日

定理6假設(shè)在根的鄰域內(nèi)具有二階連續(xù)導(dǎo)數(shù)，且對(duì)任意有，又初值，那么當(dāng)鄰域Δ充分小時(shí)，弦截法（5.2）將按階收斂到根.這里是方程的正根.25第二十五頁(yè)，共三十一頁(yè)，編輯于2023年，星期日7.5.2拋物線法

設(shè)已知方程的三個(gè)近似根，以這三點(diǎn)為節(jié)點(diǎn)構(gòu)造二次插值多項(xiàng)式，并適當(dāng)選取的一個(gè)零點(diǎn)作為新的近似根，這樣確定的迭代過程稱拋物線法，亦稱密勒（Müller）法.

在幾何上，這種方法的基本思想是用拋物線與軸的交點(diǎn)作為所求根的近似位置（圖7-6).圖7-626第二十六頁(yè)，共三十一頁(yè)，編輯于2023年，星期日插值多項(xiàng)式有兩個(gè)零點(diǎn)：（5.3）式中

問題是該如何確定，假定在三個(gè)近似根中，更接近所求的根，為了保證精度，選（5.3）中較接近的一個(gè)值作為新的近似根.為此，只要取根式前的符號(hào)與的符號(hào)相同.27第二十七頁(yè)，共三十一頁(yè)，編輯于2023年，星期日

例11用拋物線法求解方程

解設(shè)用表7-8的前三個(gè)值作為開始值，計(jì)算得故代入（5.3）式求得28第二十八頁(yè)，共三十一頁(yè)，編輯于2023年，星期日

以上計(jì)算表明，拋物線法比弦截法收斂得更快.

在一定條件下可以證明，對(duì)于拋物線法，迭代誤差有下列漸近關(guān)系式可見拋物線法也是超線性收斂的，其收斂的階,收斂速度比弦截法更接近于牛頓法.

從