题解：P3389 【模板】高斯消元法

LoongPig · 2025-05-20 16:07:01 · 题解

题目传送门

一些无意义的统计：

• 在写这篇题解的期间，浏览器炸了 6 次。
• 这篇题解由于浏览器的问题重写了 3 次。
• 耗时 4 个小时。

高斯-约旦消元法

基本操作：

对于一个有 m 个一次方程，n 个变量的线性方程组可以表示为一个增广矩阵。

举个栗子：

增广矩阵的 3 种变换，称为初等变换：

• 交换某两行的位置。
• 用一个非 0 的常数 k 乘某个方程。
• 把某一行乘 k 然后加到另一行上。

应该不用举栗子了吧。

解的情况

线性方程组的解有 3 种情况：

1. 有唯一解:

首先把左边的方程组写成右边的增广矩阵，然后反复使用初等变换，得：

最后解得 x_1=5，x_2=11，x_3=9。这是唯一解，称最后得矩阵为简化梯形矩阵，特征是左半部分是一个单位矩阵。

2. 有无穷多解:

最后的矩阵出现了一个全都是 0 的行，说明这一行无效。3 个未知数，却只有两个方程，所以有无穷多个解。

3. 无解：

最后的矩阵出现了 0x_1+0x_2+0x_3=16 的矛盾方程，说明该方程组无解。

具体实现方法

1. 从第一行开始，选择一个非 0 的系数（一般选择绝对值最大的系数，避免转换其他系数时产生过大的数值）所在的行，把这一行与第 1 行交换。此时 x_1 是主元；
2. 把 x_1 的系数转换为 1；
3. 利用主元 x_1 的系数，把其他行的这一列的主元消去；
4. 重复上述步骤，直到该增广矩阵变为简化梯形矩阵。

代码

提交记录

#include <bits/stdc++.h>
using namespace std;
const double eps=1e-7;
double a[105][105];
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n+1;j++)
            cin>>a[i][j];
    for(int i=1;i<=n;i++){
        int maxx=i;
        for(int j=i+1;j<=n;j++)//找到绝对值最大的系数的所在行
            if(fabs(a[j][i])>fabs(a[maxx][i])) maxx=j;
        for(int j=1;j<=n+1;j++)
            swap(a[i][j],a[maxx][j]);//与第 i 行交换
        if(fabs(a[i][i])<eps){
            //无解或者有无穷多解
            cout<<"No Solution";
            return 0;
        }
        for(int j=n+1;j>=1;j--) a[i][j]=a[i][j]/a[i][i];//把 x_1 的系数转换为 1
        for(int j=1;j<=n;j++){
            if(j!=i){
                //消去其他行的系数
                double tmp=a[j][i]/a[i][i];
                for(int k=1;k<=n+1;k++) a[j][k]-=a[i][k]*tmp;
            }
        }
    }
    for(int i=1;i<=n;i++) printf("%.2lf\n",a[i][n+1]);//输出该线性方程组的解
    return 0;
}