本文介绍了矩阵的三角分解,如LU分解,LDR分解,Cholesky分解等。
为博主在学习过程中,总结或者思考的记录,用于加深印象,不作为知识讲解和科普,如果理解有误还请指出。

前言

  对矩阵进行分解能够清晰反应出原矩阵的某些数字特征,在矩阵运算中可以起到化简的作用,其次在一些特定的场合将矩阵分解为合适的形式能够减少运算误差,在数值计算中有很重要的地位。

一、LR(LU)分解,也称Doolittle分解

若矩阵A可以表示为:

A = L·R

其中,L为单位下三角矩阵,R为上三角矩阵,则称A可三角分解(LR分解)。例如:

A=[21443132220]=[121111][2141511]=LRA =\begin{bmatrix} 2 & 1 & 4 \\ 4 &3&13\\ 2&2&20 \end{bmatrix} = \begin{bmatrix} 1 & & \\ 2 &1&\\ 1&1&1 \end{bmatrix} \cdot\begin{bmatrix} 2 & 1 &4 \\ &1&5\\ &&11 \end{bmatrix} = L\cdot R

LR分解可以用于解线性方程组 Ax=bAx = b,若方阵A有LR分解,即A=LRA = L\cdot R,令Rx=yRx = y,则方程组等价于:

