LU分解

LU分解是一种矩阵分解，将一个矩阵表示为下三角矩阵与上三角矩阵的乘积。其最简单的形式为 $A=LU$，其中 $L$ 是下三角矩阵，$U$ 是上三角矩阵。实际实现通常会引入行置换，得到 $PA=LU$。这种分解将高斯消元法的操作记录为可重复利用的形式，是数值线性代数中的重要工具，尤其适用于求解线性方程组。(cs.cornell.edu)

定义与存在性

对于一个 $n\times n$ 方阵，三角结构意味着

通常的规范化约定是令 $l_{ii}=1$；这样的 $L$ 称为单位下三角矩阵。这一约定消除了在两个因子之间重新分配非零对角缩放因子的自由度。对于非奇异矩阵，当且仅当其每个顺序主子矩阵均非奇异时，不含置换的规范化LU分解才存在且唯一。等价地，它的所有顺序主子式均不为零。这些主子式就是左上角 $k\times k$ 子矩阵的行列式，其中 $k=1,\ldots,n$。(cs.utexas.edu)

仅有非奇异性并不能保证不含置换的LU分解存在。例如，

虽然可逆，但其第一个主元为零。交换两行后得到单位矩阵，其三角因子显而易见。每个非奇异方阵都存在带行置换的分解 $PA=LU$，其中 $P$ 是置换矩阵。有些文献使用逆置换，写成 $A=PLU$；解读软件输出时，必须区分这些约定。(cs.cornell.edu)

矩形矩阵也可以进行带主元选取的LU分解。对于大小为 $m\times n$ 的矩阵 $A$，令 $r=\min(m,n)$，可得到大小分别为 $m\times r$ 和 $r\times n$ 的因子，具有三角形或梯形结构。奇异矩阵仍然可以分解，但 $U$ 中的零对角元素会使常规三角求解过程无法用于任意方程组。(netlib.org)

通过消元构造分解

在第 $k$ 步消元中，假设主元非零，算法先计算乘子

再更新其余元素：

这里，$a^{(k)}$ 表示该步骤开始时的矩阵。由待消去元素计算出的乘子存入 $L$，剩余的上三角部分则构成 $U$。右下剩余部分的更新是减去一个外积；以分块形式表示时，更新后的剩余矩阵是一个舒尔补。(cs.utexas.edu)

一个简单的例子是

乘子为 $2$，即从第二行中减去第一行的两倍，使第二个主元变为 $1$。

对于稠密方阵，若将乘法和加法分别计为一次运算，常规消元大约需要 $\tfrac23n^3$ 次浮点运算。因此，其计算复杂性为 $O(n^3)$。实现时通常将两个因子存放在同一个数组中：$U$ 占据对角线及上三角部分，严格下三角部分存储 $L$ 的相应元素，而 $L$ 的单位对角线无需显式存储。(cs.utexas.edu)

主元选取与数值精度

在浮点运算中，过小的主元可能产生很大的乘子，并放大舍入误差。部分主元选取在当前参与消元的列中选择绝对值最大的元素，并将其所在行与主元行交换。这使消元乘子的绝对值不超过一。完全主元选取则搜索整个当前参与消元的子矩阵，同时交换行和列，得到 $PAQ=LU$。(cs.cornell.edu)

部分主元选取通常具有良好的数值稳定性，但并不能提供无条件的保证。某些特殊矩阵的中间元素可能出现显著增长。后向误差分析将计算得到的因子与受到微小扰动的输入矩阵联系起来，其误差界取决于因子元素的大小。即使后向误差很小，也未必意味着解的误差很小：解的敏感性还取决于矩阵的条件数。(cs.cornell.edu)

求解方程组与计算行列式

得到 $PA=LU$ 后，求解 $Ax=b$ 就归结为

第一个三角方程组用前代法求解，第二个则用回代法求解。由于 $L$ 的对角元素均为一，

对于每个新的右端向量，只需 $O(n^2)$ 次运算，因此计算成本较高的分解结果可以重复利用。(cs.cornell.edu)

当 $L$ 的对角元素均为一时，

其中 $s$ 是行交换次数。置换的符号不可忽略。因此，完成分解后，只需计算对角元素的乘积以及行交换次数的奇偶性，即可求出行列式。(cs.cornell.edu)

结构化矩阵与相关分解

对于稀疏矩阵，消元可能在原矩阵的零元素位置产生非零元素，这种现象称为填充。稀疏求解器采用排序策略来控制存储量和运算量。它们通常使用 $PAQ=LU$，其中列置换主要用于减少填充，行置换则用于维持稳定性。(cs.cornell.edu)

稠密矩阵的实现则利用分块更新和矩阵乘法，提高内存数据的复用效率并支持并行计算。主元搜索和行交换会引入通信开销，从而可能限制并行性能。(cs.cornell.edu)

相关分解利用了矩阵的不同性质。对于对称或厄米正定矩阵，Cholesky分解利用其对称性，无需选取主元即可稳定地进行分解。矩形矩阵的最小二乘问题通常采用QR分解；当需要处理矩阵的秩不足的情形时，奇异值分解则可用于求取最小二乘解。(cs.cornell.edu)