LU分解

LU 分解把高斯消元中消去下三角元素的步骤保存下来：$A=LU$，其中 $L$ 是下三角矩阵、$U$ 是上三角矩阵。它适合固定同一系数矩阵、反复求解不同右端 $Ax=b$；一次分解后，每个新右端只需两次三角回代。

把消元系数留在矩阵里

取 $A=\left(\begin{array}{cc}2& 1\\ 4& 3\end{array}\right)$。第二行减去第一行的两倍得到 $U=\left(\begin{array}{cc}2& 1\\ 0& 1\end{array}\right)$；消元倍数 $2$ 放在下三角位置，得 $L=\left(\begin{array}{cc}1& 0\\ 2& 1\end{array}\right)$。直接乘回去：$LU=\left(\begin{array}{cc}2& 1\\ 4& 3\end{array}\right)=A$。

求 $Ax=(3,7{)}^T$ 时，先令 $Ux=y$，由 $Ly=(3,7{)}^T$ 得 $y_1=3$、$2y_1+y_2=7$，所以 $y=(3,1{)}^T$。再解 $Ux=y$：$x_2=1$，$2x_1+x_2=3$，得 $x=(1,1{)}^T$；代回原方程验算为 $(3,7{)}^T$。

主元、交换行与存在条件

若消元时下一个主元为零，不能硬除。例如 $\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)$ 第一格为零，但交换两行即可继续。实际算法记录置换矩阵 $P$，写成 $PA=LU$；对带主元选取的高斯消元，这比无条件声称每个矩阵都有指定形式的 $A=LU$ 更准确。即便主元非零，若它极小，交换到绝对值较大的候选常能减少放大舍入误差。是否存在精确分解与数值上是否稳定，是两个不同问题。

对 $n\times n$ 稠密矩阵，分解约需 $O(n^3)$ 运算，每个新右端的两次三角求解约需 $O(n^2)$。若只解一次，小矩阵手算直接消元更省事；若矩阵很稀疏，还要考虑消元产生的新非零元素。

参考资料与相关词条

• MIT 18.06：消元与 LU 分解。
• 相关：线性方程组与高斯消元、矩阵、条件数。