《研究生数值分析(12)高斯-赛德尔(Gauss-Seidel)迭代法》由会员分享,可在线阅读,更多相关《研究生数值分析(12)高斯-赛德尔(Gauss-Seidel)迭代法(20页珍藏版)》请在金锄头文库上搜索。
1、研究雅可比迭代法,我们发现在逐个求研究雅可比迭代法,我们发现在逐个求的分量时,当计算到的分量时,当计算到时时,分量分量都已经求得,而仍用旧分量都已经求得,而仍用旧分量计算计算。由于新计算出的分量比旧分量准确些,。由于新计算出的分量比旧分量准确些,求出,马上就用新分量求出,马上就用新分量代替雅可比迭代法中代替雅可比迭代法中来求来求, 这就是高斯这就是高斯-赛德尔赛德尔(Gauss-Seidel)迭代法。迭代法。2 高斯高斯-赛德尔(赛德尔(Gauss-Seidel)迭代法)迭代法因此设想一旦新分量因此设想一旦新分量高斯高斯-赛德尔迭代公式如下:赛德尔迭代公式如下: (5)其矩阵表示形式为其矩阵表
2、示形式为现将现将显式化,由显式化,由 得得 令令 (称为高斯称为高斯-赛德尔(赛德尔(Gauss-Seidel)迭代矩阵),)迭代矩阵),则得则得 为高斯为高斯-赛德尔迭代法的矩阵表示形式。赛德尔迭代法的矩阵表示形式。 上式左端为将系数矩阵上式左端为将系数矩阵 A 的对角线及的对角线及对角线以下元素同乘以对角线以下元素同乘以 后所得新矩阵的后所得新矩阵的行列式。行列式。 我们用定理我们用定理2来判断高斯来判断高斯-赛德尔迭代公赛德尔迭代公式是否收敛,需要考虑高斯式是否收敛,需要考虑高斯-赛德尔迭代矩赛德尔迭代矩阵阵的特征方程的特征方程即即将上式写成将上式写成由于由于所以所以例例9 用高斯用高斯
3、-赛德尔迭代法解方程组赛德尔迭代法解方程组解:解:相应的高斯相应的高斯-赛德尔迭代公式为赛德尔迭代公式为取迭代初值取迭代初值按此迭代公式进行迭代,计算结果按此迭代公式进行迭代,计算结果为为01234500.30.88040.98430.99780.999701.561.94451.99231.99891.999902.6842.95392.99382.99912.9999高斯高斯-赛德尔迭代矩赛德尔迭代矩阵阵的特征方程为的特征方程为即即 解得解得 于是于是 因而高斯因而高斯-赛德尔迭代公式是收敛的。赛德尔迭代公式是收敛的。我们先引入一个叫矩阵谱半径的概念。我们先引入一个叫矩阵谱半径的概念。3
4、迭代法收敛条件与误差估迭代法收敛条件与误差估计计定义定义 矩矩阵阵的所有特征的所有特征值值的模的最大值称为矩阵的模的最大值称为矩阵 A 的谱半径的谱半径,记作记作即即 前面前面,我们在应用我们在应用雅可比迭代法雅可比迭代法与与高斯高斯-赛赛德尔迭代法德尔迭代法解一阶线性方程组时,判断各迭代解一阶线性方程组时,判断各迭代公式是收敛还是发散,都要计算雅可比迭代矩公式是收敛还是发散,都要计算雅可比迭代矩阵阵 BJ 与高斯与高斯-赛德尔迭代矩阵赛德尔迭代矩阵 BG 的特征值的特征值.由由于矩阵于矩阵 A 有些算子范数有些算子范数(比如比如 与与 )远比远比矩阵矩阵 A 的特征值容易计算的特征值容易计算
5、,为此给出如下结论。为此给出如下结论。定理定理3 矩阵矩阵A的谱半径不超过矩阵的谱半径不超过矩阵A的的任何一种算子范数任何一种算子范数 , 即即证明:证明:设设为为A的任一特征值,的任一特征值,X为对应为对应于于的的A的特征向量,即的特征向量,即 AX= X, (X 0) 由范数的性质立即可由范数的性质立即可得得因为因为 X 0 , 所以所以 即即A的任一特征值的模都不超过的任一特征值的模都不超过于是于是定理给出了一阶线性定常迭定理给出了一阶线性定常迭代法代法收敛的充分条件,它表明只要迭代矩阵收敛的充分条件,它表明只要迭代矩阵 B 的某种子的某种子范范数数小于小于1,立即可以断定该迭代过程对,
6、立即可以断定该迭代过程对任给任给 在例在例8例例9中,我们分别用中,我们分别用雅可比迭代法雅可比迭代法和和高斯高斯-赛德尔迭代法赛德尔迭代法解方程组解方程组初始向量都收敛于方程组初始向量都收敛于方程组AX=b的唯的唯一解一解雅可比迭代矩阵雅可比迭代矩阵 高斯高斯-赛德尔迭代矩阵赛德尔迭代矩阵 雅可比迭代过程必收敛;雅可比迭代过程必收敛;高斯高斯-赛德尔迭代过程也收敛。赛德尔迭代过程也收敛。由定理的误差估计由定理的误差估计式式可以看出,可以看出,且可用来估计迭代次数。且可用来估计迭代次数。越小收敛速度越快,越小收敛速度越快,在例在例8例例9中,显然中,显然比比小,小,所以高斯所以高斯-赛德尔迭代
7、法比雅可比迭代法收敛速度快。赛德尔迭代法比雅可比迭代法收敛速度快。若在例若在例8例例9中要求近似解中要求近似解的误差的误差则由误差估计式知,只要则由误差估计式知,只要 k 满足满足将将代入得代入得,故,故Jacobi迭代迭代22次即可;次即可;代入得代入得,故,故Gauss-Seidel迭代迭代9次就可以。次就可以。将将定理定理4 若方程组若方程组AX=b的系数矩阵的系数矩阵按行严格对角占优或按列严格对角占优,即满足条件按行严格对角占优或按列严格对角占优,即满足条件或或 则方程组则方程组AX=b有唯一解,且对任意初始向量有唯一解,且对任意初始向量雅可比迭代法与高斯雅可比迭代法与高斯-赛德尔迭代
8、法都收敛。赛德尔迭代法都收敛。 对于对于雅可比迭代法雅可比迭代法与与高斯高斯-赛德尔迭代赛德尔迭代法法,还有一些使用方便的充分条件,其中主,还有一些使用方便的充分条件,其中主要有:要有:定理定理5 若方程组若方程组 AX=b 的系数矩阵的系数矩阵为对称为对称正定矩阵。则对任意初始向量正定矩阵。则对任意初始向量 高斯高斯-赛德尔迭代法赛德尔迭代法都收敛。都收敛。 如在例如在例8例例9中,由于系数矩阵中,由于系数矩阵A是严是严格对角占优,由定理格对角占优,由定理4立即可断定用雅可比立即可断定用雅可比迭代法与高斯迭代法与高斯-赛德尔迭代法求解时,迭代赛德尔迭代法求解时,迭代过程都收敛。过程都收敛。
9、只要方程组只要方程组 AX=b 的系数矩阵的系数矩阵 满足满足定理定理4或定理或定理5的条件,就可以十分方便地的条件,就可以十分方便地判断相应迭代过程的收敛性。判断相应迭代过程的收敛性。又如矩阵又如矩阵是对称正定阵(是对称正定阵(实对称阵是正定阵的,如果实二次型实对称阵是正定阵的,如果实二次型正定正定),由定理由定理5可判定用高斯可判定用高斯-赛德尔迭代法求解方程组赛德尔迭代法求解方程组时,迭代过程一定收敛。时,迭代过程一定收敛。例例10 考察用雅可比迭代法和高斯考察用雅可比迭代法和高斯-赛德尔迭代法赛德尔迭代法解:解:先计算迭代矩阵先计算迭代矩阵解方程组解方程组 AX=b 的收敛性,其中的收敛性,其中再计算再计算BJ与与BG的特征值和谱半径的特征值和谱半径 由定理由定理2知,用雅可比迭代法求解,迭代知,用雅可比迭代法求解,迭代过程收敛,用高斯过程收敛,用高斯-赛德尔迭代法求解,迭代赛德尔迭代法求解,迭代过程发散。过程发散。练习练习:考察用高斯考察用高斯-赛德尔迭代法赛德尔迭代法解方解方程组程组 AX=b 的收敛性,其中的收敛性,其中