0x00 背景
高斯消元是求线性方程组的标准方法,原理和代码都不难
0x01 基本操作
一个线性方程组有\(m\)个一次方程,\(n\)个变量,把所有系数都写成一个\(m\)行\(n\)列的矩阵,把等号右边的常数放在最右边,得到了一个\(m\)行\(n+1\)列的增广矩阵
高斯消元利用多次变换将方程组转换成若干个一元一次方程,以下是\(3\)种 基本变换
- 交换某两行的位置
- 用一个非零常数\(k\)乘上某个方程
- 把某行乘上\(k\)然后加到另一行上
举个例子
\(\begin{cases}3x+7y-5z=47 \\ x+4y+z=58 \\ 8x-3y+9z=88 \end{cases}\)
这个方程组可以转化为
\(\begin{vmatrix} 3&7&-5&47 \\ 1&4&1&58 \\ 8&-3&9&88 \end{vmatrix}\)
最后可以消元成
\(\begin{vmatrix} 0&0&0&5 \\ 0&0&0&11 \\ 0&0&0&9 \end{vmatrix}\)
它是一个简化阶梯矩阵,有且只有唯一解
0x02 高斯-约当消元法
在OI中,我们需要一些程式化的方法来进行高斯消元,这时就要用到高斯-约当消元法,消元的结果会是一个简化阶梯矩阵
消元过程如下:
- 从第一列开始,选择一个最大的系数所在的行,把这一行移动到第\(1\)行,此时\(x_1\)是主元
- 把\(x_1\)的系数转换为\(1\)
- 利用\(x_1\)的系数,把这一列一系列主元消去
- 重复以上步骤知道每行只有对角线上有主元
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
const double eps = 1e-7;
double a[N][N];
int n;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)
for(int j=1;j<=n+1;j++)
scanf("%lf",&a[i][j]);
for(int i=1;i<=n;i++){
int max=i;
for(int j=i+1;j<=n;j++)
if(fabs(a[j][i])>fabs(a[max][i])) max=j;//找到系数最大的那一行
for(int j=1;j<=n+1;j++)
swap(a[i][j],a[max][j]);//交换这两行
//swap(a[i],a[max]); 用这个来交换也可以
if(fabs(a[i][i])<eps){
puts("No Solution");//若系数为0,说明有无数组解
return 0;
}
for(int j=1;j<=n;j++)
if(j!=i){
double temp=a[j][i]/a[i][i];
for(int k=1;k<=n+1;k++)
a[j][k]-=a[i][k]*temp;//利用这一行对其它行进行消元
}
}
for(int i=1;i<=n;i++)
printf("%.2lf\n",a[i][n+1]/a[i][i]);//再除以一个系数可得答案
return 0;
}
标签:系数,end,int,矩阵,vmatrix,高斯消
From: https://www.cnblogs.com/sheepcsy/p/16871933.html