2 3 2 n O( n ) 3
mult a(i , j ) a( j, j ); for k j 1 : n a(i , k ) a(i , k ) mult * a( j , k ); end b(i ) b(i ) mult * b( j ); end
end
LU分解
求A的LU分解（L是下三角矩阵，U是上三角矩阵）
1 1 1 1 3 4 3 4
LU分解
性质1 设向量
, xn ) 且 xk 0 T 则存在唯一的下三角阵 Lk I lk ek ,满足 x ( x1 , x2 ,
T
Lk x ( x1 ,
第三章 线性方程组的直接解法
/*Direct Method for Solving Linear Systems*/
求解 A x b, A R
Cramer法则:
nn
det( A) 0
Di xi D
i 1, 2,
,n
所需乘除法的运算量大约为(n+1)!+n
n=20时，每秒1亿次运算速度的计算机要算30多万年！
Gauss消去法的消元过程算法
for for
j 1: n 1
i j 1: n
2 3 2 n O( n ) 3
mult a(i , j ) a( j, j ); for k j 1 : n a(i , k ) a(i , k ) mult * a( j , k ); end b(i ) b(i ) mult * b( j ); end
方程组可化为下面两个易求解的三角方程组
Ly b Ux y
二、 高斯消去法
设给定矩阵
1 1 3 1 1 3 [ A b] 3 4 2 0 7 7
Gauss消去法的消元过程算法
for for
j 1: n 1
i j 1: n
设给定矩阵
1 0 0 L1 2 1 0 3 0 1
则有
7 1 4 L1 A 0 3 6 0 6 11
再取Gauss变换矩阵
1 0 0 L2 0 1 0 0 2 1
,a
( k 1) 的上三角矩阵 k 1,k 1
矩阵 A
(k )
k) 的k阶主子式 ( 是上三角的 k

(k ) k
0a
0

(k ) k
[L ] [L
1 j
1 k 1 k
1 k 2 k
]
[ L ] k
1 1 k
k
其中 L
( j 1, 2,
1 j
, k 1) 均为单位下三角矩阵
end
经过n-1次消元，并将
lik 存放在矩阵零元素位置
a l 21 l 31 l n1
(1) 11
a a
(1) 12 ( 2) 22
l32
ln 2
ln,n1
a . . . (n) ann a
(1) 1n ( 2) 2n
A 的各阶顺序主子式都不等于零，即
a11 a12 i a21 a22 ai1 ai 2
a1i a2 i aii 0, i 1, 2, , k ( n)
证明： 归纳法证明(对k归纳)
设直到k-1成立,只要证明
1 , 2 ,
, k 1 非零时，
k非零的充要条件是 a
(k ) kk
1 l3 , 2 1 ln ,2 ln ,n 1
1 1 n 2 n1
1
可以分解为一系列初等下三角阵的乘积
L L L
1 1 1 2
L L
三、 三角分解的计算
Gauss消去法
1 4 7 A 2 5 8 3 6 10 取Gauss变换矩阵
Li L j ( j i)
1
1
性质4 若记 L
1 k
1

lk 1,k 1 ln ,k
1
,则有
1
L L
1 1 1 2
1 l21 1 1 Ln1 L l31 l32 1
ln1 ln 2
ln,n1 1
1 l 2 ,1 即单位下三角阵 L l3,1 ln ,1
uij x j , i n, n 1, j i 1
n
,1;
两种算法的工作量(加减乘除运算次数之和)均为 n
2ห้องสมุดไป่ตู้
三角分解法的基本思想:
设已知方程组系数矩阵的三角分解为
其中,
A LU
y Ux
L 为下三角矩阵, U 为上三角矩阵.
记
Ax b LUx b
(1) 11
取
L1 I l e
其中 l i1
T 1 1
l1 (0, l21 ,
a
(1) 11
, ln1 )
,n
T

1 1
a
(1) i1
i 2, 3,
1 1 T 1 1
记
A
( 2)
( 2)
L A
(1)
L I le
0 a I n1 c1
(1 ) 11
直接法 在没有舍入误差的情况下，经过有限次 运算可以得到方程组的精确解的方法。
§3.1 三角形方程组和三角分解
一、 三角形方程组的解法
考虑下三角形方程组
Ly b
y1 b1 y b 2 2 y ,b L lnn1 lnn ln1 ln 2 y b n n yi 的计算公式为： i 1 1 yi bi lij y j , i 1, 2, , n; lii j 1
写成分量形式：
xi xk li ,k 0 i k 1,
,n
唯一确定
li ,k
性质2
xi xk
1
i k 1,
,n
L
1 k
lk 1,k 1 ln ,k
1
I l e
T k k
1
性质3
1 1 li 1,i 1
l j 2,i ln ,i l j 1, j 1 ln , j
记
, xk , 0,
, 0)
T
, 0) .
Lk I l e
T k k
T
证明：寻找满足条件的初等下三角阵
y ( x1 ,
, xk , 0,
lk (0,
, 0, lk 1,k ,
T k k
, ln , k )
T k k
T
Lk x ( I l e ) x x l e x x lk xk y
A
1 c1 (1) a11
r A1
T 1
( 2) ( 2) T A (aij ) c1r1 A1 (1) a11 (1) (1) ai1 a1 j ( 2) (1) aij aij i , j 2, 3, , n (1) a11
l11 l21 l22 l31 l32 l33
考虑上三角形方程组
Ux y
x1 y1 x y 2 2 x ,y xn yn
U
u11 u12 ... u1n u22 ... u2 n unn
xi 的计算公式为： 1 x i yi uii
L L
L L A U
(1)
1 1 2 1
上三角矩阵
A L1L2
1 l 1 21 L l31 l32 1 ln1 ln 2 ln3
Ln1U LU
u1n u2 n u3n unn
u11 u12 u13 u u 22 23 U u33 1
(1) (1) ij
A aij R

n n
A (a ) (aij ) A
(1)
a c1
(1) 11
(1) 11
r A1
T 1
Step 1：如果 a
(1) 11
0
r
T 1
A
(1)
a c1
r A1
T 1
高斯变换
a 0
1 1 1 2
1 4 7 L2 L1 A 0 3 6 U 0 0 1
A L L U LU
其中
1 0 0 1 1 L L1 L2 2 1 0 3 2 1
Gauss消去法的矩阵表示
设给定 n 阶矩阵 记 令A
6 3 y 23 5 191 74
1 1 x 1 1
（Gauss消去法的实现条件） Th3.1.1 (i ) aii (i 1, 2, , k(k n)) 全不为零的充要条件是

det( L ) 1
(k ) kk
k 0 a
0
结论得证
因此，若矩阵的各阶顺序主子式均不为零， 可以采用Gauss消元法进行三角分解。
（矩阵三角分解的一个充分条件) Th3.1.2 若 A R
n n
的顺序主子式 Ak R
kk
(k 1, 2, , n 1)
L R
n n
(1) 11
a 0
r
T 1
类似地，对A