牛頓拉夫森(NewtonRaphson)迭代法

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

2、xk)這就是牛頓迭代公式，若得到的序列k/f(x)f(X)kxk收斂于，則就是非線性方程的根。牛頓迭代法也稱為牛頓切線法，這是由于f(x)的線xxk1k公式性化近似函數(shù)1(x)=f(X0)廣(x0)(xX0)是曲線y=f(x)過點(diǎn)(X0,f(X0)的切線而得名的，求f(x)的零點(diǎn)代之以求1(x)的零點(diǎn)，即切線1(x)與x軸交點(diǎn)的橫坐標(biāo)，如右圖所示，這就是牛頓切線法的幾何解釋。實(shí)際上，牛頓迭代法冃牛頓迭代公式，由Xk得到Xk，從幾何圖形上看，就是過點(diǎn)切線lk，切線lk與x軸的交點(diǎn)就是Xk，所以有xk一.，整理后也能得出牛頓迭代公式：xxf(Xk)kkf(x)k。要保證迭代法收斂，不管非線性方程f

3、(X)的形式如何，總可以構(gòu)造:X(X)Xk(X)f(X)(k(X)0)作為方程求解的迭代函數(shù)。因?yàn)椋航?(X)f(X)(X)廣(X)而且(X)在根附近越小，其局部收斂速度越快，故可令：()0()0k()1-f()即根不是f(X)的重根，則由()0得：廣，k(x)-XXf(Xk)因此可令廣(x)，則也可以得出迭代公式：kkf(xk)。迭代法的基本思想是將方程f(x)0改寫成等價(jià)的迭代形式xx)，但隨之而來的問題卻是迭代公式不一定收斂，或者收斂的速度較慢。運(yùn)用前述加速技巧，對(duì)于簡(jiǎn)單迭代過程xnxnf(I)，其加速公式具有形式：n!xnJI”匸”xn島(3些)其中x(x)，其中n1nxxfM2記L1

4、，上面兩式可以合并寫成：nL(x)xf(x)這種迭代公式稱作簡(jiǎn)單的牛頓公式，其相應(yīng)的迭代函數(shù)是：L。需要注意的是，由于L是(x)的估計(jì)值，若取(x)xf(x)，則(x)實(shí)際上便是f(x)的估計(jì)值。假設(shè)廣(x)，則可以用廣(x)代替上式中的L,就可得到牛頓法的迭代Xx公式：n八X?。牛頓迭代法實(shí)質(zhì)上是一種線性化方法，其基本思想是將非線性方程逐步歸結(jié)為某種線性方程來求解。.牛2頓迭代法的收斂性(x)xlL牛頓迭代公式可以看成是由廣(x)而獲得的不動(dòng)點(diǎn)迭代格式。這樣就可以應(yīng)用不動(dòng)點(diǎn)迭代的收斂原則，只須證明在根附近的迭代函數(shù)是一個(gè)壓縮映象。由于：(x)1.f(x)2f(x)f(x)f(x)f(x)f(

5、x)2f(x)2，().f()f()0這里的根是單根，即fC)網(wǎng)且廣()0，于是：ME2。那么由(x)的連續(xù)性可知，存在一個(gè)鄰域()，對(duì)這個(gè)鄰域內(nèi)的一切x，有：(x)q，其中vqvi因此(x)為區(qū)間()上的一個(gè)壓縮映象，于是有以下結(jié)論：定理設(shè)f(x)C2a，b，x*是f(x)0的精確解，且廣(x*)皿，則存在x*的鄰域(x*x*B)，對(duì)于任何迭代初值x0(x*x*-B)，迭代序列叮收斂于x*。牛頓迭代法具有較高的收斂速度，它的收斂階數(shù)為=2而牛頓迭代法的局部收斂性較強(qiáng)，只有初值充分地接近x*，才能確保迭代序列的收斂性。為了放寬對(duì)局部收斂性的限制必須再增加條件建立以下收斂的充分條件。上，定理設(shè)門

6、x)C2a，b，且滿足：在區(qū)間a，bf(a)f(b)0,)f(x)0；八X)不變號(hào)；X0叫b，滿足條件：f(%)八X0)則牛頓迭代序列Xn，單調(diào)地收斂于方程f(X)0的唯一解X*。由條件至條件可歸結(jié)為四種情形：f(b)0f(b)0f(b)0f(b)0f(a)0f(a)0f(a)0f(a)0如對(duì)定理的幾何意義作如下說明：條件保證了根的存在性；條件表明函數(shù)單調(diào)變化，在區(qū)間ab內(nèi)有惟一的根；條件表示函數(shù)圖形在區(qū)間ab上的凹向不變。條件和條件一【例丨解令f(對(duì)于給定的正數(shù)a，用牛頓法建立x，則f(x)07求平方根的收斂迭代0亦、丿hcx用牛頓法求解的迭代公式是：n由于當(dāng)x時(shí)，廣(x)2x02:.土)X

