第十讲 矩阵的三角分解
一、 Gauss 消元法的矩阵形式 n 元线性方程组
⎧a 11ξ1+a 12ξ2+ +a 1n ξn =b 1⎪
⎪a 21ξ1+a 22ξ2+ +a 2n ξn =b 2⎨⎪
⎪a ξ+a ξ+ +a ξ=b ⎩n 11n 22nn n n
→
Ax =b
⎛A =(aij )
T x =[ξ, ξ, ξ] 12n T b =[b, b b ]12n ⎝
⎫
⎪⎪ ⎪⎭
设A 0=A =(a ij )
(0)
, 设A 的k 阶顺序主子式为∆k ，若∆1=a 11≠0，可n ⨯n
以令c i1=
并构造Frobenius 矩阵
⎡1
⎢c 21⎢L 1=⎢ ⎢⎣c n 1
0⎤⎥⎥ ⎥⎥1⎦n ⨯n
a i1a
(0) 011
1
→
L
-11
⎡1⎢
-c 21⎢=
⎢ ⎢
⎣-c n 1
1
0⎤⎥⎥ ⎥⎥1⎦
计算可得
(0) ⎡a 11⎢=⎢⎢0⎢⎣
a 12
(0) (1)
A
(1)
=L A
-11
(0)
a 22
a n 2
(1)
(0) a 1n ⎤(1) ⎥a 2n ⎥
⎥ (1) ⎥a nn ⎦
→
A (0) =L 1A (1)
01
a 22，若∆2初等变换不改变行列式，故∆2=a 11
≠0
≠0，又可，则a 1
22
定义
c i 2=
a i 2a
(1) (1) 22
(i=3, 4, n ) ，并构造
⎤⎥⎥⎥ ⎥⎥1⎥⎦
Frobenius 矩阵
⎡1
⎢⎢=⎢⎢⎢⎢⎣
⎤
⎥⎥⎥ ⎥⎥1⎥⎦
⎡1
⎢⎢L 2=⎢
⎢⎢⎢⎣
1c 32 c n 2
(0)
⎡a 11⎢⎢=⎢⎢⎢⎢⎣
1-c 32 -c n 2
→
L -21
a 12
(0) (1)
a 13
(0) (1)
a 22a 23a 33
A
(2)
=L 2A
-1(1) (2)
a n 3
(2)
(0) a 1n ⎤(1) ⎥a 2n ⎥(2)
a 3n ⎥ ⎥ ⎥(2) a nn ⎥⎦
→
) (2
A (1=L 2A
依此类推，进行到第(r-1)步，则可得到
(0)
⎡a 11⎢⎢⎢=⎢⎢⎢⎢⎢⎣
a 1r -1 a r -1r -1
(r -2)
(0)
a 1r
(0)
A
(r -1)
a r -1r a a nr
(r -2) (r -1)
rr
(r -1)
(0) a 1n ⎤
⎥⎥(r -2) a r -1n ⎥
(r -1) ⎥
a rn ⎥ ⎥⎥(r -1)
a nn ⎥⎦
（r ＝2,3, ,n-1）
(0) (1) (r -2) r -1
则A 的r 阶顺序主子式∆r =a 11a 22 a r -1r -1a rr ，若∆r ≠0，则a rr ≠0
r -1
可定义c ir =
⎡1
⎢⎢⎢L r =⎢
⎢⎢⎢⎣
a ir a
r -1r -1rr
，并构造Frobenius 矩阵
⎤⎥⎥⎥⎥ ⎥⎥⎥1⎦
⎡1⎢⎢⎢=⎢⎢⎢⎢⎣
⎤⎥⎥⎥⎥ ⎥⎥⎥1⎦
1c r +11 c nr
1
1-c r +11
-c nr
1
→
L
-1r
A
(r )
=L r A
-1r -1
(0) ⎡a 11⎢⎢⎢=⎢⎢⎢⎢⎢⎣
a 1r a rr
(0)
a 1r +1 a rr +1
(r ) (r -1)
(0)
(r -1)
a r +1r +1
a nr +1
(r )
(0)
a 1n ⎤
⎥⎥(r -1) a rn ⎥(r -1) (r )
→A =L A ⎥r (r )
a r +1n ⎥ ⎥⎥(r )
a nn ⎥⎦
（r ＝2,3, ,n-1） 直到第（n －1）步，得到
(0)
⎡a 11⎢=⎢⎢⎢⎣
a 12
(0) (1)
A
(n -1)
a 22
(0) a 1n ⎤(1) ⎥a 2n ⎥
⎥n -1⎥a nn ⎦
则完成了消元的过程
而消元法能进行下去的条件是∆r 二、 LU 分解与LDU 分解
A =A
(0)
≠0（r ＝1,2, ,n-1）
=L 1A
(1)
=L 1L 2A
(2)
= =L 1L 2L 3 L n -1A
(n -1)
容易求出
⎡1⎢c ⎢21=⎢ ⎢c ⎢n -11⎢⎣c n 1
⎤
⎥⎥⎥ ⎥⎥1⎥⎦
1
c n -12c n 2
1c nn -1
L =L 1L 2 L n -1
为下三角矩阵
令U =A (n -1) 为上三角矩阵，则
A =LU （L: lower U: upper L: left R: right）
以上将A 分解成一个单位下三角矩阵与上三角矩阵的乘积，就称为LU 分解或LR 分解。
LU 分解不唯一，显然，令D 为对角元素不为零的n 阶对角阵，
则
A =L U =L D D U =L U
-1
∧
∧
可以采用如下的方法将分解完全确定，即要求 （1） L 为单位下三角矩阵 或 （2） U 为单位上三角矩阵 或
（3） 将A 分解为LDU ，其中L ，U 分别为单位下三角，单位上三角
矩阵，D 为对角阵A ＝diag[d 1, d 2, d n ]，而d k =∆k （k=1,2,…n ）, ∆0
=1，
∆k -1
n 阶非奇异矩阵A 有三角分解LU 或LDU 的充要条件是A 的顺序主子式∆r
≠0（r=1,2， ,n ）
n 个顺序主子式全不为零的条件实际上是比较严格的，特别是在
k -1) 数值计算中，a (kk 很小时可能会带来大的计算误差。因此，有必要k -1) ) (k -1) 采取选主元的消元方法，这可以是列主元（在a (kk ，a (k k +-1，…中a 1 k nk k -1) k -1) ) (k -1) 选取模最大者作为新的a (kk ）、行主元（在a (kk ，a (k k -1，…中a k +1 kn k -1) 选取模最大者作为新的a (kk ）全主元（在所有a (ij k -1) （k ≤i, j ≤n ）中k -1) 选模最大者作为新的a (kk ）。之所以这样做，其理论基础在于对于任
何可逆矩阵A ，存在置换矩阵P 使得PA 的所有顺序主子式全不为零。
列主元素法：在矩阵的某列中选取模值最大者作为新的对角元素，选取范围为对角线元素以下的各元素。比如第一步：找第一个未知数前的系数|a i1|最大的一个，将其所在的方程作为第一个方程，即交换矩阵的两行，自由项也相应变换；第二步变换时，找|a i 2|(i≤中最大的一个，然后按照第一步的方法继续。
2)
行主元素法：在矩阵的某行中选取模值最大者作为新的对角元素，选取范围为对角线元素以后的各元素，需要记住未知数变换的顺序，最后再还原回去。因此需要更多的存储空间，不如列主元素法方便。
全主元素法：若某列元素均较小或某行元素均较小时，可在各行各列中选取模值最大者最为对角元素。与以上两种方法相比，其计算稳定性更好，精度更高，计算量增大。
A x =b A =LU
⎧Ly =b
←两个三角形方程回代即可⎨
⎩U x =y
三、其他三角分解
1. 定义 设A 具有唯一的LDU 分解 （1） 若将D ，U 结合起来得A
Doolittle 分解
（2） 若将L ，D 结合起来得A
分解
2. 算法
（1） C rout 分解，设
⎡l 11
⎢∧l 21⎢L =⎢ ⎢⎣l n 1
⎤⎡1⎥⎢⎥，U =⎢⎥⎢⎥⎢l nn ⎦⎣
u 121
u 1n ⎤
⎥u 3n
⎥ ⎥⎥1⎦
=L U （L =L D ），则称为
∧
∧
=L U
（U
∧
=D U
），则称为A 的
∧
A 的Crout
l 22 l n 2
由A
∧
=L U
乘出得
（1）l i1=a i1(第1列) （2）u 1j =
a 1j
l 11
(第1行)
∧
（i =1, 2, 3, n ）
（j =2, 3, n ）
(A , L 第1列) (A , U 第1行)
∧
（3）l i 2=a i 2-l i1u 12(第2列) （4）u 2j =
1l 22
(i=2, 3, n ) (A , L 第2列)
(a
2j
-l 21u 1j )
∧
（j =3, 4, n ）(A , U 第2行)
（5）一般地，对A, L 的第k 列运算，有
k -1
l ik =a ik -
∑l
m =1
im
u mk
(k=1, 2, n; i =k +1, k +2; n )
（6） 对A ，U 的第k 行运算，有
u kj =
1l kk
k -1
(akj -
∑l
m =1
km
u m j )
(k=1, 2, n -1; j =k +1, k +2, n )
直至最后，得到的l ij , u ij 恰可排成
⎡l 11⎢l ⎢21⎢l 31⎢ ⎢⎢⎣l n 1
u 12l 22l 32 l n 2
u 13u 23l 33 l n 3
u 1n ⎤
⎥u 2n
⎥u 3n ⎥ ⎥⎥l nn ⎥⎦
先算列后算行
3. 厄米正定矩阵的Cholesky 分解
A =G G
H
i =j i >j i
1
⎧i -12
2⎫⎛
⎪ a ii -∑g ik ⎪⎪⎝k =1⎭⎪j -1⎪1g ij =⎨(aij -∑g ik g ik )
k =1⎪g jj
⎪0⎪⎪⎩
理论上，Cholesky 具有中间量g
ij 可以控制（g ij ≤
）的
好处，应较稳健，但实际计算中发现，对希尔伯特矩阵问题，不如全主元方法。
作业：p195 2、3
第十讲 矩阵的三角分解
一、 Gauss 消元法的矩阵形式 n 元线性方程组
⎧a 11ξ1+a 12ξ2+ +a 1n ξn =b 1⎪
⎪a 21ξ1+a 22ξ2+ +a 2n ξn =b 2⎨⎪
⎪a ξ+a ξ+ +a ξ=b ⎩n 11n 22nn n n
→
Ax =b
⎛A =(aij )
T x =[ξ, ξ, ξ] 12n T b =[b, b b ]12n ⎝
⎫
⎪⎪ ⎪⎭
设A 0=A =(a ij )
(0)
, 设A 的k 阶顺序主子式为∆k ，若∆1=a 11≠0，可n ⨯n
以令c i1=
并构造Frobenius 矩阵
⎡1
⎢c 21⎢L 1=⎢ ⎢⎣c n 1
0⎤⎥⎥ ⎥⎥1⎦n ⨯n
a i1a
(0) 011
1
→
L
-11
⎡1⎢
-c 21⎢=
⎢ ⎢
⎣-c n 1
1
0⎤⎥⎥ ⎥⎥1⎦
计算可得
(0) ⎡a 11⎢=⎢⎢0⎢⎣
a 12
(0) (1)
A
(1)
=L A
-11
(0)
a 22
a n 2
(1)
(0) a 1n ⎤(1) ⎥a 2n ⎥
⎥ (1) ⎥a nn ⎦
→
A (0) =L 1A (1)
01
a 22，若∆2初等变换不改变行列式，故∆2=a 11
≠0
≠0，又可，则a 1
22
定义
c i 2=
a i 2a
(1) (1) 22
(i=3, 4, n ) ，并构造
⎤⎥⎥⎥ ⎥⎥1⎥⎦
Frobenius 矩阵
⎡1
⎢⎢=⎢⎢⎢⎢⎣
⎤
⎥⎥⎥ ⎥⎥1⎥⎦
⎡1
⎢⎢L 2=⎢
⎢⎢⎢⎣
1c 32 c n 2
(0)
⎡a 11⎢⎢=⎢⎢⎢⎢⎣
1-c 32 -c n 2
→
L -21
a 12
(0) (1)
a 13
(0) (1)
a 22a 23a 33
A
(2)
=L 2A
-1(1) (2)
a n 3
(2)
(0) a 1n ⎤(1) ⎥a 2n ⎥(2)
a 3n ⎥ ⎥ ⎥(2) a nn ⎥⎦
→
) (2
A (1=L 2A
依此类推，进行到第(r-1)步，则可得到
(0)
⎡a 11⎢⎢⎢=⎢⎢⎢⎢⎢⎣
a 1r -1 a r -1r -1
(r -2)
(0)
a 1r
(0)
A
(r -1)
a r -1r a a nr
(r -2) (r -1)
rr
(r -1)
(0) a 1n ⎤
⎥⎥(r -2) a r -1n ⎥
(r -1) ⎥
a rn ⎥ ⎥⎥(r -1)
a nn ⎥⎦
（r ＝2,3, ,n-1）
(0) (1) (r -2) r -1
则A 的r 阶顺序主子式∆r =a 11a 22 a r -1r -1a rr ，若∆r ≠0，则a rr ≠0
r -1
可定义c ir =
⎡1
⎢⎢⎢L r =⎢
⎢⎢⎢⎣
a ir a
r -1r -1rr
，并构造Frobenius 矩阵
⎤⎥⎥⎥⎥ ⎥⎥⎥1⎦
⎡1⎢⎢⎢=⎢⎢⎢⎢⎣
⎤⎥⎥⎥⎥ ⎥⎥⎥1⎦
1c r +11 c nr
1
1-c r +11
-c nr
1
→
L
-1r
A
(r )
=L r A
-1r -1
(0) ⎡a 11⎢⎢⎢=⎢⎢⎢⎢⎢⎣
a 1r a rr
(0)
a 1r +1 a rr +1
(r ) (r -1)
(0)
(r -1)
a r +1r +1
a nr +1
(r )
(0)
a 1n ⎤
⎥⎥(r -1) a rn ⎥(r -1) (r )
→A =L A ⎥r (r )
a r +1n ⎥ ⎥⎥(r )
a nn ⎥⎦
（r ＝2,3, ,n-1） 直到第（n －1）步，得到
(0)
⎡a 11⎢=⎢⎢⎢⎣
a 12
(0) (1)
A
(n -1)
a 22
(0) a 1n ⎤(1) ⎥a 2n ⎥
⎥n -1⎥a nn ⎦
则完成了消元的过程
而消元法能进行下去的条件是∆r 二、 LU 分解与LDU 分解
A =A
(0)
≠0（r ＝1,2, ,n-1）
=L 1A
(1)
=L 1L 2A
(2)
= =L 1L 2L 3 L n -1A
(n -1)
容易求出
⎡1⎢c ⎢21=⎢ ⎢c ⎢n -11⎢⎣c n 1
⎤
⎥⎥⎥ ⎥⎥1⎥⎦
1
c n -12c n 2
1c nn -1
L =L 1L 2 L n -1
为下三角矩阵
令U =A (n -1) 为上三角矩阵，则
A =LU （L: lower U: upper L: left R: right）
以上将A 分解成一个单位下三角矩阵与上三角矩阵的乘积，就称为LU 分解或LR 分解。
LU 分解不唯一，显然，令D 为对角元素不为零的n 阶对角阵，
则
A =L U =L D D U =L U
-1
∧
∧
可以采用如下的方法将分解完全确定，即要求 （1） L 为单位下三角矩阵 或 （2） U 为单位上三角矩阵 或
（3） 将A 分解为LDU ，其中L ，U 分别为单位下三角，单位上三角
矩阵，D 为对角阵A ＝diag[d 1, d 2, d n ]，而d k =∆k （k=1,2,…n ）, ∆0
=1，
∆k -1
n 阶非奇异矩阵A 有三角分解LU 或LDU 的充要条件是A 的顺序主子式∆r
≠0（r=1,2， ,n ）
n 个顺序主子式全不为零的条件实际上是比较严格的，特别是在
k -1) 数值计算中，a (kk 很小时可能会带来大的计算误差。因此，有必要k -1) ) (k -1) 采取选主元的消元方法，这可以是列主元（在a (kk ，a (k k +-1，…中a 1 k nk k -1) k -1) ) (k -1) 选取模最大者作为新的a (kk ）、行主元（在a (kk ，a (k k -1，…中a k +1 kn k -1) 选取模最大者作为新的a (kk ）全主元（在所有a (ij k -1) （k ≤i, j ≤n ）中k -1) 选模最大者作为新的a (kk ）。之所以这样做，其理论基础在于对于任
何可逆矩阵A ，存在置换矩阵P 使得PA 的所有顺序主子式全不为零。
列主元素法：在矩阵的某列中选取模值最大者作为新的对角元素，选取范围为对角线元素以下的各元素。比如第一步：找第一个未知数前的系数|a i1|最大的一个，将其所在的方程作为第一个方程，即交换矩阵的两行，自由项也相应变换；第二步变换时，找|a i 2|(i≤中最大的一个，然后按照第一步的方法继续。
2)
行主元素法：在矩阵的某行中选取模值最大者作为新的对角元素，选取范围为对角线元素以后的各元素，需要记住未知数变换的顺序，最后再还原回去。因此需要更多的存储空间，不如列主元素法方便。
全主元素法：若某列元素均较小或某行元素均较小时，可在各行各列中选取模值最大者最为对角元素。与以上两种方法相比，其计算稳定性更好，精度更高，计算量增大。
A x =b A =LU
⎧Ly =b
←两个三角形方程回代即可⎨
⎩U x =y
三、其他三角分解
1. 定义 设A 具有唯一的LDU 分解 （1） 若将D ，U 结合起来得A
Doolittle 分解
（2） 若将L ，D 结合起来得A
分解
2. 算法
（1） C rout 分解，设
⎡l 11
⎢∧l 21⎢L =⎢ ⎢⎣l n 1
⎤⎡1⎥⎢⎥，U =⎢⎥⎢⎥⎢l nn ⎦⎣
u 121
u 1n ⎤
⎥u 3n
⎥ ⎥⎥1⎦
=L U （L =L D ），则称为
∧
∧
=L U
（U
∧
=D U
），则称为A 的
∧
A 的Crout
l 22 l n 2
由A
∧
=L U
乘出得
（1）l i1=a i1(第1列) （2）u 1j =
a 1j
l 11
(第1行)
∧
（i =1, 2, 3, n ）
（j =2, 3, n ）
(A , L 第1列) (A , U 第1行)
∧
（3）l i 2=a i 2-l i1u 12(第2列) （4）u 2j =
1l 22
(i=2, 3, n ) (A , L 第2列)
(a
2j
-l 21u 1j )
∧
（j =3, 4, n ）(A , U 第2行)
（5）一般地，对A, L 的第k 列运算，有
k -1
l ik =a ik -
∑l
m =1
im
u mk
(k=1, 2, n; i =k +1, k +2; n )
（6） 对A ，U 的第k 行运算，有
u kj =
1l kk
k -1
(akj -
∑l
m =1
km
u m j )
(k=1, 2, n -1; j =k +1, k +2, n )
直至最后，得到的l ij , u ij 恰可排成
⎡l 11⎢l ⎢21⎢l 31⎢ ⎢⎢⎣l n 1
u 12l 22l 32 l n 2
u 13u 23l 33 l n 3
u 1n ⎤
⎥u 2n
⎥u 3n ⎥ ⎥⎥l nn ⎥⎦
先算列后算行
3. 厄米正定矩阵的Cholesky 分解
A =G G
H
i =j i >j i
1
⎧i -12
2⎫⎛
⎪ a ii -∑g ik ⎪⎪⎝k =1⎭⎪j -1⎪1g ij =⎨(aij -∑g ik g ik )
k =1⎪g jj
⎪0⎪⎪⎩
理论上，Cholesky 具有中间量g
ij 可以控制（g ij ≤
）的
好处，应较稳健，但实际计算中发现，对希尔伯特矩阵问题，不如全主元方法。
作业：p195 2、3