数值分析对称正定矩阵的收敛性

数值分析对称正定矩阵的收敛性第一页，共十八页，2022年，8月28日例1常微分方程边值问题

在x1=0.1,x2=0.2,···,x9=0.9处的数值解解:令h=0.1,记yj=y(xj)(j=1,2,···,9),将代入微分方程,整理得–yj-1+(2–h2)yj–yj+1

=xjh2(j=1,2,···,9)

2/18第二页，共十八页，2022年，8月28日yj=[xjh2+yj-1+yj+1]/

(2–h2),(j=1,2,···,9)–yj-1+(2–h2)yj–yj+1

=xjh2高斯-赛德尔迭代格式:3/18第三页，共十八页，2022年，8月28日程序h=0.1;x=0:h:1;y=zeros(size(x));r1=h*h;r=2-r1;er=1;k=0;whilee>0.0001er=0;forj=2:10s=(y(j-1)+y(j+1)+r1*x(j))/r;er=max(er,abs(s-y(j)));y(j)=s;endk=k+1end准确解:y(x)=sinx/sin1-x-----y(x)o

yj4/18第四页，共十八页，2022年，8月28日正方形区域上第一边值问题

准确解:O1x1y5/18第五页，共十八页，2022年，8月28日取正整数n,记对区域做网格剖分:

xi=ih(i=0，1，……，n+1

)yj=jh(j=0，1，……，n+1)在点(xi，yj)处记uij=u(xi,yj),五点差分格式整理6/18第六页，共十八页，2022年，8月28日边界条件:u0,j

=0(j=1,···,n);un,j=(j=1,···,n);ui,0=0(i=1,···,n);ui,n=0(i=1,···,n)结点数n2102202

402迭代次数91303978CPU时间(s)0.141.84324.6720误差0.00285.6995e-46.6671e-4高斯-赛德尔迭代法实验:7/18第七页，共十八页，2022年，8月28日定理4.4方程组Ax=b中,若A是实对称正定矩阵,则Gauss-Seidel迭法收敛证明:由

A=D–L–LT

BG-S=(D–L)-1LT设λ为BG-S的任一特征值,x为其特征向量,则(D–L)-1LTx=λx

LTx=λ(D–L)x

A正定,故p=xTDx>0,记

xTLTx=a,则有xTLTx=λxT(D–L)xxTAx=xT(D–L–LT)x=p–a–a=p–2a>08/18第八页，共十八页，2022年，8月28日所以,迭代矩阵BG-S的谱半径ρ(BG-S)<1,从而当方程组Ax=b的系数矩阵A是实对称正定矩阵时,Gauss-Seidel迭代法收敛称

R=–lnρ(B)为迭代法的渐近收敛速度9/18第九页，共十八页，2022年，8月28日(i=1,2,···,n;k=1,2,3,··········)超松驰(SOR)迭代法Gauss-Seidel迭代格式10/18第十页，共十八页，2022年，8月28日定理4.8

若A是对称正定矩阵,则当0<ω<2时SOR迭代法解方程组

Ax=b是收敛的定理4.9

若A是严格对角占优矩阵,则当0<ω<1时SOR迭代法解方程组

Ax=b是收敛的迭代矩阵11/18第十一页，共十八页，2022年，8月28日例4.3用SOR方法解方程组(ω=1.4)w=input('input:w:=');A=[2-10;-12-1;0-12];b=[1;0;1.8];x=[1;1;1];er=1;k=0;whileer>0.0005er=0;k=k+1;fori=1:3s=0;t=x(i);x(i)=0;forj=1:3s=s+A(i,j)*x(j);endx(i)=(1-w)*t+w*(b(i)-s)/A(i,i);er=max(abs(x(i)-t),er);endendkk=10x=1.19991.39991.5999ω=1.2,只需k=612/18第十二页，共十八页，2022年，8月28日块迭代法简介设

A∈Rn×n,x∈Rn,b∈Rn将方程组Ax=b中系数矩阵A分块其中,Aii∈Rni×ni,Aij∈Rni×nj

,xi∈Rni,bi∈Rni13/18第十三页，共十八页，2022年，8月28日将A分解,A=DB–LB–UB

Jacobi块迭代

DBX(k+1)=(LB+UB)X(k)+bi=1,2,···,r(2)Gauss-Seidel块迭代DBX(k+1)=LBX(k+1)+UBX(k)+bi=1,2,···,r14/18第十四页，共十八页，2022年，8月28日块迭代求解X1=[x1

x2

x3]TX2=[x4

x5

x6]Tb1=[050]Tb2=[6–26]TDX1–X2=b1–X1+DX2=b2DX1(k+1)=b1+X2(k)DX2(k+1)=b2+X1(k)15/18第十五页，共十八页，2022年，8月28日(i,j=1,···,n)边值问题:(i,j=1,···,n;k=1,2,3,······）保留三对角块16/18第十六页，共十八页，2022年，8月28日取正整数n