數(shù)值分析3.2.迭代加速、牛頓法及弦截法

第3章非線性方程的數(shù)值解法3.1方程求根與二分法3.2迭代法及其收斂性3.3迭代收斂的加速方法3.4牛頓法3.5弦截法與拋物線法3.3迭代收斂的加速方法3.3.1埃特金加速收斂方法

對于收斂的迭代過程，只要迭代足夠多次，就可以使結(jié)果達(dá)到任意的精度，但是有時迭代過程收斂較慢，從而使計算量變得很大.設(shè)x0是根x*的某個近似值,用迭代公式校正一次得

x1=(x0)而由微分中值定理，有假設(shè)(x)改變不大,近似地取某個近似值L,則有由于

x2-x*≈L(x1-x*).若將校正值x1=(x0)再校正一次，又得

x2=(x1)將它與(3.1)式聯(lián)立，消去未知的L，有由此推知在計算了x1及x2之后，可用上式右端作為x*的新近似,記作?x1，一般情形是由xk計算xk+1,xk+2，記它表明序列{?xk}的收斂速度比{xk}的收斂速度快.(3.1)式稱為埃特金(Aitken)△2加速方法.

可以證明也稱為埃特金(Aitken)外推法.可以證明:為線性收斂,則埃特金法為平方收斂；

注：埃特金(Aitken)加速迭代法也可寫成下面格式若為p(p>1)階收斂，導(dǎo)數(shù)連續(xù)，則埃特金法為2p–1

階收斂.的

p

階若3.3.2斯蒂芬森(Steffensen)迭代法

埃特金方法不管原序列{xk}是怎樣產(chǎn)生的，對{xk}進(jìn)行加速計算，得到序列{?xk}.如果把埃特金加速技巧與不定點迭代結(jié)合，則可得到如下的迭代法：稱為斯蒂芬森(Steffensen)迭代法.

實際上(3.3)是將不定點迭代法(2.2)計算兩步合并成一步得到的，可將它寫成另一種不動點迭代其中

對不動點迭代(3.5)有以下局部收斂性定理.

定理5

若x*為(3.5)定義的迭代函數(shù)Ψ(x)的不動點，則x*為(x)的不定點.反之，若x*為(x)的不動點，設(shè)(x)在x*連續(xù)

，(x*)≠1，則x*是Ψ(x)的不動點，且斯蒂芬森迭代法(3.3)是2階收斂的.3.4牛頓法3.4.1牛頓法及其收斂性牛頓法實質(zhì)上是一種線性化方法，其基本思想是將非線性方程f(x)=0逐步歸結(jié)為某種線性方程來求解.

設(shè)已知方程f(x)=0有近似根x0，且在x0附近f(x)可用一階泰勒多項式近似，表示為當(dāng)f(x0)≠0時，方程f(x)=0可用線性方程(切線)近似代替，即f(x0)+f(x0)(x-x0)=0.

(4.1)解此線性方程得得迭代公式此式稱為牛頓(Newton)迭代公式.牛頓法的幾何意義：設(shè)xk是根x*的某個近似值，過曲線y=f(x)上橫坐標(biāo)為xk的點Pk引切線，并將該切線與x軸交點的橫坐標(biāo)xk+1作為x*的新的近似值.注意到切線方程為這樣求得的值xk+1必滿足(4.1),從而就是牛頓公式(4.2)的計算結(jié)果.xyx*xky=f(x)xk+1PkPk+1xk+2牛頓迭代法的收斂性設(shè)x*是f(x)的一個單根，即f(x*)=0，f(x*)≠0,有牛頓迭代法的迭代函數(shù)為由定理4可得由此得到，當(dāng)x*為單根時，牛頓迭代法在根x*的鄰近是二階(平方)收斂的.

定理(局部收斂性)

設(shè)fC2[a,b],若x*為f(x)在[a,b]上的根，且f(x*)0，則存在x*的鄰域U,使得任取初值x0U，牛頓法產(chǎn)生的序列{xk}收斂到x*，且滿足

解將原方程化為x–e–x=0，則牛頓迭代公式為取x0=0.5，迭代得x1=0.566311,x2=0.5671431,x3=0.5671433.

f(x)=x–e–x，f(x)=1+e–x，

例1用牛頓迭代法求方程x=e–x在x=0.5附近的根.

例2

對于給定的正數(shù)C，應(yīng)用牛頓法解二次方程我們現(xiàn)在證明，這種迭代公式對于任意初值x0>0都是收斂的.推導(dǎo)出求開方值的計算公式.事實上，對(4.5)式進(jìn)行配方整理，易知以上兩式相除得據(jù)此反復(fù)遞推有記整理(4.6)式，得對任意初值x0>0，總有|q|<1，故由上式推知，當(dāng)k→∞時，即迭代過程恒收斂.3.4.2重根情形當(dāng)x*為f(x)的m(m>0)重根時，則f(x)可表為f(x)=(x-x*)mg(x).其中g(shù)(x*)≠0，此時用牛頓迭代法(4.2)求x*仍然收斂，只是收斂速度將大大減慢.事實上，因為迭代公式令ek=xk–x*，則可見用牛頓法求方程的重根時僅為線性收斂.從而有兩種提高求重根的收斂速度的方法：

