數(shù)值分析9(迭代法收斂性證明)

迭代法收斂性條件迭代誤差估計(jì)定理

《數(shù)值分析》9*總結(jié):矩陣范數(shù)算子范數(shù)

算子范數(shù)

矩陣1范數(shù),

矩陣無(wú)窮范數(shù),矩陣2范數(shù)例4

設(shè)||.||為Rn×n

上任意一種矩陣范數(shù),則對(duì)任意的A∈Rn×n,有證明:例5

設(shè)||.||為Rn×n

上任意一種矩陣范數(shù),則對(duì)AX=b(M–N)X=bMX=NX+b記

(k)=X(k)–X*(k=0,1,2,···)則有

(k+1)=B(k)(k=0,1,2,···)迭代格式:X(k+1)=BX(k)+f(B=M-1N,f=M-1b)

X(k+1)–X*=B(X(k)–X*)設(shè)方程組的精確解為X*,則有X*=BX*+f*

||(k+1)

||=||B(k)||

≤||B||.||(k)||

(k=0,1,2,···)*迭代法構(gòu)造收斂條件中止準(zhǔn)則引理1

*參考:P.83引理2

*引理3

證:必要性,設(shè)迭代法產(chǎn)生的序列{X(k)}收斂,記X*是該序列的極限點(diǎn),則X*=B

X*+f。

定理4.1對(duì)任意的f和任意的初始向量X(0)迭代法

X(k+1)=BX(k)+f

收斂的充分必要條件是由X(0)的任意性知

*充分性

*

譜半徑小于1是迭代收斂的充要條件,但它不易計(jì)算,所以在實(shí)際使用中通常并不好用。推論4.1若||B||<1,則對(duì)任意的f和任意的初始向量X(0)迭代法

X(k+1)=BX(k)+f

收斂。*定理4.2

設(shè)X*為方程組

AX=b的解若||B||<1,則對(duì)迭代格式

X(k+1)=BX(k)+f

有(1)(2)證||X(k+1)–X*||=||B(X(k)–X*)||≤||B||||X(k)–X*||X(k+1)–X*=B(X(k)–X*

)*||X(k)–X*||=||(X(k)–X(k+1))+(X(k+1)

–X*

)||≤||X(k)–X(k+1)||+||X(k+1)

–X*||

≤||X(k)–X(k+1)||+||B||||X(k)–X*||**迭代法構(gòu)造收斂條件(局部vs全局)中止準(zhǔn)則統(tǒng)一的不動(dòng)點(diǎn)框架定義4.1

A=(aij)n×n,如果則稱(chēng)A為嚴(yán)格對(duì)角占優(yōu)陣。*性質(zhì)2

A是嚴(yán)格對(duì)角占優(yōu)矩陣,則D-L和D-U是嚴(yán)格對(duì)角占優(yōu)矩陣。性質(zhì)1

A是嚴(yán)格對(duì)角占優(yōu)矩陣,則。記A=D-L-U性質(zhì)3

A是嚴(yán)格對(duì)角占優(yōu)矩陣,則當(dāng)時(shí)則有和是嚴(yán)格對(duì)角占優(yōu)矩陣。

嚴(yán)格對(duì)角占優(yōu)矩陣定理4.3

若Ax=b的系數(shù)矩陣A是嚴(yán)格對(duì)角占優(yōu)矩陣,則Jacobi迭代和Gauss-Seidel迭代收斂。證:由于矩陣A

嚴(yán)格對(duì)角占優(yōu)*所以故Jacobi迭代矩陣BJ=D-1(D–A)第i行絕對(duì)值求和故Jacobi迭代

X(k+1)=BJX(k)+f

收斂。*推論A是嚴(yán)格對(duì)角占優(yōu)矩陣,則A非奇異。Gauss-Seidel迭代矩陣為BGS=(D-L)-1U。由于A對(duì)角占優(yōu)所以矩陣

也是對(duì)角占優(yōu)的,則矩陣一定非奇異,矛盾。注釋:考慮反證法新證:定理4.4方程組

Ax=b

