1 牛頓迭代法

牛頓迭代法實(shí)質(zhì)上是一種線性化方法，其基本思想是將非線性方程逐步歸結(jié)為某種線性方程來求解。

1.1 牛頓法

牛頓迭代法又稱切線法，是一種有特色的求根方法。用牛頓迭代法求的單根的主要步驟：

（1）Newton法的迭代公式

（2）以附近的某一個(gè)值為迭代初值，代入迭代公式，反復(fù)迭代，得到序列

（3）若序列收斂，則必收斂于精確根，即。

牛頓法有顯然的幾何意義，方程的根可解釋為曲線與軸交點(diǎn)的橫坐標(biāo)。設(shè)是根的某個(gè)近似值，過曲線上橫坐標(biāo)為的點(diǎn)引切線，并將該切線與軸交點(diǎn)的橫坐標(biāo)作為的新的近似值。

牛頓法初值的選擇：若在上連續(xù)，存在2階導(dǎo)數(shù)，且滿足下列條件：

（1）；

（2）在內(nèi)不變號(hào)，且；

（3）在內(nèi)不變號(hào)，且；

（4），且?；

則對任意的初值，牛頓迭代序列收斂于在內(nèi)的唯一根。

牛頓的優(yōu)缺點(diǎn)：牛頓法是目前求解非線性方程（組）的主要方法，至少二階局部收斂，收斂速度較快，特別是當(dāng)?shù)踔党浞挚拷_解時(shí)。對重根收斂速度較慢（線性收斂），對初值的選取很敏感，要求初值相當(dāng)接近真解，需要求導(dǎo)數(shù)。

1.2 哈利牛頓法

哈利法（Halley）可用于加速牛頓法收斂，哈利迭代公式：

哈利法在單根情況下可達(dá)到三階收斂。

1.3 簡化牛頓法

將牛頓法的迭代公式改為

為保證收斂，系數(shù)只需滿足即可。如果取常數(shù)，則稱為簡化牛頓法，也稱平行弦法。

簡化牛頓法線性收斂。

1.4 牛頓下山法

牛頓法的收斂性依賴初值的選取，如果偏離所求根較遠(yuǎn)，則牛頓法可能發(fā)散。牛頓下山法，引入下山因子，保證函數(shù)值穩(wěn)定下降的同時(shí)，加速收斂速度。

牛頓下山法公式：

下山因子的取法：從開始，逐次減半，即，直到滿足下降條件。

1.5 重根情形

當(dāng)為的重根時(shí)，則可表為，其中，此時(shí)用牛頓迭代法求仍然收斂，只是收斂速度將大大減慢，牛頓法求方程的重根時(shí)僅為線性收斂。

將求重根問題化為求單根問題進(jìn)行牛頓法求解。對，令函數(shù)

則化為求的單根的問題，對它用牛頓法是二階收斂的。其迭代函數(shù)為

從而構(gòu)造出迭代方法

2 牛頓迭代法MATLAB算法實(shí)現(xiàn)

算法說明：

（1）輸入?yún)?shù)的判定和必要的處理，包括可變參數(shù)的處理，若某個(gè)可變參數(shù)不輸入，則采用默認(rèn)值。

（2）由于牛頓法需要計(jì)算方程的一階導(dǎo)數(shù)和二階導(dǎo)數(shù)（重根情形），故方程的定義采用符號(hào)定義（避免手工計(jì)算方程的導(dǎo)數(shù)所帶來的計(jì)算量），在算法solve_diff_fun(equ)中實(shí)現(xiàn)符號(hào)函數(shù)的一階導(dǎo)數(shù)和二階導(dǎo)數(shù)的計(jì)算，并轉(zhuǎn)換為匿名函數(shù)進(jìn)行數(shù)值運(yùn)算。

（3）根據(jù)參數(shù)method選擇執(zhí)行不同的牛頓迭代方法，具體：

? ? 1）“newton”為牛頓法newton()；

? ? 2）“simplify”為簡化的牛頓法simplify_newton()；

? ? 3）“halley”為哈利法（牛頓加速法）newton_halley()；

? ? 4）“downhill”為牛頓下山法newton_downhill()，下山法包括了下山因子的存儲(chǔ)；

? ? 5）“multi”為重根情形newton_multi_root()。

（4）根據(jù)參數(shù)display選擇是否顯示迭代過程信息或僅顯示結(jié)果信息。

（5）可變輸出參數(shù)的判定和必要處理。

思考：MATLAB中沒有類似于Python的list結(jié)構(gòu)，如何在未知迭代次數(shù)的情況下，預(yù)分配內(nèi)存，存儲(chǔ)迭代過程變量信息？

3?牛頓迭代法案例測試

例1：求非線性方程在區(qū)間的近似根

可視化函數(shù)圖像：

從圖中可以看出，在區(qū)間內(nèi)存在四個(gè)根，此處僅求在附近的根，其他根求解自行設(shè)計(jì)。

驗(yàn)證輸入?yún)?shù)：

驗(yàn)證輸出參數(shù)，僅有一個(gè)輸出參數(shù)，則為結(jié)構(gòu)體，且輸出迭代過程：

驗(yàn)證輸出參數(shù)，有三個(gè)輸出參數(shù)，分別為近似解、方程在近似解處的誤差精度和退出標(biāo)記，1表示收斂到滿足精度要求的近似解，且輸出最終迭代結(jié)果：

例2：求帶有重根的非線性方程在附近的近似解

由于簡化的牛頓法收斂速度較慢，此處不再可視化簡化的牛頓法。

可視化各牛頓法的誤差精度下降曲線如圖3，可見在存在重根情形下，采用牛頓重根公式，收斂速度極快，其次為牛頓哈利法。由于此處未用到下山因子，故牛頓法和牛頓下山法求解過程一致。

各方法迭代過程

例3：求非線性方程在附近的近似解：

其中下山法由于在第二次迭代時(shí)引入了下山因子0.25，故其下降曲線相對于牛頓法而言，保持了下降收斂的性質(zhì)。