1)

取如下迭代函數(shù)得到迭代公式下面介紹一個求重數(shù)m的方法，令則求m重根具有2階收斂.但要知道x*的重數(shù)m.由式得因此得估計m的式子為對f(x)=(x-x*)mg(x),g(x*)≠0，令函數(shù)則為求μ(x)=0的單根x*的問題，對它用牛頓法是二階(平方)收斂的.其迭代函數(shù)為

2)

將求重根問題化為求單根問題.從而構(gòu)造出迭代方法為

例3用牛頓迭代法求函數(shù)

f(x)=(x-1)[sin(x-1)+3x]-x3+1=0

在0.95附近之根.

解取x0=0.95

用牛頓迭代法求得的xk見右表.可見xk收斂很慢.kxkkm01234560.950.97442790.98705830.99348780.99673280.99835760.99919010.50900.50470.50070.51252.03692.01902.00282.0511由重根數(shù)m=2,用(4.13)式加速法，作求得

x0=0.95,x1=0.9988559,x2=x3=1.收斂速度大大加快于直接用牛頓迭代公式.3.5弦截法與拋物線法用牛頓法求方程f(x)=0的根，每步除計算f(xk)外還要算f(xk)，當(dāng)函數(shù)f(x)比較復(fù)雜時，計算f(x)往往比較困難，為此可以利用已求函數(shù)值f(xk),f(xk-1),來回避導(dǎo)數(shù)值f(xk)的計算.這類方法是建立在插值原理基礎(chǔ)上的，下面介紹弦截法與拋物線法.3.5.1弦截(割線)法設(shè)xk,xk-1是f(x)=0的近似根，我們利用f(xk),f(xk-1)構(gòu)造一次插值多項式p1(x)，并用p1(x)=0的根作為方程f(x)=0的新的近似根xk+1，由于因此有這樣導(dǎo)出的迭代公式(5.2)可以看做牛頓公式中的導(dǎo)數(shù)用差商取代的結(jié)果.

(5.2)式有明顯的幾何意義：

設(shè)曲線y=f(x)上橫坐標(biāo)為xk-1和xk的點分別為Pk-1和Pk,則差商表示弦的斜率,弦的方程為Ox*xk+1xkPkxk-1yxPk-1因此，按(5.2)式求得xk+1實際上是兩點弦線與x軸交點的橫坐標(biāo)(令y=0解出x即可).這種算法因此而形象地稱為弦截(割線)法.注：弦截法與切線法(牛頓法)都是線性化分法，但兩者有本質(zhì)的區(qū)別.切線法在計算xk+1時只用到前一步的值xk，而弦截法要用到前面兩步的結(jié)果xk-1,xk，因此使用這種方法必須先給出兩個開始值x0,x1.

定理6

假設(shè)f(x)在根x*的鄰域內(nèi)△:|x-x*|≤δ具有二階連續(xù)導(dǎo)數(shù)，且對任意x△有f(x)≠0，所取的初值x0,x1△，那么當(dāng)鄰域△充分小時，弦截法(5.2)將按階收斂到x*.這里p是方程λ2-λ-1=0的正根.定理證明可見P116.因為(5.2)式用到前兩點xk-1和xk的值，故此方法又稱為雙點割線法.每步只用一個新點xk的值，此方法稱為單點割線法.如果把(5.2)式中的xk-1改為x0，即迭代公式為例4用牛頓迭代法和割線法求方程

f(x)=x4+2x2–x–3=0，在區(qū)間(1,1.5)內(nèi)之根(誤差為10-9).

解取x0=1.5，用牛頓法,可得x6=1.12412303030；取x0=1.5,x1=1，用雙點割線法，迭代6次得到同樣的結(jié)果，而采用單點割線法，則迭代18次得x18=1.124123029.*3.5.2拋物線法設(shè)已知方程f(x)=0的三個近似根xk,xk-1,xk-2，我們以這三點為節(jié)點構(gòu)造二次插值多項式p2(x)，并適當(dāng)選取p2(x)的一個零點xk+1作為新的近似根，這樣確定的迭代過程稱為拋物線法，亦稱為密勒(Müller)法.在幾何圖形上,這種方法的基本思想是用拋物線y=p2(x)與x軸的交點xk+1作為所求根x*的近似位置.Ox*xk+1xky=P2(x)xk-2yxy=f(x)xk-1拋物線法的幾何意義見下面圖形.現(xiàn)在推導(dǎo)拋物線法的計算公式.插值多項式有兩個零點式中因子在(5.3)式定出一個值xk+1，我們需要討論根式前正負(fù)號的取舍問題.在xk,xk-1,xk-2三個近似值中，自然假定x