核心概述
在线性方程组 Ax=b 的求解中，采用高斯消元与（可选）LU 分解在实数域或模域给出解或报告奇异情形，单次 O(n^3) 且可通过预分解复用以降至每次 O(n^2)。
原文引述
Description: Solve Ax=b via Gaussian elimination (LU decomposition). Supports real matrices with partial pivoting, and modular matrices using modular inverses. Time: O(n^3) Status: tested ——摘自本节点现有英文注释
-
函数/接口（据实现）
- vector
solveLinear(const vector<vector >& A, const vector & b) - 返回 x 使 Ax=b；若 A 奇异则返回空或报错。
- LU decomp：可选返回 L 与 U 或直接求解。
- 重载：solveLU(L, U, b) 利用预分解的 LU 快速求解。
- vector
-
高斯消元（前消 + 回代）
- 前向消元：
- 构造增广矩阵 [A | b]。
- 对 i=0..n-1：
- 选取主元行 p（|A[p][i]| 最大或任一非零）；若 A[p][i]=0 ⇒ 无解或无穷解。
- 交换行 i 与 p（实数域记录符号，模域直接交换）。
- 将主元归一化：第 i 行除以 piv（模域乘 inv(piv)）。
- 对所有行 j≠i，消去第 j 行第 i 列：row_j ← row_j − A[j][i]·row_i。
- 若已化为行最简形（RREF），则右侧 x 即为解；否则做回代：
- 从 i=n−1 到 0：x[i] = b[i] − Σ_{j=i+1}^{n-1} A[i][j]·x[j]。
- 前向消元：
-
数值与实现注意
- 实数域：
- 部分主元（按列最大值）提升数值稳定；对病态矩阵可能仍需更高精度或 SVD。
- EPS 判零；若某列主元极小，可认为矩阵奇异。
- 模数域：
- 多右端向量：
- 可一次求解多个 b，或预分解 LU 后重用（见 115-数值算法-线性方程求解II）。
- 稀疏矩阵：
- 对稀疏/带状矩阵可用特殊消元顺序，但模板通常不优化。
- 实数域：
-
输出语义
- 返回解向量 x（若 A 可逆唯一）；否则返回空或 NaN/INF 表示无解/无穷解。
-
复杂度
- 单次求解：O(n^3) 乘加/除法；预分解后每次求解 O(n^2)。
-
使用与注意
- 先检查 det(A)≠0（见 097-数值算法-行列式、103-数值算法-整数行列式）。
- 若仅需解一次，高斯消元最简洁；若需多次不同 b，预做 LU 更高效（见 115-数值算法-线性方程求解II）。
- 模 2 线性代数见 116-数值算法-GF2线性求解（位运算加速）。
- 三对角系统见 117-数值算法-三对角求解（O(n)）。