矩阵的三角分解

【LU 分解】

若方阵 $A$ 可分解为

$$A=LU$$

其中，$L$ 为单位下三角阵，$U$ 为上三角阵，则称 $A$ 可三角分解，或称 $A$ 可 LU 分解、Doolittle 分解

对于 $n$ 阶方阵 $A=[a_{ij}]$ 有唯一的 LU 分解的充要条件是：$A$ 的前 $n-1$ 个顺序主子式 $\Delta_k\neq 0,1\leq k\leq n-1$，其中

$$\Delta_k=\left|\begin{array}{c} a_{11} & a_{12} & \cdots & a_{1k} \\ a_{21} & a_{22} & \cdots & a_{2k} \\ \vdots & \vdots & \ddots & \vdots \\ a_{k1} & a_{k2} & \cdots & a_{kk} \\ \end{array}\right|$$

---

LU 分解的一个具体方法是：对 $A$ 的增广矩阵 $\left[ \begin{array}{c:c}A&I\end{array}\right]$ 进行初等变换，变换成一个上三角阵和单位下三角阵的格式 $\left[ \begin{array}{c:c}U&L^{-1}\end{array}\right]$，此时即可得 $A=LU$

例：

$$A=\begin{bmatrix} 2&1&4\\ 4&3&13\\ 2&2&20 \end{bmatrix}$$

对 $A$ 的增广矩阵进行初等变换

$$\left[ \begin{array}{c:c}A&I\end{array}\right] \rightarrow \left[ \begin{array}{c:c} \begin{matrix} 2&1&4\\ &1&5\\ &&1 \end{matrix} & \begin{matrix} 1&&\\ -2&1&\\ 1&-1&1 \end{matrix} \end{array}\right] \triangleq \left[ \begin{array}{c:c}U&L^{-1}\end{array}\right]$$

可得

$$L=\begin{bmatrix} 1&&\\ 2&1&\\ 1&1&1 \end{bmatrix}$$

故有

$$A=LU=\begin{bmatrix} 1&&\\ 2&1&\\ 1&1&1 \end{bmatrix}\begin{bmatrix} 2&1&4\\ &1&5\\ &&1 \end{bmatrix}$$

【带行交换的 LU 分解】

对于 $n$ 阶方阵 $A$，若其前 $n-1$ 个顺序主子式 $\exists \Delta_k=0$，则 $A$ 无法进行 LU 分解

但若 $A$ 为满秩矩阵，那么存在置换矩阵 $P$，使得 $PA$ 有 LU 分解，此时称为带行交换的 LU 分解

设 $A$ 是带有行交换的三角分解 $PA=LU$，由于 $A$ 满秩，故 $U$ 可逆，记 $Q=U^{-1}$，则 $Q$ 亦为上三角阵，于是有 $PAQ=L$，而上三角阵可逆 $Q$ 右乘 $A$，相当于对 $A$ 进行行初等变换，故分解过程如下：

$$\left[ \begin{array}{c:c} A&I\\ \hdashline I \end{array}\right] \stackrel{行置换}{\longrightarrow} \left[ \begin{array}{c:c} PA&P\\ \hdashline I \end{array}\right] \stackrel{向右列变换}{\longrightarrow} \left[ \begin{array}{c:c} PAQ&P\\ \hdashline Q \end{array}\right] \triangleq \left[ \begin{array}{c:c} L&P\\ \hdashline Q \end{array}\right]$$

则有 $PAQ=L$，从而

$$PA=LQ^{-1}=LU$$

【LDU 分解】

设方阵 $A$ 有 LU 分解

$$A=LU_1$$

若 $A$ 可逆，则上三角阵 $U_1$ 也可逆，其主对角线元素均不为 $0$

因此，$U_1$ 必可分解为对角阵 $D$ 和单位上三角阵 $U$ 的乘积，即有

$$A=LDU$$

称为方阵 $A$ 的 LDU 分解，其中，$L$ 为单位下三角阵，$D$ 为对角阵，$U$ 为单位上三角阵

---

例：

$$A=\begin{bmatrix} 2&1&4\\ 4&3&13\\ 2&2&20 \end{bmatrix}$$

由前例可知，$A$ 有 LU 分解，且 $A$ 可逆，故

$$\begin{align*} A=&\begin{bmatrix} 1&&\\ 2&1&\\ 1&1&1 \end{bmatrix}\begin{bmatrix} 2&1&4\\ &1&5\\ &&1 \end{bmatrix} \\ =& \begin{bmatrix} 1&&\\ 2&1&\\ 1&1&1 \end{bmatrix}\begin{bmatrix} 2&&\\ &1&\\ &&11 \end{bmatrix}\begin{bmatrix} 1&\frac{1}{2}&2\\ &1&5\\ &&1 \end{bmatrix} \end{align*}$$

【Cholesky 分解】

当 $A$ 是对称正定矩阵时，其顺序主子式 $\Delta_k>0(0\leq k\leq n)$，故 $A$ 有唯一的 LDU 分解 $A=LDU$，记

$$D=\text{diag} (d_1,d_2,\cdots,d_n),\quad d_i>0,1\leq i\leq n$$

由于 $A=A^T$，故有

$$LDU=(LDU)^T=U^TDL^T$$

由 LDU 分解的唯一性，可知 $L=U^T$，令

$$D^{\frac{1}{2}}=\text{diag} (\sqrt{d_1},\sqrt{d_2},\cdots,\sqrt{d_n})$$

则有

$$A=LDU=LD^{\frac{1}{2}}D^{\frac{1}{2}}L^T=(D^{\frac{1}{2}}L^T)(LD^{\frac{1}{2}})^T\triangleq GG^T$$

称为对称正定矩阵的 Cholesky 分解或平方根分解，其中，$G=LD^{\frac{1}{2}}$ 为下三角阵，其主对角元素均大于 $0$