中,若A是實(shí)對(duì)稱(chēng)正定矩陣,則Gauss-Seidel迭法收斂。證明:由

A=D–L–LT

BGS=(D–L)-1LTA正定,故

p=xTDx>0,記

xTLTx=a,則有xTAx=xT(D–L–LT)x=p–a–a=p–2a>0設(shè)

為BGS的任一特征值,x為其特征向量,則*所以迭代矩陣BGS的譜半徑

(BGS)<1,從而當(dāng)A是實(shí)對(duì)稱(chēng)正定矩陣時(shí),

Gauss-Seidel迭代法收斂。*定理

方程組

Ax=b

中,若A是實(shí)對(duì)稱(chēng)正定矩陣,則Jacobi迭法收斂？(反例)定理4.5

設(shè)BJ元素均非負(fù),則下列關(guān)系有且只有一個(gè)成立:參考文獻(xiàn):P.Stein,R.L.Rosenberg,Onthesolutionoflinearsimultaneousequationsbyiteration,J.LondonMath.Soc.**迭代法構(gòu)造收斂條件(局部vs全局)中止準(zhǔn)則統(tǒng)一的不動(dòng)點(diǎn)框架直接法vs迭代法

基于高斯消元法的直接方法提供了有限步內(nèi)就可以得到解的方法。*

尋求迭代方法的理由是什么呢？十階百階萬(wàn)階百萬(wàn)階億階小不大較大大超大迭代法優(yōu)勢(shì)1:

直接法運(yùn)行一個(gè)完整LU分解才能得到解,迭代法從初始解開(kāi)始每步對(duì)其加工改善使其更加精確。問(wèn)題是在用戶容忍的范圍內(nèi)需要多少步才能得到收斂性？*注釋:運(yùn)行一個(gè)完整LU分解花費(fèi)O(n3)階運(yùn)算,一般地,迭代法每次迭代花費(fèi)O(n2)階運(yùn)算,即每次迭代僅需要完整LU分解花費(fèi)的一部分。迭代法優(yōu)勢(shì)2:

求解稀疏方程組是使用迭代法的主要理由。*注釋:系數(shù)矩陣稀疏度為n,則求解稀疏方程組迭代法每步迭代花費(fèi)O(n)階運(yùn)算。求解特殊結(jié)構(gòu)方程組(如Toeplitz)迭代法每步迭代花費(fèi)O(nlogn)階運(yùn)算。Poisson方程:令

h=1/(n+1),xi=ih(i

=0,1,···,n+1)記

ui=u(xi),(i

=0,1,···,n+1)迭代計(jì)算格式:差分格式:n=10000;e=ones(n,1);A=spdiags([e-2*ee],-1:1,n,n),spy(A)HB矩陣稀疏模式來(lái)源

TheoriginalHarwell-Boeingcollection來(lái)源:TheUniversityofFloridaSparseMatrixCollectionFreeFieldTechnologies矩陣稀疏模式來(lái)源3Dvibro-acousticproblem,

aircraftenginenacellevanHeukelum矩陣稀疏模式來(lái)源DNAelectrophoresisgaron2矩陣稀疏模式2DFEM,Navier-Stokes,CFD

n=10000;e=ones(n,1);n2=n/2;a=spdiags([-e3*e-e],-1:1,n,n);c=spdiags([e/2],0,n,n);c=fliplr(c);a=a+c;a(n2+1,n2)=-1;a(n2,n2+1)=-1;b=zeros(n,1);b(1)=2.5;b(n)=2.5;b(2:n-1)=1.5;b(n2:n2+1)=1;%%%JacobiMethod(IterativeMethod)ticd=diag(a);%extractdiagonalofar=a-diag(d);%ristheremainderx=zeros(n,1);%initializevectorxforj=1:50%loopforJacobiiterationx=(b-r*x)./d;endt1=toctic,x=full(a)\b,t2=toc%%

BackSlash(DirectMethod)Demo1

helpsparfunMatlab與大數(shù)據(jù)處理Elementarysparsematrices(例如spdiag