550 字
2 分钟
高斯消元
高斯消元
概念详解
解决的问题： 解 n 元一次线性方程组：
a₁₁x₁ + a₁₂x₂ + … + a₁ₙxₙ = b₁ a₂₁x₁ + a₂₂x₂ + … + a₂ₙxₙ = b₂ ……
把系数和常数项拼成一个 n × (n+1) 的增广矩阵，通过三种行变换（交换两行、某行乘非零常数、某行的倍数加到另一行）把矩阵化成”阶梯形/行最简形”，就能直接读出解。
算法步骤（列主元高斯消元）：
- 选主元： 对当前列 c，从第 r 行往下找绝对值最大的那一行（避免除 0 和精度损失），换到第 r 行；
- 归一： 把该行除以主元，使主元位置变成 1；
- 消元： 用该行把下面所有行的第 c 列消成 0；
- 处理下一列、下一行，直到所有列处理完；
- 回代： 从最后一行往上，把每个未知数代入已求出的结果，解出所有变量。
解的情况判断： 设处理后非零行的个数为 r（秩）：
- r = n： 有唯一解（回代求出）；
- r < n 且某行出现
0 = 非零（即系数全 0 但常数项不为 0）：无解； - r < n 且没有矛盾行： 无穷多解（有 n - r 个自由变量）。
精度处理： 浮点比较一律用 eps（如 1e-6）：Math.abs(x) < eps 视为 0；输出时把 -0.00 归零。时间复杂度 O(n³)。
例题
题意
输入一个包含 个方程 个未知数的线性方程组，系数与常数为实数。 求解这个方程组：唯一解则输出每个未知数（保留两位小数）；无解输出
No solution；无穷多解输出Infinite group solutions。输入格式
第一行一个整数 。
接下来 行，每行 个实数，表示一个方程的 个系数与常数项。输出格式
唯一解：共 行，第 行输出 （保留两位小数）；
无穷多解：输出Infinite group solutions；
无解：输出No solution。数据范围
import java.io.*;import java.util.StringTokenizer;
public class Main { static final int N = 110; static final double EPS = 1e-6; static double[][] a = new double[N][N]; static int n;
// 返回值：0 唯一解，1 无穷多解，2 无解 static int gauss() { int c = 0, r = 0; for (; c < n; c++) { // 1. 找当前列绝对值最大的行（选主元） int t = r; for (int i = r; i < n; i++) if (Math.abs(a[i][c]) > Math.abs(a[t][c])) t = i; if (Math.abs(a[t][c]) < EPS) continue; // 该列全 0，跳过
// 2. 把主元行交换到第 r 行 double[] tmp = a[t]; a[t] = a[r]; a[r] = tmp;
// 3. 主元归一 for (int j = n; j >= c; j--) a[r][j] /= a[r][c];
// 4. 用第 r 行消去下面所有行的第 c 列 for (int i = r + 1; i < n; i++) if (Math.abs(a[i][c]) > EPS) for (int j = n; j >= c; j--) a[i][j] -= a[r][j] * a[i][c]; r++; }
if (r < n) { // 存在自由变量 for (int i = r; i < n; i++) if (Math.abs(a[i][n]) > EPS) return 2; // 0 = 非零 → 无解 return 1; // 无穷多解 }
// 回代：自底向上解出每个未知数 for (int i = n - 1; i >= 0; i--) for (int j = i + 1; j < n; j++) a[i][n] -= a[i][j] * a[j][n]; return 0; }
public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); n = Integer.parseInt(br.readLine().trim()); for (int i = 0; i < n; i++) { StringTokenizer st = new StringTokenizer(br.readLine()); for (int j = 0; j <= n; j++) a[i][j] = Double.parseDouble(st.nextToken()); }
int t = gauss(); if (t == 0) { for (int i = 0; i < n; i++) System.out.printf("%.2f\n", Math.abs(a[i][n]) < EPS ? 0.0 : a[i][n]); } else if (t == 1) { System.out.println("Infinite group solutions"); } else { System.out.println("No solution"); } }} 分享
如果这篇文章对你有帮助，欢迎分享给更多人！
部分信息可能已经过时
相关文章 智能推荐
1
贪心算法
算法 贪心算法的核心思想、解题步骤与经典的活动选择问题讲解，并给出 Java 实现。
2
欧拉函数与快速幂
算法 欧拉函数（单点与线性筛）、欧拉定理及其证明、快速幂、快速幂求逆元、扩展欧几里得算法的入门讲解与 Java 实现。
3
并查集
算法 并查集的原理、路径压缩与按 size 合并，配合合并集合、连通块中点的数量两道例题的 Java 实现。
4
最短路算法和最小生成树
算法 最短路算法与最小生成树合集，涵盖 Dijkstra、Bellman-Ford、SPFA（含判负环）、Floyd，以及 Prim 与 Kruskal 算法的原理与 Java 实现。
5
二分图
算法 二分图的定义与判定（染色法），以及匈牙利算法求最大匹配的入门讲解与 Java 实现。