抱歉，您的浏览器无法访问本站
本页面需要浏览器支持（启用）JavaScript
了解详情 >

线性代数 高斯消元

oi算法

发布于：2024年10月6日

字数：3.4k 字

时长：12 分钟

Gauss-Jordan 消元法

也叫高斯-若尔当消元法，简称高斯消元法或高斯消元。它可以在 的时间复杂度内求出矩阵方程组的解、以及给定矩阵的逆矩阵、行列式等。

基础知识

初等行变换：指的是对一个矩阵中的某些行进行的基本变换，具体如下：

  1. 交换某两行。相当于把方程组的顺序调换一下，本质上不影响该矩阵。
  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
38
39
40
int gauss() {
    int rank = 0; // 秩
    for (int c = 1, r = 1; c <= n; c++) {
        int t = r;
        for (int i = r; i <= n; i++) {
            if (abs(matrix[i][c]) > abs(matrix[t][c])) t = i; // 找出主元绝对值最大的那一行
        }
        if (abs(matrix[t][c]) < EPS) continue; // 非零才能消成1
        if (t != r) swap(matrix[t], matrix[r]); // 交换
        for (int i = n + 1; i >= c; i--) matrix[r][i] /= matrix[r][c]; // 主元消成1
        for (int i = 1; i <= n; i++) { // 反复消元，成为对角线矩阵
            if (abs(matrix[i][c]) > EPS && i ^ r) { // 当前行不消，若当前位已经是零了也不消
                for (int j = n + 1; j >= c; j--) {
                    matrix[i][j] -= matrix[i][c] * matrix[r][j]; // 消成零
                }
            }
        }
        r++;
        rank++;
    }
    if (rank < n) {
        // 无解or无数组解
        for (int i = rank + 1; i <= n; i++) {
            for (int j = 1; j <= n + 1; j++) {
                if (abs(matrix[i][j]) > EPS) return 0; // 无解
            }
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (abs(matrix[i][j]) > EPS) {
                    ans[j] = matrix[i][n + 1]; // 无数组解，找到主元并直接赋值，剩余的自由元自动赋值为0
                    break;
                }
            }
        }
        return 1;
    }
    for (int i = 1; i <= n; i++) ans[i] = matrix[i][n + 1]; // 有解，此时常数项即为答案
    return 2;
}

高斯消元例题

洛谷 P2455 [SDOI2006] 线性方程组

题目地址：P2455

题目难度：提高+/省选-

题目来源：山东  2006  各省省选

已知 元线性一次方程组。

请根据输入的数据，编程输出方程组的解的情况。如果有唯一解，则输出解。你的结果被认为正确，当且仅当对于每一个 而言结果值与标准答案值的绝对误差或者相对误差不超过 。如果方程组无解输出 ；如果有无穷多实数解，输出 ；

对于 的数据，。对于 ，有 ，。

这道题就是模板题，用方才给出的对角线版消元代码就可以轻松过掉这个题。需要注意的是，对于浮点数消元，由于精度问题，需要设置最低精度，一般当 时就可认为这个浮点数为零。

洛谷 P4035 [JSOI2008] 球形空间产生器

题目地址：P4035

题目难度：提高+/省选-

题目来源：江苏  2008  各省省选

给定一个 维球体和球面上 个点的坐标，请确定这个 维球体的球心坐标，保留 位小数。球面上的所有点距离球心均相同，坐标的每一个实数精确到小数点后 位，且其绝对值都不超过 。

保证

根据球心定义，可以列出方程组：

解出方程， 就是球心坐标。考虑等号两端同时平方，并移项消去平方项，最终可以得到一个 元线性方程组，高斯消元解出即可。

洛谷 P10315 [SHUPC 2024] 原神，启动！

题目地址：P10315

题目难度：提高+/省选-

题目来源：SHUPC  2024

雷元素方碑具有如下性质：

  1. 具有 种状态， 中的一种；
  2. 方碑受到一次攻击会进入下一个状态（ 的下一个状态是）；
  3. 某个方碑受到一次攻击时会带动其它一些方碑一起进入下一个状态。

