LU 分解

LU 分解；对于一个 $m \times n$ 矩阵 $A$ ，可以在不使用行交换的情况下，将其行化简为阶梯型矩阵 $U\in \mathbb R^{m \times n}$，行化简对应的变换矩阵为 $L \in \mathbb R^{m \times m}$，那么我们有

$$A = LU$$

此时，这样的分解就称为 LU 分解。

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

那么，我们如果可以写成 $A = LU$，那么对于 $A \boldsymbol{x} = \boldsymbol{b}$，我们可以写成

$$L(U\boldsymbol{x}) = \boldsymbol{b}$$

我们首先解 $L \boldsymbol{y} = \boldsymbol{b}$，再解 $U\boldsymbol{x} = \boldsymbol{y}$，由于 $L, U$ 都是三角矩阵，它们都比较容易解，因此我们可以快速地解出 $\boldsymbol{x}$。

LU 分解算法

普通 $LU$ 分解（不包含行变换）：$\boldsymbol{A = LU}$

在行化简的过程中，每次用一个主元进行行化简之前，将每个主元及以下的数字除以该主元之后，放入 $L$ 的对应位置。最终我们就可以得到矩阵 $L$。

由列行法则可知， $L$ 中的主元列乘以 $U$ 的主元行就得到该主元对每一行的贡献，因此该分解是成立的。

置换 $LU$ 分解（包含行变换）：$\boldsymbol{PA = LU}$

在进行行化简的过程中，我们常常使用 部分主元法 来化简，也就是需要行交换以让主元列中绝对值最大的元素作为主元。

那么我们可以用 $P$ 来表示我们进行若干次行交换之后原先的列最终去到了那一行，然后再使用正常的 $LU$ 分解即可。