高斯消元法----解多元方程 关键词:高斯消元 相关题目:【模板】高斯消元法

【模板】高斯消元法

【模板】高斯消元法

题目描述

给定一个线性方程组,对其求解

输入输出格式

输入格式: 第一行,一个正整数 nn 第二至 n+1n+1 行,每行 n+1n+1 个整数,为 a1,a2,...,ana_{1} ,a_{2} ,..., a_{n}bb ,代表一组方程。

输出格式: 共n行,每行一个数,第 ii 行为 xix_{i} (保留2位小数) 如果不存在唯一解,在第一行输出 No Solution .

分析及解决

我们举一个例子:并把代数式转换为矩阵

https://s1.ax1x.com/2018/03/31/9x8wUx.png

解决这个方程组

我们会希望它变成如下形式

https://s1.ax1x.com/2018/03/31/9x8056.png

高斯消元的目的是,一步一步将每个未知数约去。每一次操作都能够消除一个未知数。

这种方法是以列为单位消去的

首先我们将第一列转化为1 0 0的形式

  • 在这里要注意一下,我们往往是将这个系数绝对值最大的方程转移到被减的这一行,这样就可以减小误差

https://s1.ax1x.com/2018/03/31/9x8UbR.png

  • 然后将正在处理的方程式化简,让正被处理的系数化1

https://s1.ax1x.com/2018/03/31/9x8s2D.png

  • 然后使用加减法消元

https://s1.ax1x.com/2018/03/31/9x8dV1.png

  • 同理化简第二行

https://s1.ax1x.com/2018/03/31/9x8DPK.png

  • 消去第一行的第二个元素,即减去第二行 && 消去第三行的第一个元素,即减去第二行

https://s1.ax1x.com/2018/03/31/9x8IG8.png

  • 第三行不需要化简,消去第一行的第三个元素,即减去第三行 ,消去第二行的第三个元素,即减去第三行

https://s1.ax1x.com/2018/03/31/9x8IG8.png

  • 最终结果

https://s1.ax1x.com/2018/03/31/9x8r8O.png

于是该方程组的解 x=1,y=2,z=3x=1,y=2,z=3

高斯消元法的复杂度为 O(n3)O(n^{3}) 其中 nn 为未知数个数

无解:

当操作时发现该位系数绝对值的最大值为0一定无解。

这里再说明一下,代码实现的时候先处理出最后一个未知数的解,然后向上回代,进而解得所有解。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<cstdio>
#include<cmath>
#include<memory>
#define re register int
#define rep(i,a,b) for(re i=(a);i<=(b);++i)
#define drep(i,a,b) for(re i=(a);i>=(b);--i)
#define eps 1e-8
double mat[102][102],ans[102];
int n;

inline bool Gauss(){
rep(i,1,n){
int major=i;
rep(j,i+1,n)
if(fabs(mat[j][i]) > fabs(mat[major][i])) major=j; //当前位置系数绝对值最大
if(fabs(mat[major][i]) < eps) return 1; //系数为0 无解
if(major != i)
rep(j,i,n+1) std::swap(mat[major][j],mat[i][j]);//两行交换
rep(j,i+1,n){
double ratio=mat[j][i]/mat[i][i]; //该位系数变为 1
rep(k,i,n+1)
mat[j][k]-=mat[i][k]*ratio; //向下消元
}
}
drep(i,n,0){
rep(j,i+1,n)
mat[i][n+1]-=mat[i][j]*ans[j];
ans[i]=mat[i][n+1]/mat[i][i]; //答案还原
}
return 0;
}

int main(){
scanf("%d",&n);
rep(i,1,n)
rep(j,1,n+1)
scanf("%lf",mat[i]+j);
if(Gauss()) puts("No Solution");
else rep(i,1,n) printf("%.2f\n",ans[i]);
}