計算方法引論-薇第十章

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

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

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

f(a)f(b)<0則在[a,b]內有根解法迭代:取其中點為近似根,記為x0,其誤差限(b-a)/2.若誤差符合要求或其函數值接近零x0便可接受.否則取a,b中函數值與x0的函數值異號者跟x0構成新的求根區(qū)間,記為[a1,b1].重復以上做法得新近似根x1,…這樣不斷將區(qū)間分半,得到一系列區(qū)間[an,bn],和近似根(區(qū)間中點)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]的零點.f(1)<0,.f(1.5)>0x6=1.3242,誤差限0.00390625(真值ξ=1.3247…,誤差e*=-0.0005…).有三位有效數字.實際上x5就有三位有效數字了.計算方法引論(第三版)迭代法求非線性連續(xù)函數f(x)零點ξ化成x=

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

=φ(ξ),

φ(x)的不動點.故亦稱不動點迭代法計算方法引論(第三版)迭代法算例例2求f(x)=x3+2x2+10x+20在[1,1.5]的零點.取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),計算結果如表,收斂于根計算方法引論(第三版)迭代法幾何解釋幾何解釋x=φ(x)的不動點ξ是y=x和y=

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

[1,2]→[1,2].計算方法引論(第三版)收斂性改進可以改進迭代法收斂性乃至變發(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導出‘以線性函數代非線性函數’在初始近似xn作Taylor展開線性部分零點xn+1‘以直代曲’由(xn,f(xn))作f(x)的切線交x軸于xn+1.因此Newton法也叫切線法

y=f(x)

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

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

注Newton迭代法也可視為不動點迭代法

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

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

計算:

例如，設,求

其中又因計算方法引論(第三版)弦位法方法(也叫割線法)取初始近似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導出‘以線性函數代非線性函數’取線性插值函數零點xn+1‘以直代曲’作弦交x軸于xn+1.

(x1,y1)

x0x2x1

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

.x0=1,x1=1.5,計算結果見Newton法算例.注:弦位法較Newton法收斂慢,但每步不必計算導數,總計算量也有可能低于Newton法.因此,弦位法頗具競爭力.變形:試位法.保證收斂.取二初始值,其上函數值變號.算出新值后,取代與之函數值同號的舊值再算新值.與對分區(qū)間套法一樣每次迭代所用二值都分居于根的兩側.是線性收斂的計算方法引論(第三版)拋物線法方法(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導出過三點作拋物線,與x軸一交點為xn+1例6.同例2,拋物線法

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

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

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

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

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

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