数值分析第三章 解线性方程组的迭代法.ppt

第3章 解线性方程组的迭代法,迭代法的基本思想是，把n元线性方程组,（3.1）,或,Ax=b,改写成等价的方程组,，或x=Mx+g,迭代法是从某一取定的初始向量x(0)出发,按照一个适当的迭代公式 ,逐次计算出向量x(1), x(2),…,使得向量序列{x(k)}收敛于方程组的精确解.迭代法是一类逐次近似的方法.其优点是,算法简便,程序易于实现.,由此建立方程组的迭代公式x(k+1)=Mx(k)+g , k=0,1,2,… (3.2) 其中M称为迭代矩阵对任意取定的初始向量x(0),由(3.2)式可逐次算出迭代向量x(k),k=1,2,…,,如果向量序列{x(k)} 收敛于x*,由(3.2)式可得,x*=Mx*+g,从而x*是方程组x=Mx+g的解,也就是方程组Ax=b的解.,这种求解线性方程组的方法称为迭代法 ,若迭代序列{x(k)}收敛,则称迭代法收敛,否则称迭代法发散.,§1 Jacobi迭代法和Gauss-Seidel迭代法,Jacobi方法是由方程组(3.1)中第k个方程解出x(k),得到等价方程组:,从而得迭代公式,式(3.3)称为Jacobi迭代法,简称为J迭代法.,,则J迭代法可写成x(k+1)=Bx(k)+g k=0,1,2,…,可见 ,J迭代法的迭代矩阵为,若记,J法也记为,G-S迭代法也可记为,式(3.4)称为Gauss-Seidel迭代法,简称为G-S迭代法.,若在J迭代法中,充分利用新值, 则可以得到如下的迭代公式,方程组的精确解为x*=(1,1,1)T.,解 J迭代法计算公式为,例1 用J法和G-S法求解线性方程组,取初始向量x(0)=(0,0,0)T,迭代可得,计算结果列表如下:,可见,迭代序列逐次收敛于方程组的解, 而切迭代7次得到精确到小数点后两位的近似解.,G-S迭代法的计算公式为:,同样取初始向量x(0)=(0,0,0)T, 计算结果为,由计算结果可见,G-S迭代法收敛较快.取精确到小数点后两位的近似解,G-S迭代法只需迭代3次,而J迭代法需要迭代7次.,,为了进一步研究,从矩阵角度来讨论上述迭代法.,对线性方程组Ax=b,记,D=diag(a11,a22,…,ann),则有 A=D-L-U,于是线性方程组 Ax=b 可写成(D-L-U)x=b,等价于Dx=(L+U)x+b 或 x=D-1(L+U)x+D-1b,,由此建立J迭代法迭代公式x(k+1)=D-1(L+U)x(k)+D-1b k=0,1,2,…,或写成x(k+1)=Bx(k)+g k=0,1,2,…,其中,G-S迭代法迭代公式可写成x(k+1)=D-1Lx(k+1)+D-1Ux(k)+D-1b,,讨论迭代法x(k+1)=Mx(k)+g k=0,1,2,…,Dx(k+1)=Lx(k+1)+Ux(k)+b,(D-L)x(k+1)=Ux(k)+b,x(k+1)=(D-L)-1Ux(k)+(D-L)-1b,所以G-S迭代法可以写成x(k+1)=Gx(k)+g k=0,1,2,…,其中,G=(D-L)-1U , g=(D-L)-1b,§2 迭代法的收敛性,的收敛性.,,记误差向量e(k)=x(k)-x*,则迭代法收敛就是e(k)0.,由于,x(k+1)=Mx(k)+g k=0,1,2,…,x*=Mx*+g k=0,1,2,…,所以,e(k+1)=Me(k) , k=0,1,2,…,递推可得,e(k)=Mke(0) , k=0,1,2,…,可见,当k时, e(k)0  Mk O.,对任意初始向量x(0),迭代法收敛(M)<1.,定理3.1,证 若‖Mk‖0, 则k(M)=(Mk)‖Mk‖0, 所以(M)<1.,若(M)0,使得(M)+<1.则 ‖Mk‖‖M‖k ((M)+)k 0.,,若‖M‖<1,则对任意x(0),迭代法收敛,而且,定理3.2,证 由于 x(k+1)=Mx(k)+g x(k)=Mx(k-1)+gx*=Mx*+g,所以 x(k+1) -x(k)=M(x (k) -x(k-1) ) , x(k+1) –x*=M(x (k) –x* ),于是有 ‖x(k+1) -x(k) ‖‖M‖‖x (k) -x(k-1) ‖‖x(k+1) –x*‖‖M‖‖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* ‖‖M‖‖x (k) –x(k-1) ‖+‖M‖‖x(k) –x* ‖,所以,定理3.2只是收敛的充分条件,并不必要,如,则‖M‖1=1.2,‖M‖=1.3,‖M‖2=1.09,‖M‖F=1.17,但(M)=0.8<1, 所以对应的迭代法是收敛的.,由(3.5)式可见,‖x (k) -x(k-1) ‖很小时,‖x(k) –x*‖就很小,实际上用‖x (k) -x(k-1) ‖<作为迭代终止的条件。

