L LD, U D1U
LU分解紧凑方式
直接利用矩阵乘法来计算 LU分解
1
l21
1
u11 u12
u1n a11 a12
a1n
u22
u2n
a21
a22
a2n
ln1
ln,n1 1
unn an1 an2
ann
L U A
比较等式两边的第一行得：u1j = a1j ( j = 1,…, n )U 的第一行
a(k) kn
( k = 1, …, n-1)
a(k) nk
a(k) nn
则 A(k) 与 A(k+1) 之间的关系式可以表示为： A(k1) Lk A(k)
其中： 1
Lk
1 mk1,k 1
mn,k
,
mik ai(kk)
a(k) kk
( i = k+1, …, n )
1ห้องสมุดไป่ตู้
LU 分解 于是有： A(n) Ln1 L2L1A(1)
Ax = b
Ly b Ux y
两次回代过程求出方程组的解：
运算量： n2
i-1
yi bi lij yj , ( i = 1, …, n )
LU分解
j 1
n
xi yi uij x j
j i 1
总运算量：
uii , ( i = n , …, 1 ) n3 n2 n
3
3
优点：特别适合求解具有多个右端项的线性方程组。
CROUT分解的紧凑算法
算法 5.2 ： ( Crout 分解 )
For k=1,2,...,n
aik
k -1
lik aik lisusk ,
s1
运算量：(n3 - n)/3
i = k, …, n
akj
k 1
ukj akj lksusj lkk , j = k+1, …, n
s1
End For
第 k 步：此时 U 的前 k-1 行和 L 的前 k-1 列已经求出
比较等式两边的第 k 行得：
ukj akj lk1u1 j
k 1
l u k,k1 k1, j akj lksusj
s1
比较等式两边的第 k 列得：
( j = k, …, n )
lik aik li1u1k
s1
运算量：(n3 - n)/3
j = k, …, n
aik
k 1
lik aik lisusk ukk , i = k+1, …, n
s1
End For
Matlab程序参见：mylu.m
为了节省存储空间，通常用 A 的绝对下三角部分来存放 L (对角线元素无需存储)，用 A 的上三角部分来存放 U。
b1 c1
其中：A
a2
b2
c2
,
an1 bn1 cn1
an bn
d1
d
d2
dn1
dn
对 A 作 Crout分解 得
l1
L
a2
l2
,
an ln
1 u1
U
1
un1
,
1
追赶法（续）
得算法：
Ly = d Ux = y
li bi aiui1, ( i = 1, …, n )
Matlab程序：上机练习。
SPD 的 CHOLESKY 分解
若 A 是对称正定矩阵 (Symmetric Positive Definite )
设 A = LDR
AT = A
A = LDLT
RTDLT = LDR
LDR 分解唯一
R = LT
设 D=diag(d1, , dn)
可以证明：di > 0，( i = 1, …, n)
l u i,k1 k1,k
ukk
aik
i1
lisusk
ukk
s1
( i = k+1, …, n )
直到第 n 步，便可求出矩阵 L 和 U 的所有元素。
LU分解紧凑算法（续）
算法 5.1：( LU 分解 )
For k=1,2,...,n
k -1
akj
ukj akj lksusj ,
A A(1) (Ln1 L2L1)1 A(n)
容易验证： 1
Lk1
1 mk1,k 1
mn,k
( k = 1, …, n-1)
1
记：L L11L21 Lk1, U A(n) ，则
A LU LU 分解 (杜利脱尔Doolittle分解)
其中：L --- 单位下三角矩阵，U --- 上三角矩阵
LU 分解的存在唯一性
LU 分解存在
普通高斯消去法不被中断
?
a(k) kk
0
定理 普通高斯消去法求解方程组 Ax = b 时，主元
a(k) kk
0
的充要条件是：A
的所有顺序主子式不为零。
定理 ( LU分解的唯一性 )
若 A的所有顺序主子式 0 ，则 A存在唯一的 LU分解。
证：存在性由上面的定理可得；唯一性可用反证法证明。
若 A 是对称正定矩阵 ，则可利用 Cholesky 分解。 此时的求解方法称为平方根法。
举例（一）
例：用 LU分解 求线性方程组 Ax=b 的解，其中
1 2 3 4
2
A
1 11
4 6 16
9 27 81
16 26546
,
b
10 14940
解： 令 A = LU，由 LU分解 算法5.1 可得
追
yi
di ai yi1
li ,
( i = 1, …, n )
ui
ci
li ,
( i = 2, …, n-1 )
赶
xn xi
yn yi
ui
其中 u0=0, y0=0, a1=0
xi1, ( i = n-1, …, 1 )
法 运算量： 5n - 4
作业
教材第 162 页： 4、5
比较等式两边的第一列得： li1 ai1 u11 ( i = 2,…,Ln的) 第一列
比较等式两边的第二行得：u2 j a2 j l21u1 j ( j =U2,…的,第n二) 行
比较等式两边的第二列得：li2 ai2 li1u12 u22 ( iL=的3,第…二, n列)
LU分解紧凑算法（续）
类似分解
定理 若 A 的所有顺序主子式 0 ，则
(1) A 存在唯一的 LDR 分解：A = LDR，其中：
L 是单位下三角矩阵，D 是对角矩阵，R 是单位上三角矩阵 D diag(U ), R D1U
(2) A 存在唯一的克洛脱(Crout)分解：A L U，
其中：L 是下三角矩阵，U 是单位上三角矩阵
第六章 线性方程组直接解法
第三节 矩阵三角分解
矩阵三角分解
将一个矩阵分解成结构简单的三角形矩阵的乘积称为 矩阵的三角分解。 高斯消去过程其实就是一个矩阵的三角分解过程。
将 Gauss 消去过程中第 k-1 步消元后的系数矩阵记为：
a(1) 11
a(1) 1k
a(1) 1n
A(k)
a(k) kk
1
1 2 3 4
L
1 11
1 3 7
1 6
, U
1
2 6 12 6 2244
回代：解 Ly = b 得：y =[2, 8, 18, 24]T
解 Ux = y 得：x =[-1, 1, -1, 1]T
例5.4：利用平方根法解线性方程组(见158 页)。
追赶法
考虑三对角线性方程组：
Ax = d
算法 5.3 ： ( Cholesky 分解，按列)
For k=1,2,...,n
1
akk
gkk
akk
k -1
gk2s
2
s1
运算量：n3/6 +n2/2 +n /3
aik
gik
aik
k 1
gis gks
gkk ,
s1
End For
i = k+1, …, n
LU分解求解线性方程组
A LU
令
D
1 2
diag
d1 ,
1
, dn , G LD2
11
A LD2 D2 LT GGT
A GGT
SPD 的 Cholesky 分解
CHOLESKY 分解实现算法
几点说明：
(1) G 为对角线元素全为正的下三角矩阵 ； (2) 只有对称正定矩阵(SPD)才存在 Cholesky分解；
定理 SPD 矩阵的 Cholesky 分解存在且唯一