第二章 求解线性方程组的数值解法
(Numerical Solution of Linear Equations)
1 1 1 1 2 2 1 1
2 1 1 2 2 2 2 2
1 1 2 2
( 1 )
nn
nn
n n n n n n
a x a x a x b
a x a x a x b
a x a x a x b




,0,
X,.
11
ij nn
T
A X b
A
T
nn
a
,,),,)( x ( bxb b


矩 阵 表 示 记 为这 里 我 们 假 设 A
直接法,经过有限步运算后可求得方程组精确解的方法 (不计舍入误差 !)（ 2.1节）
迭代法,从解的某个近似值出发，通过构造一个无穷序列去逼近精确解的方法。分为两类：
逐次逼近法 (一般有限步内得不到精确解 ) （ 2.2节）
共轭斜量法 （不考虑计算过程的舍入误差，只用有限步就收敛于方程组的精确解） （ 2.3节）
解线性方程组的两类方法
§ 2.1 解线性方程组的直接法
( Direct Method for Solving Linear Systems)
高斯消去法 (Gaussian Elimination)
思路首先将 A化为上三角阵 ( upper-triangular
matrix ),此过程称为 消去过程,再求解如下形状的方程组，此过程称为 回代求解
( backward substitution )。
=
§ 2.1.1求解 A x b? 的高斯消去法和选主元高斯消去法将增广矩阵 的 第 i 行 + li1? 第 1行,得到：
,)(记 )1()1( nnijaAA ( 1 )( 1 ) ( 1 )
()1 Tb b b b n
消去过程：
第一步,设,计算因子0)1(11?a
)1(
11
)1(
1
1 a
al i
i
)1(1)1(1)1(12)1(11,,,baaa n
)2(A )2(b?
其中


)1(
11
)1()2(
)1(
11
)1()2(,,3,2,,
blbb
njialaa
iii
jiijij?
0)(?kkka第 k步,设,计算因子 ( ) ( )/ ( 1,...,)kkik ik k kl a a i k n
将增广矩阵 的 第 i 行 + lik? 第 k行,得到：
( 1 ) ( ) ( )
( 1 ) ( ) ( )
(,1,..,,)
k k k
ij ij ik k j
k k k
i i ik k
a a l a
b b l b
i j k n



其中
( 1 )( 1 ) ( 1 ) ( 1 ) ( 1 )
111 1 1 1,1 1
( ) ( ) ( ) ()
,1
( 1 ) ( 1 )
( 1 )
11,1 1,
1
( 1 ) ( 1 )
()
,1
0
00
00
k k n
k k k k
kk k k k k n k
kk
k
kk k k n
k
kk
k
n k n n n
n
bxa a a a
xa a a b
xaa b
aa x b













)()( / nnnnnn abx?
)1.,,,,1()( 1
)()(

ni
a
xab
x i
ii
n
ij
j
i
ij
i
i
i
定理,若 A的所有 顺序主子式 均不为 0，则高斯消去法能顺序进行消元，得到唯一解。
回代过程：
共进行 n? 1步，得到
)(
)2(
2
)1(
1
2
1
)(
)2(
2
)2(
22
)1(
1
)1(
12
)1(
11
..
.
..
.
..
....
...
...
n
nn
n
nn
n
n
b
b
b
x
x
x
a
aa
aaa
运算量 （ Amount of Computation）
（ 1） 用克莱姆 （ Cramer） 法则求解 n阶线性方程组每个行列式由 n!项相加，而每项包含了 n个因子相乘，乘法运算次数为 (n-1)n !次,
,1,2,.,,,ii Dx i nD
仅考虑乘 (除 )法运算,计算解向量包括计算
n+1个行列式和 n次除法运算,乘 (除 )法运算次数 N=(n+1)(n-1)n!+n.
当 n=8时,N＝ 200,0000
（ 2） 高斯消去法,
第 1个消去步,计算 li1(i=2,3,…,n),有 n-1次除法运算,使 aij(1)变为 aij(2) 以及使 bi(1)变为 bi(2)
有 n(n-1)次乘法运算,
第 k个消去步,有 n-k次除法运算,(n-k+1)(n-k)次乘法运算,
乘法运算总次数为：
除法运算总次数为,(n-1)+… +1=n(n-1)/2
3
1
1 ( 1
3
n
k
k k ) ( n )n

回代过程的计算除法运算次数为 n次,乘法运算的总次数为
n+(n-1)+…+1=n(n -1)/2次
Gauss消去法除法运算次数为,n(n-1)/2+n=n(n+1)/2，
乘法运算次数为,
n(n-1)(n+1)/3+n(n-1)/2=n(n-1)(2n+5)/6，
通常也说 Gauss消去法的运算次数与 n3同阶，记为 O(n3)
( 3 0,9 8 9 0 )n? 为二,选主元消去法在高斯消去法消去过程中可能出现 的情况，这时高斯消去法将无法进行；即使主元素 但很小，
其作除数,也会导致其它元素数量级的严重增长和舍入误差的扩散
() 0kkka?
() 0kkka?
例,单精度解方程组


2
110
21
21
9
xx
xx
/* 精确解为 和 */.,,1000.,,00.1
101
1
91

x
8个
.,,8 9 99.,,99.02 12 xx
8个用 Gauss消去法计算：
92 1 2 1 1 1/ 1 0l a a
9 9 9
2 2 2 11 1 0,0,,,0 1 1 0 1 0 1 0al
8个
92 2 12 1 1 0bl



99
9
10100
1110
0,1 12 xx
小主元 /* Small pivot
element */ 可能导致计算失败。
列主元消去法在第 k 步消元前，在系数矩阵第 k 列的对角线以下的元素中找出绝对值最大的元。
| | m a x | | 0pkkk ikk i naa
若 p≠k,交换第 k个与第 p个方程后，再继续消去计算,
这种方法称为 列主元 Gauss消去法。
列主元 Gauss消去法保证了｜ lik｜ ≤1
(i=k+1,k+2,…,n).
为避免这种情况的发生,可通过交换方程的次序，
选取绝对值大的元素作 主元,基于这种思想导出了
,选主元消去法,
全主元消去法在第 k步消去前,在系数矩阵右下角的 n-k+1
阶主子阵中,选绝对值最大的元素作为主元素 。
(1) If p? k then 交换第 k 行与第 p行 ;
If q? k then 交换第 k 列与第 q 列 ;
(2) 消元注,列交换改变了 xi 的顺序，须记录 交换次序,
解完后再换回来。
,| | m a x | | 0pq
kk
ijk i j naa
§ 2.1.2 三角分解法
高斯消元法的矩阵形式每一步消去过程相当于左乘初等变换矩阵 Lk
( 2 ) ( 1 )( 2 ) ( 1 )
11
1121
1 1 11
311
1
,
1
1
01
23
0 0 1
L
( ) ( )
ii
n
i,,,n
bbA L A L
l
l a a
l
l









记,
其 中
( 3 ) ( 2 )( 3 ) ( 2 )
22
22
2 2 2 2
322
2
,
1
01
01
34
0 0 1
L
( ) ( )
ii
n
i,,,n
bbA L A L
l a a
l
l









记,
( 3 ) ( 1 )( 3 ) ( 1 )
2 1 2 1,bbA L L A L L
-1
i i
1,
1,
1
1
01
01
1
1L =
01
01
01
01
i
ii
ii
ni
ni
L
l
l
l
l











列 i 列
1
1 2 1
1
1 2 1
( n ) ( )
nn
( n ) ( )
nn
A L L L A
bbL L L


1 1 1 1
1 2 1
( ) ( n ) ( n )
n L LUA L L L A A


A 的 LU 分解
( LU factorization )
定理 2.1.1：如果 Gauss消去法能顺 序进行消去，则矩阵 A可进行三角分解，即 A＝ LU
注,（ 1） L 为单位下三角阵而 U 为 一般 上三角阵的分解称为 Doolittle 分解
（ 2） L 为一般下三角阵而 U 为 单位 上三角阵的分解称为 Crout 分解 。
Doolittle分解法,
通过比较法直接导出 L 和 U 的计算公式。思路
nn
n
nnnn
n
u
uu
l
l
aa
aa
..
.
..
..,,
.,,
1.,,
.,,...
1
1
.,,
..
.
..
.
..
.
..
.
.,,
111
1
21
1
111
),m i n (
1
ji
k
jkki ul
jia
一般计算公式
11
i1 1 1 1
,j 1,,n
,i 2,,n
jj
i
ua
l a u


1
k j k r
1
1
ik ir k k
1
2,3,,
j k,,n
( ) / i k 1,,n
k
k j r j
r
k
ik r k
r
kn
u a l u
l a l u u


对 计 算
LU 分解求解线性方程组
L Y b,U X Y A X b
11
2221
31 32
1 2 ( 1)
1111 12 1n
2222 2n
nn
1
1
1
1
U X
nnn n n n
nn
yb
yb
L Y b
yb
xy
xy
Y
xy
l
ll
l l l
u u u
uu
u

















11
-1
1
,2,3,,
( 1 ) Y
i
i i jij
j
in
y b
yybl

解,
ij ii
1
(
,
i n 1,,1
2 ) x
nnnn
n
ij i
ji
yx u
yx u x u





解,
1
2
3
1 2 3 14
2 5 2 18
3 1 5 20
1 0 0 1 2 3
2 1 0 0 1 4,
3 5 1 0 0 24
( 14,18,20) ( 14,10,72),
( 14,10,72) ( 1,2,3 )
.
TT
TT
x
x
x
A L U
L y y
U x x













例,用 直 角 三 角 分 解 法 解解,用 分 解 计 算 公 式 得求 解
2.1.3 有关定理定理 2.1.2,Gauss消去法能顺 序进行消去的充要条件是矩阵 A的所有 顺序主子阵 Ai 非奇异。
证明参看课本定理 2.1.4,若 A的所有顺序主子式 均不为 0，则 A 的 LU
分解唯一（其中 L 为 单位 下三角阵）。
证明：由 定理 2.1.1和定理 2.1.2可知,LU 分解存在。
下面证明唯一性。
若不唯一，则可设 A = L1U1 = L2U2,推出
121 UU 211122211 LLUULL
上三角矩阵 对角线上为 1的下三角矩阵
I?
§ 2.1.4 求解正定方程组的 Cholesky方法回顾,对称正定阵 A的几个重要性质
（ 1） A?1 亦对称正定，且 aii > 0
（ 2） A 的顺序主子阵 Ak 亦对称正定
（ 3） A 的特征值?i > 0
（ 4） A 的全部顺序主子式 det ( Ak ) > 0
定理 2.1.6 设矩阵 A对称正定，则存在唯一的对角元全为正的下三角阵 G 使得
A＝ GGT
计算格式为
1
11 11 1
11
1
2
1
1
1
( 1 ),( 1,2,...,)
( 2),..,
,1,2,...,
i
i
k
k k k k k j
j
k
ik ij k j
j
ik
kk
a
g a g i n
g
n
g a g
a g g
g i k k n
g



对 k ＝ 2,3,
§ 2.1.5 求解三对角方程组的追赶法

nnnn
nnn
f
f
f
x
x
x
ba
cba
cba
cb
2
1
2
1
111
222
11
定理,若 A 为 对角占优 的三对角阵，且满足则方程组有唯一的 LU分解。
0,0,0||||,0|||| 11 iinn caabcb
直接比较等式两边的元素，可得到计算公式（ p.66）
第二步,追 — 即解,fyL
1
1
1
,fy
1() ( 2,.,,,)i i i
i
i
fyy i n?

第三步,赶 — 即解,yxU
1,( 1,...,1 )n n i i i ix y x y x i n
第一步,对 A 作 Crout 分解
1 1
22
1
1
1
n
nn
A