1
计 算 方 法
第八章 线性方程组的解法
计算方法课程组
2
§ 引 言
重要性：解线性代数方程组的有效方法在计算数学和
科学计算中具有特殊的地位和作用。如弹性力学、电
路分析、热传导和振动、以及社会科学及定量分析商
业经济中的各种问题。
求解线性方程组 的求解方法，其中
， 。
假设 非奇异，则方程组有唯一解.
3
§ 引 言
分类： 线性方程组的解法可分为直接法和迭代法两种方法。
(a) 直接法： 对于给定的方程组，在没有舍入误差的假设下，
能在预定的运算次数内求得精确解。最基本的直接法是
Gauss消去法，重要的直接法全都受到Gauss消去法的启发。
计算代价高.
(b) 迭代法：基于一定的递推格式，产生逼近方程组精确解的
近似序列.收敛性是其为迭代法的前提，此外，存在收敛速
度与误差估计问题。简单实用, 诱人。
4
§ 雅可比Jacobi迭代法 (AX=b)
一、迭代法的基本思想
二、例题分析
三、 Jacobi迭代公式
5
与解f (x)=0 的不动点迭代相类似，将AX=b改写
为X=BX+f 的形式，建立雅可比方法的迭代格式：
其中，B称为迭代矩阵。其计算精度可控，特别
适用于求解系数为大型稀疏矩阵(sparse matrices)
的方程组。
§ 雅可比Jacobi迭代法 (AX=b)
迭代法的基本思想
6
问题:
(a) 如何建立迭代格式？
(b) 向量序列{ x(k) }是否收敛以及收敛条件?
7
2 例题分析:
其准确解为X*={ , , }。
考虑解方程组
(1)
迭代法
8
2 例题分析:
建立与式(1)相等价的形式：
(2)
其准确解为X*={, , }。
考虑解方程组
(1)
迭代法
9
2 例题分析:
其准确解为X*={, , }。
建立与式(1)相等价的形式：考虑解方程组
取迭代初值
据此建立迭代公式：
10
迭代结果如下表：
迭 代 次 数 x 1 x 2 x 3
0 0 0 0
1 0 . 7 2 0 . 8 3 0 . 8 4
2 0 . 9 7 1 1 . 0 7 1 . 1 5
3 1 . 0 5 7 1 . 1 5 7 1 1 . 2 4 8 2
4 1 . 0 8 5 3 5 1 . 1 8 5 3 4 1 . 2 8 2 8 2
5 1 . 0 9 5 0 9 8 1 . 1 9 5 0 9 9 1 . 2 9 4 1 3 8
6 1 . 0 9 8 3 3 8 1 . 1 9 8 3 3 7 1 . 2 9 8 0 3 9
7 1 . 0 9 9 4 4 2 1 . 1 9 9 4 4 2 1 . 2 9 9 3 3 5
8 1 . 0 9 9 8 1 1 1 . 1 9 9 8 1 1 1 . 2 9 9 7 7 7
9 1 . 0 9 9 9 3 6 1 . 1 9 9 9 3 6 1 . 2 9 9 9 2 4
1 0 1 . 0 9 9 9 7 9 1 . 1 9 9 9 7 9 1 . 2 9 9 9 7 5
1 1 1 . 0 9 9 9 9 3 1 . 1 9 9 9 9 3 1 . 2 9 9 9 9 1
1 2 1 . 0 9 9 9 9 8 1 . 1 9 9 9 9 8 1 . 2 9 9 9 9 7
1 3 1 . 0 9 9 9 9 9 1 . 1 9 9 9 9 9 1 . 2 9 9 9 9 9
1 4 1 . 1 1 . 2 1 . 3
1 5 1 . 1 1 . 2 1 . 3
11
设方程组 AX=b , 通过分离变量的过程建立
Jacobi迭代公式，即
由此我们可以得到 Jacobi 迭代公式：
§ Jacobi迭代公式
12
雅可比迭代法的矩阵表示
写成矩阵形式：
A =
L U
D
B
Jacobi 迭代阵
13
§ 高斯-塞德尔迭代法 (AX=b)
注意到利用Jacobi迭代公式计算 时，已经计算好了
的值，而Jacobi迭代公式并不利用这些最新的近似值计算，
仍用
这启发我们可以对其加以改进,即在每个分量的计算中尽量
利用最新的迭代值，得到
上式称为 Gauss-Seidel 迭代法.
14
… … … …
写成矩阵形式：
BGauss-Seidel
迭代阵
§ 高斯-塞德尔迭代法
15
其准确解为X*={, , }。
考虑解方程组
高斯-塞德尔迭代法算例
高斯-塞德尔迭代格式
16
迭代次数 x1 x2 x3
0 0 0 0
1
2
3
4
5
6
7
8
17
开始
T
F
T
F
T
18
逐次超松弛迭代法(Successive Over Relaxation
Method，简写为SOR)可以看作带参数ω的高斯-塞德
尔迭代法，是 G-S 方法的一种修正或加速，是求解大
型稀疏矩阵方程组的有效方法之一。
§ 超松驰迭代法SOR方法
1. SOR基本思想
19
设方程组AX=b, 其中，A=(aij) 为非奇异阵，
x=(x1, x2, …, xn)T, b=(b1, b2, …, bn)T.
假设已算出 x(k) ，
§ 超松驰迭代法SOR方法
2. SOR算法的构造
ω称为松弛因子
利用高斯-塞德尔迭代法得:
20
§ 超松驰迭代法SOR方法
2. SOR算法的构造 (基于G-S迭代)
解方程组AX=b的逐次超松弛迭代公式：
显然，当取ω=1时，上式就是高斯-塞德尔迭代公式.
21
§ 超松驰迭代法SOR方法
2. SOR算法的构造(基于Jacobi迭代)
得到解方程组 AX=b 的逐次超松弛迭代公式：
显然，上式就是 基于Jacobi 迭代的 SOR 方法.
22
下面令 ，
希望通过选取合适的
来加速收敛，这就是松弛法 。
3. SOR算法的进一步解释
SOR方法
其中ri(k+1) =
相当于在 的基础上加个余项生成 。
0 < < 1 低松弛法
= 1 Gauss - Seidel 法
2> > 1 (渐次)超松弛法
23
利用SOR方法解方程组
SOR例题分析:
其准确解为x*={1, 1, 2}.
建立与式(1)相等价的形式：
24
据此建立G-S迭代公式：
取迭代初值
:
,ω=,迭代结果如下表.
SOR迭代公式为：
25
GS迭代法须迭代85次得到准确值 x*={1, 1, 2};而
SOR方法只须55次即得准确值.
由此可见，适当地选择松弛因子ω，SOR法具有明显的
加速收敛效果.
逐次超松弛迭代法
次数 x1 x2 x3
1
2
3
4
5
… … … …
15
… … … …
25
… … … …
55
26
关于SOR方法的说明：
(1) 显然，当 时，SOR方法就是Gauss- Seidel方法。
(2) SOR 方法每一次迭代的主要运算量是计算一次矩阵与向量
的乘法。
(3) 时称为超松弛方法， 时称为低松弛方法。
(4) 计算机实现时可用
控制迭代终止，或用
(5) SOR方法可以看成是Gauss-Seidel方法的一种修正。
27
（迭代法基本定理）
设有方程组 ，对于任意的初始向
量 ，迭代公式 收敛的充要条件是迭
代矩阵 的谱半径 .
迭代法的收敛性-充要条件
迭代法的基本定理在理论分析中有重要意义。
28
定理2：设X*是方程组AX = b的同解方程X = BX + F
的准确解，若迭代公式中迭代矩阵B的某种范数，
(1)
(2)
则有
在具体使用上，由于 ，因此，我们利
用范数可以建立判别迭代法收敛的充分条件。
29
关于解某些特殊方程组迭代法的收敛性
定义：(对角占优阵) 设
(1) 如果 元素满足
称 为严格对角占优阵
(2) 如果 元素满足
且上式至少有一个不等式严格成立，
称 为弱对角占优阵。
30
设 ，如果：
为严格对角占优，则解 的Jacobi迭代法，
Gauss-Seidel迭代法均收敛。
31
32
Seidel迭代格式为
从式中解出
故可得Seidel迭代矩阵为
从例中可以看出Jacobi迭代矩阵Bj的主对角线为零，而Seidel迭代矩阵
Bs的第1列都是零，这对一般情况也是成立的。
33
举例检验Jacoai迭代的收敛性
首先将原方程组写为迭代形式的方程组，即：
求任一行之和的最大值<1,即：
||M||=max{5/8,5/11,9/12}=9/12<1i
或求任一列之和的最大值<1,即：
||M||1=max{114/132,60/96,30/88}=114/132<1
结论：该方程组采用Jacobi迭代法计算是收敛的。
已知线性方程组为：
34
§ 迭代法的误差估计
定理4：设X*是方程组AX = b的同解方程X = BX + F
的准确解，若迭代公式中迭代矩阵B的某种范数，
(1)
(2)
则有
