主元选取与增长因子

形式陈述

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

p=\operatorname*{arg\,max}_{i\ge k}|a_{ik}^{(k)}|

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

PAQ=LU,

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

主元不只负责避免除以零。对Gaussian 消元的中间矩阵，定义元素增长因子

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

其中分子遍历消元各阶段出现的尾部元素；常见记法也用最终 $U$ 中最大元素表达相应增长，引用数值时必须说明版本。部分主元限制乘子后可推出粗略最坏界 $\rho\le2^{n-1}$ ，这个指数上界能够被专门构造的矩阵族达到，因此它不是维数无关的稳定性证明。

标准浮点模型把计算因子解释为邻近矩阵的精确 LU：

P(A+\Delta A)=\widehat L\widehat U, \qquad |\Delta A|\lesssim\gamma_n|\widehat L|\,|\widehat U|,

这里的绝对值和不等式按分量理解； $|\widehat L|$ 受乘子控制， $|\widehat U|$ 则携带元素增长。转成由矩阵范数表达的 normwise 界后，维数因子取决于所选范数、实现和 $\rho$ 的具体定义。因而部分主元通常表现稳健，却不是具有维数无关小后向误差常数的无条件定理。

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

直觉

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

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

例子与边界

设

A_\varepsilon= \begin{pmatrix} \varepsilon&1\\ 1&1 \end{pmatrix}, \qquad 0<|\varepsilon|\ll1.

若不换行，第一步乘子为 $1/\varepsilon$ ，更新后的右下元素为 $1-1/\varepsilon$ ，远大于原矩阵元素；部分主元先交换两行，首主元变为 $1$ ，乘子只有 $\varepsilon$ 。

取 binary64 中的 $\varepsilon=10^{-20}$ 与 $b=(1,2)^{\mathsf T}$ 。无主元消元把乘子舍入为约 $10^{20}$ ，尾部主元与变换后的右端都舍入为约 $-10^{20}$ ，回代得到 $\widehat x=(0,1)^{\mathsf T}$ ；代回原系统的第二行残差为 $1$ 。换行后得到约 $(1,1)^{\mathsf T}$ ，与真解

x_1=\frac{1}{1-\varepsilon}, \qquad x_2=\frac{1-2\varepsilon}{1-\varepsilon}

在 binary64 精度内一致。此时原矩阵的 $2$ -范数条件数接近 $2.618$ ，问题本身良态；失败来自无主元路径约 $10^{20}$ 的元素增长。

部分主元也有经过构造的矩阵族使 $\rho$ 随 $n$ 指数增长，因此不能写成“理论上永远稳定”。完全主元具有更强的最坏增长界，却需要在每一步扫描整个尾部矩阵并维护列置换；实践选择还受访存、稀疏填充与结构约束影响。反过来，观察到较大条件数也不能归咎于主元：条件数属于原问题，增长因子属于消元算法，两者分别控制数据敏感性和舍入传播。

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

推论与应用

LU 页面负责分解和复用，本页负责解释为什么浮点实现需要主元以及后向误差常数从何而来。数值稳定性给出逻辑链：控制元素增长可带来小后向误差，再由问题条件数判断前向精度。

正定 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, 3rd ed., SIAM, 1999, Factorizations for General Matrices.

形式陈述 ​

反向链接

形式陈述