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

高斯消元法

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

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

补充内容

系数矩阵

$$\{\begin{array}{c}{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{array}$$

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

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

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

$$\left(\begin{array}{ccccc}{a}_{11}& a_{12}& \cdots & a_{1n}& b_1\\ a_{21}& a_{22}& \cdots & a_{2n}& b_2\\ ⋮& ⋮& & ⋮& ⋮\\ a_{m1}& a_{m2}& \cdots & a_{mn}& b_m\end{array}\right)$$

初等行变换

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

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

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

行阶梯型矩阵

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

$$\left(\begin{array}{ccccc}1& \ast & \ast & \ast & \ast \\ 0& 1& \ast & \ast & \ast \\ 0& 0& 1& \ast & \ast \\ 0& 0& 0& 1& \ast \end{array}\right)$$

行最简型矩阵

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

$$\left(\begin{array}{ccccc}1& 0& 0& 0& \ast \\ 0& 1& 0& 0& \ast \\ 0& 0& 1& 0& \ast \\ 0& 0& 0& 1& \ast \end{array}\right)$$

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

算法过程

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

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

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

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

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

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

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

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

示例

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

$$\{\begin{array}{rl}1x_1+2x_2-1x_3& =-6\\ 2x_1+1x_2-3x_3& =-9\\ -1x_1-1x_2+2x_3& =7\end{array}$$

1. 读入增广矩阵：

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

2. 化为行阶梯型矩阵

$$\begin{gathered} \sim \left(\begin{array}{cccc}2& 1& -3& -9\\ 1& 2& -1& -6\\ -1& -1& 2& 7\end{array}\right)\sim \left(\begin{array}{cccc}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}{cccc}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}{cccc}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}{cccc}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) \end{gathered}$$

3. 化为行最简型矩阵

$$\sim \left(\begin{array}{cccc}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}{cccc}1& 0& 0& 1\\ 0& 1& 0& -2\\ 0& 0& 1& 3\end{array}\right)$$

4. 输出线性方程组的解

$$\{\begin{array}{rl}{x}_1& =1\\ x_2& =-2\\ x_3& =3\end{array}$$

代码

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; // 有唯一解
}