{Ly=bRx=y,此处L.R.b均为已知量\left \{\begin{aligned} Ly = b \\ Rx = y\end{aligned}\right. ,此处L.R.b均为已知量

由于L和R的特殊形式,Ly=bLy = b 很容易利用高斯消元迭代求出y,然后代入Rx=yRx = y,再次迭代求出x。

那么提出三个问题,什么矩阵可以分解?什么矩阵不可以分解?以及分解的形式是否唯一?

1. 什么矩阵可以分解

很容易找到矩阵[0110]\begin{bmatrix}0&&1\\1 &&0 \end{bmatrix},此矩阵可逆但是没有三角分解。

定理1:

n阶方阵A具有唯一LR分解的充要条件是A的前 n - 1个顺序主子式不为零。

其中, A=(a11a12a1na21a22a2nan1an2ann)A=\begin{pmatrix} a_{11} & a_{12} & \cdots & a_{1 n} \\ a_{21} & a_{22} & \cdots & a_{2 n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n 1} & a_{n 2} & \cdots & a_{n n} \end{pmatrix},第k个顺序主子式Δk=a11a12a1ka21a22a2kak1ak2akk\Delta_{k}=\left|\begin{array}{cccc} a_{11} & a_{12} & \cdots & a_{1 k} \\ a_{21} & a_{22} & \cdots & a_{2 k} \\ \vdots & \vdots & \ddots & \vdots \\ a_{k 1} & a_{k 2} & \cdots & a_{k k} \end{array}\right|
易知a110a_{11}\ne0,那么对A进行行初等变换,把除了第一行以外的所有行的第一个元素全部消除,相当于在A的左边乘以下三角矩阵L1L_{1},其中:

L1=[1a21a1111a31a1110an1a111001]L_{1}=\left[\begin{array}{ccccc} 1 & & & \\ -a_{21} a_{11}^{-1} & 1 & & & \\ -a_{31} a_{11}^{-1} & 0 & \ddots & & \\ \vdots& \vdots & \ddots & \ddots & \\ -a_{n 1} a_{11}^{-1} & 0 & \cdots & 0 & 1 \end{array}\right]

此时有:

L1A[a11a12a1n0a22(1)a2n(1)0an2(1)am(1)]L_{1} A \triangleq\left[\begin{array}{cccc} a_{11} & a_{12} & \cdots & a_{1 n} \\ 0 & a_{22}^{(1)} & \cdots & a_{2 n}^{(1)} \\ \vdots & \vdots & \ddots & \vdots \\ 0 & a_{n 2}^{(1)} & \cdots & a_{m}^{(1)} \end{array}\right]

接着构造下一个下三角矩阵L2L_{2},将第二列对角线以下的元素全部消除,注意此时的条件Δ2=a11a22(2)0,a110\Delta_{2} = a_{11}\cdot a_{22}^{(2)}\ne0,a_{11}\ne0,即a22(2)0a_{22}^{(2)}\ne0.

L2=[1010a32(1)/a22(1)10a42(1)/a22(1)00an2(1)/a22(1)001]L_{2} =\left[\begin{array}{ccccc} 1 & & & & & \\ 0 & 1 & & & & \\ 0 & -a_{32}^{(1)} / a_{22}^{(1)} & 1 & & & \\ 0 & -a_{42}^{(1)} / a_{22}^{(1)} & 0 & \ddots & & \\ \vdots & \vdots & \vdots & \ddots & \ddots & \\ 0 & -a_{n 2}^{(1)} / a_{22}^{(1)} & 0 & \cdots & 0 & 1 \end{array}\right]

继续左乘在L1AL_{1}A处,有:

L2L1A=[a11a12a13a1na22(1)a22(1)a2n(1)a33(2)a3n(2)00an3(2)am(2)]L_{2} L_{1} A= \left[\begin{array}{ccccc} a_{11} & a_{12} & a_{13} & \cdots & a_{1 n} \\ &a_{22}^{(1)} & a_{22}^{(1)} & \cdots & a_{2 n}^{(1)} \\ &\vdots & a_{33}^{(2)} & \cdots & a_{3 n}^{(2)} \\ & 0& \vdots & \ddots & \vdots \\ &0 & a_{n 3}^{(2)} & \cdots & a_{m}^{(2)} \end{array}\right]

以此类推,最终可以化简得到:

Ln1L2L1A=[a11a12a13a1na22(1)a22(1)a2n(1)a33(2)a3n(2)am(n1)]RL_{n-1} \cdots L_{2} L_{1} A=\left[\begin{array}{ccccc} a_{11} & a_{12} & a_{13} & \cdots & a_{1 n} \\ & a_{22}^{(1)} & a_{22}^{(1)} & \cdots & a_{2 n}^{(1)} \\ & & a_{33}^{(2)} & \cdots & a_{3 n}^{(2)} \\ & & & \ddots & \vdots \\ & & & & a_{m}^{(n-1)} \end{array}\right] \triangleq R

Ln1L2L1=L1L_{n-1}\cdots L_{2} L_{1}=L^{-1},则有L1A=RL^{-1}A =R,L也是下三角矩阵,且为单位下三角矩阵。(下三角矩阵的逆仍然为下三角矩阵)

2. 那什么情况下不能分解呢?

我们看看上面的过程,是不是每一次乘以 LiL_{i} 矩阵时,都需要第 ii 个主对角元素不为0,这样才能作为分母,把该列下面的元素全部通过初等行变换消掉,如果矩阵 LiL1AL_{i}\cdots L_{1}A 的第 ii 个主对角元素为0,那么久不能再乘以 LL 了,举个例子:

A=[21442132220]=r22r1,r3r1[2140050116]A = \left[\begin{array}{ccc} 2 & 1 & 4 \\ 4 & 2 &13 \\ 2& 2 & 20 \\ \end{array}\right] \xlongequal{r_{2} - 2r_{1},r_{3}-r_{1}} \left[\begin{array}{ccc} 2 & 1 & 4 \\ 0 & 0&5 \\ 0& 1 & 16 \\ \end{array}\right]

此时就无法继续化成上三角了。

2. 什么情况分解唯一

上面也讲了,当顺序主子式不等于0时,具有唯一分解。那么什么情况下不唯一呢?当然是顺序主子式等于0的情况,但是同时要注意上面举例说过如果碰到主子式等于0很可能出现无法继续化简的情况,但是如果恰好碰到该列下面所有元素都为0时,那就不用乘这个LL了。我们举例说明:

A=[2144213006]=r22r1[214005006]A = \left[\begin{array}{ccc} 2 & 1 & 4 \\ 4 & 2 &13 \\ 0& 0 & 6 \\ \end{array}\right] \xlongequal{r_{2} - 2r_{1}} \left[\begin{array}{ccc} 2 & 1 & 4 \\ 0 & 0&5 \\ 0& 0 & 6 \\ \end{array}\right]

恰好第三行需要消除的元素本身就为0.

但是此时有一个问题就是,我可以当作看成第三行没有变,我也可以是将任意倍数的第二行加到第三行,那么此时的L2L_{2}既可以是单位阵,也可以是其他下三角矩阵,即L2L_{2}不唯一,那么所有LL的乘积自然不唯一。

A=[2144213006]=[121001][214005006]=[121011][214005001]A = \left[\begin{array}{ccc} 2 & 1 & 4 \\ 4 & 2 &13 \\ 0& 0 & 6 \\ \end{array}\right] = \left[\begin{array}{ccc} 1 & & \\ 2 & 1& \\ 0& 0 & 1 \\ \end{array}\right]\cdot \left[\begin{array}{ccc} 2 & 1 & 4 \\ 0 & 0&5 \\ 0& 0 & 6 \\ \end{array}\right] = \left[\begin{array}{ccc} 1 & & \\ 2 & 1& \\ 0& 1 & 1 \\ \end{array}\right]\cdot \left[\begin{array}{ccc} 2 & 1 & 4 \\ 0 & 0&5 \\ 0& 0 & 1 \\ \end{array}\right]

二、带行变换的LU分解

之前说过,如果遇到某次变换后的主对角元素为0那么就不能继续进行变换,但是我们要是将下面的行移上来呢,那主对角元素不就非0了吗?
我们用增广矩阵的形式来描述上述过程:

[AInIn][PAPIn][PAQPQ]=[LPQ]\left [ \begin{array}{c:c} A& I_{n}\\ \hdashline I_{n}& \end{array} \right ] \rightarrow \left [ \begin{array}{c:c} PA& P\\ \hdashline I_{n}& \end{array} \right ]\rightarrow \left [ \begin{array}{c:c} PAQ& P\\ \hdashline Q& \end{array} \right ] = \left [ \begin{array}{c:c} L& P\\ \hdashline Q& \end{array} \right ]

整个过程的目的就是将A变成下三角矩阵,由于每次只会将右边的列换到左边,所以QQ一定是上三角阵,P为置换阵(多个初等行变换相乘)。

PA=LQ1=LRPA = LQ^{-1} = LR

三、LDR分解

若满秩方阵A有LR分解:

A=LR~A = L\cdot \widetilde{R}

R~\widetilde{R}也是满秩矩阵,且对焦元素不为0,有:

R~=[d1d2dn][1r12r1n1r(n1)n1]\widetilde{R}=\left[\begin{array}{cccc} d_{1} & & & \\ & d_{2} & & \\ & & \ddots & \\ & & & d_{n} \end{array}\right]\left[\begin{array}{cccc} 1 & r_{12} & \cdots & r_{1 n} \\ & 1 &\ddots &\vdots \\ & & \ddots& r_{(n-1) n}\\ & &&1 \end{array}\right]

从而A=LDRA = LDR,其中L为单位下三角阵,D为对角阵,R为单位上三角阵。
与LR分解对比,我们只需要知道如何分解得到:
R~=DR\widetilde{R} = DR,举例说明:

R~=[2141511]=[2111][11/22151]\widetilde R = \left[\begin{array}{ccc} 2 & 1 & 4 \\ & 1 &5 \\ & & 11 \\ \end{array}\right] = \left[\begin{array}{ccc} 2 & & \\ & 1 & \\ & & 11 \\ \end{array}\right] \cdot \left[\begin{array}{ccc} 1 & 1/2 & 2 \\ & 1 &5 \\ & & 1 \\ \end{array}\right]

实际上就是除以该行的主对角元素,因为对角矩阵只是会缩放当前行(左乘时),将D分解出去相当于提出了一个系数。

四、Cholesky分解

若矩阵A是对称正定矩阵,其顺序主子式Δk>0\Delta_{k}>0,所以A具有唯一的LDR分解,即A=LDRA = LDR,其中D为对角阵:

D=(d1dn)D = \begin{pmatrix} d_{1 }& & &\\ &\ddots&\\ & &d_{n}\\ \end{pmatrix}

由于A是对称矩阵,则有A=AT=LDR=(LDR)T=RTDLTA = A^{T}=LDR=(LDR)^{T}=R^{T}DL^{T},同时LDR分解是唯一的,说明:L=RTL=R^{T},A也可以表示为:

A=LDR=LD12D12LT=LD12(LD12)T=GGTA=LDR=LD^{\frac{1}{2}}D^{\frac{1}{2}}L^{T}=LD^{\frac{1}{2}}(LD^{\frac{1}{2}})^{T}=GG^{T }

这里需要说明,因为A是正定的,D作为对角阵所有元素都是大于零的 (理由我也讲不清楚,但是D的子行列式(d1d2dkd_{1}\cdot d_{2}\cdots d_{k})是等于A对应的顺序主子式Δk\Delta_{k}的),所以 D12D^{\frac{1}{2}} 相当于所有元素did_{i}开方求得。
举例:

[AInIn][PAPTPPT][DGGT]\left [ \begin{array}{c:c} A& I_{n}\\ \hdashline I_{n}& \end{array} \right ] \rightarrow \left [ \begin{array}{c:c} PAP^{T}& P\\ \hdashline P^{T}& \end{array} \right ]\rightarrow \left [ \begin{array}{c:c} D& G\\ \hdashline G^{T}& \end{array} \right ]

解释一下,这里对A同时进行行和列的变换,因为A是对称矩阵,那么行怎么化简消除,列也应该怎么化简消除,所以两边是转置的关系,又因为总是消除下面的行,消除右边的列,所以P是下三角矩阵,最后的G也是下三角矩阵。

本位最初发表于2021.11 @肆拾伍

Q.E.D.


几时归去,做个闲人