高斯消元法 · aiwiki.page

高斯消元法是一种通过系统地消去未知数来求解线性方程组的算法。它利用可逆的行变换，将方程组的矩阵表示化为更简单的形式，同时保持解集不变。作为线性代数中的核心技术，它也为确定秩和描述解集提供了方法。在数值计算中，消元通常以三角分解的形式进行，随后通过代入求解。(textbooks.math.gatech.edu)

数学基础

含有 $m$ 个方程和 $n$ 个未知数的方程组可写为

Ax=b,

其中， $A$ 是系数矩阵， $x$ 由未知数组成， $b$ 由各方程的右端项组成。计算在增广矩阵 $[A\mid b]$ 上进行，因此每次操作都会同时改变系数和相应的右端项。允许使用以下三种初等行变换：

交换两行。
将某一行乘以非零标量。
将某一行的标量倍数加到另一行上。

每一种操作都是可逆的，因此变换后的方程组与原方程组的解集完全相同。(math.mit.edu)

前向消元阶段得到行阶梯形：零行位于非零行下方；各非零行的首个非零元素从上到下依次向右移动；每个首个非零元素下方的元素均为零。这些首个非零元素称为主元。进一步消去主元上方的元素，并将主元归一化为 1，即可得到简化行阶梯形。这一扩展过程通常称为高斯–若尔当消元法。简化行阶梯形是唯一的，但中间得到的行阶梯形未必唯一。(textbooks.math.gatech.edu)

消元与回代

在每个阶段，从剩余的系数列中选取一个非零主元。必要时交换行，将其移至当前处理的行。随后，从下方各行中减去该行的适当倍数，以消去主元所在列中的相应元素。如果某一列没有可选的非零元素，就跳过该列，继续向右寻找。(textbooks.math.gatech.edu)

对于系数矩阵为非奇异方阵的方程组，这一过程得到上三角方程组 $Ux=c$ 。在第 $k$ 步，消元乘子和行更新公式为

\ell_{ik}=\frac{u_{ik}}{u_{kk}},\qquad R_i\leftarrow R_i-\ell_{ik}R_k \quad(i>k).

然后通过回代，从最后一个未知数开始，逆序求出各未知数：

x_i=\frac{c_i-\sum_{j=i+1}^{n}u_{ij}x_j}{u_{ii}}.

与高斯–若尔当消元法不同，这种方法不需要消去主元上方的元素。(math.mit.edu)

例如，考虑方程组

\begin{aligned} x+y+z&=6,\\ 2x+3y+z&=11,\\ x+2y+3z&=14. \end{aligned}

先进行 $R_2\leftarrow R_2-2R_1$ 和 $R_3\leftarrow R_3-R_1$ ，再进行 $R_3\leftarrow R_3-R_2$ ，得到

\left[\begin{array}{ccc|c} 1&1&1&6\\ 0&1&-1&-1\\ 0&0&3&9 \end{array}\right].

因此， $z=3$ 、 $y=2$ 、 $x=1$ 。

秩与解的结构

消元法也适用于系数矩阵为矩形矩阵或奇异矩阵的方程组。系数部分的主元个数等于 $A$ 的秩。如果变换后出现形如

[\,0\ \cdots\ 0\mid d\,],\qquad d\ne0,

的行，就意味着存在矛盾，从而判定方程组无解。否则，系数部分没有主元的列所对应的变量是自由变量，而主元变量可用这些自由变量表示。在实数域或复数域上，有解的方程组在每个变量列都含有主元时具有唯一解，否则具有无穷多解。(textbooks.math.gatech.edu)

对于有解的方程组，所有解都可写成 $x=x_p+z$ ，其中 $x_p$ 是一个特解， $z$ 属于 $A$ 的零空间。这个解集是一个维数为 $n-\operatorname{rank}(A)$ 的仿射空间。消元法还可用于找出线性无关的列：原矩阵中与主元位置对应的列构成其列空间的一组基。必须使用原矩阵的列，因为行变换通常会改变列空间本身。(textbooks.math.gatech.edu)

主元选取与数值精度

在数值线性代数中，浮点运算会引入舍入误差。非常小的主元可能产生很大的消元乘子，使中间元素的数值显著增大。部分选主元法在当前列尚未处理的部分中选择绝对值最大的元素，并通过交换行将其移至主元位置。完全选主元法则在整个剩余系数子矩阵中搜索，可能同时交换行和列；交换列时，需要记录未知数位置的重新排列。(netlib.org)

部分选主元法在实践中通常有效，但不能保证对每个矩阵都产生较小的误差：某些特殊例子会出现元素数值的指数增长。还必须区分算法的数值稳定性与问题的条件性。条件数衡量问题对输入扰动的敏感程度；对于病态方程组，即使计算结果的后向误差很小，解的误差仍可能很大。(epubs.siam.org)

分解与计算成本

记录消元乘子即可得到LU 分解。采用行选主元时，通常写为

PA=LU,

其中， $P$ 表示行置换， $L$ 是单位下三角矩阵， $U$ 是上三角矩阵。先求解 $Ly=Pb$ ，再求解 $Ux=y$ ，就将矩阵分解与方程求解分离开来。因此，同一组分解因子可用于多个右端向量，而无须重复消元。(math.mit.edu)

对于稠密的 $n\times n$ 矩阵，常规分解所需浮点运算次数的主导项约为 $2n^3/3$ 。用大O记号表示，之后每次三角方程组求解需要 $O(n^2)$ 次运算；将分解因子存储在同一个数组中，可使其占用 $O(n^2)$ 的存储空间。对于稀疏矩阵，消元可能产生新的非零元素，这一现象称为填充，因此排序和主元选取对存储需求及计算成本都很重要。(math.mit.edu)

历史发展

这一名称是为了纪念卡尔·弗里德里希·高斯，但消元过程的出现远早于他。中国数学著作《九章算术》中就有相关方法。现代消元法是在方程求解的漫长发展历史、高斯的计算工作，以及后来面向电子计算机的改进过程中逐步形成的；不应因其名称而将它理解为高斯的一项独立发明。(doi.org)