例如，例1中J-法计算结果如下：,‖x (6) -x(5) ‖=0.011339,‖x(7) –x(6)‖=0.0056695,由(3.6)式可得:,,若使‖x(k) –x*‖< ,只需,可以事先估计达到某一精度需要迭代多少步 即,用J迭代法求例1中方程组的解,取x(0)=(0,0,0)T,若使误差x(k)-x*<10-5,问需要迭代多少次?,解 由例1知,x(1)=(1.4,0.5,1.4)T,,于是有,x(1)-x(0)=1.4 ,B=0.5 .,例2,k应满足,故取k=19, 即需要迭代19次.,,§3 J迭代法和G-S迭代法的收敛性,定理3.3 J迭代法收敛(B)<1;若‖B‖<1J迭代法收敛; G-S迭代法收敛(G)<1;若‖G‖<1 G-S迭代法收敛;,定义3.1 若n阶矩阵A=(aij)满足:,则称矩阵A是严格对角占优矩阵.,引理 若A是严格对角占优矩阵, 则det(A)0.,证 A=D-L-U=D(E-D-1(L+U))=D(E-B),,因此, (B)‖B‖<1,故=1不是B的特征值,det(E-B)0。

定理3.4 设A是严格对角占优矩阵,则解线性方程组Ax=b的J迭代法和G-S迭代法均收敛因为A是严格对角占优矩阵, 所以det(D)0, 而且,所以, det(A)0.,证 由于‖B‖<1, 所以J迭代法收敛设是G的任一特征值, 则满足特征方程,,det(E-G)= det(E-(D-L)-1U),所以有 det((D-L)-U)=0,若||1, 则矩阵(D-L)-U 是严格对角占优矩阵, 这与 det((D-L)-U)=0矛盾, 所以||<1,于是(G)<1.,定理3.5,设A 是对称正定矩阵, 则解方程组Ax=b的(1)J迭代法收敛2D-A也正定;(2)G-S迭代法必收敛.,,= det((D-L)-1)((D-L)-U),= det((D-L)-1)det((D-L)-U)=0,试建立一个收敛的迭代格式,并说明收敛性.,解 按如下方法建立迭代格式,例3 已知解线性方程组,由于迭代矩阵的行范数小于1,故此迭代法收敛.,,改写成,将Jacobi迭代法,§4 逐次超松弛迭代法---SOR方法,写成向量形式就是x（k+1）=x（k）+D-1(b-Ax(k)) , k=0,1,2,…,Gauss-Seidel迭代法也可写成,或写成向量形式x（k+1）=x（k）+D-1(b+Lx(k+1)+(U-D)x(k)) , k=0,1,2,…,,构造迭代公式,此迭代法称为SOR方法,其中参数称为松弛因子,当>1时称为超松弛迭代, 当<1时称为欠松弛迭代.,其矩阵形式x(k+1)=x(k)+D-1(b+Lx(k+1)+(U-D)x(k)) , k=0,1,2,…,于是有Dx(k+1)=Dx(k)+(b+Lx(k+1)+(U-D)x(k)),所以x(k+1)=(D-L)-1 [(1-)D+U]x(k)+(D-L)-1b ,k=0,1,2,…,因此,SOR方法的迭代矩阵为£=(D-L)-1 [(1-)D+U],,SOR方法收敛(£)<1;若‖£‖<1,则SOR方法收敛.,定理3.7 若SOR方法收敛, 则0<<2.,定理3.6,证 设SOR方法收敛, 则(£)<1,所以|det(£)| =|12… n|<1,而det(£) =det[(D-L)-1 ((1-)D+U)],=det[(E-D-1L)-1 ]det[(1-)E+D-1U)],=(1-)n,于是|1-|<1, 或 0<<2,,定理3.8,设A是严格对角占优矩阵,则解方程组Ax=b的SOR方法,当0<1时收敛.,定理3.9 设A是对称正定矩阵, 则解方程组Ax=b的SOR方法,当0<<2时收敛.,证 设是£的任一特征值, y是对应的特征向量, 则,[(1-)D+U]y= (D-L)y,于是(1-)(Dy,y)+(Uy,y)=[(Dy,y)-(Ly,y)],由于A=D-L-U是对称正定的, 所以D是正定矩阵, 且L=UT. 若记(Ly,y)=+i, 则有,,(Dy,y)=>0,(Uy,y)=(y,Ly)=(Ly,y),,=-i,0<(Ay,y)=(Dy,y)-(Ly,y)-(Uy,y) =-2,所以,当0<<2时,有,(-+)2-(-)2= (2-)(2-)=  (2-)(2-)<0,所以||2<1, 因此(£)<1,即S0R方法收敛.,,可得 =2/,设是B的任一特征值, y是对应的特征向量, 则,(L+U)y=Dy,于是(Ly,y)+(Uy,y)=(Dy,y),当A对称正定时,即2-0,而 ((2D-A)y,y)=(Dy,y)+(Ly,y)+(Uy,y) =+2,即,当A对称正定时,Jacobi迭代法收敛2D-A正定.,SOR方法收敛的快慢与松弛因子的选择有密切关系.但是如何选取最佳松弛因子,即选取=*,使(£)达到最小,是一个尚未很好解决的问题.实际上可采用试算的方法来确定较好的松弛因子.经验上可取1.4<<1.6.,,用SOR方法解线性方程组,解 SOR方法迭代公式为,方程组的精确解是x*=(2,1,-1)T.,例4,取x(0)=(0,0,0)T,=1.46,计算结果如下:,,从结果可见 ,迭代20次时已获得精确到小数点后五位的近似解.如果取=1.25,则需要迭代56次才能得到具有同样精度的近似解;如果取=1,则需迭代110次以上.,练习题,第75页 习题33-2, 3-3, 3-4, 3-7, 3-8, 3-9,,设线性方程组,(1)写出Jacobi法和SOR法的迭代格式(分量形式);(2)讨论这两种迭代法的收敛性.(3)取初值x(0)=(0,0,0)T,若用Jacobi迭代法计算时, 预估误差x*-x(10) (取三位有效数字).,课堂练习,(2)因为A是严格对角占优矩阵,但不是正定矩阵,故Jacobi法收敛,SOR法当0<1时收敛.,解 (1)Jacobi法和SOR法的迭代格式分别为,(3)由(1)可见B=3/4,且取x(0)=(0,0,0)T,经计算可得x(1)=(1/4,-2/5,1/2)T,于是x(1)-x(0)=1/2,所以有,用SOR法求解方程组：,分别取=0.65、1、1.2、1.45计算.要求精度为10-6；并指出迭代次数。