计算方法 线性方程组迭代解法 基本矩阵分裂迭代法ch06b r

1、1第六章线性方程组的迭代解法计算方法 基本的矩阵分裂迭代法基本的矩阵分裂迭代法2本讲内容本讲内容l Jacobi 迭代算法迭代算法l Gauss-Seidel 迭代算法迭代算法l SOR 迭代算法迭代算法l 收敛性分析收敛性分析n 矩阵分裂迭代法的典型代表矩阵分裂迭代法的典型代表3Jacobi 迭代迭代考虑线性方程组考虑线性方程组Ax = b其中其中 A=(aij)n n 非奇异，且对角线元素全不为非奇异，且对角线元素全不为 0。1122diag(,)nnDaaa 211,10 0,0nn naLaa l 将将 A 分裂成分裂成 A = D - L- U， 其中其中1211,000nnnaaU

2、a 4Jacobi 迭代迭代(1)1( )1()kkxDLU xD b k = 0, 1, 2, 令令 M = D，N = L + U，可得，可得 雅可比雅可比 (Jacobi) 迭代方法迭代方法 Jacobi 迭代迭代l 迭代矩阵记为：迭代矩阵记为：1()JDLU l 分量形式：分量形式：1(1)( )( )11inkkkiiijjijjiijj ixba xa xa i = 1, 2, , n， k = 0, 1, 2, 5Gauss-Seidel 迭代迭代l 在计算在计算 时，如果用时，如果用 代替代替 ，则可能会得到更好的收敛效果。则可能会得到更好的收敛效果。(1)kix (1)(1)

3、11,kkixx( )( )11,kkixx (1)( )( )( )11122133111(1)( )( )( )22211233222(1)( )( )( )1122,11 kkkknnkkkknnkkkknnnnn nnnnxba xa xa xaxba xa xa xaxba xa xaxa (1)( )( )( )11122133111(1)(1)( )( )22211233222(1)(1)(1)(1)1122,11 kkkknnkkkknnkkkknnnnn nnnnxba xa xa xaxba xa xa xaxba xa xaxa 6Gauss-Seidel 迭代迭代 (1

4、)1(1)( )kkkxDbLxUx 写成矩阵形式写成矩阵形式:此迭代方法称为此迭代方法称为 高斯高斯-塞德尔塞德尔 (Gauss-Seidel) 迭代法迭代法k = 0, 1, 2, 11(1)( )kkxDLUxDLb 可得可得1GDLUl 迭代矩阵记为：迭代矩阵记为：7SOR 迭代迭代l 为了得到更好的收敛效果，可在修正项前乘以一个为了得到更好的收敛效果，可在修正项前乘以一个 松弛因子松弛因子 ，于是可得迭代格式，于是可得迭代格式在在 G-S 迭代中迭代中 (1)(1)(1)( )( )11,11,11,kkkkkiiii iii iii nniixba xaxaxa xa 1(1)(

5、)1( )inkkiijjijjiijj ikiba xa xax (1)1(1)()1()inkkiijjijjiijkiij ikba xaaxxx 8SOR 迭代迭代 (1)( )1(1)( )( )kkkkkxxDbLxUxDx 11(1)( )(1)kkxDLDU xDLb 写成矩阵形式写成矩阵形式:可得可得 SOR (Successive Over-Relaxation) 迭代方法迭代方法 1(1)LDLDU l 迭代矩阵记为：迭代矩阵记为：l SOR 的优点的优点：通过选取合适的：通过选取合适的 ，可获得更快的收敛速度，可获得更快的收敛速度l SOR 的缺点的缺点：最优参数最优参

6、数 的的选取比较困难选取比较困难9Jacobi、G-S、SORq Jacobi 迭代迭代(1)1( )1()kkxDLU xD b 1(1)( )( )11inkkkiiijjijjiijj ixba xa xa q SOR 迭代迭代 11(1)( )(1)kkxDLDU xDLb 1(1)( )(1)( )1inkkkkiiiijjijjiijj ixxba xa xa 11, (1)MDLNDUq G-S 迭代迭代 11(1)( )kkxDLUxDLb 1(1)(1)( )11inkkkiiijjijjiijj ixba xa xa , MDLNU , MDNLU 10举例举例例例：分别用

7、分别用 Jacobi、G-S、SOR 迭代解线性方程组迭代解线性方程组123210113180125xxx 取初始向量取初始向量 x(0) = ( 0, 0, 0 )，迭代过程中小数点后保留，迭代过程中小数点后保留 4 位。位。解：解：Jacobi 迭代：迭代： (1)( )12(1)( )( )213(1)( )32128352kkkkkkkxxxxxxx 迭代可得：迭代可得： x(1) = ( 0.5000, 2.6667, -2.5000 )Tx(21) = ( 2.0000, 3.0000, -1.0000 )T2*31x 11举例举例G-S 迭代：迭代： (1)( )12(1)(1)

