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

第六章线性方程组的迭代解法 本讲内容 Jacobi 迭代 Jacobi 迭代 Gauss-Seidel 迭代 Gauss-Seidel 迭代 SOR 迭代 SOR 迭代 Jacobi、G-S、SOR 举例 举例 举例 收敛性 对角占优矩阵 可约与不可约 Jacobi、G-S 收敛性 SOR 收敛性 举例 举例 作业 * * 计算方法 —— 基本的矩阵分裂迭代法 Jacobi 迭代算法 Gauss-Seidel 迭代算法 SOR 迭代算法 收敛性分析 矩阵分裂迭代法的典型代表 考虑线性方程组 Ax = b 其中 A=(aij)n?n 非奇异，且对角线元素全不为 0。 将 A 分裂成 A = D - L- U， 其中 k = 0, 1, 2, … 令 M = D，N = L + U，可得 雅可比 (Jacobi) 迭代方法 Jacobi 迭代 迭代矩阵记为： 分量形式： i = 1, 2, … , n， k = 0, 1, 2, … 在计算 时，如果用 代替 ，则可能会得到更好的收敛效果。 写成矩阵形式: 此迭代方法称为 高斯-塞德尔 (Gauss-Seidel) 迭代法 k = 0, 1, 2, … 可得 迭代矩阵记为： 为了得到更好的收敛效果，可在修正项前乘以一个 松弛因子?，于是可得迭代格式 在 G-S 迭代中 写成矩阵形式: 可得 —— SOR (Successive Over-Relaxation) 迭代方法 迭代矩阵记为： SOR 的优点：通过选取合适的 ?，可获得更快的收敛速度 SOR 的缺点：最优参数 ? 的选取比较困难 Jacobi 迭代 SOR 迭代 G-S 迭代 例：分别用 Jacobi、G-S、SOR 迭代解线性方程组 取初始向量 x(0) = ( 0, 0, 0 )，迭代过程中小数点后保留 4 位。 解： Jacobi 迭代： 迭代可得： x(1) = ( 0.5000, 2.6667, -2.5000 )T x(21) = ( 2.0000, 3.0000, -1.0000 )T G-S 迭代： x(1) = ( 0.5000, 2.8333, -1.0833 )T x(9) = ( 2.0000, 3.0000, -1.0000 )T 迭代可得： SOR 迭代： 取 ? = 1.1，迭代可得 x(1) = ( 0.5500, 3.1350, -1.0257 )T x(7) = ( 2.0000, 3.0000, -1.0000 )T 如何确定 SOR 迭代中的最优松弛因子是一件很困难的事 Jacobi 迭代收敛的充要条件 ?(J)1 G-S 迭代收敛的充要条件 ?(G)1 SOR 迭代收敛的充要条件 ?(L?)1 收敛性定理 Jacobi 迭代收敛的充分条件 ||J|| 1 G-S 迭代收敛的充分条件 ||G|| 1 SOR 迭代收敛的充分条件 ||L?|| 1 且至少有一个不等式严格成立，则称 A 为 弱对角占优； 若所有不等式都严格成立，则称 A 为 严格对角占优。 ( i = 1, 2, ... , n ) 定义：设 A?Rn?n，若 定义：设 A?Rn?n，若存在排列矩阵 P 使得 则称 A 为 可约矩阵；否则称为 不可约矩阵 。 如果 A 是可约矩阵，则方程组 Ax = b 等价于 y 即可以把原方程组化成两个低阶的方程组来处理。 f 定理：若 A 严格对角占优或不可约弱对角占优，则 A 非奇异 定理：若 A 严格对角占优或不可约弱对角占优，则 Jacobi 迭代和 G-S 迭代均收敛 定理：若 A 对称，且对角线元素均大于 0，则 Jacobi 迭代收敛的充要条件是 A 与 2D-A 均正定； G-S 迭代收敛的充要条件是 A 正定。 定理：若 SOR 迭代收敛，则 0 ? 2。 SOR 收敛的必要条件 定理：若 A 对称正定，且 0 ? 2，则 SOR 迭代收敛。 SOR 收敛的充分条件 定理：若 A 严格对角占优或不可约弱对角占优，且 0 ? ? 1，则 SOR 迭代收敛。 例：设 ，给出 Jacobi 和 G-S 收敛的充要条件 解： A 对称，且对角线元素均大于 0，故 (1) Jacobi 收敛的充要条件是 A 和 2D-A 均正定 (2) G-S 收敛的充要条件是 A 正定 A 正定 2D-A 正定 Jacobi 收敛的充要条件是：-0.5a0.5 G-S 收敛的充要条件是：-0.5a1 解法二： Jacobi 的迭代矩阵为 设 ? 是