第六章 线性方程组的迭代法 — Jacobi, G-S and SOR.

Presentation on theme: "第六章 线性方程组的迭代法 — Jacobi, G-S and SOR."— Presentation transcript:

1 第六章 线性方程组的迭代法 — Jacobi, G-S and SOR

2 本讲内容 几类基本迭代法 Jacobi 迭代法 Gauss-Seidel 迭代法 SOR（超松弛）迭代法 迭代法收敛性分析

3 Jacobi, G-S, SOR

4 Ax = b Jacobi 迭代 Jacobi 迭代法 考虑线性方程组 其中 A=[aij]nn 非奇异，且对角线元素全不为 0
将 A 分裂成 A = D - L- U， 其中

5 Jacobi 迭代 Jacobi 迭代法 取 M = D，N = L + U，可得 雅可比 (Jacobi) 迭代方法 迭代矩阵记为：
k = 0, 1, 2, … 迭代矩阵记为： 分量形式： i = 1, 2, … , n， k = 0, 1, 2, …

6 Gauss-Seidel 迭代 在计算 时，如果用 代替 ，则可能会得到更好的收敛效果。

7 Gauss-Seidel 迭代 Gauss-Seidel 迭代 写成矩阵形式: 可得
k = 0, 1, 2, … 此迭代方法称为 高斯-塞德尔 (Gauss-Seidel) 迭代法 迭代矩阵记为：

8 SOR 迭代 G-S 迭代法的分量形式 为了得到更好的收敛效果，可在修正项前乘以一个 松弛因子，于是可得迭代格式

9 SOR 迭代 SOR 迭代 写成矩阵形式: 可得 —— SOR (Successive Over-Relaxation) 迭代方法
迭代矩阵记为： SOR 的优点：通过选取合适的 ，可获得更快的收敛速度 SOR 的缺点：最优参数  的选取比较困难

10 Jacobi 迭代 Jacobi、G-S、SOR G-S 迭代 SOR 迭代

11 举例 例：分别用 Jacobi、G-S、SOR( = 1.1) 迭代解线性方程组 解：
取初始向量 x(0) = [0, 0, 0]T，迭代过程中小数点后保留 4 位。 解： Jacobi 迭代： 计算可得： x(1) = [ , , ]T x(21) = [ , , ]T

12 举例 G-S 迭代： 迭代可得： x(1) = [ 0.5000, 2.8333, -1.0833 ]T

13 举例 如何确定 SOR 的最优松弛因子是一件非常困难的事！ SOR 迭代： 取  = 1.1，迭代可得
x(1) = [ , , ]T x(7) = [ , , ]T 如何确定 SOR 的最优松弛因子是一件非常困难的事！

14 举例 例：(编程实践) 分别用 Jacobi、G-S、SOR( = 1.5) 迭代解线性方程组
取初始向量 x(0) = [0, 0, 0]T。 ex62.m

15 迭代方法的收敛性 对角占优、不可约矩阵 对称正定矩阵 Jacobi 迭代收敛的充要条件 (J)<1
G-S 迭代收敛的充要条件 (G)<1 SOR 迭代收敛的充要条件 (L)<1 Jacobi 迭代收敛的充分条件 ||J|| <1 G-S 迭代收敛的充分条件 ||G|| < 1 SOR 迭代收敛的充分条件 ||L|| < 1 对角占优、不可约矩阵 对称正定矩阵

16 对角占优矩阵 定义：设 ARnn，若 ( i = 1, 2, ... , n ) 且至少有一个不等式严格成立，则称 A 为 弱对角占优；

17 可约矩阵与不可约矩阵 定义：设 ARnn，若存在置换矩阵 P 使得 y f 则称 A 为 可约矩阵；否则称为 不可约矩阵 。
如果 A 是可约矩阵，则方程组 Ax = b 等价于 y 即可以把原方程组化成两个低阶的方程组来处理。 f

18 可约矩阵的几个简单判别方法 性质：设 ARnn，若 A 的所有元素都非零，则 A 不可约。
性质：设 ARnn，且 n2。若 A 可约，则 A 的零元素个数大于等于 n-1。 性质：设 ARnn 是三对角矩阵，且三条对角线元素均非零，则 A 不可约。 思考：如 A 是三对角矩阵，上、下次对角线元素均非零，则 A 是不是不可约？

19 Jacobi、G-S 收敛性 对角占优情形 定理：若 A 严格对角占优或不可约弱对角占优，则 A 非奇异
证明：仅证明严格对角占优情形 定理：若 A 严格对角占优或不可约弱对角占优，则 Jacobi 迭代和 G-S 迭代均收敛 证明：板书

20 Jacobi、G-S 收敛性 对称正定情形 定理：设 A 对称且 D 正定，则 Jacobi 迭代收敛的充要条件是
A 和 2DA 都正定。 证明：略 定理：设 A 对称且 D 正定，则 G-S 迭代收敛的充要条件是 A 正定。 证明：略

21 SOR 收敛性 SOR 收敛的必要条件 定理：若 SOR 迭代收敛，则 0 <  < 2。 SOR 收敛的充分条件
证明：板书 SOR 收敛的充分条件 定理：若 A 对称正定，且 0 <  < 2，则 SOR 迭代收敛。 证明：板书 定理：若 A 严格对角占优或不可约弱对角占优，且 0 <   1，则 SOR 迭代收敛。 证明：略

22 收敛性小结 A 对称且对角线元素为正，则 Jacobi 迭代收敛 A 正定且 2D-A正定 G-S 迭代收敛 A 正定
A 对称正定，则 SOR 迭代收敛 <  < 2 A 严格对角占优或不可约弱对角占优 Jacobi 和 Gauss-Seidel 迭代收敛 A 严格对角占优或不可约弱对角占优且 0 <   1 SOR 迭代收敛

23 举例 例：设 ，给出 Jacobi 和 G-S 收敛的充要条件 解： A 对称，且对角线元素均大于 0，故
(1) Jacobi 收敛的充要条件是 A 和 2D-A 均正定 (2) G-S 收敛的充要条件是 A 正定 A 正定 2D-A 正定 Jacobi 收敛的充要条件是：-0.5<a<0.5 G-S 收敛的充要条件是：-0.5<a<1

24 举例 解法二： Jacobi 的迭代矩阵为 设  是 J 的特征值，则由 det(I - J) = 0 可得
(  - a)2 (  +2a) = 0 Jacobi 收敛的充要条件是 (J)<1  ||<1， 即 -0.5<a<0.5

25 补：算法的实施 停机准则 ： 算法 ：Jacobi （G-S 和 SOR 的实施类似） 给定初值 x(0) 和精度要求 tol 计算
(3) 对 k = 0, 1, 2, ... , 计算 ，i = 1, 2, ..., n 若 ，则输出 x  x(k+1) ，停止计算。

26 作业 1. 教材第 209 页：1(1)，2，3，4 2. 已知线性方程组如下，写出 Jacobi，Gauss-Seidel 和 SOR（=1.5） 方法的分量格式，并判断这三个方法的收敛性 注： 第 1 题, 系数矩阵改为 第 2(1)、2(2) 题中的系数矩阵分别改为 和 第 4 题中的系数矩阵分别改为