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

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

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

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

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

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

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

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

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

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