高斯消元法 (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) $$

初等行变换

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

  1. 对调矩阵的两行。
  2. 以非零常数 $k$ 乘矩阵某一行的各元。
  3. 把某一行所有的元素的 $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. 输入方程的增广矩阵
  2. 使用初等行变换将其变为行阶梯型矩阵
  3. 再用初等行变换将其变为行最简型矩阵
  4. 通过行最简型矩阵输出方程的解

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

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

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

  1. 找到绝对值最大的一行(这个是为了精度更高)
  2. 将该行换到矩阵最上面
  3. 将改行第一个数化为 $1$
  4. 将 $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. $$

  1. 读入增广矩阵:

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

  1. 化为行阶梯型矩阵

$$ \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) $$

  1. 化为行最简型矩阵

$$ \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) $$

  1. 输出线性方程组的解

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