第一章, 解线性代数方程组的直接方法
§ 1.引言
11 1 12 2 1 1
21 1 22 2 2 2
1 1 2 2
nn
nn
n n nn n n
n
a x a x a x b
a x a x a x b
a x a x a x b
? ? ? ??
?
? ? ? ??
?
?
?
? ? ? ?
?
L
L
L
L
阶线性方程组:
[ ],X,
11
T
nnij
A X b
T
A nn,,),,)( x ( bxbab?
?
? ? ?LL
矩阵表示记为
这里
35
d e t( ) 0,
d e t( )
( 1,2,,)
d e t( )
1
( 1 ) !
3 0,2,3 8 1 0
i
i
A
A
x i n
A
n n n
n n n
n
n
?
??
?
??
??
L
如果线性方程组的系数行列式不为零,即
则该方程组有唯一解。由克莱姆(c ra me r) 法则,其解为
这种方法需要计算 个 阶行列式并作 次除法,而每个
阶行列式计算需作 次乘法,计算量十分惊人。
如 需 次乘法。可见其在理论上是绝对正确,
但在 较 大时,在实际计算中确实不可行的。
解线性方程组的两类方法,
直接法, 经过有限次运算后可求得方程组精确解的方法
(不计舍入误差 !)
迭代法:从解的某个近似值出发,通过构造一个无穷序列
去逼近精确解的方法。(一般有限步内得不到精确解)
§ 2,Gauss 消去法
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
? ? ? ?
?
? ??
?
?
?
?
??
?
?
?
L
L
L
转化为等价的(同解)的三角形方程组。
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
? ? ? ??
?
? ? ? ??
?
?
? ? ? ? ?
?
L
L
L
L
对 阶线性方程组:
11,,,nnx x x? L称消元过程。逐次计算出 称回代过程。
→ → 11 b b,a a )(ii)(ijij统一记号:
1 1 111 1 1
1
T( ) ( ) ( )( ) ( )
ij
() () X, [ ],n(,,)b a bAA bb? ? ? L原方程
)( → )(
,0≠
1
11
1
21
)1(
11
新第二行(第一行)第二行
若
aa
a
)()(??
)( → )()( 111131 新第三行第一行第三行 aa )()(??
)n(n aa )()(n 行新第(第一行)行第 → )(
1
11
1
1??
??
相当于第 i个方程 -第一个方程 × 数 → 新的第 i方
程 — 同解!第一方程不动!
一,Gauss 消去法计算过程
上述消元过程除第一个方程不变以外,
第 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
? ? ? ? ?
? ? ? ?
? ? ? ?
??
L
L
L
LL
L
( 2 ) ( 2 )
nn n na x b
?
?
?
?
?
?
?
?
?
??
?
?
22 x bA ? ()()得到新同解方程组:
b
b
b
b
aa
aa
aaa
A
)(
n
)(
)(
)(
nn
)(
n
)(
n
)(
)(
n
)()(
)(
2
2
2
1
1
( 2 )
22
2
2
2
2
22
1
1
1
12
1
11
2
0
0
?
?
??
?
?
==,其中
aamamaa )()(ii)( ji)(ij)(ij 11111111112 ???这里
2 1 1
11 23,
( ) ( ) ( )
i i i,,,n ijb b b m? ? ? ? L
( 2 )
22
0 a ?第二步消元,若,对除第一行第一列外
的子阵作计算:
00
00
0
3
3
3
2
2
1
1
( 3 )
33
3
3
3
3
33
2
2
2
23
2
22
1
1
1
13
1
12
1
11
3
b
b
b
b
b
aa
aa
aaa
aaaa
A
)(
n
)(
)(
)(
)(
nn
)(
n
)(
n
)(
)(
n
)()(
)(
n
)()()(
)(
?
?
????
?
?
?
==,
aamamaa ijijij )2(22)2( 2i2)2(2i2)2()3( ???
3 2 2
22 34,
( ) ( ) ( )
i i i,,,n ijb b b m? ? ? ? L
bxA )()( 33 =得到同解方程组
( 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
? ? ? ? ?
? ? ? ?
? ? ?
L
L
L
M
) ( 3 ) ( 3 )
3 nn na x a b
?
?
?
?
?
?
?
?
?
? ? ?
?
?
L
行下去。则此消去过程可依次进,若 0 333 ≠a )(
()()
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
? ? ? ? ?
? ? ? ?
? ? ?
L
L
L
LL
( ) ( )
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
b
n
n
n
n
nn
nn n
a a a a b
a a a b
A a a b
ab
? ? ? ?
? ? ? ?
? ? ? ?
? ? ? ?
??
? ? ? ?
? ? ? ?
? ? ? ?
? ? ? ?
? ? ? ?
L
L
L
M M M M M
L
,系数矩阵与常数项,
的过程称消去过程。,计算出 bA )n()n(
消去过程算法
( 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?
L
O M M
L
( 1 ) ( 1 )
0
0 k 1 i,j n
kk
ij jab
??
? ? ?
L
M
ni,j≤ ) k(
)(
aabbb
aaaaa
( k )
kk
( k )
ik
( k )
k
( k )
i
)(k
i
( k )
kk
( k )
ik
( k )
kj
( k )
ij
)(k
ij
????
??
?
?
11
1
() 0 k 1 i n k
ika ? ? ? ?
1n,,2,1 ?? ?k
回代过程算法
( 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
? ? ?
? ? ? ? ?
? ? ? ? ?
? ? ? ?
??
LL
LL
LL
LL
( ) ( )
nn
nn n na x b
?
?
?
?
??
?
?
?
?
?
?
??
abx )n(nn)n(nn =
( ) ( ) ( )
1
( ) i n 1,n 2,,1
n
i i i
i i i j j i i
ji
x b a x a
??
? ? ? ? ?? L
? ?
1 2 3
23
1 2 3
3 1 3 3 2 3
6;
4 5 ;
2 2 1.
1 1 1 6 1 1 1 6
| 0 4 1 5 0 4 1 5
2 2 1 1 0 4 1 11
1 1 1 6
0 4 1 5
0 0 2 6
2,( 1 )
x x x
xx
x x x
Ab
r r r r r r
? ? ??
?
??
?
?
? ? ?
?
? ? ? ?
? ? ? ?
? ? ? ?
? ? ? ?
? ? ? ?? ? ? ?
? ? ? ?
??
??
??
??
?? ??
??
? ? ? ? ? ?
例1,用消去法解方程组
解:用增广矩阵表示求解过程
消去第一列的 n-1 个系数要计算 n*(n-1) 个乘法。
????????? 1 2 2 )n()*( n -n ??二
)n(
n
k)k (
n
k
1
3
∑ 2
1
2 ???
?
总计
2
1 ∑ 1
1
)n ( n k n
k
???
?
除法
1
2
n ( n ) ?回代总计算量
3
2 1 ( 3 0,9 8 9 0 )
33
n nn n? ? ?总乘除法共 为
二,Gauss消去法乘除法计算量
( 2 ) ( 1 )( 2 ) ( 1 )
11
1121
1 1 1 1
311
1
,
1
1
01
23
0 0 1
L
( ) ( )
ii
n
i,,,n
bbA L A L
m
m a a
m
m
??
??
??
?
??
????
?? ?
??
??
?
??
?
L
LL
L
记:
其中
每一步消去过程相当于左乘初等变换矩阵 Lk
三,Gauss消去法的矩阵表示
( 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
m a a
m
m
??
??
??
??
?? ??
?? ?
??
??
??
?
?
L
LL
L
记:
( 3 ) ( 1 )( 3 ) ( 1 )
2 1 2 1,bbA L L A L L??
-1
iiLL与
1
1 2 1
1
1 2 1
( n ) ( )
nn
( n ) ( )
nn
A L L L A
bb L L L
??
??
?
?
L
L
-1
i
1,
1,
1
1
01
01
1
1
01
01
01
01
i
i
ii
ii
ni
ni
LL
m
m
m
m
?
?
??
?? ??
??
?? ??
??
???? ??
??
?? ??
??
????
??
?
?
MO
M
M
L
M M M O
M M O
列 i 列
i+1
行
i+1行
LU形式
1 1 1 1
1 2 1
( ) ( n ) ( n )
n L L UA L L L A A
? ? ?
?? ? ?L
1 1 1
1 2 1nL L L L
? ? ?
?? L
1
1
1
21
21
?
??
mm
m
nn
L ?
1
1
1
10
10
1
10
1
1
2231
21
2231
21
mm
m
mm
m =
? ?
()
()
21 31 32
1
1 1 1 6 1 1 1 6
| 0 4 1 5 0 4 1 5
2 2 1 1 0 4 1 11
1 1 1 6
0 4 1 5
0 0 2 6
( 1,,)
0,2,1,
k
ik
kik
kk
Ab
a
m i k n
a
m m m
? ? ? ?
? ? ? ?
? ? ? ?
? ? ? ?
? ? ? ?? ? ? ?
? ? ? ?
??
??
??
??
?? ??
??
? ? ?
? ? ? ? ?
L
例2:对于例,由增广矩阵表示消元过程有
由
故有
1 0 0 1 1 1
0 1 0 0 4 1,
2 1 1 0 0 2
A L U
? ? ? ?
? ? ? ?
? ? ?
? ? ? ?
? ? ? ???
? ? ? ?
( ) ( )
( ) ( )
( ) ( )
m a x{,i,j k,k 1,,n }
m a x{,i k,k 1
kk
ik ik k k ik
kk
k k ij
kk
k k ik
G auss
m a a m
aa
aa
?
? ? ?
? ? ?
L
为避免此种情况的发生,可通过交换方程的次序,选取
绝对值大的元素作主元。基于这种想法导出了主元素法。
时避免 过大,从而只要取
称主元素 消去法;
或,,n }
G auss
L
称列主元 消去法。
§ 3,高斯主元素消去法
()
()
0
0
k
kk
k
kk
a
a
?
?
在高斯法消元过程中可能出现 的情况,这时消去法
将无法进行;即使主元素 但很小,用其作除数,也会
导致其他元素数量级的严重增长和舍入误差的扩散。
? ?
1
2
3
*
0.001 2.000 3.000 1.000
3 1.000 3.712 4.623 2.000
2.000 1.072 5.643 3.000
( 0.4904,0.05104,0.3675 )
1
0.001 2.000 3.000 1.000
| 1.00
T
x
x
x
x
Ab
? ? ? ? ? ?
? ? ? ? ? ?
??
? ? ? ? ? ?
? ? ? ? ? ??
? ? ? ? ? ?
? ? ?
??
例,三阶方程组
四位有效数字精确解为
解:( )高斯消去法
21
31
32
1000
2000
1.997
0 3.712 4.623 2.000
2.000 1.072 5.643 3.000
0.001 2.000 3.000 1.000 0.001 2.000 3.000 1.000
0 2004 3005 1002 0 2004 3005 1002
0 4001 6006 2003 0 0 5.000 2.000
(0
m
m
m
x
??
??
?
??
??
?????
??
???
??
? ? ? ?
? ? ? ?
?????
? ? ? ?
? ? ? ?
? ? ? ?
??,400,0.09989,0.4000)
T
?
? ?
21
31
0,5000
0,0005
2
2.0 00 1.0 72 5.6 43 3.0 00
| 1.0 00 3.7 12 4.6 23 2.0 00
0.0 01 2.0 00 3.0 00 1.0 00
2.0 00 1.0 72 5.6 43 3.0 00
0 3.7 12 1.8 01 0.5 00
0 2.0 01 3.0 03 1.0 02
m
m
Ab
?
??
???
??
? ? ??????
??
??
??
???
?
?
?
??
( )交换行,避免绝对值小的主元作除数。(列主元素法)
32
0,6300
2.0 00 1.0 72 5.6 43 3.0 00
0 3.712 1.801 0,500
0 0 1.8 68 0.6 87
( 0.4900,0.05113,0.3678 )
m
T
x
??
?????
?
?
???
??
??
??
??
? ? ?
,
,,
,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
??
?
?
??
?
??
?
??
L
算法:(列主元素消去法)设
消元结果冲掉 乘数 冲掉 计算解
冲掉常数项 行列式值存放在
对于 做到第 步。
,按列选主元素
如果 则 计算停止。
如果 则转, 否则换行:
1,,),,
de t de t
k
ki
k n b b??
??
L
。
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
??
? ? ? ? ?
? ? ? ?
? ? ? ?
?
?
? ? ? ? ?
?
L
L
L
L
计算乘数
消元计算:
回代求解:
de t de t,
nn
a?
高斯 — 若当消去法
3
2
G a u s s J o r d a n
A
n
?消去对角线下方和上方的元素,此方法称
消去法。G - J 方法将 约化为单位矩阵,计算解就在常数项
得到,无需回代求解。计算量大约需 次乘除法,要比高
斯消去法大。G - J 方法主要用途是求一个矩阵的逆矩阵。
? ?
1
1 2 3
5 G - J 2 4 5,
356
1 2 3 1 0 0 3 5 6 0 0 1
| 2 4 5 0 1 0 2 4 5 0 1 0
3 5 6 0 0 1 1 2 3 1 0 0
n
AA
AI
?
??
??
?
??
??
??
? ? ? ?
? ? ? ?
??
? ? ? ?
? ? ? ?
? ? ? ?
例,用 法求 的逆矩阵
解:
? ?
1
1 5 / 3 2 0 0 1 / 3
0 2 / 3 1 0 1 2 / 3
0 1 / 3 1 1 0 1 / 3
1 0 1 / 2 0 5 / 2 2
0 1 3 / 2 0 3 / 2 1
0 0 1 / 2 1 1 / 2 0
1 0 0 1 3 2
0 1 0 3 3 1 |,
0 0 1 2 1 0
n
IA
?
??
??
??
??
?? ?
??
????
??
??
??
?? ?
??
???
??
? ? ? ?
??
?? ?
??
§ 4,高斯消去法的变形
一,LU 分解
1 1 1 1
1 2 1
( ) ( n ) ( n )
n L L UA L L L A A
? ? ?
?? ? ?L
1 1 1
1 2 1nL L L L
? ? ?
?? L
1
1
1
21
21
?
??
mm
m
nn
L ?
( 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
b
n
n
n
n
nn
nn n
a a a a b
a a a b
A a a b
ab
? ? ? ?
? ? ? ?
? ? ? ?
? ? ? ?
??
? ? ? ?
? ? ? ?
? ? ? ?
? ? ? ?
? ? ? ?
L
L
L
M M M M M
L
,
设 A为 n阶方阵,若 A的顺序主子式 Ai均不为零,
则矩阵存在唯一的 LU(Doolittle 杜利特尔)分解。
11 12 1n
21 22 2n
31 32
1 2 ( 1) nn
(
1
1
1 U
1
n n n n
G auss L U
A L U
L
u u u
l uu
ll
l l l u?
?
?? ??
?? ??
?? ??
?? ??
??
?? ??
?? ??
?? ??
????
L
L
LL L L L
由 消去法加上列主元 或全主元)有 分解:
直接计算 A 的 LU 分解 (例 )
??
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
++++++
+++++
+++
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
列
行
列
行
一般计算公式
n,2,i,
n,1,j,
111i1
11
?
?
==
==
ual
au
i
jj
n,,1ki )/ (
n,,k j
,,3,2
kk
1-k
1m
imik
1-k
1m
kmkj
∑
∑
?
?
?
????
???
?
?
?
uulal
ulau
mkik
mjkj
nk 计算对
计算量与 Gauss 消去法同,
LU 分解求解线性方程组
L Y b,U X Y A X L U X b? ? ? ? ?
11
2221
31 32
1 2 ( 1)
11
11 12 1n
22
22 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
?
?? ? ? ? ?
?? ? ? ? ?
?? ? ? ? ?
?? ? ? ? ?
? ? ?
?? ? ? ? ?
?? ? ? ? ?
? ? ? ???
? ? ? ???
?? ? ? ? ?
?? ? ? ? ?
?? ? ? ? ?
?? ? ? ? ?
? ? ?
?? ? ? ? ?
?? ? ? ? ?
? ? ? ???
? ? ? ???
LL
L
L
L L L
11
-1
1
,2,3,,
1,Y
i
i ijij
j
in
y b
yy bl
?
?
? ? ?? L
解:
1
ij ii
,
i n 1,,1
2,x
nnnn
i
ij i
jn
yx u
yx u x u
?
?
?
??
????
??
??
?
L
解:
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
? ? ? ? ? ?
? ? ? ? ? ?
?
? ? ? ? ? ?
? ? ? ? ? ?
? ? ? ? ? ?
? ? ? ?
? ? ? ?
? ? ?
? ? ? ?
? ? ? ???
? ? ? ?
? ? ? ? ?
? ? ? ? ?
例:用L U 三角分解法解
解:用分解计算公式得
求解
§ 1.引言
11 1 12 2 1 1
21 1 22 2 2 2
1 1 2 2
nn
nn
n n nn n n
n
a x a x a x b
a x a x a x b
a x a x a x b
? ? ? ??
?
? ? ? ??
?
?
?
? ? ? ?
?
L
L
L
L
阶线性方程组:
[ ],X,
11
T
nnij
A X b
T
A nn,,),,)( x ( bxbab?
?
? ? ?LL
矩阵表示记为
这里
35
d e t( ) 0,
d e t( )
( 1,2,,)
d e t( )
1
( 1 ) !
3 0,2,3 8 1 0
i
i
A
A
x i n
A
n n n
n n n
n
n
?
??
?
??
??
L
如果线性方程组的系数行列式不为零,即
则该方程组有唯一解。由克莱姆(c ra me r) 法则,其解为
这种方法需要计算 个 阶行列式并作 次除法,而每个
阶行列式计算需作 次乘法,计算量十分惊人。
如 需 次乘法。可见其在理论上是绝对正确,
但在 较 大时,在实际计算中确实不可行的。
解线性方程组的两类方法,
直接法, 经过有限次运算后可求得方程组精确解的方法
(不计舍入误差 !)
迭代法:从解的某个近似值出发,通过构造一个无穷序列
去逼近精确解的方法。(一般有限步内得不到精确解)
§ 2,Gauss 消去法
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
? ? ? ?
?
? ??
?
?
?
?
??
?
?
?
L
L
L
转化为等价的(同解)的三角形方程组。
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
? ? ? ??
?
? ? ? ??
?
?
? ? ? ? ?
?
L
L
L
L
对 阶线性方程组:
11,,,nnx x x? L称消元过程。逐次计算出 称回代过程。
→ → 11 b b,a a )(ii)(ijij统一记号:
1 1 111 1 1
1
T( ) ( ) ( )( ) ( )
ij
() () X, [ ],n(,,)b a bAA bb? ? ? L原方程
)( → )(
,0≠
1
11
1
21
)1(
11
新第二行(第一行)第二行
若
aa
a
)()(??
)( → )()( 111131 新第三行第一行第三行 aa )()(??
)n(n aa )()(n 行新第(第一行)行第 → )(
1
11
1
1??
??
相当于第 i个方程 -第一个方程 × 数 → 新的第 i方
程 — 同解!第一方程不动!
一,Gauss 消去法计算过程
上述消元过程除第一个方程不变以外,
第 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
? ? ? ? ?
? ? ? ?
? ? ? ?
??
L
L
L
LL
L
( 2 ) ( 2 )
nn n na x b
?
?
?
?
?
?
?
?
?
??
?
?
22 x bA ? ()()得到新同解方程组:
b
b
b
b
aa
aa
aaa
A
)(
n
)(
)(
)(
nn
)(
n
)(
n
)(
)(
n
)()(
)(
2
2
2
1
1
( 2 )
22
2
2
2
2
22
1
1
1
12
1
11
2
0
0
?
?
??
?
?
==,其中
aamamaa )()(ii)( ji)(ij)(ij 11111111112 ???这里
2 1 1
11 23,
( ) ( ) ( )
i i i,,,n ijb b b m? ? ? ? L
( 2 )
22
0 a ?第二步消元,若,对除第一行第一列外
的子阵作计算:
00
00
0
3
3
3
2
2
1
1
( 3 )
33
3
3
3
3
33
2
2
2
23
2
22
1
1
1
13
1
12
1
11
3
b
b
b
b
b
aa
aa
aaa
aaaa
A
)(
n
)(
)(
)(
)(
nn
)(
n
)(
n
)(
)(
n
)()(
)(
n
)()()(
)(
?
?
????
?
?
?
==,
aamamaa ijijij )2(22)2( 2i2)2(2i2)2()3( ???
3 2 2
22 34,
( ) ( ) ( )
i i i,,,n ijb b b m? ? ? ? L
bxA )()( 33 =得到同解方程组
( 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
? ? ? ? ?
? ? ? ?
? ? ?
L
L
L
M
) ( 3 ) ( 3 )
3 nn na x a b
?
?
?
?
?
?
?
?
?
? ? ?
?
?
L
行下去。则此消去过程可依次进,若 0 333 ≠a )(
()()
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
? ? ? ? ?
? ? ? ?
? ? ?
L
L
L
LL
( ) ( )
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
b
n
n
n
n
nn
nn n
a a a a b
a a a b
A a a b
ab
? ? ? ?
? ? ? ?
? ? ? ?
? ? ? ?
??
? ? ? ?
? ? ? ?
? ? ? ?
? ? ? ?
? ? ? ?
L
L
L
M M M M M
L
,系数矩阵与常数项,
的过程称消去过程。,计算出 bA )n()n(
消去过程算法
( 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?
L
O M M
L
( 1 ) ( 1 )
0
0 k 1 i,j n
kk
ij jab
??
? ? ?
L
M
ni,j≤ ) k(
)(
aabbb
aaaaa
( k )
kk
( k )
ik
( k )
k
( k )
i
)(k
i
( k )
kk
( k )
ik
( k )
kj
( k )
ij
)(k
ij
????
??
?
?
11
1
() 0 k 1 i n k
ika ? ? ? ?
1n,,2,1 ?? ?k
回代过程算法
( 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
? ? ?
? ? ? ? ?
? ? ? ? ?
? ? ? ?
??
LL
LL
LL
LL
( ) ( )
nn
nn n na x b
?
?
?
?
??
?
?
?
?
?
?
??
abx )n(nn)n(nn =
( ) ( ) ( )
1
( ) i n 1,n 2,,1
n
i i i
i i i j j i i
ji
x b a x a
??
? ? ? ? ?? L
? ?
1 2 3
23
1 2 3
3 1 3 3 2 3
6;
4 5 ;
2 2 1.
1 1 1 6 1 1 1 6
| 0 4 1 5 0 4 1 5
2 2 1 1 0 4 1 11
1 1 1 6
0 4 1 5
0 0 2 6
2,( 1 )
x x x
xx
x x x
Ab
r r r r r r
? ? ??
?
??
?
?
? ? ?
?
? ? ? ?
? ? ? ?
? ? ? ?
? ? ? ?
? ? ? ?? ? ? ?
? ? ? ?
??
??
??
??
?? ??
??
? ? ? ? ? ?
例1,用消去法解方程组
解:用增广矩阵表示求解过程
消去第一列的 n-1 个系数要计算 n*(n-1) 个乘法。
????????? 1 2 2 )n()*( n -n ??二
)n(
n
k)k (
n
k
1
3
∑ 2
1
2 ???
?
总计
2
1 ∑ 1
1
)n ( n k n
k
???
?
除法
1
2
n ( n ) ?回代总计算量
3
2 1 ( 3 0,9 8 9 0 )
33
n nn n? ? ?总乘除法共 为
二,Gauss消去法乘除法计算量
( 2 ) ( 1 )( 2 ) ( 1 )
11
1121
1 1 1 1
311
1
,
1
1
01
23
0 0 1
L
( ) ( )
ii
n
i,,,n
bbA L A L
m
m a a
m
m
??
??
??
?
??
????
?? ?
??
??
?
??
?
L
LL
L
记:
其中
每一步消去过程相当于左乘初等变换矩阵 Lk
三,Gauss消去法的矩阵表示
( 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
m a a
m
m
??
??
??
??
?? ??
?? ?
??
??
??
?
?
L
LL
L
记:
( 3 ) ( 1 )( 3 ) ( 1 )
2 1 2 1,bbA L L A L L??
-1
iiLL与
1
1 2 1
1
1 2 1
( n ) ( )
nn
( n ) ( )
nn
A L L L A
bb L L L
??
??
?
?
L
L
-1
i
1,
1,
1
1
01
01
1
1
01
01
01
01
i
i
ii
ii
ni
ni
LL
m
m
m
m
?
?
??
?? ??
??
?? ??
??
???? ??
??
?? ??
??
????
??
?
?
MO
M
M
L
M M M O
M M O
列 i 列
i+1
行
i+1行
LU形式
1 1 1 1
1 2 1
( ) ( n ) ( n )
n L L UA L L L A A
? ? ?
?? ? ?L
1 1 1
1 2 1nL L L L
? ? ?
?? L
1
1
1
21
21
?
??
mm
m
nn
L ?
1
1
1
10
10
1
10
1
1
2231
21
2231
21
mm
m
mm
m =
? ?
()
()
21 31 32
1
1 1 1 6 1 1 1 6
| 0 4 1 5 0 4 1 5
2 2 1 1 0 4 1 11
1 1 1 6
0 4 1 5
0 0 2 6
( 1,,)
0,2,1,
k
ik
kik
kk
Ab
a
m i k n
a
m m m
? ? ? ?
? ? ? ?
? ? ? ?
? ? ? ?
? ? ? ?? ? ? ?
? ? ? ?
??
??
??
??
?? ??
??
? ? ?
? ? ? ? ?
L
例2:对于例,由增广矩阵表示消元过程有
由
故有
1 0 0 1 1 1
0 1 0 0 4 1,
2 1 1 0 0 2
A L U
? ? ? ?
? ? ? ?
? ? ?
? ? ? ?
? ? ? ???
? ? ? ?
( ) ( )
( ) ( )
( ) ( )
m a x{,i,j k,k 1,,n }
m a x{,i k,k 1
kk
ik ik k k ik
kk
k k ij
kk
k k ik
G auss
m a a m
aa
aa
?
? ? ?
? ? ?
L
为避免此种情况的发生,可通过交换方程的次序,选取
绝对值大的元素作主元。基于这种想法导出了主元素法。
时避免 过大,从而只要取
称主元素 消去法;
或,,n }
G auss
L
称列主元 消去法。
§ 3,高斯主元素消去法
()
()
0
0
k
kk
k
kk
a
a
?
?
在高斯法消元过程中可能出现 的情况,这时消去法
将无法进行;即使主元素 但很小,用其作除数,也会
导致其他元素数量级的严重增长和舍入误差的扩散。
? ?
1
2
3
*
0.001 2.000 3.000 1.000
3 1.000 3.712 4.623 2.000
2.000 1.072 5.643 3.000
( 0.4904,0.05104,0.3675 )
1
0.001 2.000 3.000 1.000
| 1.00
T
x
x
x
x
Ab
? ? ? ? ? ?
? ? ? ? ? ?
??
? ? ? ? ? ?
? ? ? ? ? ??
? ? ? ? ? ?
? ? ?
??
例,三阶方程组
四位有效数字精确解为
解:( )高斯消去法
21
31
32
1000
2000
1.997
0 3.712 4.623 2.000
2.000 1.072 5.643 3.000
0.001 2.000 3.000 1.000 0.001 2.000 3.000 1.000
0 2004 3005 1002 0 2004 3005 1002
0 4001 6006 2003 0 0 5.000 2.000
(0
m
m
m
x
??
??
?
??
??
?????
??
???
??
? ? ? ?
? ? ? ?
?????
? ? ? ?
? ? ? ?
? ? ? ?
??,400,0.09989,0.4000)
T
?
? ?
21
31
0,5000
0,0005
2
2.0 00 1.0 72 5.6 43 3.0 00
| 1.0 00 3.7 12 4.6 23 2.0 00
0.0 01 2.0 00 3.0 00 1.0 00
2.0 00 1.0 72 5.6 43 3.0 00
0 3.7 12 1.8 01 0.5 00
0 2.0 01 3.0 03 1.0 02
m
m
Ab
?
??
???
??
? ? ??????
??
??
??
???
?
?
?
??
( )交换行,避免绝对值小的主元作除数。(列主元素法)
32
0,6300
2.0 00 1.0 72 5.6 43 3.0 00
0 3.712 1.801 0,500
0 0 1.8 68 0.6 87
( 0.4900,0.05113,0.3678 )
m
T
x
??
?????
?
?
???
??
??
??
??
? ? ?
,
,,
,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
??
?
?
??
?
??
?
??
L
算法:(列主元素消去法)设
消元结果冲掉 乘数 冲掉 计算解
冲掉常数项 行列式值存放在
对于 做到第 步。
,按列选主元素
如果 则 计算停止。
如果 则转, 否则换行:
1,,),,
de t de t
k
ki
k n b b??
??
L
。
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
??
? ? ? ? ?
? ? ? ?
? ? ? ?
?
?
? ? ? ? ?
?
L
L
L
L
计算乘数
消元计算:
回代求解:
de t de t,
nn
a?
高斯 — 若当消去法
3
2
G a u s s J o r d a n
A
n
?消去对角线下方和上方的元素,此方法称
消去法。G - J 方法将 约化为单位矩阵,计算解就在常数项
得到,无需回代求解。计算量大约需 次乘除法,要比高
斯消去法大。G - J 方法主要用途是求一个矩阵的逆矩阵。
? ?
1
1 2 3
5 G - J 2 4 5,
356
1 2 3 1 0 0 3 5 6 0 0 1
| 2 4 5 0 1 0 2 4 5 0 1 0
3 5 6 0 0 1 1 2 3 1 0 0
n
AA
AI
?
??
??
?
??
??
??
? ? ? ?
? ? ? ?
??
? ? ? ?
? ? ? ?
? ? ? ?
例,用 法求 的逆矩阵
解:
? ?
1
1 5 / 3 2 0 0 1 / 3
0 2 / 3 1 0 1 2 / 3
0 1 / 3 1 1 0 1 / 3
1 0 1 / 2 0 5 / 2 2
0 1 3 / 2 0 3 / 2 1
0 0 1 / 2 1 1 / 2 0
1 0 0 1 3 2
0 1 0 3 3 1 |,
0 0 1 2 1 0
n
IA
?
??
??
??
??
?? ?
??
????
??
??
??
?? ?
??
???
??
? ? ? ?
??
?? ?
??
§ 4,高斯消去法的变形
一,LU 分解
1 1 1 1
1 2 1
( ) ( n ) ( n )
n L L UA L L L A A
? ? ?
?? ? ?L
1 1 1
1 2 1nL L L L
? ? ?
?? L
1
1
1
21
21
?
??
mm
m
nn
L ?
( 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
b
n
n
n
n
nn
nn n
a a a a b
a a a b
A a a b
ab
? ? ? ?
? ? ? ?
? ? ? ?
? ? ? ?
??
? ? ? ?
? ? ? ?
? ? ? ?
? ? ? ?
? ? ? ?
L
L
L
M M M M M
L
,
设 A为 n阶方阵,若 A的顺序主子式 Ai均不为零,
则矩阵存在唯一的 LU(Doolittle 杜利特尔)分解。
11 12 1n
21 22 2n
31 32
1 2 ( 1) nn
(
1
1
1 U
1
n n n n
G auss L U
A L U
L
u u u
l uu
ll
l l l u?
?
?? ??
?? ??
?? ??
?? ??
??
?? ??
?? ??
?? ??
????
L
L
LL L L L
由 消去法加上列主元 或全主元)有 分解:
直接计算 A 的 LU 分解 (例 )
??
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
++++++
+++++
+++
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
列
行
列
行
一般计算公式
n,2,i,
n,1,j,
111i1
11
?
?
==
==
ual
au
i
jj
n,,1ki )/ (
n,,k j
,,3,2
kk
1-k
1m
imik
1-k
1m
kmkj
∑
∑
?
?
?
????
???
?
?
?
uulal
ulau
mkik
mjkj
nk 计算对
计算量与 Gauss 消去法同,
LU 分解求解线性方程组
L Y b,U X Y A X L U X b? ? ? ? ?
11
2221
31 32
1 2 ( 1)
11
11 12 1n
22
22 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
?
?? ? ? ? ?
?? ? ? ? ?
?? ? ? ? ?
?? ? ? ? ?
? ? ?
?? ? ? ? ?
?? ? ? ? ?
? ? ? ???
? ? ? ???
?? ? ? ? ?
?? ? ? ? ?
?? ? ? ? ?
?? ? ? ? ?
? ? ?
?? ? ? ? ?
?? ? ? ? ?
? ? ? ???
? ? ? ???
LL
L
L
L L L
11
-1
1
,2,3,,
1,Y
i
i ijij
j
in
y b
yy bl
?
?
? ? ?? L
解:
1
ij ii
,
i n 1,,1
2,x
nnnn
i
ij i
jn
yx u
yx u x u
?
?
?
??
????
??
??
?
L
解:
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
? ? ? ? ? ?
? ? ? ? ? ?
?
? ? ? ? ? ?
? ? ? ? ? ?
? ? ? ? ? ?
? ? ? ?
? ? ? ?
? ? ?
? ? ? ?
? ? ? ???
? ? ? ?
? ? ? ? ?
? ? ? ? ?
例:用L U 三角分解法解
解:用分解计算公式得
求解