計算方法引論-薇第十章

計算方法引論：數(shù)值代數(shù)解線性方程組的直接法解線性方程組最小二乘問題解線性方程組的迭代法矩陣特征值和特征向量的計算非線性方程及非線性方程組解法計算方法引論(第三版)第十章非線性方程解法局部收斂的階對分區(qū)間套法迭代法Newton法弦位法拋物線法非線性方程組Newton法和擬Newton法最速下降法計算方法引論(第三版)非線性方程求解求非線性函數(shù)方程f(x)=0根(求非線性函數(shù)f(x)零點(diǎn))ξ解法迭代法:給出一個近似解序列收斂判據(jù)可用誤差,相對誤差或函數(shù)值接近零否局部收斂

在準(zhǔn)確解附近給出一個收斂的近似解序列{xn}p階收斂:若xn→ξ并且存在p≥1,c>0,使

線性收斂p=1(c<1)超線性收斂p>1計算方法引論(第三版)對分區(qū)間套法根據(jù)函數(shù)f(x)在[a,b]連續(xù),

f(a)f(b)<0則在[a,b]內(nèi)有根解法迭代:取其中點(diǎn)為近似根,記為x0,其誤差限(b-a)/2.若誤差符合要求或其函數(shù)值接近零x0便可接受.否則取a,b中函數(shù)值與x0的函數(shù)值異號者跟x0構(gòu)成新的求根區(qū)間,記為[a1,b1].重復(fù)以上做法得新近似根x1,…這樣不斷將區(qū)間分半,得到一系列區(qū)間[an,bn],和近似根(區(qū)間中點(diǎn))xn,n=0,1,2,3…xn誤差為(b-a)/2n+1,區(qū)間[an,bn]長的一半,xn→ξ.有根區(qū)間以1/2的比率縮小,我們也稱它是線性收斂的.計算方法引論(第三版)對分區(qū)間套法算例例1. 求f(x)=x3-x-1在[1,1.5]的零點(diǎn).f(1)<0,.f(1.5)>0x6=1.3242,誤差限0.00390625(真值ξ=1.3247…,誤差e*=-0.0005…).有三位有效數(shù)字.實(shí)際上x5就有三位有效數(shù)字了.計算方法引論(第三版)迭代法求非線性連續(xù)函數(shù)f(x)零點(diǎn)ξ化成x=

φ(x),ξ=φ(ξ)迭代取初始近似x0計算 xn+1=φ(xn), n=0,1,2,…直到∣xn+1-xn∣≤ε(∣(xn+1-xn)/xn+1∣≤ε)若xn→ξ,則ξ

=φ(ξ),

φ(x)的不動點(diǎn).故亦稱不動點(diǎn)迭代法計算方法引論(第三版)迭代法算例例2求f(x)=x3+2x2+10x+20在[1,1.5]的零點(diǎn).取x0=1,迭代公式為xn+1=2-(xn3+2xn2)/10,則算得1.7,0.9307,1.74614,0.857796,…發(fā)散.取x0=1,迭代公式為xn+1=20//(xn2+2xn+10),計算結(jié)果如表,收斂于根計算方法引論(第三版)迭代法幾何解釋幾何解釋x=φ(x)的不動點(diǎn)ξ是y=x和y=

φ(x)兩條曲線的交點(diǎn).迭代從x0出發(fā)向上到達(dá)y=φ(x)上點(diǎn)(x0,φ(x0)),由此點(diǎn)再沿水平線到達(dá)y=x上點(diǎn)(φ(x0),φ(x0)),其橫坐標(biāo)即x1.如此做下去得一條階梯形或環(huán)形折線,或向交點(diǎn)接近(收斂),或遠(yuǎn)離交點(diǎn)而去(不收斂).0<φ'<1-1<φ'<00<φ'<1-1<φ'<0φ'>1φ'>1φ'<-1φ'<-1計算方法引論(第三版)迭代法收斂性不動點(diǎn)原理加于φ(x)的條件稱Lipshitz條件(L稱Lipshitz常數(shù))它強(qiáng)于連續(xù)性.實(shí)踐中常用∣φ′(x)∣≤L<1,從畫圖看出的規(guī)律.這兒φ(x)定義在(-∞,∞).換成φ：[a,b]→[a,b],定理亦成立.這兒得到誤差估計照例偏于保守.可在計算時用估計式: ∣xn+1-ξ∣≤L/(1-L)∣xn+1-xn∣習(xí)題2,3的結(jié)果也是很有用的:計算方法引論(第三版)不動點(diǎn)原理證明不動點(diǎn)原理證明計算方法引論(第三版)收斂性判定討論例2中迭代的收斂性φ(x)=2-(x3+2x2)/10,

φ

′(1.5)=-1.275,φ′(1.3)=-1.027在[1.3,1.5]有

∣φ′(x)∣>1,不收斂.φ(x)=20/(x2+2x+10)在[1,2

]有0<∣φ′(x)∣<1,局部收斂.實(shí)際上φ:

[1,2]→[1,2].計算方法引論(第三版)收斂性改進(jìn)可以改進(jìn)迭代法收斂性乃至變發(fā)散為收斂松弛法λn=φ′(xn

)(≠-1)ωn=(1+λn)-1xn+1=(1-ω)xn+ωn

