第 3章
解线性方程组的数值解法
引言
在自然科学和工程技术中很多问题的解决
常常归结为解线性代数方程组。例如电学中的
网络问题，船体数学放样中建立三次样条函数
问题，用最小二乘法求实验数据的曲线拟合问
题，解非线性方程组问题，用差分法或者有限
元法解常微分方程，偏微分方程边值问题等都
导致求解线性方程组，而且后面几种情况常常
归结为求解大型线性方程组。
线性代数方面的计算方法就是研究求解线
性方程组的一些数值解法与研究计算矩阵的特
征值及特征向量的数值方法。
引言
? 关于线性方程组的数值解法一般有两类。
? 直接法：经过有限步算术运算，可求得方程
组的精确解的方法（若在计算过程中没有舍
入误差）
? 迭代法：用某种极限过程去逐步逼近线性方
程组精确解的方法
迭代法具有占存储单元少，程序设计简单，
原始系数矩阵在迭代过程中不变等优点，但
存在收敛性及收敛速度等问题
3.1 高斯消元法
? 设线性方程组
? 简记 AX=b
?
?
?
?
?
?
?
????
????
????
nnnnnn
nn
nn
bxaxaxa
bxaxaxa
bxaxaxa
......
......
......
......
2211
22222121
11212111
高斯消元法
? 其中
? ? ? ?
T
n
T
n
nnij
n
n
n
bbbxxx
a
aaa
aaa
aaa
bx ??
?
????
?
?
2121
n2n1n
22221
12111
,
)(A
??
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
高斯消元法
? 克莱姆法则在理论上有着重大意义，但
在实际应用中存在很大的困难，在线性
代数中，为解决这一困难给出了高斯消
元法。
代替所得。列用
的第是，，
，其中法则：
bi
AAAD
ni
D
D
xG ra m e r
iii
i
i
)d e t (0A)d e t (D
,.,,,2,1
???
??
例题
? 例 1.用消元法解方程组
?
?
?
?
?
?
?
???
??
???
)3(122
)2(54
)1(6
321
32
321
xxx
xx
xxx
例题
? 第一步,-2 x（ 1） +(3)得
?
?
?
?
?
?
?
????
??
???
)4(114
)2(54
)1(6
32
32
321
xx
xx
xxx
例题
? 第二步,1 x（ 2） +（ 4）
? 回代得,x=[1,2,3]T
?
?
?
?
?
?
?
???
??
???
)5(62
)2(54
)1(6
3
32
321
x
xx
xxx
3.1.1 高斯顺序消元法
? 下三角形方程求解
设
（ 1）
nil
bxlxlxl
bxlxl
bxl
ii
nnnnnn
,.,,,2,1,0
.,,
.,,,,,
2211
2222121
1111
??
?
?
?
?
?
?
?
????
??
?
其中，
高斯顺序消元法
? 由（ 1）得
该法称为向前代入法。
即
ni
lxlbx
lbx
lxlbx
lxlbx
l
b
x
ii
i
j
jijii
n
i
nnininn
,.,,,3,2
/)(
/
/)(
......
/)(
1
1
1111
1
1
2212122
11
1
1
?
?
?
?
?
?
??
?
?
?
?
?
?
?
?
?
?
??
??
?
?
?
?
?
?
?
高斯顺序消元法
? 算法,
;/)(;
11;0
nto2i3
/2;),,2,1,,2,1(,1
1111
iiii
jij
iij
lsbx
xlss
doitojF o r
s
doF o r
lbx
ijnibl
??
??
??
?
?
?
??
、
、
、赋初值 ??
高斯顺序消元法
?
?
?
?
?
?
?
?
?
?
?
?
?
?
nnnn
lll
ll
l
L bx
?
??
21
2221
11
A
( 1 ) 其中式可简写成,
? 上三角方程组的解法
设
,.,,,n,,iu
bxu
.,,,,,
bxu.,,,,,xu
bxu.,,,,,xuxu
ii
nnnn
nn
nn
210
)2(
22222
11212111
??
?
?
?
?
?
?
?
?
???
????
其中，
? 由（ 2）式回代得
12,.,,1
1
,ni
) / uxu(bx
/ubx
ii
n
ij
jijii
nnnn
??
?
?
?
?
?
??
?
?
??
上三角方程组的解法
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
nn
n
n
u
uu
uuu
U
U bx
?
?
?
222
11211
( 2 ) 其中式可简写成,
高斯顺序消去法
? 设 Ax=b,记 A(1)=A b(1)=b
1、第一次消元。设 0?
iia
T
n
nnn
n
n
i
i
i
bbbbb
aa
aa
aaa
ni
a
a
l
n
a
a
]......[
......
......
......
......
AA
,.,,,3,2,
...,32ii)(
)2()2(
2
)1(
1
)2()1(
)2()2(
2
)2(
2
)2(
22
)1(
1
)1(
11
)1(
11
)2(1
)1(
11
)1(
1
1
)1(
11
)1(
1
??
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
??
????
）（
令
），，行（第第一行
高斯顺序消去法
),.,,,2(.
),.,,,2;,.,,,2(
)1(
1)1(
11
)1(
1)1(
1
)1(
1
)1()2(
)1(
11
)1(
1
)1(
1)1(
)1(
11
)1()2(
nib
a
a
b
lbbb
njni
a
aa
a
alaa
i
i
iii
ji
ij
jiijij
???
??
????
??
高斯顺序消去法
? 设第 k-1次消元得 A(k)x=b(k) 其中
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
)(
)(
)2(
2
)1(
1
)()(
)()(
)2(
2
)2(
22
)1(
1
)1(
12
)1(
11
)()(
.,,
.,,
.,,
.,,.,,.,,
.,,
.,,.,,.,,.,,
.,,.,,.,,
.,,.,,.,,
][
k
n
k
k
k
nn
k
nk
k
kn
k
kk
n
n
kk
b
b
b
b
aa
aa
aa
aaa
bA ?
高斯顺序消去法
则第 k次消元,
1,.,,,2,1
,.,,,1,
,.,,,1;,.,,,1,
,.,,,1,
)()()1(
)()()1(
)(
)(
??
????
??????
???
?
?
nk
nkiblbb
nkjnkialaa
nki
a
a
l
k
kik
k
i
k
i
k
kjik
k
ij
k
ij
k
k
k
ik
ik
则有令
高斯顺序消去法
? 最后
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
)(
)(
)2(
2
)1(
1
)(
)()(
)2(
2
)2(
22
)1(
1
)1(
12
)1(
11
)()(
.,,
.,,
.,,.,,
.,,.,,.,,
.,,
.,,.,,.,,.,,
.,,.,,.,,
.,,.,,.,,
][
n
n
k
k
n
nn
k
kn
k
kk
n
n
nn
b
b
b
b
a
aa
aa
aaa
bA ?
高斯顺序消去法
? 也就是对于方程组 AX=b系数矩阵做,
)1,.,,,2,1(
,.,,,1
,.,,,1
/
)()()1(
)()()1(
)()(
??
??
??
?
?
?
?
?
??
??
?
?
?
nk
nkj
nki
lbbb
alaa
aal
ik
k
k
k
i
k
i
k
kjik
k
ij
k
ij
k
kk
k
ikik
高斯顺序消去法
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
)(
)(
)2(
2
)1(
1
)(
)()(
)2(
2
)2(
22
)1(
1
)1(
12
)1(
11
)(
)()n(
.,,
.,,
.,,.,,
.,,.,,.,,
.,,
.,,.,,.,,.,,
.,,.,,.,,
.,,.,,.,,
]
)(
[
A
n
n
k
k
n
nn
k
kn
k
kk
n
n
n
n
b
b
b
b
a
aa
aa
aaa
n
A b
bx
?
其中
得到
高斯顺序消去法
?
?
?
?
?
????
?
?
?
??
)1,.,,,1(/).(
/
A
)(
1
)()(
)()(
)()(
niaxabx
abx
i
ii
n
ij
j
i
ij
i
ii
n
nn
n
n
nn
bx
回代法
再解
高斯顺序消去法；做对；
做对
机；输出算法失败信息，停
做对
输入：
kjikijij
kikii
kkikikik
kk
iij
alaankj
blbb
aala
nki
a
nk
nibnjia
????
??
??
??
?
??
??
,.,,,3
2
/1
,.,,,)2
t h e nif)
,,.,,,,)(
),.,,,,(),,.,,,,,()1(
0
0
0
1
1
01
1212
2121
高斯顺序消去法
)d e t (),,.,,,,()(
.,,)(d e t)3
/)(
,,.,,,)2
/)1
e l se,t h e nif)(
AAnix
aaaA
axabxb
ni
abxb
a
i
nn
ii
n
ij
jijiii
nnnnn
nn
的行列式的值系数矩阵输出：方程组的解；
做对；
做并停机输出算法失败信息
214
121
03
2211
1
?
?
???
??
??
?
?
??
高斯顺序消去法算法框图
高斯消去法的计算量
)13(
3
1
)1(
2
1
)52)(1(
6
1
)]1)(()[(
:
)1)((
n
),.,,,1i(/:
2
)()(
1
1
)1()(
)()(
???
??
????????
????
?
???
?
?
?
?
nnnN
nnbXA
nnnknknkn
knknAA
k
nkaalk
nn
n
k
kk
k
kk
k
ikik
即总计算量为
回代时乘除运算量为解
故总的消元计算量为
次乘法需由
次除法除法即
步第
高斯顺序消去法条件
.
,,
,0
.
,.,,,2,1,0
,.,,,2,1*)d e t (:)d e t (
1:)d e t (
0...)d e t (
)(
)(
)(
)(
)()2(
22
)1(
11
即数值不稳定
做除数易产生解的失真用此时
很小若
也就是次算法的缺点
求因此高斯顺序消去法要
即
k
kk
k
kk
k
kk
k
kk
n
nn
a
a
nka
nkaAA
A
aaaA
?
??
?
?
?
?
?
??
?
??
3.1.2 高斯主元素消去法
? Gauss列主元消元法
? 从第一列中选出绝对值最大的元素
1111 m a x ini aa ???
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
nnnnn
iinii
n
baaa
baaa
baaa
baaa
......
..............................
......
..............................
......
......
21
21
2112221
111211
交
换
高斯列主元消去法
顺序消元
计算机中实现
)3;:;;
1)2;|;|m a xm a x||
2
1;i ; ||m a x 1)
11
11
1
TaaaaT
dontojf o r
kiat h e naif
dontokf o r
a
ijijjj
kk
i
???
?
???
?
??
高斯列主元消去法
? 第 k步
从 的第 k列,, 中选取绝对值最
大项，记录所在行，即
若 交换第 k行与 l行的所有对应元素，再
进行顺序消元。
(k) kka 1?)(Ak
(k)nk.a..
(k)kka
k
k
ik
k
ki ilaa k ?? ?? 记||m a x||
)(
nik
)(
kl?
框图
高斯列主元消去法
输出奇异标志，停机；；
做对；；
即记选列主元：
做对
输入：
t h e n0if)2
,t h e n||if
,.,,,,
||
,|,|m a x||)
,,.,,,,)(
),.,,,,(),,.,,,,,()1(
m ax
m axm ax
m ax
?
???
???
??
??
??
??
??
a
ilaaaa
nkki
aakl
ilaa
nk
nibnjia
ikik
kk
kik
nik
ki
iij
k
21
1
1212
2121
高斯列主元消去法；做对；
做对；
做对
行所有对应元素，即行与第交换第
kjikijij
kikii
kkikikik
iikk
ljljkjkj
alaankj
blbb
aala
nki
TbbbbT
TaaaaT
nkkj
lkkl
????
??
??
??
???
???
??
?
,.,,,3
2
/1
,.,,,)4;;2;;
,.,,,,1
t h e n if)3
0
0
0
0
0
1
1
1
高斯列主元消去法
。输出：方程组的解；
做对；
并停机输出奇异标志
回代求解
),.,,,,()(
/)(
,,.,,,)2
/)1
e l s e,t h e nif
)(
nix
axabxb
ni
abxb
a
i
ii
n
ij
jijiii
nnnnn
nn
214
121
0
3
1
?
???
??
??
?
?
??
2,全主元消去法
? 例如,求解方程组
T
x
x
x
x
)3 6 7 5.0,0 5 1 0 4.0,4 9 0 4.0(
:4,4
0 0 0.3
0 0 0.2
0 0 0.1
6 4 3.50 7 2.10 0 0.2
6 2 3.47 1 2.30 0 0.1
0 0 0.30 0 0.20 0 1.0
*
3
2
1
???
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
位有效数字为精确解舍入到位浮点数进行计算用
全主元消去法
.)4 0 0 0.0,0 9 9 8 0.0,4 0 0 0.0(
00.2
0 0 2.1
0 0 0.1
00.500
0 0 5.32, 0 0 40
0 0 0.30 0 0.20 0 1.0
0 0 3.2
0 0 2.1
0 0 0.1
0 0 6.60 0 1.40
0 0 5.32, 0 0 40
0 0 0.30 0 0.20 0 1.0
0 0 0.3
0 0 0.2
0 0 0.1
6 4 3.50 7 2.10 0 0.2
6 2 3.47 1 2.30 0 0.1
0 0 0.30 0 0.20 0 1.0
)|A(
.
是一个很坏的解解得
用高斯顺序消去法求解
T
x
b
???
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
全主元消去法
T
x
b
)3 6 7 6.0,5 1 0 80.0,8 8 5 44.0(
6 8 6 6.0
5 0 0.0
0 0 0.3
8 6 7 6.100
8 0 1 5.13, 1 7 60
5, 6 4 31, 0 0 7 22, 0 0 0-
0 0 1 5.1
5 0 0.0
0 0 0.3
0 0 2 3.30 0 0 5.20
8 0 1 5.13, 1 7 60
5, 6 4 31, 0 0 7 22, 0 0 0-
0 0 0.1
0 0 0.2
0 0 0.3
0 0 0.3000.20 0 1.0
6 2 3.43, 7 1 21, 0 0 0-
6 4 3.50 7 2.10 0 0.2
0 0 0.3
0 0 0.2
0 0 0.1
6 4 3.50 7 2.10 0 0.2
6 2 3.47 1 2.30 0 0.1
0 0 0.30 0 0.20 0 1.0
)|A(
.
3i
???
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
? ?
?
?
?
?
?
?
?
?
?
?
?
?
??
?
得
用选列主元消去法求解
全主元消去法；；；
，对；；
中选绝对值最大者从选主元
、第一步消元
jtilat h e n
aifdo
njni
tla
njia
ij
ij
ij
???
?
??
???
?
||m a x
||m a x
,.,,,1,.,,,1;11||m a x
.),.,,,2,1,(,)1
1
11
全主元消去法
顺序消元；；做，，，
初值踪数组序发生改变，因此设跟
解的次而交换列时解的次序不变交换行时；列交换第一列与第；行交换第一行与第
)3
)()1(,)Z(.,,2)Z ( 21)Z ( 1
),(
,,,
),.,,,2,1(:
),.,,,2,1(:)2
1
1
tZZnn
iZ
niaat
njaal
iti
ljj
????
??
??
全主元消去法
顺序消元
列列交换
行行交换如果；
步选主元时得）假设第
步消元：、第
)2
)()(;,;,;||m a x
1
2
)(;
)(
tzkztkkt
lkkl
jtilaa
k
k
kk
k
ij
njik
k
ji
kk
???
??
???
??
全主元消去法
),.,,,2,1())((:)(
))(()),2(()),1((
3
21
nibizxnx
nzxbzxbzxb
i
n
??
???
则增加数组
理顺解：
、求方程组的解
?
。；；
，其解这时
做
例如
3
21
)1())3((
)2())2(()3())1((
2)2(,1)3(,3)1(
)3()1(31
3)3(,2)2(,1)1(:
bxzx
bxzxbxzx
zzz
ZZjj
zzz
??
????
???
????
???
Gauss全主元消元算法；
做对
做对；；
即记选全主元：
做对
输入：
jtilaaaa
nkkj
nkki
aaktkl
jtilaa
nk
niiiz
nibnjia
ijij
kk
kkij
njik
ji
iij
kk
????
???
???
???
???
??
??
??
??
,|,|t h e n||if
,.,,,,
,.,,,,
||;
,|,|m a x||)
,,.,,,,)(
);,.,,,,()()(
),.,,,,(),,.,,,,,()1(
m a xm a x
m a x
,
21
21
1
1213
212
2121
Gauss全主元消元算法；做对；
做对；输出奇异标志，并停机
kjikijij
kikii
kkikikik
itik
lkljkj
alaankj
blbb
aala
nki
tzkzniaakt
bbnkkjaakl
a
????
??
??
??
????
?????
?
,.,,,3
2
/1
,.,,,)4
);()();,.,,,,(t h e n if;);,.,,,,(t h e n if)3
t h e n0if)2
0
0
0
m a x
1
1
21
1
Gauss全主元消元算法
。输出解；
做对；
并停机输出奇异标志
),.,,,,()(
),.,,,())(()3
/)(
,,.,,,)2
/)1
e l s e,t h e nif)(
nix
nibizx
ababb
ni
abb
a
i
i
ii
n
ij
jijii
nnnn
nn
215
21
121
04
1
?
??
??
??
?
?
?
??
3.高斯 -约当消去法
? 与一般消去法相比，高斯 — 约当消去法
是一种无回代过程的算法
? 设方程组 AX=b经过（ k-1）次消元得
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
???
)(
)(
1
)(
1
)()(
)(
1
)(
1
)(
1
)(
1
)()(
1
1
]A[
k
n
k
k
k
k
nn
k
nk
k
kk
k
kk
k
n
k
k
kk
b
b
b
aa
aa
aa
b
?
?
?
??
?
???
?
?
高斯 -约当消去法
Tn
n
nn
k
k
k
ik
k
i
k
i
k
kj
k
ik
k
ik
k
ij
k
ik
k
kk
k
k
k
k
k
kk
k
kj
k
kj
k
kk
kik
nik
ki
k
ik
bbbxn
kinibabb
nkjkiniaaaa
kinika
nkkj
abb
aaa
alkkl
ilaa
nkkia
k
),.,,,,(,
),,.,,,2,1(
),.,,,1,,,.,,,2,1(
),.,,,2,1i(
),.,,1,(
/
/
0,,
|,|m a x||
),.,,,1,(k
)1()1(
2
)1(
1
)1()()()1(
)1()()()1(
)(
)()()1(
)()()1(
)(
)(
???
??
??
?
?
??
?
?
?
?
????
??????
???
?
?
?
??
?
?
??
??
??
得到：步消元如此进行
，即，行行加到乘以再用
由
这时新的行行与则交换若
并记选主元，即
中步消元：首先从第
算法
选列主元的 Gauss-Jordan消去法
。输出：解
做对
做但对
输出奇异标志，停机；；记选列主元：
做对
输入：
),.,,,,()(;,.,,,2;1
,.,,,,)5
);,.,,,(/)4;);,.,,,,(t h e n if)3
t h e n0if)2
|,|m a x||)
,,.,,,,)(
),.,,,,(),,.,,,,,()1(
0
0
nibx
aaaankj
babb
kinj
nkjaaa
bbnkkjaakl
a
ilaa
nk
nibnjia
ii
kjikijij
kikii
kkkjkj
lkljkj
lk
kik
nik
ki
iij
k
213
1
21
1
1
1
1212
2121
??
????
??
??
???
?????
?
??
??
??
??
? Guass-Jordan消去法形式上比 Guass消去法简
单,求解无回代过程,但从工作量角度看前者大
约需要 O( ),而后者需要量 O( ),比有
回代的 Guass消去法多 O( )工作量,
3
2
1 n
3
3
1n
3
6
1 n
小节
? 比较而言,Gauss顺序消去法条件苛刻,且数值不稳
定 ; Gauss全主元消去法工作量偏大，需要比较
个元素及行列交换工作，算法复杂；对于 Gauss-
Jordan消去法形式上比其他消元法简单，且无回
代求解，但计算量大,比 Gauss顺序消去法多
计算量。因此从算法优化的角度考虑,Gauss列
主元消去法比较好。
?
?
n
k
k
2
2
)61( 3nO