前言

本篇文章不会涉及太多的证明过程

LU分解（Dolittle分解）

定义(LU分解)：如果n阶方阵 $A$ 只使用倍加矩阵 $E_{ji;k}(j>i)$ 做行变换就可以化成阶梯型矩阵，那么存在n阶单位下三角矩阵L和n阶上三角矩阵 $U$ ，使得 $A=LU$

定义(顺序主子阵)：方阵 $A$ 的左上角 $k\times k$ 块，称为 $A$ 的第 $k$ 个顺序主子阵

定义(可逆矩阵的LU分解)：对n阶可逆矩阵A，A有LU分解 $A=LU$ ，当且仅当A的所有顺序主子阵可逆. 此时，A的LU分解唯一

计算LU分解

LU分解来自于Gauss消元，L实际上“记录”了消元的过程，而U实际上“记录”了消元的结果。事实上，读者如果通过其他了解，应知道L是多个倍加矩阵的逆矩阵的乘积，而这些倍加矩阵的逆矩阵在做矩阵乘法运算时一个良好的性质就是它们体现在最终的L矩阵中是“互不干扰”的，通过此性质我们可以直接写出L而无需计算这些倍加矩阵逆矩阵的乘积

我们以3x3Pascal矩阵为例
::: align-center
$A=\begin{bmatrix} 1 & 1 & 1 \\ 1 & 2 & 3 \\ 1 & 3 & 4 \end{bmatrix}$

:::
对其作Gauss消元，则我们的乘数
$l_{21} = l_{31} =\frac{1}{1} = 1$
之后获得
::: align-center
$\begin{bmatrix} 1 & 1 & 1 \\ 0 & 1 & 2 \\ 0 & 2 & 3 \end{bmatrix}$

:::
之后
$l_{32} = \frac{2}{1} = 2$
获得
::: align-center
$\begin{bmatrix} 1 & 1 & 1 \\ 0 & 1 & 2 \\ 0 & 2 & 3 \end{bmatrix}$

:::
Gauss消元到此结束，而我们将获得
::: align-center
$L= \begin{bmatrix} 1\\ l_{21} & 1\\ l_{31} & l_{32} & 1 \end{bmatrix} =\begin{bmatrix} 1 & 0 & 0\\ 1 & 1 & 0\\ 1 & 2 & 1 \end{bmatrix}, U=\begin{bmatrix} 1 & 1 & 1\\ 0 & 1 & 2\\ 0 & 2 & 3 \end{bmatrix}$

:::

LDU分解

LDU分解更近一步，要求U也为单位上三角矩阵，也就是将原来的U分解为DU，其中D是n阶对角矩阵。它是Gasuss-Jordan消元的体现

定义(LDU分解)：如果n阶可逆方针 $A$ 存在LU分解，那么存在n阶单位下三角矩阵L，对角元素均不为零的n阶对角矩阵D，和n阶单位上三角矩阵U，使得 $A=LDU$ ，且该分解唯一

Crout分解

在D为恒同矩阵I时的此分解也叫做Crout分解

LDLT分解

当A为可逆对称矩阵时， $L=U^T$ ，此时分解变为 $A=LDL^T$ ，称为LDLT分解

Cholesky分解

在D为恒同矩阵I时的此分解也叫做Cholesky分解

PLU分解

并非所有矩阵，也并非所有可逆矩阵都有LU分解，因为我们我们限制在消元过程中不能使用对换行变换。但是，我们在解线性方程组时，使用对换行变换只与其出现的先后顺序有关，而与矩阵的元素值无关。因此我们可以把解线性方程组的过程中使用的这一系列对换行变换率先施加在矩阵上，这样得到的矩阵只需要倍加行变换就可以变为阶梯型矩阵了。

所以，我们需要对LU分解做如下拓展，将 $L^{-1}A=U$ 拓展为 $L^{-1}P^{-1}A=U$ ，如此我们便可以得到PLU分解

定义(PLU分解)：给定n阶可逆矩阵 $A$ ，则村子n阶置换矩阵 $P$ ，n阶单位下三角矩阵L，和对角元素不为0的上三角矩阵 $U$ ，使得 $A=PLU$ ，特别地，下三角矩阵 $L$ 可以选为所有元素的绝对值都不大于1的

应用

将矩阵消元法写为矩阵的LU分解或PLU分解，再使用前代法和回代法（正向迭代和反向迭代），可方便的求解线性方程组，具体来说，给定条件合适的矩阵 $A$ ，线性方程组 $Ax=b$ 的求解过程为：

首先求 $A$ 的LU分解 $A=LU$
然后利用前代法求解下三角矩阵对应的线性方程组 $Ly=b$
最后利用回代法求解上三角矩阵对应的线性方程组 $Ux=y$

复杂度

LU分解的复杂度为 $O(n^3)$ ，而向前迭代和向后迭代的复杂度为 $O(n^2)$ ，故总复杂度为 $O(n^3)$