首页 > 其他分享 >高斯消元 学习笔记

高斯消元 学习笔记

时间:2024-08-12 21:28:05浏览次数:11  
标签:系数 变量 方程组 -- 方程式 笔记 学习 我们 高斯消

用于求解方程组。

给定 \(n\) 个关于 \(m\) 个变量的方程组,需要你判断该方程组是否无解、有无数解、有唯一解,并输出唯一的解。

考虑使用消元法。我们枚举一个变量 \(i\) ,从所有没有被操作过的方程式中选出一个,然后用它对其他没有被操作过的方程式进行消元,并将被选中的那个方程式视为被操作过的。每次在消元时我们都要将其余方程式中的变量 \(i\) 的系数变成 0 。处于对精度的考虑,我们会选择系数的绝对值最大的那个方程式进行消元(意会一下:设我们选中的方程式为第 \(k\) 个,我们将该方程式的所有系数全部除 \(i\) 的系数 \(a_{k,i}\) ,而我们将 \(\frac{1}{a_k,i}\) 视为一个基本单位,这个单位越小,我们最后在消元时得到的值损失精度的程度会降低)。

现在出现了一个问题,如果当某一个变量 \(i\) ,所有未操作过的方程式关于它的系数都为 0 怎么办?直接跳过该变量就好了,因为此时剩余的方程式的性质没有变,都是满足前面所有枚举过的变量的系数为 0。同时,这种情况会使得我们在遍历了所有变量后,在矩阵的底部存在一些所有变量的系数均为 0 的方程式,显然,这种方程式的答案一定为 0。如果不为 0,则方程组无解;如果为 0,则方程式中存在一个自由元(可以取任意值),此时方程组有无数解。

将特殊情况排除后,我们看看如何计算一个唯一解。我们发现,对于最后的一个方程式,它的系数只有一个不为 0,于是我们可以算出来。再看上一个方程式,发现其中可能有两个系数不一定为 0,但是其中一个变量已经被我们算出来了,以此类推。于是我们从下往上回带就好了。

Code

#include<bits/stdc++.h>
using namespace std;
const int N=105;const double eps=1e-9;
double a[N][N],ans[N];
int main()
{
	int n,i,j,k,l;double x;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n+1;j++)
		scanf("%lf",&a[i][j]);
	}
	for(i=1,l=1;i<=n;i++)
	{
		x=abs(a[l][i]);k=l;
		for(j=l+1;j<=n;j++)
		{
			if(abs(a[j][i])>x)
			{
				k=j;x=abs(a[j][i]);
			}
		}
		if(x<=eps)
		continue;
		for(j=i;j<=n+1;j++)
		swap(a[k][j],a[l][j]);
		x=a[l][i];
		for(j=i;j<=n+1;j++)
		a[l][j]/=x;
		for(j=l+1;j<=n;j++)
		{
			for(k=n+1;k>=i;k--)
			a[j][k]=a[j][k]-a[j][i]*a[l][k];
		}
		l++;
	}
	for(i=n;i>=l;i--)
	{
		if(abs(a[i][n+1])>eps)
		{
			printf("-1");return 0;
		}
	}
	if(l<=n)
	{
		printf("0");return 0;
	}
	for(i=n;i>=1;i--)
	{
		for(j=i+1;j<=n;j++)
		a[i][n+1]=a[i][n+1]-a[i][j]*ans[j];
		ans[i]=a[i][n+1]/a[i][i];
	}
	for(i=1;i<=n;i++)
	printf("x%d=%0.2lf\n",i,ans[i]);
	return 0;
}

标签:系数,变量,方程组,--,方程式,笔记,学习,我们,高斯消
From: https://www.cnblogs.com/Cyanwind/p/18355772

