1、研究雅可比迭代法,我们发现在逐个求研究雅可比迭代法,我们发现在逐个求(1)kX的分量时,当计算到的分量时,当计算到(1)kix时时,分量分量(1)(1)11,kkixx都已经求得,而仍用旧分量都已经求得,而仍用旧分量( )( )11,kkixx计算计算(1)kix。由于新计算出的分量比旧分量准确些,。由于新计算出的分量比旧分量准确些,(1)(1)11,kkixx求出,马上就用新分量求出,马上就用新分量(1)(1)11,kkixx代替雅可比迭代法中代替雅可比迭代法中()()11,kkixx来求来求(1)kix, 这就是高斯这就是高斯-赛德尔赛德尔(Gauss-Seidel)迭代法。迭代法。2 高
2、斯高斯-赛德尔(赛德尔(Gauss-Seidel)迭代法)迭代法因此设想一旦新分量因此设想一旦新分量*高斯高斯-赛德尔迭代公式如下:赛德尔迭代公式如下:(1)( )( )( )112 213 31111(1)(1)( )( )221 123 32211(1)(1)(1)(1)( )( )1 12 2, 11, 11(1)(1 11()1()1()1(kkkkn nkkkkn nkkkkkkiiii iii iiin niiiknnnnxa xa xa xbaxa xa xa xbaxa xa xaxaxa xbaxa xa 1)(1)(1)2 2,11)kkknn nnna xaxb (5)*
3、其矩阵表示形式为其矩阵表示形式为(1)1(1)( )()kkkXDLXUXb现将现将(1)kX显式化,由显式化,由 (1)( )()kkDL XUXb得得 (1)1( )1()()kkXDLUXDLb令令 1()GBDLU(称为高斯称为高斯-赛德尔(赛德尔(Gauss-Seidel)迭代矩阵),)迭代矩阵),1()GfDLb则得则得 (1)( )kkGGXB Xf为高斯为高斯-赛德尔迭代法的矩阵表示形式。赛德尔迭代法的矩阵表示形式。*1()GBDLU0GIB1()0IDLU1()()0DLDLU1()0DL()0DLU 上式左端为将系数矩阵上式左端为将系数矩阵 A 的对角线及对角线的对角线及对
4、角线以下元素同乘以以下元素同乘以 后所得新矩阵的行列式。后所得新矩阵的行列式。 我们用定理我们用定理2来判断高斯来判断高斯-赛德尔迭代公式是否赛德尔迭代公式是否收敛,需要考虑高斯收敛,需要考虑高斯-赛德尔迭代矩阵赛德尔迭代矩阵的特征方程的特征方程即即将上式写成将上式写成由于由于所以所以*例例9 用高斯用高斯-赛德尔迭代法解方程组赛德尔迭代法解方程组1231231231023210152510 xxxxxxxxx解:解:相应的高斯相应的高斯-赛德尔迭代公式为赛德尔迭代公式为(1)( )( )123(1)(1)( )213(1)(1)(1)3120.20.10.30.20.11.50.20.42k
5、kkkkkkkkxxxxxxxxx*取迭代初值取迭代初值(0)(0)(0)(0)123(,)(0,0,0)TTXxxx按此迭代公式进行迭代,计算结果为按此迭代公式进行迭代,计算结果为k( )1kx( )2kx( )3kx01234500.30.88040.98430.99780.999701.561.94451.99231.99891.999902.6842.95392.99382.99912.9999*高斯高斯-赛德尔迭代矩阵赛德尔迭代矩阵GB的特征方程为的特征方程为即即 2(500542)0解得解得 1232717292717290,50050005211021210*于是于是 27172
6、9()0.13721500GB因而高斯因而高斯-赛德尔迭代公式是收敛的。赛德尔迭代公式是收敛的。我们先引入一个叫矩阵谱半径的概念。我们先引入一个叫矩阵谱半径的概念。3 迭代法收敛条件与误差估计迭代法收敛条件与误差估计*定义定义 矩阵矩阵n nAR的所有特征值的所有特征值(1,2, )iin的模的最大值称为矩阵的模的最大值称为矩阵 A 的谱半径的谱半径,记作记作( )A即即1()maxiinA A1A 前面前面,我们在应用我们在应用雅可比迭代法雅可比迭代法与与高斯高斯-赛德尔迭赛德尔迭代法代法解一阶线性方程组时,判断各迭代公式是收敛还解一阶线性方程组时,判断各迭代公式是收敛还是发散,都要计算雅可
7、比迭代矩阵是发散,都要计算雅可比迭代矩阵 BJ 与高斯与高斯-赛德尔赛德尔迭代矩阵迭代矩阵 BG 的特征值的特征值.由于矩阵由于矩阵 A 有些算子范数有些算子范数(比比如如 与与 )远比矩阵远比矩阵 A 的特征值容易计算的特征值容易计算,为此给为此给出如下结论。出如下结论。*定理定理3 矩阵矩阵A的谱半径不超过矩阵的谱半径不超过矩阵A的任何的任何一种算子范数一种算子范数 , 即即证明:证明:设设为为A的任一特征值,的任一特征值,X为对应于为对应于的的A的特征向量,即的特征向量,即 AX= X, (X 0) 由范数的性质立即可得由范数的性质立即可得rrrrrXXAXAX因为因为 X 0 , 所以
8、所以 rA即即A的任一特征值的模都不超过的任一特征值的模都不超过rA于是于是( )rAA( )rAA*定理给出了一阶线性定常迭代法定理给出了一阶线性定常迭代法(1)( )kkXBXf收敛的充分条件,它表明只要迭代矩阵收敛的充分条件,它表明只要迭代矩阵 B 的某种子的某种子范数范数小于小于1,立即可以断定该迭代过程对任给,立即可以断定该迭代过程对任给*X 在例在例8例例9中,我们分别用中,我们分别用雅可比迭代法雅可比迭代法和和高斯高斯-赛德尔迭代法赛德尔迭代法解方程组解方程组1231231231023210152510 xxxxxxxxx初始向量都收敛于方程组初始向量都收敛于方程组AX=b的唯一
9、解的唯一解rB*雅可比迭代矩阵雅可比迭代矩阵 00.20.10.200.10.20.40JB0.61JB高斯高斯-赛德尔迭代矩阵赛德尔迭代矩阵 00.20.100.040.1200.0560.068GB0.31GB雅可比迭代过程必收敛;雅可比迭代过程必收敛;高斯高斯-赛德尔迭代过程也收敛。赛德尔迭代过程也收敛。*由定理的误差估计式由定理的误差估计式( )*(1)(0)1kkBXXXXB1,2,3,k 可以看出,可以看出,B且可用来估计迭代次数。且可用来估计迭代次数。越小收敛速度越快,越小收敛速度越快,在例在例8例例9中,显然中,显然GB比比JB小,小,所以高斯所以高斯-赛德尔迭代法比雅可比迭代
10、法收敛速度快。赛德尔迭代法比雅可比迭代法收敛速度快。*若在例若在例8例例9中要求近似解中要求近似解( )kX的误差的误差( )*410kXX则由误差估计式知,只要则由误差估计式知,只要 k 满足满足(1)(0)4101kBXXB将将(0)(1)0.6,(0,0,0) ,(0.3000,1.5000,2.0000)TTJBXX代入得代入得21.18k ,故,故Jacobi迭代迭代22次即可;次即可;(0)(1)0.3,(0,0,0) ,(0.3000,1.5600,2.68400)TTGBXX代入得代入得8.76k ,故,故Gauss-Seidel迭代迭代9次就可以。次就可以。将将*定理定理4
11、若方程组若方程组AX=b的系数矩阵的系数矩阵ijn nAa按行严格对角占优或按列严格对角占优,即满足条件按行严格对角占优或按列严格对角占优,即满足条件1niiijjj iaa(1,2, )in或或 1njjijiijaa(1,2, )jn则方程组则方程组AX=b有唯一解,且对任意初始向量有唯一解,且对任意初始向量(0)X雅可比迭代法与高斯雅可比迭代法与高斯-赛德尔迭代法都收敛。赛德尔迭代法都收敛。 对于对于雅可比迭代法雅可比迭代法与与高斯高斯-赛德尔迭代法赛德尔迭代法,还,还有一些使用方便的充分条件,其中主要有:有一些使用方便的充分条件,其中主要有:*定理定理5 若方程组若方程组 AX=b 的
12、系数矩阵的系数矩阵ijn nAa为对称为对称正定矩阵。则对任意初始向量正定矩阵。则对任意初始向量 高斯高斯(0)X-赛德尔迭代法赛德尔迭代法都收敛。都收敛。ij n nAa 如在例如在例8例例9中,由于系数矩阵中,由于系数矩阵A是严格对角是严格对角占优,由定理占优,由定理4立即可断定用雅可比迭代法与高斯立即可断定用雅可比迭代法与高斯-赛德尔迭代法求解时,迭代过程都收敛。赛德尔迭代法求解时,迭代过程都收敛。 只要方程组只要方程组 AX=b 的系数矩阵的系数矩阵 满足满足定理定理4或定理或定理5的条件,就可以十分方便地判断相的条件,就可以十分方便地判断相应迭代过程的收敛性。应迭代过程的收敛性。*又
13、如矩阵又如矩阵4222232314A是对称正定阵(是对称正定阵(实对称阵是正定阵的,如果实二次型实对称阵是正定阵的,如果实二次型12( ,)Tnf x xxX AX正定正定),由定理由定理5可判定用高斯可判定用高斯-赛德尔迭代法求解方程组赛德尔迭代法求解方程组AXb时,迭代过程一定收敛。时,迭代过程一定收敛。*例例10 考察用雅可比迭代法和高斯考察用雅可比迭代法和高斯-赛德尔迭代法赛德尔迭代法1221111,12211Ab 解:解:先计算迭代矩阵先计算迭代矩阵1022()101220JBDLU 解方程组解方程组 AX=b 的收敛性,其中的收敛性,其中*1022()023002GBDLU再计算再计算BJ与与BG的特征值和谱半径的特征值和谱半径()0,(1,2,3),()01iJJBiB12,3()0,()2,()21GGGBBB 由定理由定理2知,用雅可比迭代法求解,迭代过程收知,用雅可比迭代法求解,迭代过程收敛,用高斯敛,用高斯-赛德尔迭代法求解,迭代过程发散。赛德尔迭代法求解,迭代过程发散。*练习练习:考察用高斯考察用高斯-赛德尔迭代法赛德尔迭代法解方程组解方程组 AX=b 的收敛性,其中的收敛性,其中321011101A*