我的算法书 - 高斯消元

一句话算法

高斯消元就是用一行方程消掉其它行的同一列未知数，把方程组化成容易读答案的阶梯形。

问题模型

给定 $n$ 元一次线性方程组：

\begin{cases} 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\\ a_{n1}x_1+a_{n2}x_2+\cdots+a_{nn}x_n=b_n \end{cases}

要求判断方程组无解、唯一解或无穷多解，并在唯一解时输出解。

核心直觉

一行方程可以看作一个约束。若某一行中 $x_k$ 的系数不为 0，就可以把这一行当作“主元行”，用它去消掉其它行的 $x_k$ 。

不断选择主元、归一化、消元，最后每个主元列只剩一个 1，答案就能直接读出来。

算法步骤

使用增广矩阵保存方程组，矩阵大小为 n x (n+1)。
从左到右枚举列 col，用 row 表示当前要放主元的行。
在 row..n-1 中选择当前列绝对值最大的行作为主元，减少浮点误差。
若主元接近 0，说明这一列没有主元，继续下一列。
把主元行交换到 row。
将主元行除以主元系数，使主元变成 1。
用主元行消掉其它所有行在当前列的系数。
记录这一列的主元行，row++。
消元结束后：
- 若出现 0 = 非 0，无解；
- 若存在没有主元的未知数，无穷多解；
- 否则唯一解。

算法证明

关键不变量： 每次行变换后，方程组的解集不变。

允许的行变换包括：

交换两行；
一行乘以非零常数；
一行加上另一行的若干倍。

这些操作不会改变所有方程共同满足的解集合。

消元时，每一列至多选择一个主元。主元列被消成只有主元行为 1、其它行为 0，因此这个未知数可以由主元行确定。

若某行变成：

0x_1+0x_2+\cdots+0x_n=c,\quad c\ne0

它要求 0 = c，矛盾，所以无解。

若某个未知数没有主元列约束，它可以自由取值，所以无穷多解。

若每个未知数都有主元，则每个未知数都被唯一确定，所以方程组有唯一解。

复杂度分析

高斯消元有三层循环，时间复杂度为 $O(n^3)$ 。

增广矩阵空间复杂度为 $O(n^2)$ 。

代码实现

cpp

        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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

        #include <bits/stdc++.h>
using namespace std;

const double EPS = 1e-9;

// 解 n 元一次方程组，增广矩阵 a 的大小为 n x (n+1)。
// 返回值：0 无解，1 唯一解，2 无穷多解。
int gaussian_elimination(vector<vector<double>> a, vector<double>& ans) {
    int n = (int)a.size();
    int row = 0;
    vector<int> where(n, -1);

    for (int col = 0; col < n && row < n; col++) {
        int pivot = row;
        for (int i = row; i < n; i++) {
            if (fabs(a[i][col]) > fabs(a[pivot][col])) pivot = i;
        }

        if (fabs(a[pivot][col]) < EPS) continue;
        swap(a[pivot], a[row]);
        where[col] = row;

        double div = a[row][col];
        for (int j = col; j <= n; j++) a[row][j] /= div;

        for (int i = 0; i < n; i++) {
            if (i == row) continue;
            double factor = a[i][col];
            for (int j = col; j <= n; j++) {
                a[i][j] -= factor * a[row][j];
            }
        }

        row++;
    }

    ans.assign(n, 0);
    for (int i = 0; i < n; i++) {
        if (where[i] != -1) ans[i] = a[where[i]][n];
    }

    for (int i = 0; i < n; i++) {
        double sum = 0;
        for (int j = 0; j < n; j++) sum += ans[j] * a[i][j];
        if (fabs(sum - a[i][n]) > EPS) return 0;
    }

    for (int i = 0; i < n; i++) {
        if (where[i] == -1) return 2;
    }
    return 1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<vector<double>> a(n, vector<double>(n + 1));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= n; j++) cin >> a[i][j];
    }

    vector<double> ans;
    int status = gaussian_elimination(a, ans);

    if (status == 0) {
        cout << "No solution\n";
    } else if (status == 2) {
        cout << "Infinite solutions\n";
    } else {
        cout.setf(ios::fixed);
        cout << setprecision(6);
        for (double x : ans) cout << x << '\n';
    }

    return 0;
}

测试用例

输入：

2
1 1 3
1 -1 1

输出：

2.000000
1.000000

解释：

\begin{cases} x+y=3\\ x-y=1 \end{cases}

解为 $x=2,y=1$ 。

应用分类详解

高斯消元的本质是解线性约束系统。

一、实数域线性方程组

典型模式： 题目直接给出多个一次方程，要求解未知数。

识别信号： 出现“线性方程组”“增广矩阵”“唯一解/无解/无穷多解”。

核心建模： 把每个方程转成矩阵一行，直接消元。

应用场景	经典题目	核心思路
方程组模板	luogu-P3389	实数域高斯消元

二、期望 DP 方程

典型模式： 状态之间互相依赖，无法按拓扑顺序递推。

识别信号： 出现“期望”“从状态 A 可能回到 A”“方程互相引用”。

核心建模： 每个状态设一个未知数，根据转移概率列线性方程。

应用场景	经典题目	核心思路
期望方程	概率 DP 题	状态期望列方程后消元

三、异或方程组

典型模式： 变量取 0/1，方程是异或关系。

识别信号： 出现“开关”“灯”“异或”“GF(2)”。

核心建模： 在模 2 意义下做高斯消元，乘除变成异或。

应用场景	经典题目	核心思路
开关问题	异或方程题	用 bitset 优化 GF(2) 消元

经典例题

1. luogu-P3389

高斯消元模板题。重点是选主元、处理浮点误差和判断无解/无穷多解。

2. 期望 DP 方程组

状态之间有环时，普通 DP 无法直接递推。把每个状态期望当成未知数，列出方程组后高斯消元。

3. 异或开关问题

每个开关是否按下是 0/1 变量，每盏灯的最终状态是一条异或方程，可用 GF(2) 高斯消元。

参考

线性代数初等行变换
增广矩阵