第六章,线性代数方程组的数值解
Gauss 消去法
矩阵三角分解法
对称矩阵的平方根法
三对角方程组的追赶法
向量与矩阵范数及方程组的性态
解线性方程组的迭代法
分快迭代法
§ 1.引言
n阶线性方程组：
可以表示成矩阵形式：
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
a x a x a x b
a x a x a x b
a x a x a x b
A X b?
,X,11
T
ij nn
TA
nn,,),,)( x ( bxbab
35
de t( ) 0,
d e t( )
( 1,2,,)
d e t( )
1
( 1 ) !
3 0,2,3 8 1 0
i
i
A
A
xi
n
n
A
n n n
n
n
n
每 个如 果 线 性 方 程 组 的 系 数 行 列 式 不 为 零,即则 该 方 程 组 有 唯 一 解 。 由 克 莱 姆 (Cramer) 法 则,其 解 为这 种 方 法 需 要 计 算 个 阶 行 列 式 并 作 次 除 法,而阶 行 列 式 计 算 需 作 次 乘 法,计 算 量 十 分 惊 人 。
如 需 3 1 2 9 3 0 ! = 次 乘 法 。 可 见 其
n
在 理 论上 是 绝 对 正 确,但 在 较 大 时,在 实 际 计 算 中 确 实 不 可 行 的 。
解线性方程组的两类方法：
直接法,经过有限次运算后可求得方程组精确解的方法 (不计舍入误差 ! ）
迭代法,从解的某个近似值出发，通过构造一个无穷序列去逼近精确解的方法。
（一般有限步内得不到精确解 )
§ 2,Gauss 消去法
简单消去法
Gauss顺序消去法的可行性及计算量
矩阵的三角分解法
主元素消去法
Gauss-Jordan列主元消去法一、简单消去法将 n阶线性方程组 转化为等价（或同解）的三角形方程组 11 1 12 2 1 1
22 2 2 2
nn
nn
nn n n
gb x b x b x
gb x b x
gbx
11,,,nnx x x?
的过程称为消元过程，逐次求出的步骤称为回代过程。
Gauss 消去法计算过程,
统一记号11
i j i j i i,a a b b
1 1 111 11
1
T
ijX,,n,,a bbAAbb
原方程为
1
11 0 a?
113 1 1 1 ( ( ) ( )) aa第 三 行 第 一 行 新 第 三 行
111 1 1
( )
( ) ( )
n
nn aa第 行 （ 第 一 行 ） 新 第 行相当于第 i个方程 -第一个方程 × 数 → 新的第 i方程 — 同解！第一方程不动！
1121 11( ) ( ) ( )aa第 二 行 （ 第 一 行 ） 新 第 二 行
Step1 假设上述消元过程除第一个方程不变以外,第 2—
第 n个方程全消去了变量?1，而系数和常数项全得到新值：
( 1 ) ( 1 ) ( 1 ) ( 1 ) ( 1 )
11 1 12 2 13 3 1 1
( 2 ) ( 2 ) ( 2 ) ( 2 )
22 2 23 3 2 2
( 2 ) ( 2 ) ( 2 ) ( 2 )
32 2 33 3 3 3
( 2 ) ( 2 )
2 2 3 3
nn
nn
nn
nn
a x a x a x a x b
a x a x a x b
a x a x a x b
a x a x
( 2 ) ( 2 )
nn n na x b
22 XA? （ ）（ ） b
1 1 1 1
1 1 1 2 1 1
2 2 2
( 2 )2
2 2 2 2
2 2 2
2
0
0
n
()
n
n n n n
a a a b
a a b
bA
a a b
，
2 1 1 2 1 1
1 1 1 1i j i j i j i i ia a l a,b b l b,
,2 3i j,,,n?
得到同解方程组为其中
11
1 1 1 1iil a a?
( 2 )
22 0 a?
Step2.若,保留方程组中第一及第二个方程，消去其余方程中变量 x3,得同解方程组
( 1 ) ( 1 ) ( 1 ) ( 1 ) ( 1 )
11 1 12 2 13 3 1 1
( 2 ) ( 2 ) ( 2 ) ( 2 )
22 2 23 3 2 2
( 3 ) ( 3 ) ( 3 )
33 3 3 3
(3
3
n
n
n
n
a x a x a x a b
a x a x a b
a x a b
) ( 3 ) ( 3 )
3 nn na x a b
( 1 ) ( 1 ) ( 1 ) ( 1 ) ( 1 )
11 12 13 1 1
( 2 ) ( 2 ) ( 2 ) ( 2 )
22 23 2 2
( 3)( 3 )
( 3 ) ( 3 ) ( 3 )
33 3 3
( 3 ) ( 3 ) ( 3 )
3
0
00
00
n
n
n
n nn n
a a a a b
a a a b
A a a b
a a b
,b
( 2 ) 2( 3 ) ( 2 ) 3 2
22,2 2
()( ) ( )
i j i j i ijiil a l ba a b b
34,,,,n ij?
( 3 )( 3 ) x bA?记作,其中
( 2 ) ( 2 )
2222 iila a?
( 3 )
33 0a?若,则 此 消 去 过 程 可 依 次 进 行 下 去 。
()()
1
nn
n
x bA
第 步 消 去 过 程 后,得 到 等 价 三 角 方 程 组 。
( 1 ) ( 1 ) ( 1 ) ( 1 ) ( 1 )
11 1 12 2 13 3 1 1
( 2 ) ( 2 ) ( 2 ) ( 2 )
22 2 23 3 2 2
( 3 ) ( 3 ) ( 3 )
33 3 3 3
nn
nn
nn
a x a x a x a x b
a x a x a x b
a x a x b
( ) ( )
nn
nn n na x b
( 1 ) ( 1 ) ( 1 ) ( 1 ) ( 1 )
11 12 13 1 1
( 2 ) ( 2 ) ( 2 ) ( 2 )
22 23 2 2
( n)()
( 3 ) ( 3 ) ( 3 )
33 3 3
( ) ( )
0
00
0 0 0
n
n
n
n
nn
nn n
a a a a b
a a a b
A a a b
ab
,b系数矩阵与常数项：
()() nnA,b计算出 的过程为消元过程。
消去过程算法
( 1 ) ( 1 ) ( 1 )
11 1 1
( ) ( ) ( ) ( )
1
n
k k k k
k k k k k n k
a a b
a a a b?
( 1 ) ( 1 )
0
0 1,
kk
ij j
k i j n
ab
11,,1 kkk k k k
i j i j i ik j k k i,j ni k i kl a l ba a b b
() 0,1k
ik k i na
1,2,,1kn
1 k i,j nk kkk
ikikla a?
回代过程算法
( 1 ) ( 1 ) ( 1 ) ( 1 )
11 1 1 1 1
( ) ( ) ( )
( 1 ) ( 1 ) ( 1 )
1 1 1 1 1
i i n n
i i i
ii i in n i
n n n
n n n n n n n
a x a x a x b
a x a x b
a x a x b
( ) ( )
nn
nn n na x b
( ) ( )nn
n n n nx b a?
( ) ( ) ( )
1
( ),
ni i i
i i i j j i i
ji
x b a x a
1,2,,1i n n对于
13
24
1 2 3 4
24
25
3
2 4 3 17
37
xx
xx
x x x x
xx
例 1,用消去法解方程组解：用增广矩阵表示求解过程
1 0 2 0 5
0 1 0 1 3
|
1 2 4 3 17
0 1 0 3 7
Ab
3 3 1 1
1 0 2 0 5
0 1 0 1 3
0 2 2 3 1 2
0 1 0 3 7
r l r?
3 32 2
4 42 2
1 0 2 0 5
0 1 0 1 3
0 0 2 1 6
0 0 0 2 4
r l r
r l r
4
/2
1 0 2 0 5
0 1 0 1 3
0 0 2 1 6
0 0 0 1 2
r
1 0 2 0 5
0 1 0 0 1
0 0 2 0 4
0 0 0 1 2
1 0 2 0 5
0 1 0 0 1
0 0 1 0 2
0 0 0 1 2
1 0 0 0 1
0 1 0 0 1
0 0 1 0 2
0 0 0 1 2
二,Gauss顺序消去法的可行性及计算量
Gauss消去和回代过程都要求元素
0 ( 1,2,,)k
kka k n
0k
kka?
称之为主元素。若,则计算无法进行。但在系数矩阵保持一定条件时，则可保证主元素非零，使 Gauss顺序消去法在计算机上顺利执行。
定理 1 若矩阵 A的各阶顺序主子式均不为零，即,则定理 2 若矩阵 A对称正定,则
de t 0kkDA
0 1,2,,k
kka k n
定理 3 若矩阵 A严格对角占优,则
0 1,2,,k
kka k n
0 1,2,,k
kka k n
矩阵 严格对角占优，若
ij nnAa
1
,1,2,,
n
i i i j
j
ji
a a i n
消去第一列的 n-1 个系数要计算 (n-1)+n*(n-1）
次乘法。
22
11
1
3
1
2
n
kk
n n
k k n ( n ) nk
Gauss消去法乘法计算量消去第二列的 n-2 个系数要计算 (n-2)+(n-1）
*(n-2） 次乘法。
……
乘法计算量
3
2 1 ( 3 0,9 8 9 0 )
33
n n n n 为
1
2
n( n )?回代过程总计算量
Gauss消去法乘除法总运算量为三,矩阵三角分解法
( 2 ) ( 1 )( 2 ) ( 1 )
11,bbA L A L
1121
1 1 11
311
1
1
1
01
23
0 0 1
L
( ) ( )
ii
n
i,,,n
l
l a a
l
l
其中每一步消去过程相当于左乘初等变换矩阵 Lk,记
22
2 2 2 2
32
( 3 ) ( 2 )(3
2
2
) ( 2 )
22
1
01
01
34
0 0 1
,
L
( ) ( )
ii
n
i,,,n
l
bbAL
a
l
A
l
L
a
记,
( 3 ) ( 1 )( 3 ) ( 1 )
2 1 2 1,bbA L L A L L
依此类推，得矩阵的 LU分解形式
1 1 1 1
1 2 1
( n ) ( n )
n LUA A L L L A L A
21
12
1
1
1
nn
L
l
ll
其中
1 1 1 2 1 3 1
2 2 2 3 2
3 3 3
0
0 0
0 0 0
n
n
n
nn
u u u u
u u u
uu
u
( 1 ) ( 1 ) ( 1 ) ( 1 )
1 1 1 2 1 3 1
( 2 ) ( 2 ) ( 2 )
2 2 2 3 2
( 3 ) ( 3 )
3 3 3
()
0
00
0 0 0
n
n
n
n
nn
U
a a a a
a a a
aa
a
L U x? b
方程组可写成若令
Ly? by Ux?
则上式变成则求解原方程组 Ax=b便转化为
Ly
U x y
b
上述矩阵分解法称为 Doolittle分解,计算公式为
11
1
1
,
( 2,3,,)i
i i i k k
k
yb
in
y b l y
1
,
( 1,2,,1 )
/
n n nn
n
i i ik k ii
ki
x y u
i n n
x y u x u
其中
11
1 1 11
1,2,,,
/ 2,3,,,
ii
ii
u a i n
l a a i n
1
1
1
1
,1,,,
/,1,2,,,,
r
r i r i r k k i
k
r
i r i r i k k r r r
k
u a l u i r r n
l a l u u i r r n r n
000
00
0
1
01
001
0001
44
3433
442322
14131211
434241
3231
21
44434241
34333231
24232221
14131211
u
uu
uuu
uuuu
lll
ll
l
aaaa
aaaa
aaaa
aaaa
uululululululululul
uululuululululul
uuluuluulul
uuuu
44344324421441334323421341224212411141
34243214313323321331223212311131
2414212313212212211121
14131211
++++++
+++++
+++
n.,3,i -; -,- 2
n,2,j,-; -,-,- u2
n,2,i,;,,1
n,1,j,;,,,1
2212i22i2
22124142422212313232
12122j
142124241321232312212222
111i1114141113131112121
11j1414131312121111
uulal
uulaluulal
ulau
ulauulauulau
ualualualual
auauauauau
)(
)()(l
l
u
i
jj
i
j
列行列行
()
() ( 1,2,,1 ; 1,,)
k
ik
ik k
kk
a
l k n i k n
a
得
3 1 3 2 4 21,2,1,l l l
其余全为 0。
例 2,对于 例 1，由增广矩阵表示消元过程，
有故有
1 0 2 0 1 1 0 2 0
0 1 0 1 0 1 1 0 1
1 2 4 3 1 2 1 2 1
0 1 0 3 0 1 0 1 2
A
1
2
3
4
15
0 1 3
1 2 1 17
0 1 0 1 7
y
y
Ly
y
y
1
2
3
4
5
3
6
4
y
y
y
y
1
2
3
4
1 0 2 0 5
1 0 1 3
2 1 6
24
x
x
Ux
x
x
1
2
3
4
1
1
2
2
x
x
x
x
1
2
3
1 2 3 1 4
2 5 2 1 8
3 1 5 2 0
1 0 0 1 2 3
2 1 0 0 1 4,
3 5 1
0 0 2 4
( 1 4,1 8,2 0 ) ( 1 4,1 0,7 2 ),
( 1 4,1 0,7 2 ) ( 1,2,3 ),
TT
TT
x
x
x
A L U
L y y
U x x
例 3,用 LU 三 角 分 解 法 解解,用 分 解 计 算 公 式 得求 解高斯主元素消去法
()
()
0
0
k
kk
k
kk
a
a
在 高 斯 法 消 元 过 程 中 可 能 出 现 的 情 况,
这 时 消 去 法 将 无 法 进 行 ； 即 使 主 元 素但 很 小,用 其 作 除 数,也 会 导 致 其 他 元 素 数量 级 的 严 重 增 长 和 舍 入 误 差 的 扩 散 。
例 1 在只取小数点后四位数字的条件下，
用 Gauss顺序消去法解方程组
12
12
0,0 0 0 3 3,0 0 0 0 2,0 0 0 1
1
xx
xx
解：
21
11 10000
0.00 03 3l
12
2
0,0 0 0 3 3,0 0 0 0 2,0 0 0 1
9 9 9 9 6 6 6 6
xx
x
由第二个方程可求出
2
6666 0.6667
9999
x
代入第一个方程可求出
1 2,0 0 0 1 0,6 6 6 7 3 / 0,0 0 0 3 0x
120,3 3 3 3,0,6 6 6 7xx
而方程组的准确解为设
,1,2i i ix x i
由第一个方程知因此
1 1 2 20,0 0 0 3 3,0 0 0 0 2,0 0 0 1xx
120,0 0 0 3 3,0 0 0 0 0
120,0 0 0 3 3,0 0 0 0 2,0 0 0 1xx
而于是，有
4
1210
小主元素是算法不稳定的主要原因。
( ) ( )
( ) ( )
( ) ( )
m a x{,,,1,,}
m a x{,,1,
kk
ik ik k k ik
kk
k k ij
kk
k k ik
G
i j k
aus
kn
ik
s
k
l a a l
aa
aa
为 避 免 此 种 情 况 的 发 生,可 通 过 交 换 方 程 的 次 序,
选 取 绝 对 值 大 的 元 素 作 主 元 。 基 于 这 种 想 法 导 出 了 主元 素 法 。 计 算 时 避 免 很 小,
主 元 素 消 去 法从 而 只 要 取称 为 ；
或
,}
G au s
n
s列 主称 为 。元 消 去 法
1
2
3
*
0,0 0 1 2,0 0 0 3,0 0 0 1,0 0 0
1,0 0 0 3,7 1 2 4,6 2 3 2,0 0 0
2,0 0 0 1,
0 7 2 5,6 4 3 3,0 0 0
( 0,
4 9 0 4,0,0 5 1 0 4,0,3 6 7 5 )
T
x
x
x
x
例,3 阶 方 程 组四 位 有 效 数 字 精 确 解 为
解,1 高 斯 消 去 法
32 1.997
0,0 0 1 2,0 0 0 3,0 0 0 1,0 0 0
0 2 0 0 4 3 0 0 5 1 0 0 2
0 4 0 0 1 6 0 0 6 2 0 0 3
l?
0,0 0 1 2,0 0 0 3,0 0 0 1,0 0 0
0 2 0 0 4 3 0 0 5 1 0 0 2
0 0 5,0 0 0 2,0 0 0
0,4 0 0
.0 9 9 8 9
0,4 0 0
x
21
31
1000
2000
0,0 0 1 2,0 0 0 3,0 0 0 1,0 0 0
| 1,0 0 0 3,7 1 2 4,6 2 3 2,0 0 0
2,0 0 0 1,0 7 2 5,6 4 3
3
.0
00
l
l
Ab
2（ ） 交 换 行,避 免 绝 对 值 小 的 主 元
（ 列 主 元作 除 数 。
素 法 ）
21
31
0,5 0 0 0
0,0 0 0 5
0,0 0 1 2,0 0 0 3,0 0 0 1,0 0 0
| 1,0 0 0 3,7 1 2 4,6 2 3 2,0 0 0
1,0 7 2 5,6 4 3 3,0 0 0
1,0 7 2 5,6 4 3 3,0 0 0
1,0 0 0 3,7 1 2 4,6 2 3 2,0 0 0
0,0 0 1 2,0 0 0 3,0 0 0 1,0 0
2,0 0
2,0 0 0
0
0
l
l
Ab
2,0 0 0 1,0 7 2 5,6 4 3 3,0 0 0
0 3,1 7 6 1,8 0 1 0,5 0 0
0 0 1,8 6 8 0,6 8 7
( 0,4 9 0 0,0,0 5 1 1 3,0,3 6 7 8 ) Tx
32 0.6297
2,00 05 / 3,17 60
2,0 0 0 1,0 7 2 5,6 4 3 3,0 0 0
0 1,8 0 1 5 0,5
0 2,0 0 0 5 3,0 0 2 8 1,0 0 1 5
3,1 7 6 0
l?
,
,,
,de t,
1,de t 1
1,2,,1 7
2
m a x,
3,0,de t 0,
4,5
(,
k
k
k
ij ij
i k ik
k i n
ik
k
k j i j
Ax b
A m a x
b
kn
aa
a
ik
a a j k
算法：（列主元素消去法）设消元结果冲掉 乘数 冲掉 计算解冲掉常数项 行列式值存放在对于 做到第 步。
,按列选主元素如果 则 计算停止。
如果 则转,否则换行：
1,,),,
de t de t
k
ki
k n b b
。
1
5.,
/ ( 1,,) ( 1 )
6,
(,1,,)
( 1,,)
7,de t de t,
8,
/ ;
( ) / ( 1,2,,1 ),
9,
ik
ik ik ik k k ik
ij ij ik k j
i i ik k
kk
n n nn
n
i i ij ii
ji
m
a m a a i k n m
a a m a i j k n
b b m b i k n
a
b b a
b b a a i n n
计算乘数消元计算：
回代求解：
de t de t,
nn
a?
在 LU分解法中，若 时，计算无法进行，或者 绝对值很小时，按分解公式
0iiu?
iiu
计算时可能会引起舍入误差的增大，因此，
与 Gauss消去法一样，为了保证运算能顺利进行以及方法的稳定性，三角分解一般采用选列主元的技术，并称之为 Crout分解 。
Gauss-Jordan消去法
3
2
Gaus s J or dan A
n
消 去 对 角 线 下 方 和 上 方 的 元 素,此 方 法 称消 去 法 。 G-J 方 法 将 约 化 为 单 位矩 阵,计 算 解 就 在 常 数 项 得 到,无 需 回 代 求 解 。
计 算 量 大 约 需 次 乘 除 法,要 比 高 斯 消 去 法大 。 G-J 方 法 主 要 用 途 是 求 一 个 矩 阵 的 逆 矩 阵 。
1
1 2 3
2 4 5
3
5 G - J,
56
AA?
例,用 法 求 的 逆 矩 阵
1 2 3 1 0 0 3 5 6 0 0 1
| 2 4 5 0 1 0 2 4 5 0 1 0
5 6 0 0 1 1 23 10
30
n
AI
解,
5 / 3 2 0 0 1 / 3
0 1 0 1 2 / 3
0 1 / 3 1 1 0 1 / 3
2/
1
3
0 1 / 2 0 5 / 2 2
0 3 / 2 0 3 / 2 1
0 0 1 / 2 1 1 / 2 0
1
1
1
1
1
1
.
0 0 1 3 2
0 0 3 3 1 |
0 0 2 1 0
n
IA
Crammer法则
Gauss顺序消去法
Gauss-
Jordan
LU分解法
1 1 !n n n 321133n n n323
2 n O n? 3
1
3On
运算量比较
Gauss 消去法
矩阵三角分解法
对称矩阵的平方根法
三对角方程组的追赶法
向量与矩阵范数及方程组的性态
解线性方程组的迭代法
分快迭代法
§ 1.引言
n阶线性方程组：
可以表示成矩阵形式：
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
a x a x a x b
a x a x a x b
a x a x a x b
A X b?
,X,11
T
ij nn
TA
nn,,),,)( x ( bxbab
35
de t( ) 0,
d e t( )
( 1,2,,)
d e t( )
1
( 1 ) !
3 0,2,3 8 1 0
i
i
A
A
xi
n
n
A
n n n
n
n
n
每 个如 果 线 性 方 程 组 的 系 数 行 列 式 不 为 零,即则 该 方 程 组 有 唯 一 解 。 由 克 莱 姆 (Cramer) 法 则,其 解 为这 种 方 法 需 要 计 算 个 阶 行 列 式 并 作 次 除 法,而阶 行 列 式 计 算 需 作 次 乘 法,计 算 量 十 分 惊 人 。
如 需 3 1 2 9 3 0 ! = 次 乘 法 。 可 见 其
n
在 理 论上 是 绝 对 正 确,但 在 较 大 时,在 实 际 计 算 中 确 实 不 可 行 的 。
解线性方程组的两类方法：
直接法,经过有限次运算后可求得方程组精确解的方法 (不计舍入误差 ! ）
迭代法,从解的某个近似值出发，通过构造一个无穷序列去逼近精确解的方法。
（一般有限步内得不到精确解 )
§ 2,Gauss 消去法
简单消去法
Gauss顺序消去法的可行性及计算量
矩阵的三角分解法
主元素消去法
Gauss-Jordan列主元消去法一、简单消去法将 n阶线性方程组 转化为等价（或同解）的三角形方程组 11 1 12 2 1 1
22 2 2 2
nn
nn
nn n n
gb x b x b x
gb x b x
gbx
11,,,nnx x x?
的过程称为消元过程，逐次求出的步骤称为回代过程。
Gauss 消去法计算过程,
统一记号11
i j i j i i,a a b b
1 1 111 11
1
T
ijX,,n,,a bbAAbb
原方程为
1
11 0 a?
113 1 1 1 ( ( ) ( )) aa第 三 行 第 一 行 新 第 三 行
111 1 1
( )
( ) ( )
n
nn aa第 行 （ 第 一 行 ） 新 第 行相当于第 i个方程 -第一个方程 × 数 → 新的第 i方程 — 同解！第一方程不动！
1121 11( ) ( ) ( )aa第 二 行 （ 第 一 行 ） 新 第 二 行
Step1 假设上述消元过程除第一个方程不变以外,第 2—
第 n个方程全消去了变量?1，而系数和常数项全得到新值：
( 1 ) ( 1 ) ( 1 ) ( 1 ) ( 1 )
11 1 12 2 13 3 1 1
( 2 ) ( 2 ) ( 2 ) ( 2 )
22 2 23 3 2 2
( 2 ) ( 2 ) ( 2 ) ( 2 )
32 2 33 3 3 3
( 2 ) ( 2 )
2 2 3 3
nn
nn
nn
nn
a x a x a x a x b
a x a x a x b
a x a x a x b
a x a x
( 2 ) ( 2 )
nn n na x b
22 XA? （ ）（ ） b
1 1 1 1
1 1 1 2 1 1
2 2 2
( 2 )2
2 2 2 2
2 2 2
2
0
0
n
()
n
n n n n
a a a b
a a b
bA
a a b
，
2 1 1 2 1 1
1 1 1 1i j i j i j i i ia a l a,b b l b,
,2 3i j,,,n?
得到同解方程组为其中
11
1 1 1 1iil a a?
( 2 )
22 0 a?
Step2.若,保留方程组中第一及第二个方程，消去其余方程中变量 x3,得同解方程组
( 1 ) ( 1 ) ( 1 ) ( 1 ) ( 1 )
11 1 12 2 13 3 1 1
( 2 ) ( 2 ) ( 2 ) ( 2 )
22 2 23 3 2 2
( 3 ) ( 3 ) ( 3 )
33 3 3 3
(3
3
n
n
n
n
a x a x a x a b
a x a x a b
a x a b
) ( 3 ) ( 3 )
3 nn na x a b
( 1 ) ( 1 ) ( 1 ) ( 1 ) ( 1 )
11 12 13 1 1
( 2 ) ( 2 ) ( 2 ) ( 2 )
22 23 2 2
( 3)( 3 )
( 3 ) ( 3 ) ( 3 )
33 3 3
( 3 ) ( 3 ) ( 3 )
3
0
00
00
n
n
n
n nn n
a a a a b
a a a b
A a a b
a a b
,b
( 2 ) 2( 3 ) ( 2 ) 3 2
22,2 2
()( ) ( )
i j i j i ijiil a l ba a b b
34,,,,n ij?
( 3 )( 3 ) x bA?记作,其中
( 2 ) ( 2 )
2222 iila a?
( 3 )
33 0a?若,则 此 消 去 过 程 可 依 次 进 行 下 去 。
()()
1
nn
n
x bA
第 步 消 去 过 程 后,得 到 等 价 三 角 方 程 组 。
( 1 ) ( 1 ) ( 1 ) ( 1 ) ( 1 )
11 1 12 2 13 3 1 1
( 2 ) ( 2 ) ( 2 ) ( 2 )
22 2 23 3 2 2
( 3 ) ( 3 ) ( 3 )
33 3 3 3
nn
nn
nn
a x a x a x a x b
a x a x a x b
a x a x b
( ) ( )
nn
nn n na x b
( 1 ) ( 1 ) ( 1 ) ( 1 ) ( 1 )
11 12 13 1 1
( 2 ) ( 2 ) ( 2 ) ( 2 )
22 23 2 2
( n)()
( 3 ) ( 3 ) ( 3 )
33 3 3
( ) ( )
0
00
0 0 0
n
n
n
n
nn
nn n
a a a a b
a a a b
A a a b
ab
,b系数矩阵与常数项：
()() nnA,b计算出 的过程为消元过程。
消去过程算法
( 1 ) ( 1 ) ( 1 )
11 1 1
( ) ( ) ( ) ( )
1
n
k k k k
k k k k k n k
a a b
a a a b?
( 1 ) ( 1 )
0
0 1,
kk
ij j
k i j n
ab
11,,1 kkk k k k
i j i j i ik j k k i,j ni k i kl a l ba a b b
() 0,1k
ik k i na
1,2,,1kn
1 k i,j nk kkk
ikikla a?
回代过程算法
( 1 ) ( 1 ) ( 1 ) ( 1 )
11 1 1 1 1
( ) ( ) ( )
( 1 ) ( 1 ) ( 1 )
1 1 1 1 1
i i n n
i i i
ii i in n i
n n n
n n n n n n n
a x a x a x b
a x a x b
a x a x b
( ) ( )
nn
nn n na x b
( ) ( )nn
n n n nx b a?
( ) ( ) ( )
1
( ),
ni i i
i i i j j i i
ji
x b a x a
1,2,,1i n n对于
13
24
1 2 3 4
24
25
3
2 4 3 17
37
xx
xx
x x x x
xx
例 1,用消去法解方程组解：用增广矩阵表示求解过程
1 0 2 0 5
0 1 0 1 3
|
1 2 4 3 17
0 1 0 3 7
Ab
3 3 1 1
1 0 2 0 5
0 1 0 1 3
0 2 2 3 1 2
0 1 0 3 7
r l r?
3 32 2
4 42 2
1 0 2 0 5
0 1 0 1 3
0 0 2 1 6
0 0 0 2 4
r l r
r l r
4
/2
1 0 2 0 5
0 1 0 1 3
0 0 2 1 6
0 0 0 1 2
r
1 0 2 0 5
0 1 0 0 1
0 0 2 0 4
0 0 0 1 2
1 0 2 0 5
0 1 0 0 1
0 0 1 0 2
0 0 0 1 2
1 0 0 0 1
0 1 0 0 1
0 0 1 0 2
0 0 0 1 2
二,Gauss顺序消去法的可行性及计算量
Gauss消去和回代过程都要求元素
0 ( 1,2,,)k
kka k n
0k
kka?
称之为主元素。若,则计算无法进行。但在系数矩阵保持一定条件时，则可保证主元素非零，使 Gauss顺序消去法在计算机上顺利执行。
定理 1 若矩阵 A的各阶顺序主子式均不为零，即,则定理 2 若矩阵 A对称正定,则
de t 0kkDA
0 1,2,,k
kka k n
定理 3 若矩阵 A严格对角占优,则
0 1,2,,k
kka k n
0 1,2,,k
kka k n
矩阵 严格对角占优，若
ij nnAa
1
,1,2,,
n
i i i j
j
ji
a a i n
消去第一列的 n-1 个系数要计算 (n-1)+n*(n-1）
次乘法。
22
11
1
3
1
2
n
kk
n n
k k n ( n ) nk
Gauss消去法乘法计算量消去第二列的 n-2 个系数要计算 (n-2)+(n-1）
*(n-2） 次乘法。
……
乘法计算量
3
2 1 ( 3 0,9 8 9 0 )
33
n n n n 为
1
2
n( n )?回代过程总计算量
Gauss消去法乘除法总运算量为三,矩阵三角分解法
( 2 ) ( 1 )( 2 ) ( 1 )
11,bbA L A L
1121
1 1 11
311
1
1
1
01
23
0 0 1
L
( ) ( )
ii
n
i,,,n
l
l a a
l
l
其中每一步消去过程相当于左乘初等变换矩阵 Lk,记
22
2 2 2 2
32
( 3 ) ( 2 )(3
2
2
) ( 2 )
22
1
01
01
34
0 0 1
,
L
( ) ( )
ii
n
i,,,n
l
bbAL
a
l
A
l
L
a
记,
( 3 ) ( 1 )( 3 ) ( 1 )
2 1 2 1,bbA L L A L L
依此类推，得矩阵的 LU分解形式
1 1 1 1
1 2 1
( n ) ( n )
n LUA A L L L A L A
21
12
1
1
1
nn
L
l
ll
其中
1 1 1 2 1 3 1
2 2 2 3 2
3 3 3
0
0 0
0 0 0
n
n
n
nn
u u u u
u u u
uu
u
( 1 ) ( 1 ) ( 1 ) ( 1 )
1 1 1 2 1 3 1
( 2 ) ( 2 ) ( 2 )
2 2 2 3 2
( 3 ) ( 3 )
3 3 3
()
0
00
0 0 0
n
n
n
n
nn
U
a a a a
a a a
aa
a
L U x? b
方程组可写成若令
Ly? by Ux?
则上式变成则求解原方程组 Ax=b便转化为
Ly
U x y
b
上述矩阵分解法称为 Doolittle分解,计算公式为
11
1
1
,
( 2,3,,)i
i i i k k
k
yb
in
y b l y
1
,
( 1,2,,1 )
/
n n nn
n
i i ik k ii
ki
x y u
i n n
x y u x u
其中
11
1 1 11
1,2,,,
/ 2,3,,,
ii
ii
u a i n
l a a i n
1
1
1
1
,1,,,
/,1,2,,,,
r
r i r i r k k i
k
r
i r i r i k k r r r
k
u a l u i r r n
l a l u u i r r n r n
000
00
0
1
01
001
0001
44
3433
442322
14131211
434241
3231
21
44434241
34333231
24232221
14131211
u
uu
uuu
uuuu
lll
ll
l
aaaa
aaaa
aaaa
aaaa
uululululululululul
uululuululululul
uuluuluulul
uuuu
44344324421441334323421341224212411141
34243214313323321331223212311131
2414212313212212211121
14131211
++++++
+++++
+++
n.,3,i -; -,- 2
n,2,j,-; -,-,- u2
n,2,i,;,,1
n,1,j,;,,,1
2212i22i2
22124142422212313232
12122j
142124241321232312212222
111i1114141113131112121
11j1414131312121111
uulal
uulaluulal
ulau
ulauulauulau
ualualualual
auauauauau
)(
)()(l
l
u
i
jj
i
j
列行列行
()
() ( 1,2,,1 ; 1,,)
k
ik
ik k
kk
a
l k n i k n
a
得
3 1 3 2 4 21,2,1,l l l
其余全为 0。
例 2,对于 例 1，由增广矩阵表示消元过程，
有故有
1 0 2 0 1 1 0 2 0
0 1 0 1 0 1 1 0 1
1 2 4 3 1 2 1 2 1
0 1 0 3 0 1 0 1 2
A
1
2
3
4
15
0 1 3
1 2 1 17
0 1 0 1 7
y
y
Ly
y
y
1
2
3
4
5
3
6
4
y
y
y
y
1
2
3
4
1 0 2 0 5
1 0 1 3
2 1 6
24
x
x
Ux
x
x
1
2
3
4
1
1
2
2
x
x
x
x
1
2
3
1 2 3 1 4
2 5 2 1 8
3 1 5 2 0
1 0 0 1 2 3
2 1 0 0 1 4,
3 5 1
0 0 2 4
( 1 4,1 8,2 0 ) ( 1 4,1 0,7 2 ),
( 1 4,1 0,7 2 ) ( 1,2,3 ),
TT
TT
x
x
x
A L U
L y y
U x x
例 3,用 LU 三 角 分 解 法 解解,用 分 解 计 算 公 式 得求 解高斯主元素消去法
()
()
0
0
k
kk
k
kk
a
a
在 高 斯 法 消 元 过 程 中 可 能 出 现 的 情 况,
这 时 消 去 法 将 无 法 进 行 ； 即 使 主 元 素但 很 小,用 其 作 除 数,也 会 导 致 其 他 元 素 数量 级 的 严 重 增 长 和 舍 入 误 差 的 扩 散 。
例 1 在只取小数点后四位数字的条件下，
用 Gauss顺序消去法解方程组
12
12
0,0 0 0 3 3,0 0 0 0 2,0 0 0 1
1
xx
xx
解：
21
11 10000
0.00 03 3l
12
2
0,0 0 0 3 3,0 0 0 0 2,0 0 0 1
9 9 9 9 6 6 6 6
xx
x
由第二个方程可求出
2
6666 0.6667
9999
x
代入第一个方程可求出
1 2,0 0 0 1 0,6 6 6 7 3 / 0,0 0 0 3 0x
120,3 3 3 3,0,6 6 6 7xx
而方程组的准确解为设
,1,2i i ix x i
由第一个方程知因此
1 1 2 20,0 0 0 3 3,0 0 0 0 2,0 0 0 1xx
120,0 0 0 3 3,0 0 0 0 0
120,0 0 0 3 3,0 0 0 0 2,0 0 0 1xx
而于是，有
4
1210
小主元素是算法不稳定的主要原因。
( ) ( )
( ) ( )
( ) ( )
m a x{,,,1,,}
m a x{,,1,
kk
ik ik k k ik
kk
k k ij
kk
k k ik
G
i j k
aus
kn
ik
s
k
l a a l
aa
aa
为 避 免 此 种 情 况 的 发 生,可 通 过 交 换 方 程 的 次 序,
选 取 绝 对 值 大 的 元 素 作 主 元 。 基 于 这 种 想 法 导 出 了 主元 素 法 。 计 算 时 避 免 很 小,
主 元 素 消 去 法从 而 只 要 取称 为 ；
或
,}
G au s
n
s列 主称 为 。元 消 去 法
1
2
3
*
0,0 0 1 2,0 0 0 3,0 0 0 1,0 0 0
1,0 0 0 3,7 1 2 4,6 2 3 2,0 0 0
2,0 0 0 1,
0 7 2 5,6 4 3 3,0 0 0
( 0,
4 9 0 4,0,0 5 1 0 4,0,3 6 7 5 )
T
x
x
x
x
例,3 阶 方 程 组四 位 有 效 数 字 精 确 解 为
解,1 高 斯 消 去 法
32 1.997
0,0 0 1 2,0 0 0 3,0 0 0 1,0 0 0
0 2 0 0 4 3 0 0 5 1 0 0 2
0 4 0 0 1 6 0 0 6 2 0 0 3
l?
0,0 0 1 2,0 0 0 3,0 0 0 1,0 0 0
0 2 0 0 4 3 0 0 5 1 0 0 2
0 0 5,0 0 0 2,0 0 0
0,4 0 0
.0 9 9 8 9
0,4 0 0
x
21
31
1000
2000
0,0 0 1 2,0 0 0 3,0 0 0 1,0 0 0
| 1,0 0 0 3,7 1 2 4,6 2 3 2,0 0 0
2,0 0 0 1,0 7 2 5,6 4 3
3
.0
00
l
l
Ab
2（ ） 交 换 行,避 免 绝 对 值 小 的 主 元
（ 列 主 元作 除 数 。
素 法 ）
21
31
0,5 0 0 0
0,0 0 0 5
0,0 0 1 2,0 0 0 3,0 0 0 1,0 0 0
| 1,0 0 0 3,7 1 2 4,6 2 3 2,0 0 0
1,0 7 2 5,6 4 3 3,0 0 0
1,0 7 2 5,6 4 3 3,0 0 0
1,0 0 0 3,7 1 2 4,6 2 3 2,0 0 0
0,0 0 1 2,0 0 0 3,0 0 0 1,0 0
2,0 0
2,0 0 0
0
0
l
l
Ab
2,0 0 0 1,0 7 2 5,6 4 3 3,0 0 0
0 3,1 7 6 1,8 0 1 0,5 0 0
0 0 1,8 6 8 0,6 8 7
( 0,4 9 0 0,0,0 5 1 1 3,0,3 6 7 8 ) Tx
32 0.6297
2,00 05 / 3,17 60
2,0 0 0 1,0 7 2 5,6 4 3 3,0 0 0
0 1,8 0 1 5 0,5
0 2,0 0 0 5 3,0 0 2 8 1,0 0 1 5
3,1 7 6 0
l?
,
,,
,de t,
1,de t 1
1,2,,1 7
2
m a x,
3,0,de t 0,
4,5
(,
k
k
k
ij ij
i k ik
k i n
ik
k
k j i j
Ax b
A m a x
b
kn
aa
a
ik
a a j k
算法：（列主元素消去法）设消元结果冲掉 乘数 冲掉 计算解冲掉常数项 行列式值存放在对于 做到第 步。
,按列选主元素如果 则 计算停止。
如果 则转,否则换行：
1,,),,
de t de t
k
ki
k n b b
。
1
5.,
/ ( 1,,) ( 1 )
6,
(,1,,)
( 1,,)
7,de t de t,
8,
/ ;
( ) / ( 1,2,,1 ),
9,
ik
ik ik ik k k ik
ij ij ik k j
i i ik k
kk
n n nn
n
i i ij ii
ji
m
a m a a i k n m
a a m a i j k n
b b m b i k n
a
b b a
b b a a i n n
计算乘数消元计算：
回代求解：
de t de t,
nn
a?
在 LU分解法中，若 时，计算无法进行，或者 绝对值很小时，按分解公式
0iiu?
iiu
计算时可能会引起舍入误差的增大，因此，
与 Gauss消去法一样，为了保证运算能顺利进行以及方法的稳定性，三角分解一般采用选列主元的技术，并称之为 Crout分解 。
Gauss-Jordan消去法
3
2
Gaus s J or dan A
n
消 去 对 角 线 下 方 和 上 方 的 元 素,此 方 法 称消 去 法 。 G-J 方 法 将 约 化 为 单 位矩 阵,计 算 解 就 在 常 数 项 得 到,无 需 回 代 求 解 。
计 算 量 大 约 需 次 乘 除 法,要 比 高 斯 消 去 法大 。 G-J 方 法 主 要 用 途 是 求 一 个 矩 阵 的 逆 矩 阵 。
1
1 2 3
2 4 5
3
5 G - J,
56
AA?
例,用 法 求 的 逆 矩 阵
1 2 3 1 0 0 3 5 6 0 0 1
| 2 4 5 0 1 0 2 4 5 0 1 0
5 6 0 0 1 1 23 10
30
n
AI
解,
5 / 3 2 0 0 1 / 3
0 1 0 1 2 / 3
0 1 / 3 1 1 0 1 / 3
2/
1
3
0 1 / 2 0 5 / 2 2
0 3 / 2 0 3 / 2 1
0 0 1 / 2 1 1 / 2 0
1
1
1
1
1
1
.
0 0 1 3 2
0 0 3 3 1 |
0 0 2 1 0
n
IA
Crammer法则
Gauss顺序消去法
Gauss-
Jordan
LU分解法
1 1 !n n n 321133n n n323
2 n O n? 3
1
3On
运算量比较
