企业官网建设流程全解析

OI Wiki 高斯消元：如何求解线性方程组并判断解的情况

【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. （某大型游戏线上攻略，内含炫酷算术魔法）项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki

当你在算法题中需要解一个线性方程组，或者要把求行列式、求逆矩阵这类问题归约到消元上时，OI-wiki 的 高斯消元 一文给出了从手工消元到 C++ 参考实现的完整路径。这篇文章以该文档为主线，覆盖两件事：用「五步骤法」把增广矩阵化到行最简形并列出方程组通解，以及利用文档中明确给出的终止条件判断解的情况（出现自由未知量、矩阵不可逆、无解/多解返回空向量、行列式为 0）。文档中的程序部分均以 C++ 片段形式给出。

准备：增广矩阵与三条行变换规则

消元操作的对象是增广矩阵：方程组系数矩阵 $A$ 与常数列 $b$ 并生成的新矩阵 $(A \mid b)$，其中竖线分隔系数矩阵和常数列，代表等号（见 docs/math/numerical/gauss.md 例二的写法）。初等矩阵 一文也给出了同样定义：未知数前的系数构成系数矩阵，在右端补上常数项构成增广矩阵。

高斯消元依赖消元法理论的三条核心结论，行初等变换只作用在系数上，不改变方程组的解：

• 两方程互换，解不变；
• 一方程乘以非零数 $k$，解不变；
• 一方程乘以数 $k$ 加上另一方程，解不变。

对应的初等行变换就是三种：第 $i$ 行乘非零数 $k$（倍乘）、第 $i$ 与 $j$ 行互换（对换）、第 $j$ 行乘 $k$ 加到第 $i$ 行（倍加）。高斯消元法的思路是：先把增广矩阵用行初等变换化为行最简形，再以线性无关为准则对自由未知量赋值，最后列出方程组的通解。

用五步骤法求解线性方程组

文档把手工消元划分为五个步骤，便于处理行最简形之后的自由未知量赋值：

1. 增广矩阵行初等变换为行最简形；
2. 还原线性方程组；
3. 求解第一个变量；
4. 补充自由未知量；
5. 列表示方程组通解。

下面按文档的例二完整走一遍。方程组为：

$$ \begin{cases} 2x_1+5x_3+6x_4&=9 \ x_3+x_4&=-4 \ 2x_3+2x_4&=-8 \end{cases} $$

第 1 步：化行最简形。写出增广矩阵后依次做行变换：

$$ \left(\begin{matrix} 2 & 0 & 5 & 6 \ 0 & 0 & 1 & 1 \ 0 & 0 & 2 & 2 \end{matrix} \middle| \begin{matrix} 9 \ -4 \ -8 \end{matrix} \right) \xrightarrow{r_3-2r_2} \left(\begin{matrix} 2 & 0 & 5 & 6 \ 0 & 0 & 1 & 1 \ 0 & 0 & 0 & 0 \end{matrix} \middle| \begin{matrix} 9 \ -4 \ 0 \end{matrix} \right) $$

先化为行阶梯形，再继续：

$$ \xrightarrow{\frac{r_1}{2}} \left(\begin{matrix} 1 & 0 & 2.5 & 3 \ 0 & 0 & 1 & 1 \ 0 & 0 & 0 & 0 \end{matrix} \middle| \begin{matrix} 4.5 \ -4 \ 0 \end{matrix} \right) \xrightarrow{r_1-r_2 \times 2.5} \left(\begin{matrix} 1 & 0 & 0 & 0.5 \ 0 & 0 & 1 & 1 \ 0 & 0 & 0 & 0 \end{matrix} \middle| \begin{matrix} 14.5 \ -4 \ 0 \end{matrix} \right) $$

得到行最简形。

第 2 步：还原线性方程组。把行最简形的各位置系数重新赋予变量，竖线还原为等号：

$$ \begin{cases} x_1+0.5x_4 &= 14.5\ x_3+x_4 &= -4 \ \end{cases} $$

第 3 步：求解第一个变量。把每个方程的第一个变量用其余量表示：

$$ \begin{cases} x_1 = -0.5x_4+14.5 \ x_3 = -x_4-4 \end{cases} $$

第 4 步：补充自由未知量。此时 $x_1$、$x_3$ 已求解，说明 $x_2$、$x_4$ 不受方程组约束，是自由未知量，按 $x_2 = x_2$、$x_4 = x_4$ 补充：

$$ \begin{cases} x_1 = -0.5x_4+14.5 \ x_2 = x_2 \ x_3 = -x_4-4 \ x_4 = x_4 \end{cases} $$

第 5 步：列示通解。把解写成列向量组合，其中 $C_1$、$C_2$ 为任意常数（以下为文档示例结果）：

$$ \begin{aligned} \begin{pmatrix} x_1 \ x_2 \ x_3 \ x_4 \end{pmatrix} &= \begin{pmatrix} 0 \ 1 \ 0 \ 0 \end{pmatrix} x_2+ \begin{pmatrix} -0.5 \ 0 \ -1 \ 1 \end{pmatrix} x_4 + \begin{pmatrix} 14.5 \ 0 \ -4 \ 0 \end{pmatrix} \ &= \begin{pmatrix} 0 \ 1 \ 0 \ 0 \end{pmatrix} C_1+ \begin{pmatrix} -0.5 \ 0 \ -1 \ 1 \end{pmatrix} C_2 + \begin{pmatrix} 14.5 \ 0 \ -4 \ 0 \end{pmatrix} \end{aligned} $$

