第三章解线性方程组的迭代法.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次得到精确到小数点后两位的近似解.,k,x,1,(k),x,2,(k),x,3,(k),x,(k),-x,*,0,1,2,3,4,5,6,7,0,1.4,1.11,0.929,0.9906,1.01159,1.000251,0.9982364,0,0.5,1.20,1.055,0.9645,0.9953,1.005795,1.0001255,0,1.4,1.11,0.929,0.9906,1.01159,1.000251,0.9982364,1,0.5,0.2,0.071,0.0355,0.01159,0.005795,0.0017636,G-S,迭代法的计算公式为:,同样取初始向量,x,(0),=(0,0,0),T,计算结果为,由,计算结果可见,G-S,迭代法收敛较快.取精确到小数点后两位的近似解,G-S,迭代法只需迭代3次,而,J,迭代法需要迭代7次.,k,x,1,(k),x,2,(k),x,3,(k),x,(k),-x,*,0,1,2,3,0,1.4,1.0634,0.9951044,0,0.78,1.02048,0.99527568,0,1.026,0.987516,1.00190686,1,0.4,0.0634,0.0048956,为了进一步研究,从矩阵角度来讨论上述迭代法.,对,线性方程组,Ax,=,b,记,D,=,diag,(a,11,a,22,a,nn,),则有,A,=,D,-,L,-,U,于是线性方程组,Ax,=,b,可,写成,(,D,-,L,-,U,),x,=,b,等价于,Dx,=(,L,+,U,),x,+,b,或,x,=,D,-1,(,L,+,U,),x,+,D,-1,b,由此建立,J,迭代法迭代公式,x,(k+1),=,D,-1,(,L,+,U,),x,(k),+,D,-1,b,k=0,1,2,或写成,x,(k+1),=,Bx,(k),+,g,k=0,1,2,其中,G-S,迭代法迭代公式可写成,x,(k+1),=,D,-1,Lx,(k+1),+,D,-1,Ux,(k),+,D,-1,b,讨论迭代法,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,),-1,Ux,(k),+(,D,-,L,),-1,b,所以,G-S,迭代法可以写成,x,(k+1),=,Gx,(k),+,g,k=0,1,2,其中,G,=(,D,-,L,),-1,U,g,=(,D,-,L,),-1,b,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),=,M,k,e,(0),k=0,1,2,可见,当,k,时,e,(k),0,M,k,O,.,对任意初始向量,x,(0),迭代法收敛,(,M,)1.,定理3.1,证,若,M,k,0,则,k,(,M,)=(,M,k,),M,k,0,所以,(,M,)1.,若,(,M,)0,使得,(,M,)+1.,则,M,k,M,k,(,M,)+),k,0.,若,M,1,则,对任意,x,(0),迭代法收敛,而且,定理3.2,证,由于,x,(k+1),=,Mx,(k),+,g,x,(k),=,Mx,(k-1),+,g,x,*,=,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+1),-,x,(k),=,(,x,(k+1),x,*,)-(,x,(k),x,*,),x,(k),x,*,-,x,(k+1),x,*,x,(k+1),-,x,(k),=,(,x,(k+1),x,*,)-(,x,(k),x,*,),x,(k),x,*,-,x,(k+1),x,*,(1-,M,),x,(k),x,*,所以,定理3.2只是收敛的充分条件,并不必要,如,则,M,1,=1.2,M,=1.3,M,2,=1.09,M,F,=1.17,但,(,M,)=0.81,所以迭代法是收敛的.,由(3.5)式可见,M,越小,收敛越快,且当,x,(k),-,x,(k-1),很小时,x,(k),x,*,就,很小,实际上用,x,(k),-,x,(k-1),作为,迭代终止的条件,.例如,k,x,1,(k),x,2,(k),x,3,(k),x,(k),-x,*,0,1,2,3,4,5,6,7,0,1.4,1.11,0.929,0.9906,1.01159,1.000251,0.9982364,0,0.5,1.20,1.055,0.9645,0.9953,1.005795,1.0001255,0,1.4,1.11,0.929,0.9906,1.01159,1.000251,0.9982364,1,0.5,0.2,0.071,0.0355,0.01159,0.005795,0.0017636,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,=(,a,ij,),满足:,则称矩阵,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,),-1,U,),=,det,(,(,D-L,),-1,),det,(,(,D-L,)-,U,)=0,所以有,det,(,(,D-L,)-,U,)=0,若|,|1,则矩阵,(,D-L,)-,U,是,严格对角占优矩阵,这与,det,(,(,D-L,)-,U,)=0,矛盾,所以,|,|1,于是(,G,)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,),-1,b,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,-1,L,),-1,det,(1-,),E,+,D,-1,U,),=,(1-,),n,于是,|,1-,|1,或 0,2,定理3.8,设,A,是严格对角占优,矩阵,则解方程组,Ax=b,的,SOR,方法,当01时收敛.,定理3.9,设,A,是对称正定,矩阵,则解方程组,Ax=b,的,SOR,方法,当00,(,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,而 (,2,D-A,),y,y,)=(,Dy,y,)+(,Ly,y,)+(,Uy,y,)=,+2,即,当,A,对称正定时,Jacobi,迭代法收敛,2,D,-,A,正定.,SOR,方法收敛的快慢与松弛因子,的选择有密切关系.但是如何选取最佳松弛因子,即选取=,*,使(,)达到最小,是一个尚未很好解决的问题.实际上可采用试算的方法来确定较好的松弛因子.经验上可取1.41.6.,用,SOR,方法解线性方程组,解,SOR,方法迭代公式为,方程组的精确解是,x,*,=(2,1,-1),T,.,例4,取,x,(0),=(0,0,0),T,=1.46,计算结果如下:,k,x,1,(k),x,2,(k),x,3,(k),0,1,2,3,20,0,3.65,2.32166910,2.5661399,1.9999987,0,0.8845882,0.4230939,0.6948261,1.0000013,0,-0.2021098,-0.22243214,-0.4952594,-1.0000034,从结果可见,迭代20次时已获得精确到小数点后五位的近似解.如果取,=1.25,则需要迭代56次才能得到具有同样精度的近似解;如果取=1,则需迭代110次以上.,练习题,第,75页 习题3,3-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,法当01时收敛.,解 (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,；并指出迭代次数。,上机实验题目,（,参考,P66,解线性方程组的,SOR,迭代算法）,课间休息,