φ(xn),Aitken法un+1=φ(xn)vn+1=φ(un+1)xn+1=xn-(un+1-xn)2/(vn+1-2un+1+xn) =vn+1-(vn+1-un+1)2/(vn+1-2un+1+xn)計算方法引論(第三版)松弛法算例例3.同例2,取x0=1,φ(x)==20//(x2+2x+10).計算方法引論(第三版)Aitken方法算例例3(續(xù)).同例2,取x0=1,φ(x)=

2-(x3+2x2)/10.取x0=1,φ(x)==20//(x2+2x+10).計算方法引論(第三版)Newton法方法取初始近似x0迭代 n=0,1,2,…

xn+1=xn-f(xn)/f′(xn)直到∣xn+1-xn∣≤ε和(或)∣(xn+1-xn)/xn+1∣≤ε1, ∣f(xn+1)∣≤ε2導(dǎo)出‘以線性函數(shù)代非線性函數(shù)’在初始近似xn作Taylor展開線性部分零點(diǎn)xn+1‘以直代曲’由(xn,f(xn))作f(x)的切線交x軸于xn+1.因此Newton法也叫切線法

y=f(x)

x0x1(x0,f(x0))計算方法引論(第三版)Newton法算例例4.例2,取x0=1,.用Newton法.結(jié)果見下表左欄.

計算方法引論(第三版)Newton法收斂性定理

注Newton迭代法也可視為不動點(diǎn)迭代法

φ(x)=x-f(x)/f′(x)單根的假設(shè)是必要的.例如,求(x-1)2=0的二重根1.Newton迭代是線性收斂的: xn+1-1=(xn-1)/2計算方法引論(第三版)Newton法變形幾個方法簡化Newton法.為減少計算導(dǎo)數(shù)的化費(fèi),可只求f′(x0)以后所有導(dǎo)數(shù)不另求.這相當(dāng)于第一次作切線,以后作其平行線.當(dāng)然,這樣收斂要慢些.還可以取折衷方案,隔幾步計算一下導(dǎo)數(shù)Newton-下山法.每次迭代在改變量前加一因子以保證收斂: xn+1=xn-λnf(xn)/f′(xn) 這兒λn在0,1間,可用各種方法搜索,例如用分半法取1,1/2,1/4,…試探,使 ∣f(xn+1)∣<∣f(xn)∣用差商代導(dǎo)數(shù)xn+1=xn-f(xn)(xn-xn-1)/(f(xn)-f(xn-1)) 它免除了計算導(dǎo)數(shù)

計算方法引論(第三版)綜合除法多項(xiàng)式的情況計算可應(yīng)用綜合除法故再對進(jìn)行上述過程即得f′(c)

計算:

例如，設(shè),求

其中又因計算方法引論(第三版)弦位法方法(也叫割線法)取初始近似x0,x1迭代 n=1,2,…

xn+1=xn-f(xn)(xn-xn-1)/ (f(xn)-f(xn-1))直到∣xn+1-xn∣≤ε和(或) ∣(xn+1-xn)/xn+1∣≤ε1, ∣f(xn+1)∣≤ε2導(dǎo)出‘以線性函數(shù)代非線性函數(shù)’取線性插值函數(shù)零點(diǎn)xn+1‘以直代曲’作弦交x軸于xn+1.

(x1,y1)

x0x2x1

(x0,,y0)計算方法引論(第三版)弦位法收斂性定理例5.同例2,弦位法

.x0=1,x1=1.5,計算結(jié)果見Newton法算例.注:弦位法較Newton法收斂慢,但每步不必計算導(dǎo)數(shù),總計算量也有可能低于Newton法.因此,弦位法頗具競爭力.變形:試位法.保證收斂.取二初始值,其上函數(shù)值變號.算出新值后,取代與之函數(shù)值同號的舊值再算新值.與對分區(qū)間套法一樣每次迭代所用二值都分居于根的兩側(cè).是線性收斂的計算方法引論(第三版)拋物線法方法(Muller法)取初始近似x0,x1,x2迭代 n=2,3,…

求λ2,δ2,a,b,c求λ3,

及xn+1,yn+1

直到∣xn+1-xn∣≤ε和(或)

∣(xn+1-xn)/xn+1∣≤ε1,

∣f(xn+1)∣≤ε2導(dǎo)出過三點(diǎn)作拋物線,與x軸一交點(diǎn)為xn+1例6.同例2,拋物線法

.x0=1,x1=1.5,x2=1.25計算結(jié)果見Newton法算例.收斂性計算方法引論(第三版)非線性方程組Newton法二元情況方程方法取初值x0,y0迭代

n=0,1,2,…解方程組求Δx,Δy計算 xn+1=xn+Δx,yn+1=yn+Δy

直至改變量合乎要求導(dǎo)出:Taylor公式線性化計算方法引論(第三版)算例例7計算方法引論(第三版)非線性方程組Newton法(續(xù))一般情況方程方法計算方法引論(第三版)擬Newton法差商代替導(dǎo)數(shù)Newton法:k=0由Newton法求x1:

A0=f′(x(0))k=1取可逆A1并令A(yù)1滿足擬Newton方程其中A1有很多選擇,每一種選擇都規(guī)定了一種擬Newton法.Broyden秩1修改法希望對A0作適當(dāng)修改就得到A1:由,,可推得,計算方法引論(第三版)Broyden秩1修改法算法

注計算方法引論(第三版)Broyden法算例例8同例7用Broyden方法計算結(jié)果列于下表.收斂慢于Newton法

計算方法引論(第三版)Broyd