相关文章

  • 拉格朗日插值 学习笔记
    我们知道,对于一个\(k\)次多项式,我们只需知道它在\(k+1\)个点上的取值,就能求出这个多项式。我们可以列方程求出每一个的系数,但是这样的时间复杂度是\(n^3\)的,所以我们使用一些别的方法来求出对于某个点的值。拉格朗日插值:设已知平面内的\(n\)个点,要求这\(n\)个点的\(n......
  • 深度学习--数据增强总结
    1.数据增强简介数据增强(DataAugmentation)是一种通过对现有数据进行多种转换和变换,从而生成更多样本的方法。其主要目的是通过增加数据量和多样性,帮助模型更好地泛化,减少过拟合现象。数据增强方法广泛应用于计算机视觉、自然语言处理、语音识别等领域。在深度学习中,由于模型......
  • Java基础-学习笔记09
    **09单例设计模式、final关键字、抽象类、模板设计模式、接口**单例设计模式(静态方法和属性的经典使用)所谓类的单例设计模式,就是采取一定的方法保证在整个的软件系统中,对某个类只能存在一个对象实例,并且该类只提供一个取得其对象实例的方法。//比如某个核心类,很耗费资源,但只......
  • 二维差分·学习备忘录
    二维差分为什么我为OI泪目?因为我菜得离谱......引入一维差分用来O(1)修改区间,配合上一维前缀和就是O(N)的查询区间和。差分为前缀和的逆运算。二维差分同理。接下来这道题就用二维差分来解决。\(例题:地毯>>\)地毯题目描述在\(n\timesn\)的格子上有\(m\)个地毯。......
  • 做题笔记(三)
    [USACO13DEC]VacationPlanningG题目传送门[USACO13DEC]VacationPlanningG思路总结:一点点小思维+最短路板子。显然我们发现,对于每一次询问的出发点\(u\)只有两种可能:是中枢或者不是中枢。同时注意到,\(K\)的范围非常小,所以可以考虑在中枢上做文章。我们可以先试着在......
  • OpenCv学习-python
    一.OpenCv介绍简介OpenCV(OpenSourceComputerVisionLibrary:opencv官网地址)是一个开源的基于BSD许可的库,它包括数百种计算机视觉算法。文档OpenCV2.xAPI描述的是C++API,相对还有一个基于C语言的OpenCV1.xAPI,后者的描述在文档opencv1.x.pdf中。OpenCV具有模块化结......
  • 差分约束 笔记
    差分约束笔记给定约束\(n\)个未知数的\(m\)个约束条件,求满足条件的未知数的其中一个整数解。\(m\)个约束条件如下:\[\left\{\begin{matrix} x_{c_1}+w_1\gex_{c'_1}\\ x_{c_2}+w_2\gex_{c'_2}\\ x_{c_3}+w_3\gex_{c'_3}\\ \dots\\ x_{c_m}+w_m\ge......
  • Java中类与对象的学习上
    类与对象类和对象的概念类定义对象的蓝图,包括属性和方法。具有相同特性(数据元素)和行为(功能)的对象的抽象就是类。因此,对象的抽象是类,类的具体化就是对象,也可以说类的实例是对象,类实际上就是一种数据类型。类具有属性,它是对象的状态的抽象,用数据结构来描述类的属性。类具有操作,......
  • C语言学习心得-二维数组
    (一)二维数组的定义和初始化定义二维数组arr[3][5]:intarr[3][5]={{1,2,3,4,5},{2,3,4,5,6},{3,4,5,6,7}};仔细看这个数组arr[0] 是第一个一维数组,包含元素 arr[0][0],arr[0][1],arr[0][2],arr[0][3],arr[0][4]arr[1] 是第二个一维数组,包含元素 ......
  • 二维前缀和学习指南
    为什么我为OI泪目,因为我菜得离谱......二维前缀和引子二维前缀和,仅仅是由一维前缀和进阶了一维而已。为了方便后面的学习,我先给出二维前缀和重点代码。处理二维前缀和for(inti=1;i<=n;i++) for(intj=1;j<=m;j++) sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[......