第3章 线性方程组的解法
1
3.1 问题综述
在自然科学与社会科学的研究中，常常需要求解线性代数方程组，这些方 程组的系数矩阵大致分为两种：一种是低阶稠密矩阵（例如：阶数大约为小 于等于150），另一种是大型稀疏矩阵（即矩阵阶数高且零元素较多）。
在计算机上求解线性代数方程组 AX=B 的常用的数值解法： • 1、直接法：就是经过有限次算术运算，可求得方程组精确解的方 法（若计算过程中没有舍入误差）。但实际计算中由于舍入误差的存在 和影响，这种方法也只能求得线性方程组的近似解。
A =LU,
其中，L 是下三角矩阵，U 是上三角矩阵.
这时解方程组 Ax=b， 可化为求解两个三角方程组
Ly =b, Ux =y .
先由 Ly =b 解出向量 y，再由 Ux =y 解出向量 x， 则 x
是原方程组 Ax=b 的解向量。
27
对于
Ly =b
1
由
l21
1
l31
l32
1
y1 b1
1.消元过程
对于k =1,2,…,n -1执行
(1)选行号ik，使
a(k) ik k
max
k in
a(k) ik
.
(2)交换第 k 行与第 ik 行。
21
(3)对于 i = k +1,k +2,…,n 计算
mik
a(k ik
)
/
a(k kk
)
a(k 1) ij
a(k) ij
mik
a(k kj
)
( j k 1, k 2,..., n)
Gauss消去法是一个古老的求解线性代数方程组的方法（早 在公元前250年我国就掌握了解三元一次联立方程组的方法）。 但由于它改进、变形得到的主元素消去法、三角分解法仍然是目 前计算机上常用的有效方法。
高斯消去法步骤： (1) 首先将增广阵 [ A, b ] 化为上三角阵； (2) 用三角方程组，回代求解 。
Gauss消去法求解。
18
写出原方程组的增广矩阵：
0.0120 0.0100 0.1670 0.6781
1.000
0.8334 5.910
12.10
3200 1200 4.200 981.0
针对第一列找出绝对值最大的元素，进行等价变换：
3200 1200 4.200 981.0
1.000
/*
精确解为
x1
1
1 109
8个
1.00...0100...和
x2
2
x1
8个
0.99 ...9899...*/
用顺序主元素消去法计算：
m21 a21 / a11 1098个 a22 1 m21 1 0.0 ...01109 109 109 b2 2 m21 1 109
109 1
b(k 1) i
bi(k )
mikbk(k )
2.回代过程
xn
b(n) n
/
a(n) nn
xk
bk(
k
)
n
a(k) kj
x
j
/
a(k) kk
(k n 1, n 2,...,1)
jk 1
22
评论：列主元素消去法，所需条件较少，仅
仅要求方程组的系数矩阵 A 非奇异。 而且，对一般的方程组，它还具有良好的数
A(n) Ln1 A(n1) Ln1Ln2 A(n2) Ln1Ln2 L2 L1 A 24
这时
A L11 L21
L A 1 (n) n1
令
L L11 L21
L1 n1
,
U A(n)
容易验证
1
l
21
1
L
L11 L21
L1 n1
l
31
l32
1
ln1 ln2 lnn1 1
11.79
0.5329
求得方程的解为：x3＝5.546，x2＝－45.76，x1＝17.46
精确解为： x3＝5.546 ，x2＝－45.76， x1＝17.46
由此可见，第二种Gauss消去法的精度明显高于顺序Gauss消去法，我 们称它为列主元Gauss消去法。
列主元Gauss消去法与顺序Gauss消去法的不同之处在于：
x3＝5.546 ，x2＝－45.76， x1＝17.46 有较大的误差。
对于此例，由于顺序Gauss消去法中的主元素绝对值非常小，使 消元乘数绝对值非常大，计算过程中出现大数吃掉小数现象，产生
较大的舍入误差，最终导致计算解 x1＝－104.0 和 x2＝100.0 已完全 失真。
为避免这种现象发生，可以对原方程组作等价变换，再利用顺序
5
用一个简单的例子说明消去法的基本思想。
例1 用消去法解方程组
x1 x2 x3 6
(1)
4x2 x3 5
(2)
2x1 2x2 x3 1
(3)
6
解 (1) 化上三角方程组
x1 x2 x3 6
①
4x2 x3 5
②
③+(-2)×① 2x1 2x2 x3 1
③
x1 x2 x3 6
0.1670
0.6781
0
0.1000 103
8.010
44.41
0
1467 445410 1798102
0.0120
0
0
0.0100 0.1000 103
0
0.1670 8.010 1175 105
0.6781
44.41
6517 105
17
经回代求解得
x3＝5.546，x2＝100.0，x1＝－104.0 和此方程组的精确解相比
顺序高斯消去法求解n 元线性方程组的乘除运算总次数为：
(n3 3n2 n) / 3
➢顺序高斯消去法计算过程中出现的
a
(k kk
称) 为主元素.
出现
a(k ) kk
，0消元过程就进行不下去了。
12
定理: 顺序高斯消去法的前
n
-1
个主元素
a(k kk
)均
不为零的充要条件是方程组的系数矩阵A的前n -
x3 (6) / (2) 3
用x3, x2的值求x1 把x3的值代入②求x2
8
从下向上逐步求解
对应的增广矩阵的变化
1 1 1 6 1 1 1 6
( A | b) 0
4
1 5 0
4
1
5
2 2 1 1 0 4 1 11
1 1 1 6 041 Nhomakorabea5
0 0 2 6
(-2)×r1 + r3→r3
a1n b1
a2n
b2
M M
ann
bn
用行变换
a01(11)
a (1) 12
a(2) 22
0 0
a (1) 1n
a(2) 2n
b(1) 1
b(2) 2
a(n) nn
b(n) n
消元过程
根据下面的上三角方程组,逐次回代求解 xk
a1(11) x1
a (1) 12
x2
a x (2) 2212 2
1个顺序主子式
a(1) 11
Dk
a(1) 21 M
a(1) k1
a(1) 12
L
a(1) 22
L
M
a(1) k2
L
a(1) 1k
a(1) 2k
0
M
a(1) kk
(k 1, 2,..., n 1).
13
顺序Gauss消去法计算过程中的 akk(k) 称为主元素，在 第k步消元时要用它作除数,则可能会出现以下几种情况
①
4x2 x3 5
②
④+ ②
4x2 x3 11
④
x1 x2 x3 6
①
4x2 x3 5
②
7
2x3 6
⑤
(2)回代过程. 得到下同解方程组后,如下处理
x1 x2 x3 6
①
4x2 x3 5
②
2x3 6
⑤
x1 6 (x2 x3 ) 1
x2 x3 5 / 4 2
此方程组具有四位有效数字的精确解为
x1＝17.46，x2＝－45.76，x3＝5.546
16
解 用顺序Gauss消去法求解，消元过程如下
0.0120 0.0100 0.1670 0.6781
1.000
0.8334
5.910
12.10
3200 1200 4.200 981.0
0.0120 0.0100
25
从顺序Gauss消去法的矩阵运算表示式可知，系数矩阵 A可分解为一个单位下三角矩阵L和一个上三角矩阵U的乘 积，即
A
L11 L21
L A 1 (n) n1
LU
a1(11)
其中 U A(n)
a(1) 12
a(2) 22
a(1) 1n
a(2) 2n
u11
u12 u22
u1n
u2
y2
b2
y3
b3
ln1 ln2 lnn1 1 yn bn
解得
y1 yk
b1 bk
k 1 i 1
lki
yi
,
k 2,3, , n
28
对于 Ux =y
a22 x2 M
L
a2n xn
b2
an1x1 an2 x2 L ann xn bn
a11 a12 L a21 a22 L
M M an1 an2 L