高等工程数学（一） 矩阵的三角分解 （LU分解，LDR分解，Cholesky分解）

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

前言

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

一、LR（LU）分解，也称Doolittle分解

若矩阵A可以表示为：

A = L·R

其中，L为单位下三角矩阵，R为上三角矩阵，则称A可三角分解（LR分解）。例如：

A = [ 2 1 4 4 3 13 2 2 20 ] = [ 1 2 1 1 1 1 ] ⋅ [ 2 1 4 1 5 11 ] = L ⋅ R A =

$$\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 A=⎣⎡​242​132​41320​⎦⎤​=⎣⎡​121​11​1​⎦⎤​⋅⎣⎡​2​11​4511​⎦⎤​=L⋅R
LR分解可以用于解线性方程组 $Ax=b$，若方阵A有LR分解，即$A=L\cdot R$，令$Rx=y$，则方程组等价于：
$$\{\begin{array}{r}Ly=b\\ Rx=y\end{array}，此处L.R.b均为已知量$$
由于L和R的特殊形式，$Ly=b$ 很容易利用高斯消元迭代求出y，然后代入$Rx=y$，再次迭代求出x。

• 那么提出两个问题，是否所有矩阵可分解？分解的形式是否唯一？

  1. 什么矩阵可以分解

  很容易找到矩阵$\left[\begin{array}{ccc}0& & 1\\ 1& & 0\end{array}\right]$，此矩阵可逆但是没有三角分解。
  定理1： n阶方阵A具有唯一LR分解的充要条件是A的前 n - 1个顺序主子式不为零。
  其中， $A=\left(\begin{array}{cccc}{a}_{11}& a_{12}& \cdots & a_{1n}\\ a_{21}& a_{22}& \cdots & a_{2n}\\ ⋮& ⋮& \ddots & ⋮\\ a_{n1}& a_{n2}& \cdots & a_{nn}\end{array}\right)$ ，第k个顺序主子式${\Delta }_k=\left|\begin{array}{cccc}{a}_{11}& a_{12}& \cdots & a_{1k}\\ a_{21}& a_{22}& \cdots & a_{2k}\\ ⋮& ⋮& \ddots & ⋮\\ a_{k1}& a_{k2}& \cdots & a_{kk}\end{array}\right|$
  易知$a_{11}\ne 0$，那么对A进行行初等变换，把除了第一行以外的所有行的第一个元素全部消除，相当于在A的左边乘以下三角矩阵$L_1$，其中：$$L_1=\left[\begin{array}{ccccc}1& & & & \\ -a_{21}{a}_{11}^{-1}& 1& & & \\ -a_{31}{a}_{11}^{-1}& 0& \ddots & & \\ ⋮& ⋮& \ddots & \ddots & \\ -a_{n1}{a}_{11}^{-1}& 0& \cdots & 0& 1\end{array}\right]$$
  此时有：$$L_{1}A\triangleq \left[\begin{array}{cccc}{a}_{11}& a_{12}& \cdots & a_{1n}\\ 0& a_{22}^{(1)}& \cdots & a_{2n}^{(1)}\\ ⋮& ⋮& \ddots & ⋮\\ 0& a_{n2}^{(1)}& \cdots & a_m^{(1)}\end{array}\right]$$
  接着构造下一个下三角矩阵$L_2$，将第二列对角线以下的元素全部消除，注意此时的条件${\Delta }_2=a_{11}\cdot a_{22}^{(2)}\ne 0,a_{11}\ne 0,即a_{22}^{(2)}\ne 0.$

L 2 = [ 1 0 1 0 − a 32 ( 1 ) / a 22 ( 1 ) 1 0 − a 42 ( 1 ) / a 22 ( 1 ) 0 ⋱ ⋮ ⋮ ⋮ ⋱ ⋱ 0 − a n 2 ( 1 ) / a 22 ( 1 ) 0 ⋯ 0 1 ] 继 续 左 乘 在 L 1 A 处 ， 有 L 2 L 1 A = [ a 11 a 12 a 13 ⋯ a 1 n a 22 ( 1 ) a 22 ( 1 ) ⋯ a 2 n ( 1 ) ⋮ a 33 ( 2 ) ⋯ a 3 n ( 2 ) 0 ⋮ ⋱ ⋮ 0 a n 3 ( 2 ) ⋯ a m ( 2 ) ]

$$\begin{gathered} 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] 继续左乘在L_{1}A处，有 \\ 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] \end{gathered}$$ L2​=L2​L1​A=​⎣⎢⎢⎢⎢⎢⎢⎢⎢⎡​1000⋮0​1−a32(1)​/a22(1)​−a42(1)​/a22(1)​⋮−an2(1)​/a22(1)​​10⋮0​⋱⋱⋯​⋱0​1​⎦⎥⎥⎥⎥⎥⎥⎥⎥⎤​继续左乘在L1​A处，有⎣⎢⎢⎢⎢⎢⎢⎢⎡​a11​​a12​a22(1)​⋮00​a13​a22(1)​a33(2)​⋮an3(2)​​⋯⋯⋯⋱⋯​a1n​a2n(1)​a3n(2)​⋮am(2)​​⎦⎥⎥⎥⎥⎥⎥⎥⎤​​以此类推，最终可以化简得到：
$$L_{n-1}\cdots L_2{L}_{1}A=\left[\begin{array}{ccccc}{a}_{11}& a_{12}& a_{13}& \cdots & a_{1n}\\ & a_{22}^{(1)}& a_{22}^{(1)}& \cdots & a_{2n}^{(1)}\\ & & a_{33}^{(2)}& \cdots & a_{3n}^{(2)}\\ & & & \ddots & ⋮\\ & & & & a_m^{(n-1)}\end{array}\right]\triangleq R$$
记$L_{n-1}\cdots L_2{L}_1=L^{-1}，则有L^{-1}A=R，L也是下三角矩阵，且为单位下三角矩阵$。（下三角矩阵的逆仍然为下三角矩阵）

