LU 分解（带选主元）

在第一门课里，你用高斯消元法解 Ax = b：把某一行的倍数从下方各行减去，直到矩阵变成上三角。进阶的洞见是：消元本身就是一种分解。你做的每一步行运算其实都是左乘一个简单的下三角矩阵，把这些运算记录下来就得到 A = L U，其中 L 是单位下三角矩阵（对角线为 1，下方是消元乘子），U 则是消元后的上三角结果。

朴素消元在主元为零时立刻失效，而当主元只是非常小的时候表现也很糟，因为除以一个很小的数会放大舍入误差。补救办法是部分选主元：在对某一列消元之前，先交换行，把绝对值最大的元素换到主元位置。把这些交换记录在置换矩阵 P 中，就得到实用的形式 P A = L U。这样 L 中每个乘子的绝对值都不超过 1。

这正是实际求解器所计算的东西。先做一次分解，代价约为 (2/3) n^3 次浮点运算；之后对任意右端项解 A x = b，只需做一次前代 L y = P b 与一次回代 U x = y，每次仅花费 n^2。同一个分解还给出 det(A) = (±1) 乘以 U 对角线元素之积，符号来自行交换的奇偶性。

诚实的提醒：部分选主元在实践中对几乎所有矩阵都是稳定的，但并非无条件稳定。存在人为构造的矩阵（经典例子的增长像 2^n），其中 U 的元素会爆炸式增长。这类矩阵在真实问题里几乎从不出现，这也是为什么部分选主元仍是默认选择，而非代价更高的完全选主元。