首页 > 其他分享 >高斯消元

高斯消元

时间:2022-11-09 08:33:43浏览次数:59  
标签:系数 end int 矩阵 vmatrix 高斯消

0x00 背景

高斯消元是求线性方程组的标准方法,原理和代码都不难

0x01 基本操作

一个线性方程组有\(m\)个一次方程,\(n\)个变量,把所有系数都写成一个\(m\)行\(n\)列的矩阵,把等号右边的常数放在最右边,得到了一个\(m\)行\(n+1\)列的增广矩阵

高斯消元利用多次变换将方程组转换成若干个一元一次方程,以下是\(3\)种 基本变换

  1. 交换某两行的位置
  2. 用一个非零常数\(k\)乘上某个方程
  3. 把某行乘上\(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. 从第一列开始,选择一个最大的系数所在的行,把这一行移动到第\(1\)行,此时\(x_1\)是主元
  2. 把\(x_1\)的系数转换为\(1\)
  3. 利用\(x_1\)的系数,把这一列一系列主元消去
  4. 重复以上步骤知道每行只有对角线上有主元

题目链接

#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

相关文章

  • 第45届国际大学生程序设计竞赛 亚洲区域赛(济南)A // 高斯消元
    题目来源:第45届国际大学生程序设计竞赛(ICPC)亚洲区域赛(济南)A题目链接:A-MatrixEquation题意定义01矩阵的两种运算:对于大小为\(N\timesN\)的01矩阵\(X\)、\(Y\),记......
  • 高斯消元
    高斯消元高斯消元适用于求解线性方程。线性方程形如\[\begin{cases}a_{1,1}x_1+a_{1,2}x_2+...+a_{1,n}x_n=b_1\\a_{2,1}x_1+a_{2,2}x_2+...+a_{2,n}x_n=b_2\\...\\a_{......
  • 【XSY4180】串串游走(AC自动机,期望DP,高斯消元)
    假瑞出搬的神仙题。原题CFgym103119B。先把\(T\)去重。考虑先用\(O(nm\logk)\)建出所有串的AC自动机。注意建AC自动机的时候,为了保证空间,假设当前点\(u\)没......
  • 【XSY2416】带权图(图论,高斯消元)
    感觉非常高妙。考虑暴力做法。首先对于题目中的第三种限制:若两个环满足,那么这两个环拼起来得到的环肯定也满足。那么我们可以只考虑那些互相独立的简单环。随便找到原......
  • 高斯消元
    高斯消元是求解线性方程组的方法。对于一个\(m\)个等式\(n\)个未知数的方程组,我们可以将其写成\(m\times(n+1)\)的增广矩阵的形式:对于这个矩阵我们可以进行三......
  • luogu P3232 [HNOI2013]游走 (期望, 高斯消元)
    https://www.luogu.com.cn/problem/P3232思路:算出每条边的期望访问次数,将期望访问次数多的赋予小的编号。一条边的期望访问次数=访问点u的期望/u的度+访问点v的期望......
  • CF963E Circles of Waiting(高斯消元,主元法)
    CF963ECirclesofWaiting平面直角坐标系上有一个点,开始在\((0,0)\),每秒钟这个点都会随机移动:如果它在\((x,y)\),下一秒它去\(4\)个方向的概率为\(p_0,p_1,p_2,......
  • 高斯消元
    盘活一下线性代数。我也不知道为什么看着格路计数然后看到LGV引理然后就来补线性代数了。高斯消元可以拿来干什么?解方程组。线性方程组。怎么解?我们现在有一个线性方程组......
  • Luogu P3389【模板】高斯消元法
    题意给定一个线性方程组,对其求解。$1\leqn\leq100,\left|a_i\right|\leq{10}^4,\left|b\right|\leq{10}^4$题解因为之前贺题解的时候没有理解高斯-约......
  • 异或方程组高斯消元模板
    inlinevoidsolve(intn){for(inti=1,top=1;i<=n;i++,top++){intcur=0;for(intj=top;j<=n;j++)if(m......