7、nXn，式，故由收斂定理可知，對(duì)于任意滿足條件X0a的初始近似值，由選代公式所產(chǎn)生的序列必定收斂于平方根Z。公式是計(jì)算平方根的準(zhǔn)確而有效的計(jì)算方法。牛.頓3迭代法的變形用牛頓法解方程，雖然在單根附近具有較快的收斂速度，但它有個(gè)明顯的缺點(diǎn)，就是每次都要計(jì)算導(dǎo)數(shù)廣(X)，當(dāng)f(X)比較復(fù)雜時(shí)，計(jì)算廣(X)可能很困難。下面介紹兩種克服這種困難的方法，另外還介紹一種擴(kuò)大牛頓迭代法初值選擇范圍的方法，它們統(tǒng)稱為變形的牛頓迭代法。1簡(jiǎn)化牛頓法為避免頻繁地計(jì)算導(dǎo)數(shù)值廣(x)，可將它取為固定值，比如在牛頓迭代公式中用廣()代替f(xn)，即在迭代過程中始終保持分母不變，則有簡(jiǎn)化牛頓迭代公式(或固定斜率切線xx

8、.丿乞2法：nn廣(x)公式其幾何意義如下圖所示，這時(shí)除第一次迭代仍為曲線的切線外，其余皆為該切線的平行線。簡(jiǎn)化牛頓法避免了每次計(jì)算導(dǎo)數(shù)值。I1更一般地，若取廣FL則迭代公式成為：xx.02nnL，稱為推廣的簡(jiǎn)化切線法。這時(shí)L值應(yīng)MW)有滿足下式：(x)1f.1，可見當(dāng)L與廣(X)同號(hào)且滿足上述不等式時(shí)，推廣的簡(jiǎn)化多數(shù)法里也曾得到過。牛頓法對(duì)初始值的選取要求是很高的。一般地說，牛頓法只艮太遠(yuǎn)時(shí)，迭代將不收斂，而一旦初始值進(jìn)入收斂域內(nèi)，牛頓法就有平方收斂的速度，為了揚(yáng)長(zhǎng)避短，擴(kuò)大初始值選取的范圍，下面介紹牛頓法的一種改進(jìn)牛頓下山法。xxf(Xn)將牛頓法的迭代公式修改為：f(J)公式其中，是一個(gè)

9、參數(shù)，的選取應(yīng)使fXV成立，當(dāng)f(Xn)V或XnXnVx*x，就停止迭代，且取XXn，其中,為事先給定的精度，稱為殘量精確度，為根的誤差限；否則再減，繼續(xù)迭代。按上述迭代過程計(jì)算，實(shí)際上得到了一個(gè)以零為下界的嚴(yán)格單調(diào)下降的函數(shù)值序列，這個(gè)方法就稱為牛頓下山法。稱為下山因子，要求滿足V1，稱為下山因子下界，為了方便，一般開始時(shí)可簡(jiǎn)單地取1，然后逐步分半11減小，即可選耳又，2，22，巳，且使?V丁怎)成立。牛頓下山法計(jì)算步驟可歸納如下：選取初始近似值Xo；取下山因子I；XXf(Xn)計(jì)算Xn-，”n八叮計(jì)算f(Xn)，并比較fWJ與fF的大小，分以下兩種情況：若?V/叮，則當(dāng)V時(shí)，則就耳艾XXn

10、，計(jì)算過程結(jié)束；當(dāng)XnXn，時(shí)，則把I作為新的1值，并重復(fù)回到。若f(Xn)f(Xn)，則當(dāng)且fW.)V，就取，計(jì)算過程結(jié)束；否則，若，而fJ)時(shí)，則把Xn加上一個(gè)適當(dāng)選定的小正數(shù)，即取J作為新的Xn值，并轉(zhuǎn)向重復(fù)計(jì)算；當(dāng).，且f(X時(shí)，則將下山因子縮小一半，并轉(zhuǎn)向重復(fù)計(jì)算。牛頓下山法不但放寬了初值的選取，且有時(shí)對(duì)某一初值，雖然用牛頓法不收斂，但用牛頓下山法卻有可能收斂。一般來說，牛頓下山法不再有平方收斂速度，它的優(yōu)點(diǎn)在于可能將原來收斂域以外的初始值，經(jīng)過幾次迭代后拉入收斂域內(nèi)。例如，已知方程f(X)X3X二的一個(gè)根為X*2若取初值X0二.用牛頓法計(jì)算得到的第一次近似值x117.9反而比x0更

11、偏離根。丄25時(shí)，可得x1.140631，修正后的迭代序列收斂。若改用牛頓下山法，當(dāng)取下山因(沈建華)(史萬明)f(X)f(X)n0XXn0.弦4截法1單點(diǎn)弦截法為避免牛頓迭代法中導(dǎo)數(shù)的計(jì)算，可用平均變化率0來近似代替f(xn)，于是得到如下迭代公式0 xxnnf(x)nf(x)f(x)n0 x、xf(x)xf(x)0f(x)f(x)n0公式0稱為單點(diǎn)弦截法。單點(diǎn)弦截法具有明顯的幾何意義，它是用聯(lián)結(jié)點(diǎn)(0,y0與點(diǎn)(,yn的直線，代替曲線求取與橫軸交點(diǎn)作為近似值xn的方法，以后再過x0，人與xn1，yn兩點(diǎn)，作直線求取與橫軸的交點(diǎn)作為xn2，等等。其中x0，是一個(gè)固定點(diǎn)，稱為不動(dòng)點(diǎn)，另一點(diǎn)則不斷更換，故名單點(diǎn)弦截法?？梢宰C明，單點(diǎn)弦截法具有收斂的階=,即具有線性收斂速度。，y0改為變動(dòng)點(diǎn)xn，yn)則得到下面的雙點(diǎn)弦截lx、xf(x)xf(x)nf(x)f(xj公式nnj上相當(dāng)于過點(diǎn)x，fq.)和點(diǎn)“k，f*)作弦，然后用弦與x軸的交點(diǎn)的橫坐標(biāo)xk1作為x*的新的近似值。由于在雙點(diǎn)弦截法中，構(gòu)造的迭代公式在計(jì)算新的近似值xk!時(shí)，不僅用到點(diǎn)xk上的函數(shù)值f(X，而且還用到點(diǎn)xk及其函數(shù)值，這就有可能提高迭代法的收