主元(pivot element)，一种变元。指在消去过程中起主导作用的元素。

消去法介绍

[pivoting elimination method]

高斯消去法在消元过程中可能出现零主元，即 ，这时消元过程将无法进行；也可能主元，但其绝对值非常小，用它做除法将会导致舍入误差的扩散，使数值解不可靠。解决该问题的办法是避免使用绝对值过小的元素作主元。选主元早在1947年就已由约翰·冯·诺依曼（von Neumann）和戈尔德施泰因（Goldstine）所使用。

在第 k 步消元时，通常采用如下方式选取主元：在中选择绝对值最大者作为主元；或在 中选择绝对值最大者作为主元。前者被称为部分主元（partial pivoting）或列主元，后者则被称为全主元（complete pivoting）。术语“部分主元”和“全主元”由威尔金森（Wilkin-son）所提出。

部分主元

部分主元高斯消去法消元过程的第 k 步如下：

（1）选主元，选取作为主元。若有多个值，则取 中最小者；

（2）交换的第 k ，行，并将交换之后的增广矩阵仍记为 ；

（3）将第 k 行的倍加到第行。

经过步消元，得到，其中是上三角矩阵，则化为一个同解上三角方程组，应用回代法即可求得方程组的解。部分主元高斯消去法的工作量约为个浮点运算和次逻辑运算。

也可以用矩阵运算表示部分主元高斯消去法的消元过程。交换单位矩阵 I 的第 i ，j两行（列）所得的矩阵被称为初等置换矩阵，记为，简记为，则是对称正交矩阵。设第 k 步中交换第 k，行的初等置换矩阵为，高斯变换矩阵为 。记， 则可以证明：P 是排列矩阵，并且。因此，矩阵 A 的部分主元消元过程实现了 A 的一个部分主元三角分解。

全主元介绍

全主元高斯消去法消元过程的第 k 步如下：

（1）选主元，选取作为主元。若有多少个值，则分别取中最小者；

（2）交换的第 k ，行和第列，并将交换之后的增广矩阵仍记为；

（3）将第 k 行的 倍加到第行。

经过步消元，得到数组和，其中是该上三角矩阵。应用回代法即可求得上三角方程组的解，利用数组可得到原方程的解。

全主元高斯消去法的工作量约为 个浮点运算和次逻辑运算。与部分主元高斯消去法相比，全主元高斯消去法在其每步的两维数组搜索时需要增加很大的选主元工作量。

全主元高斯消去法的消元过程也可用矩阵运算表示。设第 k 步中交换的第行的初等置换矩阵为，交换的第列第初等置换矩阵为，高斯变换矩阵为。记, ，则可以证明：P，Q是排列矩阵，并且。因此，矩阵 A 的全主元消元过程实现了 A 的一个全主元三角分解。

基本应用

在20世纪40年代中期，约翰·冯·诺依曼等预言高斯消去法一定是数值不稳定的。在20世纪50年代早期，计算经验已经证实主元高斯消去法实际上是稳定的。对这种现象的解释在理论上是一个很大的挑战。威尔金森因对这个课题的贡献而成名。可以证明：如果 n 阶矩阵 A 非奇异，则用主元高斯消去法求解所得到的计算解满足，其中是单位舍入，为主元高斯消去法的增长因子。

主元高斯消去法的数值稳定性取决于其增长因子的大小。对于部分主元高斯消去法，其增长因子以为上界。威尔金森和赖特（Wright）构造了一些例子，说明部分主元高斯消去法的增长因子的这个上界是可以达到的。但是，在大多数实际计算中，由部分主元高斯消去法所产生的矩阵元素迅速增长的情况非常罕见。

对全主元高斯消去法，威尔金森证明了。威尔金森指出，对于充分大的 n ，这个界远远小于。据此可以推断：全主元高斯消去法是数值稳定的。威尔金森曾猜测：全主元高斯消去法的增长因子以矩阵的阶为界，即 。但是，古尔德（Gould）构造了一个反例，说明威尔金森的猜测是不正确的。

参考资料