数值分析迭代法的收敛性分析

数值分析迭代法的收敛性分析第1页，共18页，2023年，2月20日，星期六平面点列:(x1,y1),(x2,y2),···,(xk,yk),······Xk∈Rn:X1,X2,···,Xk,·······利用向量范数等价性,对任意范数||·||2/18第2页，共18页，2023年，2月20日，星期六原方程: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*)设方程组的精确解为X*,则有X*=BX*+f3/18第3页，共18页，2023年，2月20日，星期六(1)(k)=B(k-1)=B2

(k-2)=···=Bk

(0)(2)迭代格式

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

！4/18第4页，共18页，2023年，2月20日，星期六证:由(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||<15/18第5页，共18页，2023年，2月20日，星期六矩阵B的谱设n阶方阵B的n个特征值为:则称集合为B的谱.记为

chB矩阵B的谱半径注1:当B是对称矩阵时,||B||2=(B)

注2:对

Rn×n

中的范数||·||,有

(B)≤||B||特征值取模最大6/18第6页，共18页，2023年，2月20日，星期六定理4.1迭代法

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

收敛

谱半径ρ(B)<1证:对任何

n阶矩阵B都存在非奇矩阵P使

B=P–1JP其中,J为B的Jordan标准型其中,Ji为Jordan块7/18第7页，共18页，2023年，2月20日，星期六其中,λ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)<18/18第8页，共18页，2023年，2月20日，星期六注1:AX=bX=BX+

f(I–B)X=f

X=(I–B)-1

f注2:若

则(I-B)-1=I+B+B2+······+Bk+······事实上(I-B)(I+B+B2+······+Bk

)=I–Bk+1注3:X(k)=BX(k-1)+f=B(BX(k-2)+f)+f=····=BkX(0)+(I+B+····+Bk-1)f

≈

(I–B)-1

f9/18第9页，共18页，2023年，2月20日，星期六Ans=1.2604e-005例线性方程组

AX=b,分别取系数矩阵为试分析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]10/18第10页，共18页，2023年，2月20日，星期六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.118011/18第11页，共18页，2023年，2月20日，星期六DL=tril(A2)B2=DL\(DL-A2)max(abs(eig(B2)))Ans=1/2对矩阵A1,求A1X=b的Jacobi迭代法收敛,而Gauss-Seidel迭代法发散;对矩阵A2,求A2X=b的Jacobi迭代法发散,而Gauss-Seidel迭代法收敛.除非BJ是非负矩阵时,两种迭代法有联系。12/18第12页，共18页，2023年，2月20日，星期六定理4.2:设X*为方程组

AX=b的解若||B||<1,则对迭代格式

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

有(1)(2)误差估计定理13/18第13页，共18页，2023年，2月20日，星期六证由||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*=B(X(k)–X*

)14/18第14页，共18页，2023年，2月20日，星期六所以X(k+1)–X(k)=B(X(k)–X(k-1)

)||X(k+1)–X(k)||≤||B||||X(k)–X(k-1)||误差估计:15/18第15页，共18页，2023年，2月20日，星期六定义4.1A=(aij)n×n,如果则称A为严格对角占优阵.例4.19>|-1|+|-1|10>|-1|+|-1|15>|-1|+|-1||a11|>|a12|+|a13||a22|>|a21|+|a23||a33|>|a31|+|a32|16/18第16页，共18页，2023年，2月20日，星期六定理4.3

若Ax=b的系数矩阵A是严格对角占优矩阵,则Jacobi迭代和Seidel迭代均收敛证:由于矩阵A严格对角占优由A矩阵构造Jacobi迭代矩阵BJ