线性代数 Cheat Sheet 2-5：矩阵因式分解

Author: nex3z 2018-11-21

　　矩阵 $A$ 的因式分解是把 $A$ 表示为两个或更多个矩阵的乘积。矩阵乘法是数据的综合，矩阵因式分解是数据的分解，分解后的结构可能更有用，或更便于计算。

1. LU 分解

　　设 $A$ 是 $m \times n$ 矩阵，它可以行化简为阶梯形而不必进行行对换，则 $A$ 可写成形式 $A = LU$，$L$ 是 $m \times m$ 下三角矩阵，主对角线元素全是 $1$，$U$ 是 $A$ 的一个 $m \times n$ 阶梯形矩阵。

$$\begin{equation} A = LU = \begin{bmatrix} 1 & 0 & 0 & 0 \\ * & 1 & 0 & 0 \\ * & * & 1 & 0 \\ * & * & * & 1 \end{bmatrix} \begin{bmatrix} \blacksquare & * & * & * & * \\ 0 & \blacksquare & * & * & * \\ 0 & 0 & 0 & \blacksquare & * \\ 0 & 0 & 0 & 0 & 0 \end{bmatrix} \end{equation}$$

　　其中矩阵 $L$ 是可逆的，称为单位下三角矩阵。

　　当 $A = LU$ 时，方程 $A \boldsymbol x = \boldsymbol b$ 可以写成 $L(U \boldsymbol x) = \boldsymbol b$，把 $U \boldsymbol x$ 写成 $\boldsymbol y$，则可以由解下面一对方程来求解 $\boldsymbol x$：

$$\begin{equation} L \boldsymbol y = \boldsymbol b \\ U \boldsymbol x = \boldsymbol y \end{equation}$$

首先解 $L \boldsymbol y = \boldsymbol b$ 求得 $\boldsymbol y$，然后解 $U \boldsymbol x = \boldsymbol y$ 求得 $\boldsymbol x$。由于 $L$ 和 $U$ 都是三角矩阵，这两个方程都比较容易解。

2. LU 分解算法

　　设 $A$ 可以化为阶梯形 $U$，化简过程中仅使用行倍加变换，此时存在单位下三角矩阵 $E_1, \cdots, E_p$，使

$$\begin{equation} E_p \cdots E_1 A = U \tag{1} \end{equation}$$

于是

$$\begin{equation} A = (E_p \cdots E_1)^{-1}U = LU \end{equation}$$

其中

$$\begin{equation} L = (E_p \cdots E_1)^{-1} \tag{2} \end{equation}$$

　　可以证明，单位下三角矩阵的乘积和逆也是单位下三角矩阵，于是 $L$ 是单位下三角矩阵。

　　由 $(2)$ 式有

$$\begin{equation} E_p \cdots E_1 L = I \end{equation}$$

可见 $(1)$ 中的行变换 $E_p \cdots E_1$ 把 $A$ 化为 $U$，也把 $L$ 化为 $I$。

　　LU 分解的算法
1. 如果可能的话，用一系列的行倍加变换把 $A$ 化为阶梯形 $U$。
2. 填充 $L$ 的元素使相同的行变换把 $L$ 变为 $I$。

　　注意上面的第 1 步并不总是可能的，如果可能，则 LU 分解存在。