主元选取与增长因子

形式陈述 ​

Gaussian 消元第 $k$ 步面对尾部子矩阵 $A_{k:n,k:n}^{(k)}$。部分主元法在当前列选择

$$p=\underset{i\ge k}{\arg \max }|a_{ik}^{(k)}|$$

并交换第 $p,k$ 行；这样所有消元乘子满足 $|l_{ik}|\le 1$。完全主元法在整个尾部子矩阵中选择最大绝对值元素，同时交换行和列，因而分解形式为

$$PAQ=LU,$$

其中列置换 $Q$ 会改变变量顺序，求解后必须还原。Rook pivoting 交替在候选行和列寻找局部最大元，试图以较低搜索成本取得接近完全主元的控制；对称不定系统还需要保持对称结构的 $1\times 1$ 或 $2\times 2$ 主元策略，例如 Bunch–Kaufman，而不能直接照搬非对称换行。

主元不只负责避免除以零。定义元素增长因子

$$\rho =\frac{\underset{i,j,k}{max}|a_{ij}^{(k)}|}{\underset{i,j}{max}|a_{ij}|},$$

其中分子遍历消元各阶段出现的尾部元素；常见记法也用最终 $U$ 中最大元素表达相应增长。标准浮点分析把计算因子解释为邻近矩阵的精确 LU：

$$P(A+\mathrm{\Delta }A)=\hat{L}\hat{U},|\mathrm{\Delta }A|\lesssim {\gamma }_n|\hat{L}||\hat{U}|,$$

这里的绝对值和不等式按分量理解；转成 normwise 界后，维数因子取决于所选范数、实现和增长因子的具体定义。因而部分主元通常表现稳健，却不是具有维数无关小后向误差常数的无条件定理；其最坏增长可达到指数级。

主元过程输入当前尾部矩阵和允许的置换结构，输出主元位置、更新后的置换及乘子。每步若所有合法候选均为零，分解检测到奇异；若候选虽非零却相对当前行列尺度极小，算法仍应记录近奇异风险，而不是只做精确零判断。

直觉 ​

消元会用“当前主元的倒数”放大下面的元素。选择较大的主元，好比先找到一根结实支点再做杠杆：它限制乘子，减少小输入误差被中间步骤放大的机会。但后续尾部矩阵还会由相减产生新元素，乘子不大并不自动保证所有中间量都小；增长因子正是记录这条完整路径。

完全主元看得更远，代价是扫描更多元素并打乱列顺序。部分主元只在当前列搜索，便宜且在实践中非常可靠，所以成为稠密通用 LU 的默认策略；“默认”来自理论、成本与经验的平衡，不等于最坏情形不存在。

例子与边界 ​

设

$$A_{\epsilon }=\left(\begin{array}{cc}\epsilon & 1\\ 1& 1\end{array}\right),0<|\epsilon |\ll 1.$$

若不换行，第一步乘子为 $1/\epsilon$，更新后的右下元素为 $1-1/\epsilon$，远大于原矩阵元素；后续舍入要在这些巨大中间量之间相减。部分主元先交换两行，首主元变为 $1$，乘子只有 $\epsilon$，同一精确问题得到完全不同的有限精度路径。

部分主元也有经过构造的矩阵族使 $\rho$ 随 $n$ 指数增长，因此不能写成“理论上永远稳定”。反过来，观察到较大条件数也不能归咎于主元：条件数属于原问题，增长因子属于消元算法，两者分别控制数据敏感性和舍入传播。

列交换的边界同样具体。完全主元得到的是 $PAQ=LU$；若解完三角系统后忘记用 $Q$ 恢复变量，数值残差可能直接暴露错误，变量语义也已错位。结构化矩阵还可能禁止任意置换，必须选择尊重对称性、带宽或稀疏模式的策略。

推论与应用 ​

LU 页面公理库Gaussian 消元与 LU 分解Gaussian elimination · LU factorization · PA equals LU把 Gaussian 消元保存为可复用的带置换 LU 分解，再用三角求解处理一个或多个右端。负责分解和复用，本页负责解释为什么浮点实现需要主元以及后向误差常数从何而来。二者与算法稳定性公理库数值稳定性Numerical stability · Backward stability以允许的小输入扰动刻画算法的有限精度行为，并与问题条件性及其他稳定性概念分开。共同给出逻辑链：控制元素增长可带来小后向误差，再由问题条件数判断前向精度。

正定 Cholesky 在精确算术中不需要主元，因为所有递推主元为正；对称不定、秩亏或稀疏系统则有各自的结构化策略。将所有“选一个非零元素”的操作都叫同一种 pivoting，会忽略这些不变量。

参考资料

• Nicholas J. Higham, Accuracy and Stability of Numerical Algorithms, 2nd ed., SIAM, 2002, Ch. 9.
• Lloyd N. Trefethen and David Bau III, Numerical Linear Algebra, SIAM, 1997, Lecture 22.
• LAPACK Users’ Guide, Factorizations for General Matrices.