2.3 Jacobi方法与Gauss-Seidel方法-w

解线性方程组的迭代法线性方程组11112211211222221122nnnnnnnnnnaxaxaxbaxaxaxbaxaxaxbAx=b1112111212222212nnnnnnnnaaaxbaaaxbaaaxb已知线性代数方程组Axb将方程组改写成等价的形式xHxg建立迭代式：10,1,2kkxHxgkkx称为迭代序列，并称H为迭代矩阵。简单迭代法基本迭代法其中，A=(aij)∈Rn×n为非奇异矩阵设线性方程组Ax=b，其中，M为可选择的非奇异矩阵，且使Mx=d容易求解，一般选择A的某种近似，称M为分裂矩阵.将A分裂为A=M-N.线性方程组的迭代法1逐步逼近Jacobi迭代法Gauss-Seidel迭代法松弛(SOR)迭代法2下降法2.1最速下降法2.2共轭梯度法设aii0(i=1,2,,n)，并将A写成三部分.00000000,121,211,1121,212,11,1212211ULDaaaaaaaaaaaaaaaAnnnnnnnnnnnnnn111212122212nnnnnnaaaaaaAaaa1122nnaaDa2112000nnaLaa1212000nnaaaU即A=D-L-UbDxULDx11)(,ULDaaaaaaaaaAnnnnnn000000211221212211设，将A分解为),,2,1(0niaiiA=-UbxULDxbxULDbAx)()(BJfJacobi迭代阵-L2.3.1雅可比(Jacobi)迭代法于是雅可比迭代法可写为矩阵形式bDxULDxkk1)(1)1()(其Jacobi迭代矩阵为)(1ULDBJ0002122222211111112nnnnnnnnaaaaaaaaaaaa下面给出雅可比迭代法的分量计算公式,记,),,,,()()()(1)(Tknkikkxxxx由雅可比迭代法有,)()()1(bxULDxkk每一个分量写出来为).,,2,1(1)(11)()1(nibxaxaxainijkjijijkjijkiii即当aii0时，有).,,2,1()(11)(11)()1(nibxaxaaxinijkjijijkjijiiki于是，解Ax=b的雅可比迭代法的计算公式为)6.2().,1,0(),,2,1(,/)(,),,(1)()1()0()0(1)0(表示迭代次数kniaxabxxxxiinijjkjijikiTn雅可比迭代法计算公式简单，每迭代一次只需计算一次矩阵和向量的乘法且计算过程中原始矩阵A始终不变.。的矩阵迭代形式并求解写出，取初始向量：例JacobixxxxxxxxxxT,)0,0,0(5223122)0(321321321,...1,0,531022101220)()1(kxxkk5,)5,3,1(,)0,0,0()0()1()1()0(xxxxTT8,)3,3,5()1()2()2(xxxT0,)1,1,1(4,)1,1,1()4()4()4()2()3()3(xxxxxxTTTxx)1,1,1(*)4(所以分量形式1111221331111112221123322222111221111,1...1......1...1,1,2,...,kkkknnkkkknnkkkknnnnnnnnnnnnkkiiijjjjiiiiibxaxaxaxaabxaxaxaxaabxaxaxaxaaborxaxinaa1/)225(1/)3(1/)221()0,0,0()(2)(1)1(3)(3)(1)1(2)(3)(2)1(1)0(kkkkkkkkkTxxxxxxxxxx为上面例对应的分量形式TTTxxx)3,3,5()5,3,1()0,0,0()2()1()0()(11)(1)(414)(313)(21211)1(1bxaxaxaxaaxknnkkkk)(12)(2)(424)(323)1(12122)1(2bxaxaxaxaaxknnkkkk)(13)(3)(434)1(232)1(13133)1(3bxaxaxaxaaxknnkkkk)(1)1(11)1(33)1(22)1(11)1(nknnnknknknnnknbxaxaxaxaax…………只存一组向量即可。写成矩阵形式：bDUxLxDxkkk1)()1(1)1()(bUxxLDkk)()1()(bLDUxLDxkk1)(1)1()()(BGfGauss-Seidel迭代阵2.3.2高斯－赛德尔迭代法缩写为称为高斯—塞德尔(Gauss—Seidel)迭代法.bLDxULDxkk1)(1)1()()(其Gauss—Seidel迭代矩阵为BG=(D-L)-1U可写为矩阵形式).,,2,1()(11)(11)1()1(nibxaxaaxinijkjijijkjijiiki例1用雅可比迭代法解方程组2.453.82102.7210321321321xxxxxxxxx)2.4(51)3.82(101)2.72(101)(2)(1)1(3)(3)(1)1(2)(3)(2)1(1kkkkkkkkkxxxxxxxxx.3.12.11.1x解确精解：Jacobi迭代格式为kx1(k)x2(k)x3(k)10.720.830.8420.9711.071.15…………111.0999931.1999931.299991121.0999981.1999981.299997取x(0)=(0,0,0)T计算结果如下：解：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对比(1)：存储空间Jacobi迭代Gauss-Seidel迭代计算x(k+1)时需要x(k)的所有分量，因此需两组存储单元分别存放x(k)和x(k+1)计算xi(k+1)时只需要x(k)的i+1~n个分量，因此x(k+1)的前i个分量可存贮在x(k)的前i个分量所占的存储单元，无需开两组存储单元取x(0)=(0,0,0)T计算结果如下：kx1(k)x2(k)x3(k)10.720.9021.1644…………81.0999981.1999991.3对比(2)：计算速度迭代收敛的充分必要条件(1)迭代法x(k+1)=Hx(k)+f收敛limHk=O；(2)迭代法x(k+1)=Hx(k)+f收敛(H)1.推论设Ax=b，其中A=D-L-U为非奇异矩阵且D非奇异矩阵，则有(1)Jacobi迭代法收敛(J)1,其中J=D-1(L+U).(2)G-S迭代法收敛(G)1,其中G=(D-L)-1U.212111111A计算特征值：123502,,1512(())DLU1212000111()DLU1212J法不收敛Jacobi迭代法的迭代矩阵：例方程组的系数矩阵为：G-S法的迭代矩阵：1()GDLU20211101010100001011201211200120010000101112()GG-S法收敛12000012121212定义2.4(对角占优阵)设A=(aij)n×n.(1)如果A的元素满足).,,2,1(1niaaiinijjij称A为严格(按行)对角占优阵.(2)如果A的元素满足).,,2,1(1niaaiinijjij且上式至少有一个不等式成立，称A为弱(按行)对角占优阵.定理:A=(aij)n×n为严格对角占优矩阵则A为非奇异矩阵.实例例如310131012A310121011B其中A是严格对角占优阵（每一行对角元素的绝对值严格大于同行其他元素绝对值之和)；B是弱对角占优阵（至少有一个不等式成立）。定义2.5(可约与不可约矩阵)设A=(aij)n×n(n≥2)，如果存在置换阵P使,DOCBPAPT其中B为r阶方阵，D为n-r阶方阵(1≤r≤n)，则称A为可约矩阵.否则，则称A为不可约矩阵.定理2.6A不可约，且具有弱对角优势，则A非奇异.例如：矩阵11100011A2是可约的11100011213rr13cc1110001121.A没有零元素或零元素太少(少于n-1)时不可约;2.三对角阵如果三条对角线上的元素都不为零时不可约注意：例设有矩阵),,(.4110140110410114,11122211都不为零iiinnnnncbaBbacbacbacbA则A,B都是不可约矩阵.可约矩阵的等价定义2()nnARn设矩阵，，如果存在的两个非空子集和，满足T12,,,n,使得0,ijaij则称矩阵可约，否则称不可约。AA例如：矩阵11100011A22,31定理2.6如果A=(aij)n×n为严格对角占优矩阵或A为不可约弱对角占优矩阵，则A为非奇异矩阵.证明只就A为严格对角占优矩阵证明此定理.采用反证法，如果det(A)=0，则Ax=0有非零解，记为x=(x1,x2,,xn)T，则.0max1inikxx由齐次方程组第k个方程,01njjkjxa则有,||111nkjjkjknkjjjkjnkjjjkjkkkaxxaxaxa即,1nkjjkjkkaa这与假设矛盾，故det(A)≠0.定理2.7设方程组Ax=b，如果(1)A为严格对角占优阵，则解Ax=b的Jacobi迭代法,Gauss-Seidel迭代法均收敛.(2)A为不可约弱对角占优阵,则解Ax=b的Jacobi迭代法,Gauss-Seidel迭代法均收敛.证明只证(1).因为A是严格对角占优阵，所以aii≠0(i=1,,n).)(1ULDJ0002122222211111112nnnnnnnnaaaaaaaaaaaa则||J||1，