牛頓-拉夫森(Newton-Raphson)迭代法

1、3.4 牛頓迭代法牛頓迭代法也稱為牛頓-拉夫森(Newton-Raphson)迭代法，它是數(shù)值分析中最重要的方法之一，它不僅適用于方程或方程組的求解，還常用于微分方程和積分方程求解。3.4.1 牛頓迭代法用迭代法解非線性方程時(shí)，如何構(gòu)造迭代函數(shù)是非常重要的，那么怎樣構(gòu)造的迭代函數(shù)才能保證迭代法收斂呢？牛頓迭代法就是常用的方法之一，其迭代格式的來源大概有以下幾種方式：1設(shè)，對(duì)在點(diǎn)作泰勒展開：略去二次項(xiàng)，得到的線性近似式：。由此得到方程0的近似根(假定0)，即可構(gòu)造出迭代格式(假定0)： 公式(3.4.1)這就是牛頓迭代公式，若得到的序列收斂于，則就是非線性方程的根。2 牛頓迭代法也稱為牛頓切線法

2、，這是由于的線性化近似函數(shù)是曲線過點(diǎn)的切線而得名的，求的零點(diǎn)代之以求的零點(diǎn)，即切線與軸交點(diǎn)的橫坐標(biāo)，如右圖所示，這就是牛頓切線法的幾何解釋。實(shí)際上，牛頓迭代法也可以從幾何意義上推出。利用牛頓迭代公式，由得到，從幾何圖形上看，就是過點(diǎn)作函數(shù)的切線，切線與軸的交點(diǎn)就是，所以有，整理后也能得出牛頓迭代公式：。3 要保證迭代法收斂，不管非線性方程0的形式如何，總可以構(gòu)造： 作為方程求解的迭代函數(shù)。因?yàn)椋憾以诟浇叫?，其局部收斂速度越快，故可令：?(即根不是0的重根)，則由得：，因此可令，則也可以得出迭代公式：。4 迭代法的基本思想是將方程改寫成等價(jià)的迭代形式，但隨之而來的問題卻是迭代公式不一定收

3、斂，或者收斂的速度較慢。運(yùn)用前述加速技巧，對(duì)于簡(jiǎn)單迭代過程，其加速公式具有形式：，其中記，上面兩式可以合并寫成：這種迭代公式稱作簡(jiǎn)單的牛頓公式，其相應(yīng)的迭代函數(shù)是：。需要注意的是，由于是的估計(jì)值，若取，則實(shí)際上便是的估計(jì)值。假設(shè)，則可以用代替上式中的，就可得到牛頓法的迭代公式：。牛頓迭代法實(shí)質(zhì)上是一種線性化方法，其基本思想是將非線性方程逐步歸結(jié)為某種線性方程來求解。3.4.2 牛頓迭代法的收斂性牛頓迭代公式可以看成是由而獲得的不動(dòng)點(diǎn)迭代格式。這樣就可以應(yīng)用不動(dòng)點(diǎn)迭代的收斂原則，只須證明在根附近的迭代函數(shù)是一個(gè)壓縮映象。由于：，這里的根是單根，即且，于是：。那么由的連續(xù)性可知，存在一個(gè)鄰域，對(duì)這

4、個(gè)鄰域內(nèi)的一切，有：，其中O1，因此為區(qū)間上的一個(gè)壓縮映象，于是有以下結(jié)論： 定理 3.4.1 設(shè)，是的精確解，且，則存在的鄰域，對(duì)于任何迭代初值，迭代序列收斂于。牛頓迭代法具有較高的收斂速度，它的收斂階數(shù)為2；而牛頓迭代法的局部收斂性較強(qiáng)，只有初值充分地接近，才能確保迭代序列的收斂性。為了放寬對(duì)局部收斂性的限制，必須再增加條件建立以下收斂的充分條件。定理 3.4.2 設(shè)，且滿足：在區(qū)間上， ； ； 不變號(hào)； ，滿足條件：則牛頓迭代序列，單調(diào)地收斂于方程的唯一解。由條件至條件可歸結(jié)為四種情形： ，； ，； ，； ，。對(duì)定理的幾何意義作如下說明：條件保證了根的存在性；條件表明函數(shù)單調(diào)變化，在區(qū)間

5、內(nèi)有惟一的根；條件表示函數(shù)圖形在區(qū)間上的凹向不變。條件和條件一起保證了每一次迭代值都界于區(qū)間內(nèi)。在不滿足上述收斂充分條件時(shí)，有可能導(dǎo)致迭代值遠(yuǎn)離所求根的情況或死循環(huán)的情況(如下圖所示)?！纠?.4.1】對(duì)于給定的正數(shù)，用牛頓法建立求平方根的收斂迭代公式。 解 令，(0)，則的正根就是。用牛頓法求解的迭代公式是：， 公式(3.4.2)由于當(dāng)0時(shí)，0，0，故由收斂定理可知，對(duì)于任意滿足條件的初始近似值，由選代公式所產(chǎn)生的序列必定收斂于平方根。公式(3.4.2)是計(jì)算平方根的準(zhǔn)確而有效的計(jì)算方法。3.4.3 牛頓迭代法的變形用牛頓法解方程，雖然在單根附近具有較快的收斂速度，但它有個(gè)明顯的缺點(diǎn)，就是每

