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$ 行倍加。高斯消元法的思路是先把增广矩阵用行初等变换化为行最简形再以线性无关为准则对自由未知量赋值最后列出方程组的通解。用五步骤法求解线性方程组文档把手工消元划分为五个步骤便于处理行最简形之后的自由未知量赋值增广矩阵行初等变换为行最简形还原线性方程组求解第一个变量补充自由未知量列表示方程组通解。下面按文档的例二完整走一遍。方程组为$$ \begin{cases} 2x_15x_36x_49 \ x_3x_4-4 \ 2x_32x_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_10.5x_4 14.5\ x_3x_4 -4 \ \end{cases} $$第 3 步求解第一个变量。把每个方程的第一个变量用其余量表示$$ \begin{cases} x_1 -0.5x_414.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_414.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::vectorbool。矩阵不可逆用高斯消元把 $(A, I_n)$ 化简为最简形后若左半部分不是单位矩阵 $I_n$则矩阵 $A$ 不可逆。行列式为 0消元过程中如果在当前列找不到非零单元算法停止并返回 0。矩阵求逆的完整流程适用于 $n$ 阶方阵 $A$构造 $n \times 2n$ 的矩阵 $(A, I_n)$用高斯消元法将其化简为最简形 $(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; vectorvectordouble a(n, vectordouble(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::bitset1010与 2010 个方程实际使用时按题目规模调整std::bitset1010 matrix[2010]; // matrix[1~n]增广矩阵0 位置为常数 std::vectorbool 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::vectorbool(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::vectorbool 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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考