09 矩阵的三角分解

第九讲 矩阵的三角分解

一、 Gauss 消元法的矩阵形式 n 元线性方程组 ⎧a 11ξ1+a 12ξ2+⎪

⎪a 21ξ1+a 22ξ2+⎨⎪⎪⎩a n1ξ1+a n2ξ2+

+a 1n ξn =b 1+a 2n ξn =b 2+a nn ξn =b n

⎫

⎪T

ξn ]⎪

⎪b n ]T ⎭

→ Ax =b

⎛A =(aij )

x =[ξ1, ξ2,

⎝b =[b1, b 2

设A 0=A =(a ij )

(0)

, 设A 的k 阶顺序主子式为∆k ，若∆1=a 11≠0，可n ⨯n

a (0)

以令c i1=i1 0

a 11

并构造Frobenius 矩阵 ⎡1⎢c L 1=⎢21

⎢⎢⎣c n1

0⎤⎡1

⎢-c ⎥

211⎢⎥ → L -=1

⎢⎥

⎢⎥

1⎦n ⨯n ⎣-c n1

0⎤

⎥⎥ ⎥⎥1⎦

10

10

计算可得

(0)⎡a 11⎢=⎢⎢0⎢⎣

(0)a 12a (1)22

(0)

⎤a 1n ⎥a (1)2n ⎥ → A (0)=L 1A (1) ⎥(1)⎥a nn ⎦

1(0)

A (1)=L -1A

a (1)n2

01

初等变换不改变行列式，故∆2=a 11，又可a 22，若∆2≠0，则a 122≠0

定义

a (1)i2

c i2=(1)(i=3,4,

a 22

n) ，并构造Frobenius 矩阵

⎡1⎢1⎢

L 2=⎢c 32

⎢⎢⎢⎣

c n2

(0)

⎡a 11⎢⎢=⎢⎢⎢⎢⎣

⎤⎡1

⎥⎢1⎥⎢

⎥ → L -21=⎢-c 32⎥⎢⎥⎢

⎢1⎥⎦⎣

-c n2

(0)

a 12a (1)22

(0)

a 13a (1)23a (2)33

⎤

⎥⎥⎥ ⎥⎥1⎥⎦

A (2)=L -21A (1)

a (2)n3

(0)

⎤a 1n ⎥a (1)2n ⎥

(2

⎥ → A (1) =L a (2)2A 3n ⎥⎥(2)⎥a nn ⎦

依此类推，进行到第(r-1)步，则可得到

(0)

⎡a 11⎢⎢⎢=⎢⎢⎢⎢⎢⎣

(0)

a 1r -1

(0)

a 1r

(0)

⎤a 1n ⎥⎥(r-2) a r -1n ⎥

（r ＝2,3, (r-1) ⎥a rn ⎥⎥-1) ⎥a (rnn ⎥⎦

A (r-1)

(r-2)

a r -1r -1

(r-2)

a r -1r (r-1) a rr

,n-1）

-1) a (rnr

(0)(1)

则A 的r 阶顺序主子式∆r =a 11a 22(r-2) r -1-1

，若∆r ≠0，则a r a r -1r -1a rr rr ≠0

-1

a r ir

可定义c ir =r ，并构造Frobenius 矩阵 -1

a rr

⎡1⎢⎢⎢L r =⎢

⎢⎢⎢⎣

1c r +111c nr

⎤⎡1⎥⎢⎥⎢⎥⎢-1

⎥ → L r =⎢⎥⎢⎥⎢⎥⎢1⎦⎣

1

-c r +111-c nr

⎤⎥⎥⎥⎥ ⎥⎥⎥1⎦

1r -1

A (r)=L -r A

(0)

⎡a 11⎢⎢⎢=⎢⎢⎢⎢⎢⎣

(0)

a 1r (0)a 1r +1

(r-1)

a rr

(r-1) a rr +1(r)a r +1r +1

a (r)nr +1

(0)

⎤a 1n ⎥⎥(r-1) a rn ⎥(r-1) (r)

→ A =L A ⎥r (r)

a r +1n ⎥

⎥⎥a (r)nn ⎥⎦

（r ＝2,3, ,n-1）

直到第（n －1）步，得到

(0)

⎡a 11⎢=⎢⎢⎢⎣

(0)a 12a (1)22

(0)

⎤a 1n ⎥a (1)2n ⎥ 则完成了消元的过程 ⎥n -1⎥a nn ⎦

A (n-1)

而消元法能进行下去的条件是∆r ≠0（r ＝1,2, 二、 LU 分解与LDU 分解

,n-1）

A =A (0)=L 1A (1)=L 1L 2A (2)=容易求出

=L 1L 2L 3

L n -1A (n-1)

L =L 1L 2

⎡1⎢c 1⎢21

L n -1=⎢

⎢

⎢c n -11c n -12⎢c n2⎣c n1

1c nn -1

⎤

⎥⎥

⎥ 为下三角矩阵 ⎥⎥1⎥⎦

令U =A (n-1) 为上三角矩阵，则

A =LU （L: lower U: upper L: left R: right）

以上将A 分解成一个单位下三角矩阵与上三角矩阵的乘积，就称为LU 分解或LR 分解。

LU 分解不唯一，显然，令D 为对角元素不为零的n 阶对角阵，

则

A =LU =LDD U =LU

-1

∧∧

可以采用如下的方法将分解完全确定，即要求 （1） L 为单位下三角矩阵 或 （2） U 为单位上三角矩阵 或

（3） 将A 分解为LDU ，其中L ，U 分别为单位下三角，单位上三角

矩阵，D 为对角阵A ＝diag[d 1,d 2, （k=1,2,…n ）, ∆0=1，

n 阶非奇异矩阵A 有三角分解LU 或LDU 的充要条件是A 的顺序主子式∆r ≠0（r=1,2，

,n ）

d n ]，而d k =

∆k

k -1

n 个顺序主子式全不为零的条件实际上是比较严格的，特别是在数值计算中，a (k-1)很小时可能会带来大的计算误差。因此，有必要kk

(k-1)(k-1)采取选主元的消元方法，这可以是列主元（在a (k-1)，，…中a a kk k +1 k nk (k-1)(k-1)(k-1)选取模最大者作为新的a (k-1)）、行主元（在，，…中a a a kk kk k k +1 kn

(k-1)

a 选取模最大者作为新的a (k-1)）全主元（在所有（k ≤i, j ≤n ）中ij kk

选模最大者作为新的a (k-1)）。之所以这样做，其理论基础在于对于任kk 何可逆矩阵A ，存在置换矩阵P 使得PA 的所有顺序主子式全不为零。

列主元素法：在矩阵的某列中选取模值最大者作为新的对角元素，选取范围为对角线元素以下的各元素。比如第一步：找第一个未知数前的系数|a i1|最大的一个，将其所在的方程作为第一个方程，即交换矩阵的两行，自由项也相应变换；第二步变换时，找|a i2|(i≤2) 中最大的一个，然后按照第一步的方法继续。

行主元素法：在矩阵的某行中选取模值最大者作为新的对角元素，选取范围为对角线元素以后的各元素，需要记住未知数变换的顺序，最后再还原回去。因此需要更多的存储空间，不如列主元素法方便。

全主元素法：若某列元素均较小或某行元素均较小时，可在各行各列中选取模值最大者最为对角元素。与以上两种方法相比，其计算稳定性更好，精度更高，计算量增大。

Ax =b

A =LU

⎧Ly =b

←两个三角形方程回代即可⎨

⎩Ux =y

三、其他三角分解

1. 定义 设A 具有唯一的LDU 分解

（1） 若将D ，U 结合起来得A =LU （U =DU ），则称为A 的

Doolittle 分解

（2） 若将L ，D 结合起来得A =LU （L =LD ），则称为A 的Crout

分解

2. 算法

（1） C rout 分解，设

⎡l 11

⎢l ∧

L =⎢21

⎢⎢⎣l n1

∧

∧

∧

∧∧

l 22l n2

⎤⎡1u 12⎥⎢1⎥，U =⎢⎥⎢⎥⎢l nn ⎦⎣u 1n ⎤

u 3n ⎥⎥ ⎥⎥1⎦

由A =LU 乘出得

（1）l i1=a i1(第1列) （2）u 1j =

（i =1, 2, 3, （j =2, 3,

n ）n ）

(A,L第1列) (A,U第1行)

∧

a 1j

11

(第1行)

（3）l i2=a i2-l i1u 12(第2列) （4）u 2j =

1

a 2j -l 21u 1j )(l 22

∧

(i=2, 3,

（j =3,4,

n)

n ）

(A,L第2列)

(A,U 第2行)

∧

（5）一般地，对A, L 的第k 列运算，有

l ik =a ik -∑l im u mk

m =1k -1

(k=1, 2, n;i =k +1, k +2; n)

（6） 对A ，U 的第k 行运算，有

u kj =

1l kk

(akj -∑l km u mj )

m =1k -1

(k=1, 2, n -1; j =k +1, k +2, n)

直至最后，得到的l ij ,u ij 恰可排成

⎡l 11

⎢l ⎢21⎢l 31⎢⎢⎢⎣l n1

u 12

l 22l 32l n2

u 13u 23l 33l n3

u 1n ⎤u 2n ⎥⎥

u 3n ⎥ 先算列后算行 ⎥⎥l nn ⎥⎦

3. 厄米正定矩阵的Cholesky 分解

A =GG H

⎧⎛i -12⎫

⎪ a ii -∑g ik ⎪⎪⎝k =1⎭⎪j -1⎪1

g ij =⎨(aij -∑g ik g ik )

k =1⎪g jj

⎪0⎪⎪⎩

i =j i >j i

理论上，Cholesky 具有中间量g

ij 可以控制（g ij ≤

）的

好处，应较稳健，但实际计算中发现，对希尔伯特矩阵问题，不如全主元方法。

作业：p195 2、3