本文介绍了矩阵的三角分解，如LU分解，LDR分解，Cholesky分解等。
为博主在学习过程中，总结或者思考的记录，用于加深印象，不作为知识讲解和科普，如果理解有误还请指出。
前言
对矩阵进行分解能够清晰反应出原矩阵的某些数字特征，在矩阵运算中可以起到化简的作用，其次在一些特定的场合将矩阵分解为合适的形式能够减少运算误差，在数值计算中有很重要的地位。
一、LR（LU）分解，也称Doolittle分解
若矩阵A可以表示为：
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
LR分解可以用于解线性方程组 Ax = b，若方阵A有LR分解，即A = L\cdot R，令Rx = y，则方程组等价于：
\left \{\begin{aligned} Ly = b \\ Rx = y\end{aligned}\right. ，此处L.R.b均为已知量
由于L和R的特殊形式，Ly = b 很容易利用高斯消元迭代求出y，然后代入Rx = y，再次迭代求出x。
那么提出三个问题，什么矩阵可以分解？什么矩阵不可以分解？以及分解的形式是否唯一？
1. 什么矩阵可以分解
很容易找到矩阵\begin{bmatrix}0&&1\\1 &&0 \end{bmatrix}，此矩阵可逆但是没有三角分解。
定理1：
其中， 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个顺序主子式\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|
易知a_{11}\ne0，那么对A进行行初等变换，把除了第一行以外的所有行的第一个元素全部消除，相当于在A的左边乘以下三角矩阵L_{1}，其中：
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]
此时有：
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]
接着构造下一个下三角矩阵L_{2}，将第二列对角线以下的元素全部消除，注意此时的条件\Delta_{2} = a_{11}\cdot a_{22}^{(2)}\ne0,a_{11}\ne0,即a_{22}^{(2)}\ne0.
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]
以此类推，最终可以化简得到：
L_{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
记L_{n-1}\cdots L_{2} L_{1}=L^{-1}，则有L^{-1}A =R，L也是下三角矩阵，且为单位下三角矩阵。（下三角矩阵的逆仍然为下三角矩阵）
2. 那什么情况下不能分解呢？
我们看看上面的过程，是不是每一次乘以 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] \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时，那就不用乘这个L了。我们举例说明：
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.
但是此时有一个问题就是，我可以当作看成第三行没有变，我也可以是将任意倍数的第二行加到第三行，那么此时的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了吗？
我们用增广矩阵的形式来描述上述过程：
\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变成下三角矩阵，由于每次只会将右边的列换到左边，所以Q一定是上三角阵，P为置换阵（多个初等行变换相乘）。
PA = LQ^{-1} = LR
三、LDR分解
若满秩方阵A有LR分解：
A = L\cdot \widetilde{R}
则\widetilde{R}也是满秩矩阵，且对焦元素不为0，有：
\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 = LDR,其中L为单位下三角阵，D为对角阵，R为单位上三角阵。
与LR分解对比，我们只需要知道如何分解得到：
\widetilde{R} = DR，举例说明：
\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是对称正定矩阵，其顺序主子式\Delta_{k}>0，所以A具有唯一的LDR分解，即A = LDR，其中D为对角阵：
D = \begin{pmatrix}
d_{1 }& & &\\
&\ddots&\\
& &d_{n}\\
\end{pmatrix}
由于A是对称矩阵，则有A = A^{T}=LDR=(LDR)^{T}=R^{T}DL^{T}，同时LDR分解是唯一的，说明：L=R^{T},A也可以表示为：
A=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的子行列式（d_{1}\cdot d_{2}\cdots d_{k}）是等于A对应的顺序主子式\Delta_{k}的）,所以 D^{\frac{1}{2}} 相当于所有元素d_{i}开方求得。
举例：
\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 @肆拾伍