牛頓-拉夫森迭代法 2

§3.4牛頓迭代法牛頓迭代法也稱(chēng)為牛頓-拉夫森(Newton-Raphson)迭代法，它是數(shù)值分析中最重要的方法之一，它不僅適用于方程或方程組的求解，還常用于微分方程和積分方程求解。3.4.1牛頓迭代法用迭代法解非線性方程時(shí)，如何構(gòu)造迭代函數(shù)是非常重要的，那么怎樣構(gòu)造的迭代函數(shù)才能保證迭代法收斂呢？牛頓迭代法就是常用的方法之一，其迭代格式的來(lái)源大概有以下幾種方式：1設(shè)f(x)GC2［a,b］，對(duì)f(x)在點(diǎn)X0日",b］作泰勒展開(kāi)：f(x)=f(x)+f(x)(x-x)+f(提Txo)2ooo2!略去二次項(xiàng)，得到f⑴的線性近似式：f(x)牝f(xo)+f(xo)(x-xo)。x=x八、00），_f（x）

氣+】—?dú)鈅廣（x）

kf(x)由此得到方程f3)=x=x八、00），_f（x）

氣+】—?dú)鈅廣（x）

k由此得到方程f3)=0的近似根(假定『3)。即可構(gòu)造出迭代格式(假定廣(氣)*0)：這就是牛頓迭代公式，若得到的序列｛xo即可構(gòu)造出迭代格式(假定廣(氣)*0)：這就是牛頓迭代公式，若得到的序列｛x2牛頓迭代法也稱(chēng)為牛頓切線法，這是由于f(x)的線性化近似函數(shù)l(x)=f(xo)+廣(xo)(x-xo)是曲線＞=f(x)過(guò)點(diǎn)(xo,f(xo))的切線而得名的，求f(x)的零點(diǎn)代之以求l(x)的零點(diǎn)，即切線l(x)與x軸交點(diǎn)的橫坐標(biāo)，如右圖所示，這就是牛頓切線法的幾何解釋。實(shí)際上，牛頓迭代法也可以從幾何意義上推出。利用牛頓迭代公式，由xk得到xk+1，從幾何圖形上看，就是過(guò)點(diǎn)(氣,f(氣))作函數(shù)f⑴的切線lk，切線lk與x軸的交點(diǎn)就是xk+1，所以有f(x)=)kTxk+i，整理后也能得出牛頓迭代公式：_f(x)氣+廣x_fd)

k。3要保證迭代法收斂，不管非線性方程f(x)=0的形式如何，總可以構(gòu)造：x=9(x)=x一k(x)f(x)(k(x)*o)作為方程求解的迭代函數(shù)。因?yàn)椋?'(x)=1-k(x)f(x)一k(x)f(x)而且9(x)在根a附近越小，其局部收斂速度越快，故可令：9'(a)=°

