研究生数值分析(12)高斯-赛德尔(Gauss-Seidel)迭代法

研究雅可比迭代法，我们发现在逐个求(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高斯-赛德尔（Gauss-Seidel）迭代法因此设想一旦新分量高斯-赛德尔迭代公式如下：(1)()()()11221331111(1)(1)()()22112332211(1)(1)(1)(1)()()1122,11,11(1)(111()1()1()1(kkkknnkkkknnkkkkkkiiiiiiiiiinniiiknnnnxaxaxaxbaxaxaxaxbaxaxaxaxaxaxbaxaxa1)(1)(1)22,11)kkknnnnnaxaxb（5）其矩阵表示形式为(1)1(1)()()kkkXDLXUXb现将(1)kX显式化，由(1)()()kkDLXUXb得(1)1()1()()kkXDLUXDLb令1()GBDLU（称为高斯-赛德尔（Gauss-Seidel）迭代矩阵），1()GfDLb则得(1)()kkGGXBXf为高斯-赛德尔迭代法的矩阵表示形式。1()GBDLU0GIB1()0IDLU1()()0DLDLU1()0DL()0DLU上式左端为将系数矩阵A的对角线及对角线以下元素同乘以λ后所得新矩阵的行列式。我们用定理2来判断高斯-赛德尔迭代公式是否收敛，需要考虑高斯-赛德尔迭代矩阵的特征方程即将上式写成由于所以例9用高斯-赛德尔迭代法解方程组1231231231023210152510xxxxxxxxx解：相应的高斯-赛德尔迭代公式为(1)()()123(1)(1)()213(1)(1)(1)3120.20.10.30.20.11.50.20.42kkkkkkkkkxxxxxxxxx取迭代初值(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,,50050005211021210于是271729()0.13721500GB因而高斯-赛德尔迭代公式是收敛的。我们先引入一个叫矩阵谱半径的概念。3迭代法收敛条件与误差估计定义矩阵nnAR的所有特征值(1,2,,)iin的模的最大值称为矩阵A的谱半径,记作()A即1()maxiinAA1A前面,我们在应用雅可比迭代法与高斯-赛德尔迭代法解一阶线性方程组时，判断各迭代公式是收敛还是发散，都要计算雅可比迭代矩阵BJ与高斯-赛德尔迭代矩阵BG的特征值.由于矩阵A有些算子范数(比如与)远比矩阵A的特征值容易计算,为此给出如下结论。定理3矩阵A的谱半径不超过矩阵A的任何一种算子范数,即证明：设λ为A的任一特征值，X为对应于λ的A的特征向量，即AX=λX,(X≠0)由范数的性质立即可得rrrrrXXAXAX因为X≠0，所以rA即A的任一特征值的模都不超过rA于是()rAA()rAA定理给出了一阶线性定常迭代法(1)()kkXBXf收敛的充分条件，它表明只要迭代矩阵B的某种子范数小于1，立即可以断定该迭代过程对任给*X在例8例9中，我们分别用雅可比迭代法和高斯-赛德尔迭代法解方程组1231231231023210152510xxxxxxxxx初始向量都收敛于方程组AX=b的唯一解rB雅可比迭代矩阵00.20.10.200.10.20.40JB0.61JB高斯-赛德尔迭代矩阵00.20.100.040.1200.0560.068GB0.31GB雅可比迭代过程必收敛；高斯-赛德尔迭代过程也收敛。由定理的误差估计式()*(1)(0)1kkBXXXXB1,2,3,k可以看出，B且可用来估计迭代次数。越小收敛速度越快，在例8例9中，显然GB比JB小，所以高斯-赛德尔迭代法比雅可比迭代法收敛速度快。若在例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若方程组AX=b的系数矩阵[]ijnnAa按行严格对角占优或按列严格对角占优，即满足条件1niiijjjiaa(1,2,,)in或1njjijiijaa(1,2,,)jn则方程组AX=b有唯一解，且对任意初始向量(0)X雅可比迭代法与高斯-赛德尔迭代法都收敛。对于雅可比迭代法与高斯-赛德尔迭代法，还有一些使用方便的充分条件，其中主要有：定理5若方程组AX=b的系数矩阵[]ijnnAa为对称正定矩阵。则对任意初始向量高斯(0)X-赛德尔迭代法都收敛。[]ijnnAa如在例8例9中，由于系数矩阵A是严格对角占优，由定理4立即可断定用雅可比迭代法与高斯-赛德尔迭代法求解时，迭代过程都收敛。只要方程组AX=b的系数矩阵满足定理4或定理5的条件，就可以十分方便地判断相应迭代过程的收敛性。又如矩阵4222232314A是对称正定阵（实对称阵是正定阵的，如果实二次型12(,,,)TnfxxxXAX正定),由定理5可判定用高斯-赛德尔迭代法求解方程组AXb时，迭代过程一定收敛。例10考察用雅可比迭代法和高斯-赛德尔迭代法1221111,12211Ab解：先计算迭代矩阵1022()101220JBDLU解方程组AX=b的收敛性，其中1022()023002GBDLU再计算BJ与BG的特征值和谱半径()0,(1,2,3),()01iJJBiB12,3()0,()2,()21GGGBBB由定理2知，用雅可比迭代法求解，迭代过程收敛，用高斯-赛德尔迭代法求解，迭代过程发散。练习:考察用高斯-赛德尔迭代法解方程组AX=b的收敛性，其中321011101A