Gaussian 消元与 LU 分解

形式陈述 ​

对方阵 $A\in {\mathbb{F}}^{n\times n}$，Gaussian 消元在第 $k$ 步用主元 $a_{kk}^{(k)}$ 消去其下方元素。若主元非零，乘子和尾部更新为

$$l_{ik}=\frac{a_{ik}^{(k)}}{a_{kk}^{(k)}},a_{ij}^{(k+1)}=a_{ij}^{(k)}-l_{ik}{a}_{kj}^{(k)}(i,j>k).$$

把第 $k$ 步写成左乘一个消元矩阵 $M_k$，便有

$$M_{n-1}\cdots M_{1}A=U,A=LU,$$

其中 $U$ 上三角，$L=M_1^{-1}\cdots M_{n-1}^{-1}$ 是单位下三角，并在严格下三角部分保存所有乘子。标准无置换 LU 在每一步主元都非零时存在；等价地，所有顺序领先主子式非零。可逆本身不足以保证这组条件。

实际通用算法在消元前交换行并记录置换矩阵，得到

$$PA=LU.$$

输入矩阵 $A$ 后，分解阶段输出置换信息与 $L,U$；求解 $Ax=b$ 时依次计算

$$Ly=Pb,Ux=y.$$

稠密分解主成本约为 $2n^3/3$ 次浮点运算，两个三角求解公理库三角线性方程求解Triangular solve · Forward substitution · Backward substitution按依赖顺序用前代或回代求解三角系统，作为 LU、Cholesky 与 QR 分解后的共同计算底层。合计为 $\mathrm{\Theta }(n^2)$。对多个右端，昂贵分解只做一次，每个新右端复用同一因子；因子通常覆盖存回 $A$ 的上下三角部分，另存主元索引，而不是显式保存所有消元矩阵。

这是一种有限步直接法，没有迭代收敛判据。完成准则是每一步都找到可用主元、因子全部生成、三角求解结束；随后检查尺度化残差与非有限值。若某一步候选主元全为零，应报告奇异或秩亏。浮点结果的后向误差还受主元策略与元素增长公理库主元选取与增长因子Pivoting · Growth factor · Partial pivoting通过行列置换限制消元乘子和中间元素增长，并把主元策略与 LU 的有限精度后向误差联系起来。控制，不能从 $O(n^3)$ 成本单独推出可靠性。

直觉 ​

消元不是把方程组一路改写后丢掉过程，而是在构造一个计算图。$L$ 记录“每行用了前面哪一行的多少倍”，$U$ 记录消元后的阶梯结构，$P$ 记录为了找到可靠主元做过的换行。保存这三部分，就能对任何新右端重放前代与回代，而不必重新消元。

这也解释了 Gaussian 消元、Gauss–Jordan、LU 和求逆的分工。Gaussian 消元只把矩阵化到上三角；Gauss–Jordan 继续消去主元上方以得到 RREF；LU 保存前一种消元的因子。为了解 $Ax=b$ 而形成 $A^{-1}$，会额外求出许多当前右端根本不用的信息，并不是默认路线。

例子与边界 ​

矩阵

$$A=\left(\begin{array}{cc}0& 1\\ 1& 1\end{array}\right)$$

可逆，却无法从左上角零元素开始无置换消元。交换两行后

$$PA=\left(\begin{array}{cc}1& 1\\ 0& 1\end{array}\right)$$

已经是上三角矩阵；此例中 $L=I$。它直接否定“每个可逆矩阵都有标准无置换 LU”这一常见误写，也说明行交换不是理论装饰。

若同一 $A$ 要分别求解 $Ax=b_1,\dots ,Ax=b_p$，一次 $PA=LU$ 后只需对每个 $P{b}_j$ 做前代和回代。相比每个右端重复约 $2n^3/3$ 的消元，这正是矩阵分解作为算法组织方式的价值。

小而非零的主元是另一类边界。精确算术允许继续相除，浮点中却可能产生巨大乘子和中间量；仅检查主元是否等于零远远不够。具体怎样选行、何时还需列交换，以及最坏增长如何进入后向误差，由主元页面独立讨论。

推论与应用 ​

行化简公理库行化简Row reduction用初等行变换把矩阵化为阶梯形以求解线性方程组和判定秩。保留行等价、秩与解集的代数解释，本页则规定大规模浮点求解的计算路线：带置换分解，加两次三角求解。Gauss–Jordan 和 RREF 仍适合展示完整解结构，但不应被暗示为稠密方阵单右端的默认数值实现。

行列式可由 $P,L,U$ 的对角线与置换奇偶性得到；多个右端、逆迭代和迭代精化也会复用已有 LU 因子。对对称/Hermitian 正定矩阵，专用的 Cholesky 分解利用更多结构，成本和存储都低于通用 LU。

参考资料

• Lloyd N. Trefethen and David Bau III, Numerical Linear Algebra, SIAM, 1997, Lectures 20–22.
• Nicholas J. Higham, Accuracy and Stability of Numerical Algorithms, 2nd ed., SIAM, 2002, Ch. 9.
• LAPACK Users’ Guide, LU Factorization.