• 那什么情况下不能分解呢？
  我们看看上面的过程，是不是每一次乘以 $L_i$ 矩阵时，都需要第 $i$ 个主对角元素不为0，这样才能作为分母，把该列下面的元素全部通过初等行变换消掉，如果矩阵 $L_i\cdots L_{1}A$ 的第 $i$ 个主对角元素为0，那么久不能再乘以 $L$ 了，举个例子：
  $$A=\left[\begin{array}{ccc}2& 1& 4\\ 4& 2& 13\\ 2& 2& 20\end{array}\right]\stackrel{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时，那就不用乘这个$L$了。我们举例说明：
  $$A=\left[\begin{array}{ccc}2& 1& 4\\ 4& 2& 13\\ 0& 0& 6\end{array}\right]\stackrel{r_2-2r_1}{=}\left[\begin{array}{ccc}2& 1& 4\\ 0& 0& 5\\ 0& 0& 6\end{array}\right],恰好第三行需要消除的元素本身就为0.$$
  但是此时有一个问题就是，我可以当作看成第三行没有变，我也可以是将任意倍数的第二行加到第三行，那么此时的$L_2$既可以是单位阵，也可以是其他下三角矩阵，即$L_2$不唯一，那么所有$L$的乘积自然不唯一。
  $$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了吗？
我们用增广矩阵的形式来描述上述过程：

[ A I n I n ] → [ P A P I n ] → [ P A Q P Q ] = [ L P Q ] \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 ] [AIn​​In​​​]→[PAIn​​P​​]→[PAQQ​P​​]=[LQ​P​​]
整个过程的目的就是将A变成下三角矩阵，由于每次只会将右边的列换到左边，所以$Q$一定是上三角阵，P为置换阵（多个初等行变换相乘）。
$$PA=L{Q}^{-1}=LR$$

三、LDR分解

若满秩方阵A有LR分解：
$$A=L\cdot \tilde{R}$$
则$\tilde{R}$也是满秩矩阵，且对焦元素不为0，有：
R ~ = [ d 1 d 2 ⋱ d n ] [ 1 r 12 ⋯ r 1 n 1 ⋱ ⋮ ⋱ r ( n − 1 ) n 1 ] \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] R =⎣⎢⎢⎡​d1​​d2​​⋱​dn​​⎦⎥⎥⎤​⎣⎢⎢⎢⎡​1​r12​1​⋯⋱⋱​r1n​⋮r(n−1)n​1​⎦⎥⎥⎥⎤​
从而$A=LDR$,其中L为单位下三角阵，D为对角阵，R为单位上三角阵。
与LR分解对比，我们只需要知道如何分解得到：
$$\tilde{R}=DR$$，举例说明：
$$\tilde{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是对称正定矩阵，其顺序主子式${\Delta }_k>0$，所以A具有唯一的LDR分解，即$A=LDR$，其中D为对角阵：
D = ( d 1 ⋱ d n ) D =

$$\begin{pmatrix} d_{1 }& & &\\ &\ddots&\\ & &d_{n}\\ \end{pmatrix}$$ D=⎝⎛​d1​​⋱​dn​​⎠⎞​
由于A是对称矩阵，则有$A=A^T=LDR=(LDR{)}^T=R^{T}D{L}^T$，同时LDR分解是唯一的，说明：$L=R^T$,A也可以表示为：
$$A=LDR=L{D}^{\frac{1}{2}}{D}^{\frac{1}{2}}{L}^T=L{D}^{\frac{1}{2}}(L{D}^{\frac{1}{2}}{)}^T=G{G}^T$$
这里需要说明，因为A是正定的，D作为对角阵所有元素都是大于零的 （理由我也讲不清楚，但是D的子行列式（$d_1\cdot d_2\cdots d_k$）是等于A对应的顺序主子式${\Delta }_k$的）,所以 $D^{\frac{1}{2}}$ 相当于所有元素$d_i$开方求得。
举例：$$\left[\begin{array}{cc}A& I_n\\ I_n& \end{array}\right]\to \left[\begin{array}{cc}PA{P}^T& P\\ P^T& \end{array}\right]\to \left[\begin{array}{cc}D& G\\ G^T& \end{array}\right]$$
解释一下，这里对A同时进行行和列的变换，因为A是对称矩阵，那么行怎么化简消除，列也应该怎么化简消除，所以两边是转置的关系，又因为总是消除下面的行，消除右边的列，所以P是下三角矩阵，最后的G也是下三角矩阵。