若廣(口)"0(即根a不是/(x)=0的重根)，則由0(a)=0得：()廣(以),k(x)=1x=x-旦因此可令f，(X)，則也可以得出迭代公式：k+1kf(Xk)O4迭代法的基本思想是將方程f(x)=0改寫(xiě)成等價(jià)的迭代形式x=^(x)，但隨之而來(lái)的問(wèn)題卻是迭代公式不一定收斂，或者收斂的速度較慢。運(yùn)用前述加速技巧，對(duì)于簡(jiǎn)單迭代過(guò)程七+1=J+f("，其加速公式具有形式:"n+1—七)天—中(x)，其中n+1nf(x)nL記L=°T,上面兩式可以合并寫(xiě)成：i"1*X"n+1—七)天—中(x)，其中n+1nf(x)nL記L=°T,上面兩式可以合并寫(xiě)成：i"1*需要注意的是，由于L是甲'(x)的估計(jì)值，若取中(x)=x+f(x)，則0(x)實(shí)際上便是f'(x)的估計(jì)值。假設(shè)廣(x)"0，則可以用廣(x)代替上式中的L，就可得到牛頓法的迭代xf(x「x—x—n公式：En廣(叩o牛頓迭代法實(shí)質(zhì)上是一種線性化方法，其基本思想是將非線性方程逐步歸結(jié)為某種線性方程來(lái)求解。3.4.2牛頓迭代法的收斂性中(x)-x—^牛頓迭代公式可以看成是由廣(x)而獲得的不動(dòng)點(diǎn)迭代格式。這樣就可以應(yīng)用不動(dòng)點(diǎn)迭代的收斂原則，只須證明在根a附近的迭代函數(shù)是一個(gè)壓縮映象。由于：=1—[f(x)]2-f(x)f"(x)=f(x)f"(x)^_[f3]2[f'(x)]20(a)=f(a)f"(a)=0這里的根^單根，即f(a)=0且f(a)。0，于是：[f(a)]2O那么由0'(x)的連續(xù)性可知，存在一個(gè)鄰域(a—&,a+&)，對(duì)這個(gè)鄰域內(nèi)的一切x，有：0'(x)<q，其中ovq<1，因此0(x)為區(qū)間(a-&，a+&)上的一個(gè)壓縮映象，于是有以下結(jié)論：定理3.4.1設(shè)f⑴GC2[a,b]，**是f⑴=0的精確解，且廣3^"0，則存在**的&鄰域(**一&'X*+5)，對(duì)于任何迭代初值*0日**一如**+5)，迭代序列｛收斂于x*O牛頓迭代法具有較高的收斂速度，它的收斂階數(shù)為P=2；而牛頓迭代法的局部收斂性較強(qiáng)，只有初值充分地接近'*，才能確保迭代序列的收斂性。為了放寬對(duì)局部收斂性的限制，必須再增加條件建立以下收斂的充分條件。定理3.4.2設(shè)f(x)GC2［a,b］，且滿(mǎn)足：在區(qū)間［a，b］上，⑴f(a)f(b)<0；⑵廣⑴。0；⑶f"(x)不變號(hào)；⑷幻或⑶滿(mǎn)足條件：f(<「(<>0①f(a)<0，f(b)>0，f(x)>0，f"(x)>0.；②f(a)<0，f(b)>0，廣⑴>0，f"(x)<0.；③f(a)>0，f(b)<0，f(x)<0，f"(x)>0.；④f(a)>0，f(b)<0，f(x)<0，f"(x)<0。則牛頓迭代序列'七｝，單調(diào)地收斂于方程f(x)=0的唯一解x*。由條件⑴至條件⑷可歸結(jié)為四種情形：對(duì)定理的幾何意義作如下說(shuō)明：條件⑴保證了根的存在性；條件⑵表明函數(shù)單調(diào)變化，在區(qū)間［a,b］內(nèi)有惟一的根；條件⑶表示函數(shù)圖形在區(qū)間［缶b］上的凹向不變。條件⑶和條件⑷一起保證了每一次迭代值都界于區(qū)間［ab］i,y內(nèi)。性)>0/V)<0理)A0b=x。f'Xx)<0在不滿(mǎn)足上述收斂充分條件時(shí)，有可能導(dǎo)致迭代值遠(yuǎn)離所求根的情況或死循環(huán)的情況(如卜圖所示)。【例3.4.1】對(duì)于給定的正數(shù)a，用牛頓法建立求平方根的收斂迭代公式。解令f3)=42—a，(x>0)，則/⑴=°的正根就是［??'"。x2一a1.a.七+廣七—丐廠=2(Xn+r)用牛頓法求解的迭代公式是：七七，公式(3.4.2)由于當(dāng)x>0時(shí)，廣(x)=2x>0,f"(x)=2>0,故由收斂定理可知，對(duì)于任意滿(mǎn)足條件%>履的初始近似值，由選代公式所產(chǎn)生的序列必定收斂于平方根*a。公式(3.4.2)是計(jì)算平方根的準(zhǔn)確而有效的計(jì)算方法。3.4.3牛頓迭代法的變形用牛頓法解方程，雖然在單根附近具有較快的收斂速度，但它有個(gè)明顯的缺點(diǎn)，就是每次都要計(jì)算導(dǎo)數(shù)廣(x)，當(dāng)f(x)比較復(fù)雜時(shí)，計(jì)算廣(x)可能很困難。下面介紹兩種克服這種困難的方法，另外還介紹一種擴(kuò)大牛頓迭代法初值選擇范圍的方法，它們統(tǒng)稱(chēng)為變形的牛頓迭代法。1簡(jiǎn)化牛頓法為避免頻繁地計(jì)算導(dǎo)數(shù)值廣(x)，可將它取為固定值，比如在牛頓迭代公式中用f'(X°)代替廣"J，即在迭代過(guò)程中始終保持分母不變，則有簡(jiǎn)化牛頓迭代公式(或固定斜率切線法)：Xn+法)：Xn+1f(X)nf(x)°公式(3.4.3)滿(mǎn)足上式的L滿(mǎn)足上式的L為:其幾何意義如下圖所示，這時(shí)除第一次迭代仍為曲線的切線外，其余皆為該切線的平行線。簡(jiǎn)化牛頓法避免了每次計(jì)算導(dǎo)數(shù)值。更一般地，若取f(Xn)=L,則迭代公式成為：x=X一f(Xn)〃+1nL，稱(chēng)為推廣的簡(jiǎn)化切線法。這時(shí)L值應(yīng)滿(mǎn)足下式：b'(X)|=1—平<1L可見(jiàn)當(dāng)L與廣(x)同號(hào)且滿(mǎn)足上述不等式時(shí)，推廣的簡(jiǎn)化切線法是收斂的。該迭代形式在參數(shù)法里也曾得到過(guò)。2由牛頓法的收斂性定理知，牛頓法對(duì)初始值的選取要求是很高的。一般地說(shuō)，牛頓法只有局部收斂性。當(dāng)初始值取得離根太遠(yuǎn)時(shí)，迭代將不收斂，而一旦初始值進(jìn)入收斂域內(nèi)，牛頓法就有平方收斂的速度，為了揚(yáng)長(zhǎng)避短，擴(kuò)大初始值選取的范圍，下面介紹牛頓法的一種改進(jìn)——牛頓下山法。x=x_xf(七)將牛頓法的迭代公式修改為："1"E)公式(3.4.3)f(x)f(x)f(x)xx其中，入是一個(gè)參數(shù)，入的選取應(yīng)使f(nJ<”(n)成立，當(dāng)"(n+/<"1或1n+1/<￡x*牝x￡￡￡￡2，就停止迭代，且取n+1，其中1，2為事先給定的精度，1稱(chēng)為殘量精確度，2為根的誤差限；否則再減入，繼續(xù)迭代。按上述迭代過(guò)程計(jì)算，實(shí)際上得到了一個(gè)以零為下界的嚴(yán)格單調(diào)下降的函數(shù)值序列，這個(gè)方法就稱(chēng)為牛頓下山法。入稱(chēng)為下山因子，要求滿(mǎn)足0<￡x-1-1，匕稱(chēng)為下山因子下界，為了方便，一般開(kāi)始時(shí)可簡(jiǎn)單地取*=1，然后逐步分半11減小，即可選取"T，2，22，…，"%，且使f("<fC成立。牛頓下山法計(jì)算步驟可歸納如下：⑴選取初始近似值^0；⑵取下山因子入=Lx=x_^3⑶計(jì)算%+1，En廣")⑷計(jì)算f(xn+1)，并比較/(七+1)與If3n)k勺大小，分以下兩種情況：若^^n+1)'<''3『，則當(dāng)七+1Xn<%時(shí)，則就取，~*n+1，計(jì)算過(guò)程結(jié)束；當(dāng)lx—xUYY1n+1n1>￡2時(shí)，則把xn+1作為新的^值，并重復(fù)回到⑶。若f(七+1)Jf心，則當(dāng)攔％且If(七+1)<￡1，就取渺牝孔，計(jì)算過(guò)程結(jié)束；否則，若X-￡X，而f(xn+1)N￡1時(shí)，則把、1加上一個(gè)適當(dāng)選定的小正數(shù)，即取七+1葺作為新的七值，并轉(zhuǎn)向⑶重復(fù)計(jì)算；當(dāng)"'％，且f(xn+1)N￡1時(shí)，則將下山因子縮小一半，并轉(zhuǎn)向⑶重復(fù)計(jì)算。牛頓下山法不但放寬了初值的選取，且有時(shí)對(duì)某一初值，雖然用牛頓法不收斂，但用牛頓下山法卻有可能收斂。一般來(lái)說(shuō)，牛頓下山法不再有平方收斂速度，它的優(yōu)點(diǎn)在于可能將原來(lái)收斂域以外的初始值，經(jīng)過(guò)幾次迭代后拉入收斂域內(nèi)。例如，已知方程f(x)=x3_x_1=0的一個(gè)根為x*a1.32472,若取初值xo=0.6，用牛頓法計(jì)算得到的第一次近似值x1=17.9反而比x0更偏離根。若改用牛頓下山法，當(dāng)取下山因子"=2時(shí)，可得'廣質(zhì)63，修正后的迭代序列收斂。(沈建的…史萬(wàn)明P48)3.4.4弦截法1單點(diǎn)弦截法為避免牛頓迭代法中導(dǎo)數(shù)的計(jì)算，可用平均變化率:

來(lái)近似代替廣（七），于是得到如下迭代公式：X=X-"）（一）二X0f3”）—f3。）"1”2）-f（x°）”0f（叩—f（X0）公式（3.4.4）i稱(chēng)為單點(diǎn)弦截法。單點(diǎn)弦截法具有明顯的幾何意義，它林宥是用聯(lián)結(jié)點(diǎn)A（X。，*）與點(diǎn)B（七，七）的直線，代替/\曲線求取與橫軸交點(diǎn)作為近似值七+1的方法，以后再過(guò)//:（Xo，*）與（七+1，七+1）兩點(diǎn)，作直線求取與橫軸的丁:,一交點(diǎn)作為X”+2，等等。其中（X0，*）是一個(gè)固定點(diǎn)，°/：/X一拓―r稱(chēng)為不動(dòng)點(diǎn)，另一點(diǎn)則不斷更換，故名單點(diǎn)弦截法?？?；/以證明，單點(diǎn)弦截法具有收斂的階r=1，即具有線性收斂速度。2雙點(diǎn)弦截法若把單點(diǎn)弦截法中的不動(dòng)點(diǎn)（氣），*）改為變動(dòng)點(diǎn)（七一1，七一1），則得到下面的雙點(diǎn)弦截法的迭代公式：X=X-f（叩（X-X）=七-1f（Xn）一"（七一1）n+1”f（X）-f（X）n”-1f（X）-f（X）公式（345）nn-1nn-1有J-\i\D.%O/m-t-i--t-b.、，-u［、.lqjl/_.、l/＞、ra-r/.rt/—rri.t-t、r,—、—ui—/Xf（XJ\/rti—/Xf（XJ\ir.用弦截法求根的近似值，在兒何上相當(dāng)于過(guò)點(diǎn)（k-1，k-1），和點(diǎn)（k，k）作弦，然后用弦與X軸的交點(diǎn)的橫坐標(biāo)Xk+1作為X*的新的近似值。由于在雙點(diǎn)弦截法中，構(gòu)造的迭代公式在計(jì)算新的近似值Xk+1時(shí)，不僅用到點(diǎn)Xk上的函數(shù)值f（氣），而且還用到點(diǎn)Xk-1及其函數(shù)值，這就有可能提高迭代法的收斂