• 通过初等行变换把 增广矩阵 化为 阶梯型矩阵 并回代 得到方程的解
  • 适用于求解 包含个方程， 个未知数的多元线性方程组

消元法理论的核心

消元法理论的核心主要如下：

  • 两方程互换，解不变；

  • 一方程乘以非零数 ，解不变；

  • 一方程乘以数 加上另一方程，解不变。

对于方程组 增广矩阵为

初等行（列）变换

  1. 把某一行乘一个非0的数 (方程的两边同时乘上一个非0数不改变方程的解)
  2. 交换某两行 (交换两个方程的位置)
  3. 把某行的若干倍加到另一行上去 (把一个方程的若干倍加到另一个方程上去)

用初等行（列）变换将增广矩阵变为阶梯型矩阵: 最后再把阶梯型矩阵从下到上回代到第一层即可得到方程的解

解的个数

  • 完美阶梯型: 唯一解
  • : 无解
  • : 无穷组解

算法步骤

枚举每一列 ，

  1. 找到当前列绝对值最大的一行
  2. 用初等行变换 把这一行换到最上面（未确定阶梯型的行，并不是第一行）
  3. 用初等行变换 将该行的第一个数变成 （其余所有的数字依次跟着变化）
  4. 用初等行变换 将下面所有行的当且列的值变成

例子: 利用高斯消元法五步骤法求解线性方程组

增广矩阵行（初等）变换为行最简形

所谓增广矩阵，即为方程组系数矩阵 与常数列 的并生成的新矩阵，即 ，增广矩阵行初等变换化为行最简形，即是利用了高斯消元法的思想理念，省略了变量而用变量的系数位置表示变量，增广矩阵中用竖线隔开了系数矩阵和常数列，代表了等于符号。

化为行阶梯形
化为最简形
还原线性方程组

解释

所谓的还原线性方程组，即是在行最简形的基础上，将之重新书写为线性方程组的形式，即将行最简形中各位置的系数重新赋予变量，中间的竖线还原为等号。

代码模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
// a[N][N]是增广矩阵
int gauss()
{
    int c, r;
    for (c = 0, r = 0; c < n; c ++ )
    {
        int t = r;
        for (int i = r; i < n; i ++ )   // 找到绝对值最大的行
            if (fabs(a[i][c]) > fabs(a[t][c]))
                t = i;

        if (fabs(a[t][c]) < eps) continue;

        for (int i = c; i <= n; i ++ ) swap(a[t][i], a[r][i]);      // 将绝对值最大的行换到最顶端
        for (int i = n; i >= c; i -- ) a[r][i] /= a[r][c];      // 将当前行的首位变成1
        for (int i = r + 1; i < n; i ++ )       // 用当前行将下面所有的列消成0
            if (fabs(a[i][c]) > eps)
                for (int j = n; j >= c; j -- )
                    a[i][j] -= a[r][j] * a[i][c];

        r ++ ;
    }

    if (r < n)
    {
        for (int i = r; i < n; i ++ )
            if (fabs(a[i][n]) > eps)
                return 2; // 无解
        return 1; // 有无穷多组解
    }

    for (int i = n - 1; i >= 0; i -- )
        for (int j = i + 1; j < n; j ++ )
            a[i][n] -= a[i][j] * a[j][n];

    return 0; // 有唯一解
}

参考

[1] 高斯消元 - OI Wiki