8、( )213(1)(1)32128352kkkkkkkxxxxxxx x(1) = ( 0.5000, 2.8333, -1.0833 )Tx(9) = ( 2.0000, 3.0000, -1.0000 )T迭代可得：迭代可得： 12举例举例SOR 迭代：迭代： (1)( )( )( )1112(1)( )(1)( )( )22123(1)( )(1)( )3323122833522kkkkkkkkkkkkkxxxxxxxxxxxxx 取取 = 1.1，迭代可得，迭代可得x(1) = ( 0.5500, 3.1350, -1.0257 )Tx(7) = ( 2.0000, 3.0000, -

9、1.0000 )T如何确定如何确定 SOR 迭代中的最优松弛因子是一件迭代中的最优松弛因子是一件很困难很困难的事的事13l Jacobi 迭代收敛的迭代收敛的充要充要条件条件 (J)1l G-S 迭代收敛的迭代收敛的充要充要条件条件 (G)1l SOR 迭代收敛的迭代收敛的充要充要条件条件 (L )1收敛性收敛性收敛性定理收敛性定理l Jacobi 迭代收敛的迭代收敛的充分充分条件条件 |J| 1l G-S 迭代收敛的迭代收敛的充分充分条件条件 |G| 1l SOR 迭代收敛的迭代收敛的充分充分条件条件 |L | 114对角占优矩阵对角占优矩阵且且至少有一个至少有一个不等式严格成立，则称不等式

10、严格成立，则称 A 为为 弱对角占优弱对角占优；若若所有不等式所有不等式都严格成立，则称都严格成立，则称 A 为为 严格对角占优严格对角占优。( i = 1, 2, . , n )定义定义：设设 A Rn n，若，若1, |niiijjj iaa 15可约与不可约可约与不可约定义定义：设设 A Rn n，若存在排列矩阵，若存在排列矩阵 P 使得使得 则称则称 A 为为 可约矩阵可约矩阵；否则称为否则称为 不可约矩阵不可约矩阵 。111222,0TAAP APA () ()1122, 11r rn rn rARARrn l 如果如果 A 是可约矩阵，则方程组是可约矩阵，则方程组 Ax = b 等

11、价于等价于 TTTP APP xP b 11112212222 A yA yfA yf y即可以把原方程组化成两个即可以把原方程组化成两个低阶低阶的方程组来处理。的方程组来处理。f16Jacobi、G-S 收敛性收敛性定理定理：若若 A 严格对角占优严格对角占优或或不可约弱对角占优不可约弱对角占优，则，则 A 非奇异非奇异定理定理：若若 A 严格对角占优严格对角占优或或不可约弱对角占优不可约弱对角占优，则，则 Jacobi 迭迭代和代和 G-S 迭代均收敛迭代均收敛 定理定理：若若 A 对称，且对角线元素均大于对称，且对角线元素均大于 0，则，则Jacobi 迭代收敛的充要条件是迭代收敛的充要

12、条件是 A 与与 2D-A 均正定；均正定；(1) G-S 迭代收敛的充要条件是迭代收敛的充要条件是 A 正定。正定。17SOR 收敛性收敛性定理定理：若若 SOR 迭代收敛，则迭代收敛，则 0 2。l SOR 收敛的必要条件收敛的必要条件定理定理：若若 A 对称正定，且对称正定，且 0 2，则则 SOR 迭代收敛。迭代收敛。l SOR 收敛的充分条件收敛的充分条件定理定理：若若 A 严格对角占优或不可约弱对角占优，且严格对角占优或不可约弱对角占优，且 0 1，则则 SOR 迭代收敛。迭代收敛。18举例举例例例：设设 ，给出，给出 Jacobi 和和 G-S 收敛的充要条件收敛的充要条件 111aaAaaaa 解：解：A 对称，且对角线元素均大于对称，且对角线元素均大于 0，故，故 (1) Jacobi 收敛的充要条件是收敛的充要条件是 A 和和 2D-A 均正定均正定(2) G-S 收敛的充要条件是收敛的充要条件是 A 正定正定A 正定正定2212310,10,(1) (12 )0DDaDaa 0.51a 2D-A 正定正定2212310,10,(1) (12 )0DDaDaa 0.50.5aJacobi 收敛的充要条件是：收敛的充要条件是：-0.5a0.5G-S 收敛的充要条件是：收敛的充要条件是：-0.5a119举