第七章非線性方程數(shù)值求解NumericalValueAnalysis§7.3Newton迭代法華長生制作1

§7.3Newton迭代法將f(x)在點xn作Taylor展開:

——Taylor展開線性化f(x)=0

近似于

f(xn)+f′(xn)(x-xn)=0(1)從(1)解出x,記為xn+1,則1.Newton迭代公式建立2它對應(yīng)的迭代方程為顯然是f(x)=0的同解方程，故其迭代函數(shù)為

在f(x)=0的根x*的某個鄰域內(nèi),在x*的鄰域R內(nèi)，對任意初值，應(yīng)用公式（2）來解方程的方法就稱為牛頓迭代法。它是解代數(shù)方程和超越方程的有效方法之一.42.Newton迭代法的幾何意義

與x軸(y=0)的交點x，作為下一個迭代點xn+1,即

用f(x)在xn處的切線Newton迭代法又稱切線法.43、牛頓迭代法的步驟步一、準備。選定初始近似值，計算步二、迭代。按公式迭代一次，得到新的近似值，計算步三、控制。如果滿足或.則終止迭代，以作為所求的根；否則轉(zhuǎn)步四。此處是允許誤差,15而 其中c是取絕對值或相對誤差的控制常數(shù)，一般可取c=1。步四、修改。如果迭代次數(shù)達到預(yù)定指定的次數(shù)N，或者 ,則方法失敗；否則以代替轉(zhuǎn)步二繼續(xù)迭代。16例用Newton迭代法求下面方程的一個正根,計算結(jié)果精確到7位小數(shù).解:由Newton迭代法x1

=1.4666667,…,x4

=1.3688081x5

=1.3688081迭代5次精度達10-7x*

≈

1.36880874.Newton迭代法收斂定理（1）Newton迭代公式在單根情況下至少2階收斂;定理7.3.1

設(shè)f(x*)=0,,且在x*的鄰域上存在,連續(xù),則可得84.Newton迭代法收斂定理證：將f(x)在xn處作2階Taylor展開,并將解x*代入9所以，Newton法至少二階收斂.

注意到ξn在xn及x*之間,10

Newton法在重根情形下的收斂階20

有局部線性收斂性,重數(shù)m越高,

越接近于1,收斂越慢。20

Newton迭代法的特征

Newton迭代公式是一種特殊的不動點迭代,其迭代函數(shù)為:

Newton迭代是局部線性化方法,它在單根附近具有較高的收斂速度.

方法有效前提:135.Newton迭代法的應(yīng)用----------開方公式對于給定正數(shù)應(yīng)用牛頓迭代法解二次方程可導(dǎo)出求開方值的計算公式設(shè)是的某個近似值，則自然也是一個近似值，上式表明，它們兩者的算術(shù)平均值將是更好的近似值。

定理

開方公式對于任意給定的初值均為平方收斂。

14牛頓迭代法的優(yōu)缺點在單根附近,牛頓迭代法具有平方收斂的速度，所以在迭代過程中只要迭代幾次就會得到很精確的解。優(yōu)點缺點重根情形下為局部線性收斂;2.牛頓迭代法計算量比較大:因每次迭代除計算函數(shù)值外還要計算微商值;3.選定的初值要接近方程的解，否則有可能得不到收斂的結(jié)果;21牛頓迭代法的改進缺點克服:

局部線性收斂

------改進公式或加速2.每步都要計算微商值

-----簡化Newton迭代法或弦截法3.初值近似問題-------二分法求初值或”下山算法”21方法一、若已知重數(shù)m(m>1),則利用m構(gòu)造新的迭代公式:此時,至少2階收斂.6.Newton法的改進(I)---重根情形不實用:m往往不確定.17方法二、取,再對函數(shù)F(x)用Newton迭代:此時,X*為F(x)的單根,所以是2階收斂.缺點：要用到二階導(dǎo)數(shù).18Newton迭代法需要求每個迭代點處的導(dǎo)數(shù)復(fù)雜！這種格式稱為簡化Newton迭代法精度稍低6.Newton法的改進(II)19則Newton迭代法變?yōu)檫@種格式稱為弦截法收斂階約為1.61820例用簡化Newton法和弦截法解下面方程的根，并和Newton迭代法比較

解:由簡化Newton法由弦截法由Newton迭代法21x0=0.5x1=0.3333333333x2=0.3497942387x3=0.3468683325x4=0.3473702799x5=0.3472836048x6=0.3472985550x7=0.3472959759x8=0.3472964208x9=0.3472963440x10=0.3472963572x11=0.3472963553x0=0.5;x1=0.4;x2=0.3430962343x3=0.3473897274x4=0.3472965093x5=0.3472963553x6=0.3472963553簡化Newton法由弦截法要達到精度10-8簡化Newton法迭代11次弦截法迭代5次Newton迭代法迭代4次x0=0.5;x1=0.3333333333x2=0.3472222222x3=0.3472963532x4=0.3472963553由Newton迭代法22無論哪種迭代法：Newton迭代法簡化Newton法弦截法用Newton迭代法求解:x0=2x1=-3.54x2=13.95x3=-279.34x4=122017是否收斂均與初值的位置有關(guān).例:x0=1x1=-0.5708x2=0.1169x3=-0.0011x4=7.963110-10x5=0收斂發(fā)散迭代法的局部收斂性236.Newton法的改進(III):牛頓下山法

一般地說，牛頓法的收斂性依賴于初值的選取，如果偏離較遠，則牛頓法可能發(fā)散。為了防止發(fā)散，通常對迭代過程再附加一項要求，即保證函數(shù)值單調(diào)下降：

滿足這項要求的算法稱為下山法。牛頓下山法采用以下迭代公式：其中稱為下山因子。牛頓下山法只有線性收斂.24第七章非線性方程數(shù)值求解NumericalValueAnalysis§7.4Aitken加速方案/Steffensen迭代法華長生制作25改進、加速收斂

/*acceleratingconvergence*/有些迭代過程雖收斂，但速度很慢。為了達到所要求的精度，需要迭代的次數(shù)很多，由此必須設(shè)法加速迭代過程。1.基本思想上式說明，將預(yù)測值x0和校正值x1作線性組合作為x*的一個新近似值，可能比x1更好。令：

ξ介于x0與x*之間，設(shè)變化不大，，則有微分中值定理x0----x*的預(yù)測值26一般地，有線性組合校正殘差27

簡單迭代公式的加速設(shè)是根的某個近似值，用迭代公式校正一次得假設(shè)，則有據(jù)此可導(dǎo)出如下加速公式：其一步分為兩個環(huán)節(jié)：

迭代:改進:2829在方法1中含有L（或q），實際應(yīng)用中不便。下面設(shè)法消除L（或q），得到一種新的加速方法---Aitken（埃特金）方法。

x0——prediction推廣，有下面一般計算公式：

x1=g(x0)——updatingx2=g(x1)——further

updating30埃特金迭代法求方程的實根31定理7.4.1設(shè)序列線性收斂于x*,則的Aitken序列存在,且即比更快收斂于x*.3233Steffensen迭代