6、次都要計(jì)算導(dǎo)數(shù)，當(dāng)比較復(fù)雜時(shí)，計(jì)算可能很困難。下面介紹兩種克服這種困難的方法，另外還介紹一種擴(kuò)大牛頓迭代法初值選擇范圍的方法，它們統(tǒng)稱為變形的牛頓迭代法。1 簡(jiǎn)化牛頓法為避免頻繁地計(jì)算導(dǎo)數(shù)值，可將它取為固定值，比如在牛頓迭代公式中用代替，即在迭代過程中始終保持分母不變，則有簡(jiǎn)化牛頓迭代公式(或固定斜率切線法)： 公式(3.4.3)其幾何意義如下圖所示，這時(shí)除第一次迭代仍為曲線的切線外，其余皆為該切線的平行線。簡(jiǎn)化牛頓法避免了每次計(jì)算導(dǎo)數(shù)值。更一般地，若取,則迭代公式成為：，稱為推廣的簡(jiǎn)化切線法。這時(shí)值應(yīng)滿足下式：滿足上式的為：，可見當(dāng)與同號(hào)且滿足上述不等式時(shí)，推廣的簡(jiǎn)化切線法是收斂的。該迭代形

7、式在參數(shù)法里也曾得到過。2 由牛頓法的收斂性定理知，牛頓法對(duì)初始值的選取要求是很高的。一般地說，牛頓法只有局部收斂性。當(dāng)初始值取得離根太遠(yuǎn)時(shí)，迭代將不收斂，而一旦初始值進(jìn)入收斂域內(nèi)，牛頓法就有平方收斂的速度，為了揚(yáng)長(zhǎng)避短，擴(kuò)大初始值選取的范圍，下面介紹牛頓法的一種改進(jìn)牛頓下山法。將牛頓法的迭代公式修改為： 公式(3.4.3)其中，是一個(gè)參數(shù)，的選取應(yīng)使成立，當(dāng)或，就停止迭代，且取，其中，為事先給定的精度，稱為殘量精確度，為根的誤差限；否則再減，繼續(xù)迭代。按上述迭代過程計(jì)算，實(shí)際上得到了一個(gè)以零為下界的嚴(yán)格單調(diào)下降的函數(shù)值序列，這個(gè)方法就稱為牛頓下山法。稱為下山因子，要求滿足0，稱為下山因子下界

8、，為了方便，一般開始時(shí)可簡(jiǎn)單地取，然后逐步分半減小，即可選取，且使成立。牛頓下山法計(jì)算步驟可歸納如下： 選取初始近似值； 取下山因子； 計(jì)算， 計(jì)算，并比較與的大小，分以下兩種情況： 若，則當(dāng)時(shí)，則就取，計(jì)算過程結(jié)束；當(dāng)時(shí)，則把作為新的值，并重復(fù)回到。若，則當(dāng)且，就取，計(jì)算過程結(jié)束；否則，若，而時(shí)，則把加上一個(gè)適當(dāng)選定的小正數(shù)，即取作為新的值，并轉(zhuǎn)向重復(fù)計(jì)算；當(dāng)，且時(shí)，則將下山因子縮小一半，并轉(zhuǎn)向重復(fù)計(jì)算。牛頓下山法不但放寬了初值的選取，且有時(shí)對(duì)某一初值，雖然用牛頓法不收斂，但用牛頓下山法卻有可能收斂。一般來說，牛頓下山法不再有平方收斂速度，它的優(yōu)點(diǎn)在于可能將原來收斂域以外的初始值，經(jīng)過幾次迭

9、代后拉入收斂域內(nèi)。例如，已知方程0的一個(gè)根為1.32472，若取初值0.6，用牛頓法計(jì)算得到的第一次近似值反而比更偏離根。若改用牛頓下山法，當(dāng)取下山因子時(shí)，可得，修正后的迭代序列收斂。（沈建華P138）（史萬明P48）3.4.4 弦截法1 單點(diǎn)弦截法為避免牛頓迭代法中導(dǎo)數(shù)的計(jì)算，可用平均變化率：來近似代替，于是得到如下迭代公式： 公式(3.4.4)稱為單點(diǎn)弦截法。單點(diǎn)弦截法具有明顯的幾何意義，它是用聯(lián)結(jié)點(diǎn)A(，)與點(diǎn)B(，)的直線，代替曲線求取與橫軸交點(diǎn)作為近似值的方法，以后再過(，)與(，)兩點(diǎn)，作直線求取與橫軸的交點(diǎn)作為，等等。其中(，)是一個(gè)固定點(diǎn)，稱為不動(dòng)點(diǎn)，另一點(diǎn)則不斷更換，故名單點(diǎn)弦截法?？梢宰C明，單點(diǎn)弦截法具有收斂的階r1，即具有線性收斂速度。2 雙點(diǎn)弦截法若把單點(diǎn)弦截法中的不動(dòng)點(diǎn)(，)改為變動(dòng)點(diǎn)(，)，則得到下面的雙點(diǎn)弦截法的迭代公式： 公式(3.4.5)用弦截法求根的近似值，在幾何上相當(dāng)于過點(diǎn)(，)，和點(diǎn)(，)作弦，然后用弦與軸的交點(diǎn)的橫坐標(biāo)作為的新的近似值。由于在雙點(diǎn)弦截法中，構(gòu)造的迭代公式在計(jì)算新的近似值時(shí)，不僅用到點(diǎn)上的函數(shù)值，而且還用到點(diǎn)及其函數(shù)值，這就有可能提高迭代法的收斂速度。與牛頓法一樣，如果函數(shù)在其根附近具有直到二階的連續(xù)導(dǎo)數(shù)，且，則弦截法具有局部收斂性，即當(dāng)初始近