高斯消元

从零开始的高斯消元

说在前面：
高斯消元看上去是一个很复杂的东西，但是其实只要是理解了就会发现也就那样的

---

算法功能：

解方程组。
没错就是如此的简单，就是去解方程组。但是高斯消元一般是用来解决含有上百个未知数的方程组。
其时间复杂度为 $O(n^3)$

算法详解：

下面我就来介绍一下高斯消元的最简单的应用，也就是解正常的一次方程组。
比如我们有以下的方程组：

$$\left\{ \begin{array}{} 3x_1 + 4x_2 + x_3 = 9 \\ 5x_1 + 10x_2 + 7x_3 = 5 \\ 2x_1 + 7x_2 + 3x_3 = 10 \end{array} \right.$$

在高斯消元的过程中我们会将它转化为一个矩阵，矩阵里第 $i$ 行代表第 $i$ 个式子，第 $j$ 列代表第 $j$ 个未知数的系数，其中第 $n+1$ 也就是最后一列，代表常数项，也就是等于号后面的数
那么以上的这个方程组就会被写为：

$$\begin{bmatrix} x_1 & x_2 & x_3 & C \\ 3 & 4 & 1 & 9 \\ 5 & 10 & 7 & 5 \\ 2 & 7 & 3 & 10 \\ \end{bmatrix}$$

这个时候可能会很懵，但是一定要静下心来仔细看看这个矩阵和上面的方程组
我们高斯消元的思想就是加减消元，就是我们在小学会学习到的那个知识

---

---

加减消元的解释：（如果会了就请跳过，避免看了之后有点晕）
比如我们有以下一个二元一次方程组：

$$\left\{ \begin{array}{} 3x + 2y = 6 & (1)\\ x + 3y = 2 & (2) \end{array} \right.$$

那么如何进行加减消元呢？
我们考虑先消掉 $x$
很简单：$(1) - 3 \times (2)$
这样就能得到

$$-7y = 0$$

我们就成功地将 $x$ 这个未知数消掉了，接下来就只剩下了一个未知数，很明显就可以直接算出来 $y = 0$，然后将这个值带回去，就能解出 $x = 2$

---

---

我们在高斯消元中，就是用加减消元，从第一个未知数开始一个一个地消，直到消到只剩下一个未知数就能很轻松地能将方程解出来
按我的代码习惯而言，就是将每一个式子都消掉只剩一个未知数，这样 $n$ 个式子每个式子对应一个未知数就很好地能解出来

代码详解：

下面先放代码，根据代码一点点来解释

点击查看代码

#include<bits/stdc++.h>
using namespace std;
double a[105][105];
int n;
bool Gauss(){
	for(int i=1; i<=n; i++){   //第几个未知数/第几列 
		int mx = i;  //先让最大值为 i;
		for(int j = i+1; j<=n; j++){   //找到第 i 列上绝对值最大的那个数在第几行 
			//前 i-1 行已经有了自己的位置，就是自己有独特的保留的未知数了，再次将他设为 i 需要的值
			//那么它本身的那个数就没了 
			if(fabs(a[j][i]) > fabs(a[mx][i])){
				mx = j;
			}
		}
		//我们认为第 i 行就是仅包含第 i 个未知数的那一行 
		if(mx != i){  //交换两行，需要全部交换 
			for(int j=1; j<=n+1; j++){
				swap(a[i][j],a[mx][j]);
			}
		} 
		if(!a[i][i]){   //这一列都是 0 ，所以说这一列对未知数没有限制，也就是有可以任意取值的未知数 
			printf("No Solution");
			return false;
		}
		for(int j=1; j<=n; j++){
			if(j != i){
				double tmp = a[j][i] / a[i][i];   //代表要减多少倍才能将这一行的第 i 个未知数消掉，因为要减一起减，所以就全部减了 
				for(int k = i; k<=n+1; k++){
					//因为前 i 列已经被之前消没了，就全是 0 了 
					a[j][k] -= a[i][k] * tmp;
				}
			}
		}
	}
	return true;
}
int main(){
	cin>>n;
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n+1; j++){
			cin>>a[i][j];
		}
	}
	if(Gauss()){
		for(int i=1; i<=n; i++){
			printf("%.2f\n",a[i][n + 1] / a[i][i]);
		}
	}
	return 0;
}

我们就顺着代码一点点来看，这里的高斯消元部分也就是那个 $Gauss()$ 函数（可能有点长，但是耐心读一读应该会有所收获）
首先最外层循环，枚举当前消到了哪一个未知数，也就是该消哪一个了。
注意我上文的解释，既然枚举到了这一个未知数，那么按照我的码风来说，前 $i-1$ 个未知数是都被消没了的，因为如果没有消没，就不可能再将后面的式子都化为只含有一个未知数的式子

然后就继续往下看。
下面的这个 $for$ 循环就是在寻找当前未知数中绝对值最大的是谁在哪一个式子里，然后我们就要将别的式子通过加减我们找到的这个式子，来将当前的未知数消掉。
而且我们默认有一点：第 $i$ 个式子其最后只含有第 $i$ 个未知数，所以我们的 $j$ 是从 $i$ 开始枚举，一开始第 $i$ 行被认为是最大的一行，也相当于枚举了，也就有了下面的 $if$ 里面的交换操作。
注意对于交换完了之后第 $i$ 个式子就是我们找到的当前未知数绝对值最大的一个式子，那么第 $i$ 行的第 $i$ 列，也就是第 $i$ 个未知数绝对值最大的那个数

继续最后的一个循环，就是用第 $i$ 行的这个式子去消其他的式子，也就是将其他行的第 $i$ 个未知数消去，让他们的系数全都变成 $0$
其他的不用我多说，我代码里写的也很清楚，也很简单，重点在于 $k$ 的范围 $[i,n+1]$，是不是有种很懵的感觉
不着急，我们一点点看，先看左边界 $i$ ，因为我们消元就是将除了第 $i$ 个式子之外的所有式子中含有的未知数 $i$ 的系数全部变成 $0$，那么就意味着当我们枚举到 $i$ 的时候前 $i-1$ 个未知数，也就是前 $i-1$ 行，一定都被全消成 $0$ 了，那么此时我们再去枚举这些本来就是 $0$ 的地方，想让他变成 $0$ 也就没有任何意义了。
再来看右边界 $n+1$，我们考虑第 $n+1$ 列存的是什么，存的是不是就是我们的常数项啊，在我们加减消元的过程中常数项也是需要加减的，因为这样才会满足等式的性质，等于号才不变

如果有感觉我哪里解释的不对或者不清楚，欢迎给我留言