由此可以对照判断解的结构：像 $x_2$、$x_4$ 这样没有对应主元、不受方程约束的变量就是自由未知量，取任意值后方程组仍有解，通解由含任意常数的向量组合表达。

判断解的情况：文档给出的四个判定条件

文档在程序实现中给出了四个与「解的情况」直接对应的判定条件，注意它们各自的适用对象不同：

• 自由未知量（通解）：行最简形中某些列没有主元，对应变量不受约束，按五步骤法第 4、5 步补充自由未知量并列出含任意常数的通解。
• 异或方程组无解 / 多解：参考实现GaussElimination的函数注释明确「多解 / 无解返回一个空的 vector」，实现中当某一列在后续所有行都找不到含主元的行时（if (cur > m)）直接返回空std::vector<bool>。
• 矩阵不可逆：用高斯消元把 $(A, I_n)$ 化简为最简形后，若左半部分不是单位矩阵 $I_n$，则矩阵 $A$ 不可逆。
• 行列式为 0：消元过程中如果在当前列找不到非零单元，算法停止并返回 0。

矩阵求逆的完整流程（适用于 $n$ 阶方阵 $A$）：

1. 构造 $n \times 2n$ 的矩阵 $(A, I_n)$；
2. 用高斯消元法将其化简为最简形 $(I_n, A^{-1})$，即可得到逆矩阵；若左半部分不是 $I_n$，则 $A$ 不可逆。

矩阵 一文也说明了：逆矩阵不一定存在，如果存在，可以使用高斯消元求解；行列式 一文指出「高斯消元」法计算行列式同样基于初等变换的性质，复杂度为 $O(n^3)$。

C++ 参考实现

以下代码均摘自 docs/math/numerical/gauss.md。

求行列式（$O(n^3)$）。片段中n是方阵阶数，a是待求行列式的 $n \times n$ 矩阵，EPS是数值判零阈值：

constexpr double EPS = 1E-9; int n; vector<vector<double>> a(n, vector<double>(n)); double det = 1; for (int i = 0; i < n; ++i) { int k = i; for (int j = i + 1; j < n; ++j) if (abs(a[j][i]) > abs(a[k][i])) k = j; if (abs(a[k][i]) < EPS) { det = 0; break; } swap(a[i], a[k]); if (i != k) det = -det; det *= a[i][i]; for (int j = i + 1; j < n; ++j) a[i][j] /= a[i][i]; for (int j = 0; j < n; ++j) if (j != i && abs(a[j][i]) > EPS) for (int k = i + 1; k < n; ++k) a[j][k] -= a[i][k] * a[j][i]; } cout << det;

注意两处与解的情况相关的逻辑：当前列找不到绝对值不小于EPS的元素时det = 0并终止；每次行交换后通过det = -det记录符号。

解异或方程组（std::bitset优化版）。异或方程组形如 $a_{1,1}x_1 \oplus \cdots \oplus a_{1,n}x_n = b_1$ 等 $m$ 个方程，系数与常数均为 0 或 1。消元时用「异或消元」而非「加减消元」，且不需要乘除改系数；由于增广矩阵是 01 矩阵，用std::bitset后复杂度可降到 $O(\dfrac{n^2m}{\omega})$，其中 $n$ 为元的个数，$m$ 为方程条数，$\omega$ 一般为 32（与机器有关）。文档示例把matrix上限定为std::bitset<1010>与 2010 个方程，实际使用时按题目规模调整：

std::bitset<1010> matrix[2010]; // matrix[1~n]：增广矩阵，0 位置为常数 std::vector<bool> GaussElimination( int n, int m) // n 为未知数个数，m 为方程个数，返回方程组的解 // （多解 / 无解返回一个空的 vector） { for (int i = 1; i <= n; i++) { int cur = i; while (cur <= m && !matrix[cur].test(i)) cur++; if (cur > m) return std::vector<bool>(0); if (cur != i) swap(matrix[cur], matrix[i]); for (int j = 1; j <= m; j++) if (i != j && matrix[j].test(i)) matrix[j] ^= matrix[i]; } std::vector<bool> ans(n + 1); for (int i = 1; i <= n; i++) ans[i] = matrix[i].test(0); return ans; }

调用方判断解的情况的方式即看返回值：非空向量是解，空向量表示文档注释所说的「多解 / 无解」。

适用边界与配套练习

• 实数场景的行列式实现依赖EPS判零，属于浮点运算；异或方程组版本要求系数和常数都是 0/1，用异或代替加减，两者不要混用。
• 求逆矩阵的文档只给出步骤与不可逆判定，未附代码；实现时按「构造 $(A, I_n)$、消到最简形、检查左半是否为 $I_n$」执行。
• 文档末尾给了两道练习题可作验证材料：Codeforces 的「巫师和赌注」与 luogu 的「SDOI2010 外星千足虫」（题目地址以仓库原文为准，本文不附外部链接）。
• 需要初等变换与增广矩阵的完整定义时，可对照 docs/math/linear-algebra/elementary-operations.md 的「应用：线性方程组求解」一节。

【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. （某大型游戏线上攻略，内含炫酷算术魔法）项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki