迭代矩陣譜半徑課件

《數(shù)值分析》10迭代法的收斂性Convergenceofiterativemethod迭代矩陣譜半徑Spectralradius對角占優(yōu)矩陣diagonallydominantmatrix

迭代矩陣譜半徑原始方程:Ax=b記

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

(k+1)=B

(k)

(k)=B

(k-1)(k=1,2,3,······)迭代格式:x(k+1)=Bx(k)+f

x(k+1)–x*=B(x(k)–x*)設(shè)方程組的精確解為x*,則有x*=Bx*+f2/15迭代矩陣譜半徑(1)

(k)=B

(k-1)=B2

(k-2)=···=Bk

(0)(2)迭代格式x(k+1)=Bx(k)+f收斂??！3/15迭代矩陣譜半徑證:由

(k)=B

(k-1),得

||

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

(k-1)||

(k=1,2,3,······)所以命題若||B||<1,則迭代法x(k+1)=Bx(k)+f

收斂||

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

(0)||

||B||<14/15迭代矩陣譜半徑矩陣A的譜設(shè)n階方陣A的n個特征值為:則稱集合為A的譜.記為chA矩陣A的譜半徑注1:當(dāng)A是對稱矩陣時,||A||2=(A)

注2:對Rn×n

中的范數(shù)||·||,有

(A)≤||A||特征值取模最大5/15迭代矩陣譜半徑定理4.1迭代法x(k+1)=Bx(k)+f

收斂<=>譜半徑ρ(B)<1證:對任何n階矩陣B都存在非奇矩陣P使

B=P–1JP其中,J為B的Jordan標(biāo)準(zhǔn)型其中,Ji

為Jordan塊6/15迭代矩陣譜半徑其中,λi

是矩陣B的特征值,由B=P–1JPBk=(P–1JP)(P–1JP)···(P–1JP)=P–1JkP迭代法x(k+1)=Bx(k)+f

收斂<=>(i=1,2,···,r)(i=1,2,···,r)譜半徑

(B)<17/15迭代矩陣譜半徑Ans=1.2604e-005例線性方程組Ax=b,分別取系數(shù)矩陣為試分析Jacobi迭代法和Seidel迭代法的斂散性D=diag(diag(A1));B1=D\(D-A1);max(abs(eig(B1)))(1)A1=[1,2,-2;1,1,1;2,2,1]8/15迭代矩陣譜半徑DL=tril(A1)B1=DL\(DL-A1)max(abs(eig(B1)))Ans=2(2)A2=[2,-1,1;1,1,1;1,1,-2]D=diag(diag(A2))B2=D\(D-A2)max(abs(eig(Bj)))Ans=1.11809/15迭代矩陣譜半徑DL=tril(A2)B2=DL\(DL-A2)max(abs(eig(B2)))Ans=1/2兩種迭代法之間沒有直接聯(lián)系對矩陣A1,求A1x=b的Jacobi迭代法收斂,而Gauss-Seidel迭代法發(fā)散;對矩陣A2,求A2x=b的Jacobi迭代法發(fā)散,而Gauss-Seidel迭代法收斂.10/15迭代矩陣譜半徑定理4.2:設(shè)x*為方程組Ax=b的解若||B||<1,則對迭代格式x(k+1)=Bx(k)+f

有(1)(2)誤差估計定理11/15迭代矩陣譜半徑證由||B||<1,有||x(k+1)–x(k)||=||(x*–x(k))–(x*–

x(k+1))||≥||(x*–x(k))||–||(x*–

x(k+1))||

≥||(x*–x(k))||–||B||||(x*–

x(k))||=(1-||B||)||(x*–

x(k))||所以||x(k+1)–x*||≤||B||||x(k)–x*||x(k+1)–x*=(Bx(k)+f)–(Bx*+f)=B(x(k)–x*

)12/15迭代矩陣譜半徑所以x(k+1)–x(k)=(Bx(k)–f)–(Bx(k-1)–f)=B(x(k)–x(k-1)

)||x(k+1)–x(k)||≤||B||||x(k)–x(k-1)||誤差估計:13/15迭代矩陣譜半徑定義4.1A=(aij)n×n,如果則稱A為嚴格對角占優(yōu)陣.例4.19>|-1|+|-1|10>|-1|+|-1|15>|-1|+|-1||a11|>|a12|+|a13||a22|>|a21|+|a23||a33|>|a31|+|a32|14/15迭代矩陣譜半徑定理4.3

若Ax=b的系數(shù)矩陣A是嚴格對角占優(yōu)矩陣,則Jacobi迭代和Seidel迭代均收斂證:由于矩陣A嚴格對角占優(yōu)由A矩陣構(gòu)造Jacobi迭代矩陣BJ=D-1(D–A)

第i行絕對值求和所以15/15迭代矩陣譜半徑矩陣的條件數(shù)概念

方程組Ax=b,右端項

b

有一擾動引起方程組解x的擾動設(shè)

x是方程組

Ax=b

的解,則有化簡,得由Ax=b

得所以12/16迭代矩陣譜半徑定義條件數(shù):Cond(A)=||A–1||||A||

或C(A)=||A–1||||A||當(dāng)條件數(shù)很大時,方程組Ax=b是病態(tài)問題;當(dāng)條件數(shù)較小時,方程組Ax=b是良態(tài)問題注:13/16迭代矩陣譜半徑類似,設(shè)方程組Ax=b,矩陣A

有一擾動時,將引起方程組解x的擾動設(shè)

x是方程組

Ax=b

的解,則有化簡,得取范數(shù)14/16迭代矩陣譜半徑階數(shù)456條件數(shù)19.4×1052.9×1079.8×108條件數(shù)21.5×1044.7×1051.4×107條件數(shù)∞

9.4×1052.9×1079.8×108Afamousexampleofabadlyconditionedmatrix15/16迭代矩陣譜半徑ans=-2.400027.0000-64.800042.0000ans=