高斯消元法 (Gaussian Elimination): 线性代数中的一个算法，可以把矩阵转化为行阶梯形矩阵。用这种方法可以求线性方程组的解。

高斯消元法

我们很早便学习了通过消元求解线性方程组，高斯消元法实际上就是这个方法。只不过它用线性代数的数学语言来描述该过程，利用矩阵的变换来求解线性方程组。为了该笔记更多人能看懂，下面简单介绍一些线性代数的概念。

我们程序实现的时候，只有唯一解的情况可解出方程组的解，无穷解无法得出通解。

补充内容

系数矩阵

$$ \left\{ \begin{matrix} a_{11}x_1+a_{12}x_2+\cdots+a_{1n}x_n=b_1\\ a_{21}x_1+a_{22}x_2+\cdots+a_{2n}x_n=b_2\\ \cdots\cdots\cdots\cdots\\ a_{m1}x_1+a_{m2}x_2+\cdots+a_{mn}x_n=b_m\\ \end{matrix} \right. $$

对于上述线性方程组，系数构成的矩阵叫做系数矩阵：

$$ \left( \begin{array}{cccc} a_{11}&a_{12}&\cdots&a_{1n}\\ a_{21}&a_{22}&\cdots&a_{2n}\\ \vdots&\vdots&&\vdots\\ a_{m1}&a_{m2}&\cdots&a_{mn} \end{array} \right) $$

系数与常数项构成的矩阵叫做增广矩阵：

$$ \left( \begin{array}{cccc|c} a_{11}&a_{12}&\cdots&a_{1n}&b_1\\ a_{21}&a_{22}&\cdots&a_{2n}&b_2\\ \vdots&\vdots&&\vdots&\vdots\\ a_{m1}&a_{m2}&\cdots&a_{mn}&b_m \end{array} \right) $$

初等行变换

下面的三种变换称为矩阵的初等行变换：

对调矩阵的两行。
以非零常数 $k$ 乘矩阵某一行的各元。
把某一行所有的元素的 $k$ 倍加到另一行对应的元上去。

对线性方程组的增广矩阵做上述初等行变换，线性方程组的解不变。

行阶梯型矩阵

可画出一条阶梯线，线的下方的元素全为 $0$，每个台阶只有一行，如下所示：（$*$ 代表任意数）

$$ \left( \begin{array}{cccc|c} 1&*&*&*&*\\ 0&1&*&*&*\\ 0&0&1&*&*\\ 0&0&0&1&*\\ \end{array} \right) $$

行最简型矩阵

非零行的第一个非零元为 $1$，且非零行的第一个非零元所在的列的其他元都为 $0$，如下所示：（$*$ 代表任意数）

$$ \left( \begin{array}{cccc|c} 1&0&0&0&*\\ 0&1&0&0&*\\ 0&0&1&0&*\\ 0&0&0&1&*\\ \end{array} \right) $$

可以发现，如果我们得到了行最简型矩阵，线性方程组的解就可以直接写出了。

算法过程

输入方程的增广矩阵
使用初等行变换将其变为行阶梯型矩阵
再用初等行变换将其变为行最简型矩阵
通过行最简型矩阵输出方程的解

下面详细解释下每步的过程：

使用初等行变换将其变为行阶梯型矩阵

从第一列遍历到最后一列：

找到绝对值最大的一行（这个是为了精度更高）
将该行换到矩阵最上面
将改行第一个数化为 $1$
将 $1$ 下面的数全部化为 $0$

再用初等行变换将其变为行最简型矩阵

从最后一行遍历到第一行：

将该行 $1$ 上方的数全部化为 $0$

示例

我们以下面的线性方程组为例来模拟一遍操作：

$$ \left\{ \begin{align} 1x_1+2x_2-1x_3&=-6\\ 2x_1+1x_2-3x_3&=-9\\ -1x_1-1x_2+2x_3&=7 \end{align} \right. $$

读入增广矩阵：

$$ \left( \begin{array}{ccc|c} 1 & 2 & -1 & -6\\ 2 & 1 & -3 & -9\\ -1 & -1 & 2 & 7 \end{array} \right) $$

化为行阶梯型矩阵

$$ \sim \left( \begin{array}{ccc|c} 2 & 1 & -3 & -9\\ 1 & 2 & -1 & -6\\ -1 & -1 & 2 & 7 \end{array} \right) \sim \left( \begin{array}{ccc|c} 1 & \frac{1}{2} & -\frac{3}{2} & -\frac{9}{2}\\ 1 & 2 & -1 & -6\\ -1 & -1 & 2 & 7 \end{array} \right) \\ \sim \left( \begin{array}{ccc|c} 1 & \frac{1}{2} & -\frac{3}{2} & -\frac{9}{2}\\ 0 & \frac{3}{2} & \frac{1}{2} & -\frac{3}{2}\\ 0 & -\frac{1}{2} & \frac{1}{2} & \frac{5}{2} \end{array} \right) \sim \left( \begin{array}{ccc|c} 1 & \frac{1}{2} & -\frac{3}{2} & -\frac{9}{2}\\ 0 & 1 & \frac{1}{3} & -1\\ 0 & -\frac{1}{2} & \frac{1}{2} & \frac{5}{2} \end{array} \right) \sim \left( \begin{array}{ccc|c} 1 & \frac{1}{2} & -\frac{3}{2} & -\frac{9}{2}\\ 0 & 1 & \frac{1}{3} & -1\\ 0 & 0 & \frac{2}{3} & 2 \end{array} \right) $$

化为行最简型矩阵

$$ \sim \left( \begin{array}{ccc|c} 1 & \frac{1}{2} & -\frac{3}{2} & -\frac{9}{2}\\ 0 & 1 & \frac{1}{3} & -1\\ 0 & 0 & 1 & 3 \end{array} \right) \sim \left( \begin{array}{ccc|c} 1 & 0 & 0 & 1\\ 0 & 1 & 0 & -2\\ 0 & 0 & 1 & 3 \end{array} \right) $$

输出线性方程组的解

$$ \left\{ \begin{align} x_1&=1\\ x_2&=-2\\ x_3&=3 \end{align} \right. $$

代码

const int MAXN = 110;     // 最大方程数
const double EPS = 1e-6;  // 浮点误差
int n;                    // 方程个数
double mat[MAXN][MAXN];   // 增广矩阵

int gauss()
{
    int row, col;
    for (row = 0, col = 0; col < n; col++)
    {
        int max_row = row;
        for (int i = row; i < n; i++)
            if (fabs(mat[i][col]) > fabs(mat[max_row][col]))
                max_row = i;
        if (fabs(mat[max_row][col]) < EPS)
            continue;
        for (int i = col; i <= n; i++)
            swap(mat[max_row][i], mat[row][i]);
        for (int i = n; i >= col; i--)
            mat[row][i] /= mat[row][col];
        for (int i = row + 1; i < n; i++)
            if (fabs(mat[i][col]) > EPS)
                for (int j = n; j >= col; j--)
                    mat[i][j] -= mat[i][col] * mat[row][j];
        row++;
    }
    if (row < n)
    {
        for (int i = row; i < n; i++)
            if (fabs(mat[i][n]) > EPS)
                return 2; // 无解
        return 1; // 无穷解
    }
    for (int i = n - 1; i >= 0; i--)
        for (int j = i + 1; j < n; j++)
            mat[i][n] -= mat[i][j] * mat[j][n];
    return 0; // 有唯一解
}

数论 | 高斯消元法