38第八节 雅可比与高斯―塞德尔迭代法

数学学院信息与计算科学系生成向量序列{x(k)}，若xxkk)(lim称为迭代格式（1）的迭代矩阵。则有x*=Bx*+f，即x*为原方程组Ax=b的解，B基本思想：将方程组Ax=b(|A|0)转化为与其等价的方程组x=Bx+fx(k+1)=Bx(k)+f（k=0,1,2,)(1)取初始向量x(0)按下列迭代格式第八节雅可比迭代法与高斯—塞德尔迭代法数学学院信息与计算科学系序列{x(k)}的收敛条件，收敛速度，误差估计等。问题：如何构造迭代格式，迭代法产生的向量设方程组nnnnnnnnnnbxaxaxabxaxaxabxaxaxa22112222212111212111一、雅可比迭代法数学学院信息与计算科学系其中aii0(i=1,2,…,n)等价方程组112211112211222211221[]1[]1[]nnnnnnnnnnxaxaxbaxaxaxbaxaxaxba数学学院信息与计算科学系建立迭代格式)(1)(1)(1)(11)(11)1(2)(2)(323)(12122)1(21)(1)(313)(21211)1(1nknnnknnnknknnkkkknnkkkbxaxaaxbxaxaxaaxbxaxaxaax数学学院信息与计算科学系称为雅可比(Jacobi)迭代法，又称简单迭代法。或缩写为)(11)(11)()1(inijkjjiijkjjiiikibxaxaax),,2,1(ni数学学院信息与计算科学系111212122212nnnnnnaaaaaaAaaa1122nnaaDa2112000nnaLaa1212000nnaaaU记矩阵A=D-L-U，其中数学学院信息与计算科学系于是雅可比迭代法可写为矩阵形式bDxULDxkk1)(1)1()(其Jacobi迭代矩阵为B1=BJ=D-1(L+U)，即)(1ULDBJ0002122222211111112nnnnnnnnaaaaaaaaaaaa数学学院信息与计算科学系例如已知线性方程组Ax=b的矩阵为1()JBDLU其雅可比迭代矩阵为2111.5A13220010101223001010122300数学学院信息与计算科学系在Jacobi迭代中,计算xi(k+1)（2in）时,使用xj(k+1)代替xj(k)（1ji-1），即)(1)(1)(1)1(11)1(11)1(2)(2)(323)1(12122)1(21)(1)(313)(21211)1(1nknnnknnnknknnkkkknnkkkbxaxaaxbxaxaxaaxbxaxaxaax建立迭代格式二、高斯——塞德尔迭代法数学学院信息与计算科学系或缩写为nixaxabaxijnijkjijkjijiiiki,2,1][1111)()1()1(称为高斯—塞德尔（Gauss—Seidel）迭代法。其G-S迭代矩阵为B2=BG=(D-L)-1UbLDxULDxkk1)(1)1()()(于是高斯—塞德尔迭代法可写为矩阵形式数学学院信息与计算科学系例如已知线性方程组Ax=b的矩阵为1()GBDLU其G-S迭代矩阵为2111.5A132200110032010130012121300数学学院信息与计算科学系例1用雅可比迭代法解方程组2.453.82102.7210321321321xxxxxxxxx3.12.11.1x)2.4(51)3.82(101)2.72(101)(2)(1)1(3)(3)(1)1(2)(3)(2)1(1kkkkkkkkkxxxxxxxxx解：Jacobi迭代格式为精确解是数学学院信息与计算科学系kx1(k)x2(k)x3(k)10.720.830.8420.9711.071.15…………111.0999931.1999931.299991121.0999981.1999981.299997取计算如下Tx)0,0,0()0()2.4(51)3.82(101)2.72(101)(2)(1)1(3)(3)(1)1(2)(3)(2)1(1kkkkkkkkkxxxxxxxxx数学学院信息与计算科学系解：Gauss-Seidel迭代格式为)2.4(51)3.82(101)2.72(101)1(2)1(1)1(3)(3)1(1)1(2)(3)(2)1(1kkkkkkkkkxxxxxxxxx例2用Gauss—Seidel迭代法解上题。2.453.82102.7210321321321xxxxxxxxx数学学院信息与计算科学系取x(0)=(0,0,0)T计算如下：kx1(k)x2(k)x3(k)10.720.9021.1644…………81.0999981.1999991.3)2.4(51)3.82(101)2.72(101)1(2)1(1)1(3)(3)1(1)1(2)(3)(2)1(1kkkkkkkkkxxxxxxxxx数学学院信息与计算科学系定理1在下列任一条件下，雅克比迭代法收敛。1max31max21max11111111njiijjijjTnijiiiijjnijjiiijiaaADIaaBaaB三、迭代收敛的充分条件数学学院信息与计算科学系定理2设B1,B2分别为雅克比迭代矩阵与高斯—塞德尔迭代矩阵，则.21BB从而，当时，1max11nijjiiijiaaB高斯—塞德尔迭代法收敛。定义1设n阶矩阵A=(aij)n×n，如果则称矩阵A为行（或列）严格对角占优。ijijiiniaa),,2,1(||||jiijjjnjaa),,2,1(||||或(证明见书P77)数学学院信息与计算科学系定理3若矩阵A行（或列）严格对角占优，则解线性方程组Ax=b的Jacobi迭代法和Gauss-Seidel迭代法均收敛。证①设矩阵A行严格对角占优,由)(1ULDBJ0002122222211111112nnnnnnnnaaaaaaaaaaaa数学学院信息与计算科学系由此根据第五节定理4知道(I-BJ)是非奇异矩阵，因此A=D(I-BJ)也是非奇异矩阵.因为所以Jacobi迭代收敛.ijijiiniaa),,2,1(||||11,1,11maxmax1nnijJijininjijjijiiiiaBaaa所以有结论若矩阵A行(或列)严格对角占优，则A是非奇异矩阵.数学学院信息与计算科学系])(det[)det(1ULDIBIG0])(det[])det[(1ULDLD)1(0])(det[ULD②下面证明Gauss—Seidel迭代法收敛.ULDBG1)(，得由ijnijijijijijiiniaaaa),,2,1(||||||||111下面证明||1.若不然,即有使||1,则这说明(D-L)-U是奇异矩阵.数学学院信息与计算科学系ijnijijijijijiiniaaaa),,2,1(||||||||111是行严格对角占优矩阵,由结论知它是非奇异矩阵,这与式(1)矛盾,所以||1,从而(BG)1,即Gauss—Seidel迭代法收敛.即矩阵ULD)(nnnnnnaaaaaaaaa212222111211数学学院信息与计算科学系定理4若A为正定矩阵，则方程组Ax=b的Gauss—Seidel迭代法收敛。证因为A是对称正定的,所以有A=D-L-LT,对BG=(D-L)-1LT，设为BG的特征值，y为对应的特征向量，即有(D-L)-1LTy=y，LTy=(D-L)y，则[LTy,y]=[(D-L)y,y]],[],[],[yyLyyDyyLT从而数学学院信息与计算科学系因A正定，所以D正定，故设[Dy,y]=0。所以||1，从而(BG)1，故Gauss—Seidel迭代法收敛。,)(],[],[],[ibaibayyLyyDyyLT1)(||22222baba)(],[],[],[ibayyLyLyyyLT令-[Ly,y]=a+ib，则由复向量内积的性质有数学学院信息与计算科学系定理5若Jacobi迭代矩阵BJ为非负矩阵，则下列关系有一个且仅有一个成立：(1)(BJ)=(BG)=0；(2)0(BG)(BJ)1；(3)(BJ)=(BG)=1；(4)1(BJ)(BG).说明：当Jacobi迭代矩阵BJ为非负矩阵时,Jacobi方法和Gauss—Seidel方法同时收敛或同时发散,若为同时收敛,则后者比前者收敛快。数学学院信息与计算科学系例3已知方程组12310.500.70.510.50.800.510.9xxx判断雅可比迭代法和高斯—塞德尔法的敛散性？00.500.500.500.50JB解雅可比迭代矩阵数学学院信息与计算科学系20.50det()0.50.5(0.5)00.5JIB15.0)(JB故Jacobi迭代法收敛。再由定理5的2)或由A是对称正定阵知Gauss—Seidel迭代法也收敛，且比Jacobi迭代法收敛得快。