3e基本的矩阵迭代法

1 第三章线性方程组的迭代解法计 算 方 法 基本的矩阵分裂迭代法 2 本讲内容l Jacobi 迭代算法l G auss-Seidel 迭代算法l SOR 迭代算法l 收敛性分析n 矩阵分裂迭代法的典型代表 3 Jacobi 迭代考虑线性方程组Ax = b其中 A=(aij)nn 非奇异，且对角线元素全不为 0。 11 22diag( , , , )nnD a a a 211 , 10 0 ,0n n naL a a l 将 A 分裂成 A = D - L- U， 其中12 11,0 0 0 nn na aU a 4 Jacobi 迭代( 1) 1 ( ) 1( )k kx D L U x D b k = 0, 1, 2, 令 M = D，N = L + U，可得 雅可比 (Jacobi) 迭代方法 Jacobi 迭代l 迭代矩阵记为： 1( )J D L U l 分量形式：1( 1) 1 1i nki i ij j ij j iij j ix b a x a x a i = 1, 2, , n， k = 0, 1, 2, 5 6 G auss-Seidel 迭代l 在计算 时，如果用 代替 ，则可能会得到更好的收敛效果。 ( 1)kix ( 1) ( 1)1 1, ,k kix x ( ) ( )1 1, ,k kix x ( 1) ( ) ( ) ( )1 1 12 2 13 3 1 11( 1) ( ) ( ) ( )2 2 21 1 23 3 2 22( 1) ( ) ( ) ( )1 1 2 2 , 1 1 k k k kn nk k k kn nk k k kn n n n n n n nnx b a x a x a x ax b a x a x a x ax b a x a x a x a ( 1) ( ) ( ) ( )1 1 12 2 13 3 1 11( 1) ( 1) ( ) ( )2 2 21 1 23 3 2 22 ( 1) ( 1) ( 1) ( 1)1 1 2 2 , 1 1 k k k kn nk k k kn nk k k kn n n n n n n nnx b a x a x a x ax b a x a x a x ax b a x a x a x a 7 G auss-Seidel 迭代 ( 1) 1 ( 1) ( )k k kx D b Lx Ux 写成矩阵形式:此迭代方法称为 高斯-塞德尔 (G auss-Seidel) 迭代法k = 0, 1, 2, 1 1( 1) ( )k kx D L Ux D L b 可得 1G D L U l 迭代矩阵记为： 8 SOR 迭代l 为了得到更好的收敛效果，可在修正项前乘以一个 松弛因子，于是可得迭代格式在 G -S 迭代中 ( 1) ( 1) ( 1) ( ) ( )1 1 , 1 1 , 1 1 ,k k k k ki i i i i i i i i i n n iix b a x a x a x a x a 1 ( 1) ( ) 1( ) i nk ki ij j ij j iij j iki b a x a x ax ( 1) 1 ( 1) () 1( )i nk ki ij j ij j iijki i j ik b a x a ax x x 9 SOR 迭代 ( 1) ( ) 1 ( 1) ( ) ( )k k k k kx x D b Lx Ux Dx 1 1 ( 1) ( )(1 )k kx D L D U x D L b 写成矩阵形式:可得 SOR (Successive Over-Relaxation) 迭代方法 1 (1 )L D L D U l 迭代矩阵记为：l SOR 的优点：通过选取合适的 ，可获得更快的收敛速度l SOR 的缺点：最优参数 的选取比较困难 10 Jacobi、G -S、SORq Jacobi 迭代( 1) 1 ( ) 1( )k kx D L U x D b 1( 1) ( ) ( )1 1i nk k ki i ij j ij j iij j ix b a x a x a q SOR 迭代 1 1( 1) ( )(1 )k kx D L D U x D L b 1( 1) ( ) ( 1) ( )1i nk k k ki i i ij j ij j iij j ix x b a x a x a 1 1, (1 )M D L N D U q G -S 迭代 1 1( 1) ( )k kx D L Ux D L b 1( 1) ( 1) ( )1 1i nk k ki i ij j ij j iij j ix b a x a x a , M D L N U , M D N L U 11 举例例：分别用 Jacobi、G -S、SOR 迭代解线性方程组1232 1 0 11 3 1 80 1 2 5xxx 取初始向量 x(0) = ( 0, 0, 0 )，迭代过程中小数点后保留 4 位。解：Jacobi 迭代： ( 1) ( )1 2( 1) ( ) ( )2 1 3( 1) ( )3 21 28 35 2k kk k kk kx xx x xx x 迭代可得： x(1) = ( 0.5000, 2.6667, -2.5000 )Tx(21) = ( 2.0000, 3.0000, -1.0000 )T 2* 31x 12 举例G -S 迭代： ( 1) ( )1 2( 1) ( 1) ( )2 1 3( 1) ( 1)3 21 28 35 2k kk k kk kx xx x xx x x(1) = ( 0.5000, 2.8333, -1.0833 )Tx (9) = ( 2.0000, 3.0000, -1.0000 )T迭代可得： 13 举例SOR 迭代： ( 1) ( ) ( ) ( )1 1 1 2( 1) ( ) ( 1) ( ) ( )2 2 1 2 3( 1) ( ) ( 1) ( )3 3 2 31 2 28 3 35 2 2k k k kk k k k kk k k kx x x xx x x x xx x x x 取 = 1.1，迭代可得x(1) = ( 0.5500, 3.1350, -1.0257 )Tx (7) = ( 2.0000, 3.0000, -1.0000 )T如何确定 SOR 迭代中的最优松弛因子是一件很困难的事 14 15 收敛性分析( 1) ( )k kx Bx f 定理：对任意初始向量 x(0)，上述迭代格式收敛的充要条件是( ) 1B 定理：若存在算子范数 | |，使得 |B| 1，对任意的初始向量 x (0)，上述迭代格式收敛。 16 l Jacobi 迭代收敛的充要条件 (J)1l G -S 迭代收敛的充要条件 (G)1l SOR 迭代收敛的充要条件 (L)1收敛性(A) A 收敛性定理l Jacobi 迭代收敛的充分条件 |J| 1l G -S 迭代收敛的充分条件 |G| 1l SOR 迭代收敛的充分条件 |L| 1谱半径1(A) m ax ii n 17 18 收敛性分析( 1) ( )k kx Bx f B = M-1N定理：若存在算子范数 | |，使得 |B| = q 1，则证明：P112 ( ) (0)k kx x q x x (1)迭代法收敛(2) (3) (4) ( ) ( ) ( 1)1k k kqx x x xq ( ) (1) (0)1 kk qx x x xq 19 系数矩阵法-对角占优矩阵且至少有一个不等式严格成立，则称 A 为 弱对角占优；若所有不等式都严格成立，则称 A 为 严格对角占优。( i = 1, 2, . , n )定义：设 ARnn，若1, | | | |nii ijj j ia a 20 Jacobi、G -S 收敛性引理3-2：若 A 严格对角占优，则 A 非奇异定理3-25：若 A 严格对角占优，则 Jacobi 迭代和 G -S 迭代均收敛 定理：若 A 对称，且对角线元素均大于 0，则(1) Jacobi 迭代收敛的充要条件是 A 与 2D-A 均正定；(2) G -S 迭代收敛的充要条件是 A 正定。 21 SOR 收敛性定理：若 SOR 迭代收敛，则 0 2。l SOR 收敛的必要条件定理：若 A 对称正定，且 0 2，则 SOR 迭代收敛。l SOR 收敛的充分条件定理：若 A 严格对角占优，且 0 1，则 SOR 迭代收敛。 22 举例例：设 ，给出 Jacobi 和 G -S 收敛的充要条件 1 1 1a aA a aa a 解：A 对称，且对角线元素均大于 0，故 (1) Jacobi 收敛的充要条件是 A 和 2D-A 均正定(2) G -S 收敛的充要条件是 A 正定A 正定 2 21 2 31 0, 1 0, (1 ) (1 2 ) 0D D a D a a 0.5 1a 2D-A 正定2 21 2 31 0, 1 0, (1 ) (1 2 ) 0D D a D a a 0.5 0.5a Jacobi 收敛的充要条件是：-0.5a0.5G -S 收敛的充要条件是：-0.5a1 23 举例解法二：Jacobi 的迭代矩阵为设 是 J 的特征值，则由 det(I - J) = 0 可得1 1 1a aJ a aa a ( - a)2 ( +2a) = 0Jacobi 收敛的充要条件是 (J)1 |1，即 -0.5a0.5 24 作业1. 教材 页，习题 2. 教材 页，习题