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

1、數(shù)值分析迭代加速、牛頓法及弦截法3.3 迭代收斂的加速方法迭代收斂的加速方法3.3.1 埃特金加速收斂方法 對于收斂的迭代過程，只要迭代足夠多次，就可以使結(jié)果達到任意的精度，但是有時迭代過程收斂較慢，從而使計算量變得很大. 設(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，一般情

2、形是由xk計算 xk+1, xk+2，記它表明序列xk的收斂速度比xk的收斂速度快.(3.1)式稱為埃特金(Aitken) 2加速方法. 可以證明也稱為埃特金 ( Aitken ) 外推法. 可以證明:為線性收斂,則埃特金法為平方收斂； 注：埃特金(Aitken)加速迭代法也可寫成下面格式若)(1kkxx 為 p ( p 1)階收斂，導(dǎo)數(shù)連續(xù)，則埃特金法為 2p1 階收斂.的 p 階若3.3.2 3.3.2 斯蒂芬森斯蒂芬森(Steffensen)(Steffensen)迭代法迭代法 埃特金方法不管原序列xk是怎樣產(chǎn)生的，對xk進行加速計算，得到序列 xk . 如果把埃特金加速技巧與不定點迭代

3、結(jié)合，則可得到如下的迭代法：稱為斯蒂芬森(Steffensen)迭代法. 實際上(3.3)是將不定點迭代法(2.2)計算兩步合并成一步得到的，可將它寫成另一種不動點迭代其中 對不動點迭代(3.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

4、)=0有近似根x0，且在 x0附近f(x)可用一階泰勒多項式近似，表示為當 f(x0)0 時，方程 f(x)=0 可用線性方程(切線) 近似代替，即 f(x0)+f(x0)(x-x0)=0. (4.1)解此線性方程得得迭代公式此式稱為牛頓(Newton)迭代公式.牛頓法的幾何意義：設(shè)xk是根x*的某個近似值，過曲線y=f(x)上橫坐標為xk的點Pk引切線，并將該切線與x軸交點的橫坐標xk+1作為x*的新的近似值. 注意到切線方程為這樣求得的值xk+1必滿足(4.1), 從而就是牛頓公式(4.2)的計算結(jié)果. xyx*xky=f(x)xk+1PkPk+1xk+2牛頓迭代法的收斂性設(shè)x*是 f(x

5、) 的一個單根，即 f(x*)=0，f(x*)0, 有牛頓迭代法的迭代函數(shù)為由定理4可得由此得到，當x*為單根時，牛頓迭代法在根x*的鄰近是二階(平方)收斂的.設(shè)fC2a, b, 若x*為 f(x)在a, b上的根，且 f(x*)0，則存在 x* 的鄰域 U, 使得任取初值 x0U，牛頓法產(chǎn)生的序列 xk 收斂到 x*，且滿足 解 將原方程化為 xex= 0，則牛頓迭代公式為取 x0=0.5，迭代得x1=0.566311, x2=0.5671431, x3=0.5671433. f(x)=xex， f(x)=1+ex， 例1 用牛頓迭代法求方程x=ex在x=0.5附近的根.例2 對于給定的正數(shù)

6、 C，應(yīng)用牛頓法解二次方程我們現(xiàn)在證明，這種迭代公式對于任意初值x00都是收斂的.推導(dǎo)出求開方值 的計算公式.C事實上，對(4.5)式進行配方整理，易知以上兩式相除得據(jù)此反復(fù)遞推有記整理(4.6)式，得對任意初值x00，總有|q|0)重根時，則 f(x) 可表為 f(x)=(x-x*)mg(x).其中 g(x*)0，此時用牛頓迭代法(4.2)求 x* 仍然收斂，只是 收斂速度將大大減慢. 事實上，因為迭代公式令ek=xkx*，則可見用牛頓法求方程的重根時僅為線性收斂.從而有兩種的方法：1) 取如下迭代函數(shù)得到迭代公式下面介紹一個求重數(shù)m的方法，令則求m重根具有2階收斂. 但要知道x*的重數(shù)m.

7、由式得因此得估計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.03

8、692.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)，當函數(shù) f(x) 比較復(fù)雜時，計算 f(x)往往比較困難，為此可以利用已求函數(shù)值 f(xk),f(xk-1),來回避導(dǎo)數(shù)值 f(xk)的計算. 這類方法是建立在插值原理基礎(chǔ)上的，下面介紹弦截法與拋物線法.3.5.1 3.5.1 弦截弦截( (割線割線) )法法設(shè) xk, xk-1是 f(x)

9、=0的近似根，我們利用 f(xk), f(xk-1)構(gòu)造一次插值多項式 p1(x)，并用 p1(x)=0 的根作為方程f(x)=0 的新的近似根 xk+1，由于因此有這樣導(dǎo)出的迭代公式(5.2)可以看做牛頓公式11)()( kkkkxxxfxf中的導(dǎo)數(shù) 用差商 取代的結(jié)果.)(kxf (5.2)式有明顯的幾何意義： 設(shè)曲線y=f(x)上橫坐標為xk-1和xk的點分別為Pk-1和Pk, 則差商 表示弦 的斜率, 弦 的方程為11)()( kkkkxxxfxfkkPP1 kkPP1 Ox*xk+1xkPkxk-1yxPk-1因此，按(5.2)式求得xk+1實際上是兩點弦線 與x軸交點的橫坐標(令y

10、=0解出x即可).這種算法因此而形象地稱為弦截(割線)法.kkPP1 注：弦截法與切線法(牛頓法)都是線性化分法，但兩者有本質(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，那么當鄰域充分小時，弦截法(5.2)將按階收斂到x*. 這里p是方程2-1=0的正根.定理證明可見P116.因為(5.2)式用到前兩點xk-1和xk的值，故此方法又稱為雙點割線法.每步只用一個新點

11、xk的值，此方法稱為單點割線法.如果把(5.2)式中的xk-1改為x0，即迭代公式為例4 用牛頓迭代法和割線法求方程 f(x)=x4+2x2x3=0， 在區(qū)間(1, 1.5)內(nèi)之根(誤差為10-9). 解 取x0=1.5，用牛頓法, 可得x6；取x0=1.5, x1=1，用雙點割線法，迭代6次得到同樣的結(jié)果，而采用單點割線法，則迭代18次得x18=1.124123029.* *3.5.2 3.5.2 拋物線法拋物線法設(shè)已知方程 f(x)=0的三個近似根 xk, xk-1, xk-2，我們以這三點為節(jié)點構(gòu)造二次插值多項式 p2(x)，并適當選取 p2(x) 的一個零點 xk+1 作為新的近似根，

12、這樣確定的迭代過程稱為拋物線法，亦稱為密勒(Mller)法. 在幾何圖形上, 這種方法的基本思想是用拋物線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，我們需要討論根式前正負號的取舍問題.在xk, xk-1, xk-2三個近似值中，自然假定xk更接近所求的根x*，這時，為了保證精度，我們選(5.3)式中接近xk的一個值作為新的近似根xk+1. 為此，只要取根式前的符號與的符號相同. 例5