LUD

LUD

LU分解是矩阵分解的一种，将一个矩阵分解为一个下三角矩阵和一个上三角矩阵的乘积，有时需要再乘上一个置换矩阵。LU分解可以被视为高斯消元法的矩阵形式。

定义

对于方阵 $A$，$A$ 的 LU 分解是将它分解成一个下三角矩阵 $L$ 与上三角矩阵 $U$ 的乘积，也就是

$$A = LU$$

并不是每个矩阵都能直接写成 $A=LU$。在很多情况下, 需要先对 $A$ 做行置换, 再写成

$$PA = LU,$$

这就是常见的 PLU 分解。

示例

举例来说一个 $3 \times 3$ 的矩阵 $A$ ，其 LU 分解会写成下面的形式：

$$A = \begin{bmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{bmatrix} = \begin{bmatrix} l_{11} & 0 & 0 \\ l_{21} & l_{22} & 0 \\ l_{31} & l_{32} & l_{33} \end{bmatrix} \begin{bmatrix} u_{11} & u_{12} & u_{13} \\ 0 & u_{22} & u_{23} \\ 0 & 0 & u_{33} \end{bmatrix}$$

事实上，并不是每个矩阵都有 LU 分解。例如，从上式可知 $a_{11} = l_{11}u_{11}$，若 $a_{11} = 0$，则 $l_{11}$ 或 $u_{11}$ 等于 0，故 $L$ 或 $U$ 是非可逆矩阵，$A$ 必须也是非可逆矩阵。然而，存在着可逆矩阵 $A$ 满足 $a_{11} = 0$，这些 $A$ 就是没有 LU 分解的例子。该问题可借由置换 $A$ 的各行顺序来解决，最终会得到一个 $A$ 的 PLU 分解。

消元条件与求解

通常规定 $L$ 的对角元全为 $1$。对可逆方阵，所有顺序主子式非零当且仅当存在这种无需行交换的 LU 分解，此时分解唯一；不作单位对角约定时，因子间可重新分配缩放，不能声称唯一。带行置换的形式约定为 $PA=LU$。

例如 $A=\begin{bmatrix}0&1\\1&1\end{bmatrix}$ 可逆但无 LU 分解。交换两行，取 $P=\begin{bmatrix}0&1\\1&0\end{bmatrix}$，则 $PA=\begin{bmatrix}1&1\\0&1\end{bmatrix}=IU$。求 $Ax=b$ 时先解 $Ly=Pb$，再回代 $Ux=y$；不能漏掉右端的置换。

数值计算即使主元非零，也常使用部分选主元（在当前列剩余行中选绝对值最大的元素）减小除以小数的风险。它通常改善稳定性，但不消除原问题的病态性。