选主元

朴素的高斯消元用主元——当前正在处理的对角元——去除每一行。数学上任何非零主元都行，但在计算机上，微小的主元是毒药：除以一个接近零的数会产生巨大的乘数，而那些巨大的数会把矩阵其余部分淹没在舍入误差里。选主元就是这个简单的修正：每步消元前，交换行使主元尽可能大。

选主元的标准做法是部分选主元：在当前列中从对角元往下扫描，把绝对值最大的那一行换到顶部。这保证每个乘数的绝对值至多为 1，故单步中没有元素会失控增长。它产生的分解是 PA = LU，其中 P 是记录交换的置换矩阵。完全选主元还会跨列搜索整个剩余子矩阵中的最大元；理论上更安全，但很少值得那份额外开销。

更深一层的要点是：选主元正是让高斯消元值得信赖的东西。没有它，消元在再普通不过的矩阵上也可能灾难性地不稳定；有了部分选主元，它在实践中对你遇到的几乎所有矩阵都变得后向稳定。代价仅是行交换的记账——与算术相比微不足道。

有一点告诫值得知道：部分选主元在实践中稳定，但在最坏情形下并非可证明稳定。存在人为构造的矩阵，其元素增长是指数级的。它们在实际应用中几乎从不出现，这正是部分选主元仍是通用默认、而完全选主元只留给真正多疑者的原因。