第二章 求解线性方程组的数值解法
武汉大学数学与统计学院
1 1 1 1 2 2 1 1
2 1 1 2 2 2 2 2
1 1 2 2
nn
nn
n 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
? ? ? ??
?
? ? ? ??
?
?
?
? ? ? ?
?
阶 线 性 方 程 组,
[ ],X,11
T
nnij
A X b
TA
nn,,),,)( x ( bxbab?
?
? ? ?
矩 阵 表 示 记 为
这 里
解线性方程组的两类方法,
直接法, 经过有限次运算后可求得方程组精确解的方
法 (不计舍入误差 !)
迭代法：从解的某个近似值出发，通过构造一个无穷
序列去逼近精确解的方法 (一般有限步内得不到精确解 )
§ 2.1 解线性方程组的直接法
一、高斯消去法
思
路
首先将方程组 Ax=b 化为上三角方程组,
此过程称为 消去过程,再求解上三角方程
组，此过程称为 回代过程,
§ 2.1.1 高斯消去法和选主元高斯消去法
将增广矩阵 的 第 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? ? ? ?
( 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
?
?
? ??
?
???
??
共进行 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
)()( / nnnnnn abx ?
)1.,,,,1()( 1
)()(
??
?
?
?
?? ni
a
xab
x i
ii
n
ij
j
i
ij
i
i
i
定理,若 A的所有 顺序主子式 均不为 0，则高斯消
去法能顺序进行消元，得到唯一解。
iii
i
i
aa
aa
A
...
.........
...
)d e t (
1
111
?
回代过程：
二,选主元消去法
为避免这种情况的发生,可通过交换方程的次序，选取
绝对值大的元素作主元, 基于这种思想导出了主元素法
在高斯消去法消去过程中可能出现 的情况，这时
高斯消去法将无法进行；即使主因素 但很小，
其作除数,也会导致其它元素数量级的严重增长和舍
误差的扩散
() 0kkka ?
() 0kkka ?
?列主元消去法
在第 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 ????
? 运算量 （ 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.
（ 2） 高斯消去法,
在第 1个消去步,计算 li1(i=2,3,…, n),有 n-1次
除法运算, 使 aij(1)变为 aij(2) 以及使 bi(1)变为 bi(2)
有 n(n-1)次乘法运算和 n(n-1)次加 (减 )法运算,
在第 k个消去步，有 n-k次除法运算,(n-k+1)(n-k)次
乘法运算和相同的加 (减 )法运算,
首先统计乘法运算总次数, 将每个消去步的乘法运算
次数相加,有
n(n-1)+(n-1)(n-2)+… +3.2+2.1=n(n-1)(n+1)/3
加 (减 )法运算次数总计也为 n(n-1)(n+1)/3.
除法运算总次数为 n+(n-1)+… +1=n(n-1)/2
回代过程的计算
除法运算次数为 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，
加 (减 )法运算次数为,n(n-1)(2n+5)/6
通常也说 Gauss消去法的运算次数与 n3同阶，记为 O(n3)
?全主远消去法,
比 高斯消去法多出 比较，保证稳定，但费时 。
???
?
???
?
3
3n
O
?列主元消去法,
比 高斯消去法只多出 的 比较，略省时。??
?
?
???
?
3
2nO
§ 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.4,若 A的所有顺序主子式 均不为 0，则 A 的 LU
分解唯一（其中 L 为 单位 下三角阵）。
证明：由 § 1中定理可知,LU 分解存在。下面证明唯一性。
若不唯一，则可设 A = L1U1 = L2U2, 推出
??121 UU 211122211 LLUULL ??? ?
上三角矩阵 对角线上为 1的下三角矩阵
I? ?
注, （ 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
一般计算公式
计算量与 Gauss 消去法同,
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
??
?
??
????
??
??
?
解,
§ 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
2
1
1
1
,1,2,..,,
k
k k k k k j
j
k
ik ij k j
j
ik
kk
g a g
a g g
g i k k n
g
?
?
?
?
??
?
? ? ? ?
?
?
§ 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
? ?
??
?
??
?
?? ??
?? ??
?? ???
?? ??
????
武汉大学数学与统计学院
1 1 1 1 2 2 1 1
2 1 1 2 2 2 2 2
1 1 2 2
nn
nn
n 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
? ? ? ??
?
? ? ? ??
?
?
?
? ? ? ?
?
阶 线 性 方 程 组,
[ ],X,11
T
nnij
A X b
TA
nn,,),,)( x ( bxbab?
?
? ? ?
矩 阵 表 示 记 为
这 里
解线性方程组的两类方法,
直接法, 经过有限次运算后可求得方程组精确解的方
法 (不计舍入误差 !)
迭代法：从解的某个近似值出发，通过构造一个无穷
序列去逼近精确解的方法 (一般有限步内得不到精确解 )
§ 2.1 解线性方程组的直接法
一、高斯消去法
思
路
首先将方程组 Ax=b 化为上三角方程组,
此过程称为 消去过程,再求解上三角方程
组，此过程称为 回代过程,
§ 2.1.1 高斯消去法和选主元高斯消去法
将增广矩阵 的 第 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? ? ? ?
( 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
?
?
? ??
?
???
??
共进行 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
)()( / nnnnnn abx ?
)1.,,,,1()( 1
)()(
??
?
?
?
?? ni
a
xab
x i
ii
n
ij
j
i
ij
i
i
i
定理,若 A的所有 顺序主子式 均不为 0，则高斯消
去法能顺序进行消元，得到唯一解。
iii
i
i
aa
aa
A
...
.........
...
)d e t (
1
111
?
回代过程：
二,选主元消去法
为避免这种情况的发生,可通过交换方程的次序，选取
绝对值大的元素作主元, 基于这种思想导出了主元素法
在高斯消去法消去过程中可能出现 的情况，这时
高斯消去法将无法进行；即使主因素 但很小，
其作除数,也会导致其它元素数量级的严重增长和舍
误差的扩散
() 0kkka ?
() 0kkka ?
?列主元消去法
在第 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 ????
? 运算量 （ 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.
（ 2） 高斯消去法,
在第 1个消去步,计算 li1(i=2,3,…, n),有 n-1次
除法运算, 使 aij(1)变为 aij(2) 以及使 bi(1)变为 bi(2)
有 n(n-1)次乘法运算和 n(n-1)次加 (减 )法运算,
在第 k个消去步，有 n-k次除法运算,(n-k+1)(n-k)次
乘法运算和相同的加 (减 )法运算,
首先统计乘法运算总次数, 将每个消去步的乘法运算
次数相加,有
n(n-1)+(n-1)(n-2)+… +3.2+2.1=n(n-1)(n+1)/3
加 (减 )法运算次数总计也为 n(n-1)(n+1)/3.
除法运算总次数为 n+(n-1)+… +1=n(n-1)/2
回代过程的计算
除法运算次数为 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，
加 (减 )法运算次数为,n(n-1)(2n+5)/6
通常也说 Gauss消去法的运算次数与 n3同阶，记为 O(n3)
?全主远消去法,
比 高斯消去法多出 比较，保证稳定，但费时 。
???
?
???
?
3
3n
O
?列主元消去法,
比 高斯消去法只多出 的 比较，略省时。??
?
?
???
?
3
2nO
§ 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.4,若 A的所有顺序主子式 均不为 0，则 A 的 LU
分解唯一（其中 L 为 单位 下三角阵）。
证明：由 § 1中定理可知,LU 分解存在。下面证明唯一性。
若不唯一，则可设 A = L1U1 = L2U2, 推出
??121 UU 211122211 LLUULL ??? ?
上三角矩阵 对角线上为 1的下三角矩阵
I? ?
注, （ 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
一般计算公式
计算量与 Gauss 消去法同,
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
??
?
??
????
??
??
?
解,
§ 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
2
1
1
1
,1,2,..,,
k
k k k k k j
j
k
ik ij k j
j
ik
kk
g a g
a g g
g i k k n
g
?
?
?
?
??
?
? ? ? ?
?
?
§ 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
? ?
??
?
??
?
?? ??
?? ??
?? ???
?? ??
????