现在有 个雷元素方碑，每个雷元素方碑有 种状态。对于每个方碑 ，当它受到攻击时，都有 个其它方碑和它一起进入下一个状态。给定 个雷元素方碑的初始状态 和终止状态 ，请你计算需要分别攻击每个方碑多少下，才能将雷元素方碑从状态 变换到 。如果无解请输出niuza，如果存在无数组解则任意输出一组。

，保证 为质数。

本题数据过水，求无数组解特解的样例放在了后面。

本题其实是在让我们求如下方程组的特解：

思路和普通高斯消元是一样的，只是和实数高斯消元不同，带模数的式子中不能直接出现除法。那我们直接把除法改换成逆元就好了。注意负数的处理，最终答案要规约到 内。

接下来是 Hack 数据（有两种可行解）：

1
2
3
4
5
6
7
8
9
10
In:
3 3
2 2 3
2 1 3
1 1
0 0 0
2 1 2

Out:
0 1 1 or 1 0 1

题解同步于本站

洛谷 P6126 [JSOI2012] 始祖鸟

题目地址：P6126

题目难度：省选/NOI-

题目来源：江苏  2012  各省省选

现在有 只始祖鸟，我们从 开始编号。对于第 只始祖鸟，有 个认识的朋友，它们的编号分别是 ，，，。朋友的认识关系是单向的，也就是说如果第只始祖鸟认识第 只始祖鸟，那么第 只始祖鸟不一定认识第 只始祖鸟。

聚会的地点分为两处，一处在上游，一处在下游。对于每一处聚会场所，都必须满足对于在这个聚会场所中的始祖鸟，有恰好有偶数个自己认识的朋友与之在同一个聚会场所中。当然，每一只始祖鸟都必须在两处聚会场所之一。

现在需要你给出一种安排方式。你只需要给出在上游的始祖鸟编号，如果有多组解，请输出任何一组解。如果无法满足要求，只输出一行 Impossible。

对于的数据，。

把所有始祖鸟按朋友个数的奇偶性分类，这只鸟如果有偶数个朋友，只要上游和下游其中一方存在偶数个朋友，那么另一端也会有偶数个朋友，这只鸟哪里都可以去；如果它有奇数个朋友，这奇数个朋友必定是“奇数+偶数”分布的，那么只需让这只鸟到有偶数个朋友的一段即可。

令在上游为 ，在下游为 。若存在偶数个朋友在其中一方，即（此时只算朋友的情况）偶数个 和 全部异或，结果为 ；若存在奇数个朋友，如果有偶数个朋友在上游，这只鸟必定到上游，（此时算上当前这只鸟和它的所有朋友）也就是奇数个 和奇数个 异或，结果是 ；反过来，如果有偶数个朋友在下游，那么就是奇数个 和奇数个 异或，结果为 。那么对于一只有 个朋友的鸟 ，能够得到这样的关系：

分别对应朋友数为偶数和奇数的情况。紧接下来使用 bitset 优化异或高斯消元：

与一般的高斯消元接近，异或高斯消元使用异或来代替消元时的减法操作，而且因为方程组的系数只会出现 ，因而不需要将当前的首个元素通过除法化为 。其余步骤，包括找出绝对值最大的行，和普通高斯消元是一致的。

双倍经验：P3429 [POI2005] DWA-Two Parties

题解同步于本站

P2973 [USACO10HOL] Driving Out the Piggies G

题目地址：P2973

题目难度：省选/NOI-

题目来源：USACO  2010

一个 个点、 条边的无向图，节点1有一个炸弹，在每个单位时间内，有 的概率在这个节点炸掉，有 的概率随机选择一条出去的路到其他的节点上。问最终炸弹在每个节点上爆炸的概率。

对于当前点，它可能由与它相连的点转移过来。假如与当前点相连的所有点的爆炸概率分别设成未知数，那么在这个点爆炸的概率就应该是在相连点不爆炸的情况下再移动到当前点上的概率，即：

其中 为 点的度数。我们发现有一个特殊点是 号点，要么在这个点爆炸，要么转移到相连的点，即：

然后直接套高斯消元模板即可。

本页文档最后更新于：2024年10月11日

算法

oi

线性代数

评论