《研究生数值分析(12)高斯-赛德尔(Gauss-Seidel)迭代法》由会员分享，可在线阅读，更多相关《研究生数值分析(12)高斯-赛德尔(Gauss-Seidel)迭代法（20页珍藏版）》请在装配图网上搜索。
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 nkkkkkkiiiiiiiiiin niiiknnnnxaxaxaxbaxaxa xa xbaxaxaxa xa xaxbaxaxa 1)(1)(1)2 2,11)kkknnnnna xa xb （5）其矩阵表示形式为其矩阵表示形式为(1)1(1
3、)()()kkkXD LXUXb现将现将(1)kX显式化，由显式化，由(1)()()kkD LXUXb得得 (1)1()1()()kkXD L UXD L b令令 1()GBD L U（称为高斯称为高斯-赛德尔（赛德尔（Gauss-Seidel）迭代矩阵），）迭代矩阵），1()GfD L b则得则得 (1)()kkGGXB Xf为高斯为高斯-赛德尔迭代法的矩阵表示形式。赛德尔迭代法的矩阵表示形式。1()GBD L U0GI B1()0ID L U1()()0D LD L U1()0D L()0D L U 上式左端为将系数矩阵上式左端为将系数矩阵 A 的对角线及的对角线及对角线以下元素同乘以对角
4、线以下元素同乘以 后所得新矩阵的后所得新矩阵的行列式。行列式。我们用定理我们用定理2来判断高斯来判断高斯-赛德尔迭代公赛德尔迭代公式是否收敛，需要考虑高斯式是否收敛，需要考虑高斯-赛德尔迭代矩赛德尔迭代矩阵阵的特征方程的特征方程即即将上式写成将上式写成由于由于所以所以例例9 用高斯用高斯-赛德尔迭代法解方程组赛德尔迭代法解方程组1231231231023210152510 xxxxxxxxx 解：解：相应的高斯相应的高斯-赛德尔迭代公式为赛德尔迭代公式为(1)()()123(1)(1)()213(1)(1)(1)3120.20.10.30.20.11.50.20.42kkkkkkkkkxxxx
5、xxxxx取迭代初值取迭代初值(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于是于是 271729()0.1372 1500GB因
6、而高斯因而高斯-赛德尔迭代公式是收敛的。赛德尔迭代公式是收敛的。我们先引入一个叫矩阵谱半径的概念。我们先引入一个叫矩阵谱半径的概念。3 迭代法收敛条件与误差估迭代法收敛条件与误差估计计定义定义 矩矩阵阵n nA R的所有特征的所有特征值值(1,2,)iin的模的最大值称为矩阵的模的最大值称为矩阵 A 的谱半径的谱半径,记作记作()A即即1()maxii nA A1A 前面前面,我们在应用我们在应用雅可比迭代法雅可比迭代法与与高斯高斯-赛赛德尔迭代法德尔迭代法解一阶线性方程组时，判断各迭代解一阶线性方程组时，判断各迭代公式是收敛还是发散，都要计算雅可比迭代矩公式是收敛还是发散，都要计算雅可比迭代
7、矩阵阵 BJ 与高斯与高斯-赛德尔迭代矩阵赛德尔迭代矩阵 BG 的特征值的特征值.由由于矩阵于矩阵 A 有些算子范数有些算子范数(比如比如 与与 )远比远比矩阵矩阵 A 的特征值容易计算的特征值容易计算,为此给出如下结论为此给出如下结论。定理定理3 矩阵矩阵A的谱半径不超过矩阵的谱半径不超过矩阵A的的任何一种算子范数任何一种算子范数,即即证明：证明：设设为为A的任一特征值，的任一特征值，X为对应为对应于于的的A的特征向量，即的特征向量，即 AX=X,(X 0)由范数的性质立即可由范数的性质立即可得得rrrrrXXAXA X因为因为 X 0 ，所以所以 rA即即A的任一特征值的模都不超过的任一特
8、征值的模都不超过rA于是于是()rAA()rAA定理给出了一阶线性定常迭定理给出了一阶线性定常迭代法代法(1)()kkXBXf收敛的充分条件，它表明只要迭代矩阵收敛的充分条件，它表明只要迭代矩阵 B 的某种子的某种子范范数数小于小于1，立即可以断定该迭代过程对，立即可以断定该迭代过程对任给任给*X 在例在例8例例9中，我们分别用中，我们分别用雅可比迭代法雅可比迭代法和和高斯高斯-赛德尔迭代法赛德尔迭代法解方程组解方程组1231231231023210152510 xxxxxxxxx 初始向量都收敛于方程组初始向量都收敛于方程组AX=b的唯的唯一解一解rB雅可比迭代矩阵雅可比迭代矩阵 00.2
9、0.10.200.10.2 0.4 0JB0.6 1JB高斯高斯-赛德尔迭代矩阵赛德尔迭代矩阵 00.20.10 0.040.120 0.056 0.068GB0.3 1GB雅可比迭代过程必收敛；雅可比迭代过程必收敛；高斯高斯-赛德尔迭代过程也收敛。赛德尔迭代过程也收敛。由定理的误差估计由定理的误差估计式式()*(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 若方程组若方程组AX=b的系数矩阵的系数矩阵 ij n nAa
11、按行严格对角占优或按列严格对角占优，即满足条件按行严格对角占优或按列严格对角占优，即满足条件1niiijjj iaa(1,2,)in或或 1njjijii jaa(1,2,)jn则方程组则方程组AX=b有唯一解，且对任意初始向量有唯一解，且对任意初始向量(0)X雅可比迭代法与高斯雅可比迭代法与高斯-赛德尔迭代法都收敛。赛德尔迭代法都收敛。对于对于雅可比迭代法雅可比迭代法与与高斯高斯-赛德尔迭代赛德尔迭代法法，还有一些使用方便的充分条件，其中主，还有一些使用方便的充分条件，其中主要有：要有：定理定理5 若方程组若方程组 AX=b 的系数矩阵的系数矩阵 ij n nA a为对称为对称正定矩阵。则对
12、任意初始向量正定矩阵。则对任意初始向量 高斯高斯(0)X-赛德尔迭代法赛德尔迭代法都收敛。都收敛。ij n nA a 如在例如在例8例例9中，由于系数矩阵中，由于系数矩阵A是严是严格对角占优，由定理格对角占优，由定理4立即可断定用雅可比立即可断定用雅可比迭代法与高斯迭代法与高斯-赛德尔迭代法求解时，迭代赛德尔迭代法求解时，迭代过程都收敛。过程都收敛。只要方程组只要方程组 AX=b 的系数矩阵的系数矩阵 满足满足定理定理4或定理或定理5的条件，就可以十分方便地的条件，就可以十分方便地判断相应迭代过程的收敛性。判断相应迭代过程的收敛性。又如矩阵又如矩阵42222323 14A是对称正定阵（是对称正
13、定阵（实对称阵是正定阵的，如果实二次型实对称阵是正定阵的，如果实二次型12(,)Tnf x xxX AX正定正定),由定理由定理5可判定用高斯可判定用高斯-赛德尔迭代法求解方程组赛德尔迭代法求解方程组AX b时，迭代过程一定收敛。时，迭代过程一定收敛。例例10 考察用雅可比迭代法和高斯考察用雅可比迭代法和高斯-赛德尔迭代法赛德尔迭代法1 2211 11,12 211Ab 解：解：先计算迭代矩阵先计算迭代矩阵102 2()1 0122 0JBD L U 解方程组解方程组 AX=b 的收敛性，其中的收敛性，其中102 2()0 230 02GBD L U再计算再计算BJ与与BG的特征值和谱半径的特征值和谱半径()0,(1,2,3),()0 1iJJBiB 12,3()0,()2,()2 1GGGBBB 由定理由定理2知，用雅可比迭代法求解，迭代知，用雅可比迭代法求解，迭代过程收敛，用高斯过程收敛，用高斯-赛德尔迭代法求解，迭代赛德尔迭代法求解，迭代过程发散。过程发散。练习练习:考察用高斯考察用高斯-赛德尔迭代法赛德尔迭代法解方解方程组程组 AX=b 的收敛性，其中的收敛性，其中321011101A
研究生数值分析(12)高斯-赛德尔(Gauss-Seidel)迭代法
