正确实现直接求解器：选主元、浮点运算次数与何时止步

为何朴素消元会爆炸

第一卷的高斯消元把每一行除以它的主元。若主元很小，乘数就变得巨大，而巨大的乘数会放大数据中已有的舍入误差。结果是一团后向不稳定的乱麻：你算出的答案所求解的问题，与你提出的问题相去甚远。在精确算术下消元能处理得很好的同一个矩阵，在浮点下可能丢光每一位数字。

Solve  [1e-20, 1; 1, 1] x = [1; 2]   in double precision.
True answer is essentially  x = (1, 1).

NAIVE (pivot = 1e-20):
  multiplier = 1 / 1e-20 = 1e20
  row2 <- row2 - 1e20 * row1
        = [0,  1 - 1e20]  ->  fl gives [0, -1e20]   (the '1' vanished!)
  back-substitute:  x2 = 1,  x1 = (1 - x2)/1e-20 = 0   WRONG

WITH PARTIAL PIVOTING (swap so pivot = 1):
  rows: [1, 1; 1e-20, 1],  multiplier = 1e-20
  row2 <- [0, 1 - 1e-20] = [0, 1]   (no information lost)
  back-substitute:  x2 = 1,  x1 = 1   CORRECT

一个 2x2 例子：朴素消元返回 x1 = 0，而选主元返回正确的 x1 = 1。

部分选主元：标准的修复方法

解药是部分选主元：在消去第 k 列之前，交换行使该列中绝对值最大的元素位于对角线上。这迫使每个乘数满足 |m| <= 1，于是它们再也无法放大误差。形式上它计算分解 P A = L U，其中 P 记录行交换、L 的元素以单位为界——这就是你在第一卷见过的LU 分解，如今变得安全。

计算成本：浮点运算次数与稀疏性

成本以浮点运算次数度量——即浮点运算。稠密 n x n 矩阵的 LU 分解约需 (2/3) n^3 次浮点运算；之后每次三角求解仅为 O(n^2)。这种不对称正是“分解一次、反复复用”的原因：对十个不同的右端项 b 求解，代价是一次立方分解加十次廉价的二次求解，而非十次分解。

n^3 这堵墙残酷无比：n 翻倍，成本增长八倍。对于离散化偏微分方程产生的巨型系统——数百万个未知量——直接分解根本不可能。但这些矩阵通常是稀疏的：几乎所有元素都为零。稀疏矩阵方法只存储并运算非零元，而核心危险是填充：消元会把结构零变成非零，破坏稀疏性。重排行列以最小化填充，正是稀疏直接求解器的全部技艺。