#创作计划#高斯消元

༺ཌༀཉི༒白·羊༒༃ༀད༻

2025-09-29 20:10:35

发布于：上海

11阅读

0回复

0点赞

$\tiny 我最近好高产啊$

今天我们来学习一种强大的算法——高斯消元

目录

1.简介

2.核心思想

3.算法流程

4.代码实现

5.初级应用

6.进阶应用 ~~也没多进阶~~

Part 1. 简介

高斯消元法是一种用于求解 $n$ 元一次方程组的经典算法。它的核心思想是通过加减消元法来求解方程。

Part 2. 核心思想

高斯消元法的核心思想是通过加减消元法来求解线性方程。

Part 3. 算法流程

我们首先从二元一次方程组来入手，二元一次方程组主要有两种方法：加减消元法和代入消元法。我们主要讲解加减消元法。
举个例子：

$\begin{cases} 5x + 3y = 100 \\ 2x + 2y = 50 \end{cases}$

我们通过一式、二式同时乘一定的数值来消去 $x$ ，变形为：

$\begin{cases} 10x + 6y = 200 \\ 10x + 10y = 250 \end{cases}$

于是就可以二式减去一式，得

$4y=50$

于是

$y=\frac{25}{2}$

代回去，得

$\begin{cases} x = \frac{25}{2} \\ y = \frac{25}{2} \end{cases}$

于是，我们可以把加减消元法扩展至 $n$ 的情况
注意此方程

$\begin{cases} a_1x_1+a_2x_2+\dots+a_nx_n=b_1 \\ a_{n+1}x_1+a_{n+2}x_2+\dots+a_{2n}x_n=b_2 \\ \dots\\ a_{n^2-n+1}x_1+a_{n^2-n+2}x_2+\dots+a_{n^2}x_n=b_n \end{cases}$

或者写作

$\begin{cases} a_{1,1}x_1+a_{1,2}x_2+\dots+a_{1,n}x_n=b_1 \\ a_{2,1}x_1+a_{2,2}x_2+\dots+a_{2,n}x_n=b_2 \\ \dots\\ a_{n,1}x_1+a_{n,2}x_2+\dots+a_{n,n}x_n=b_n \end{cases}$

用一式、二式消掉 $x_1$
用二式、三式消掉 $x_1$
$\dots$
用最后两式消掉 $x_1$

于是，我们可以得到 $n-1$ 个方程，其中有 $n-1$ 个未知数。

再重复消元这一步骤，消到 $n-2$ 个元、 $n-3$ 个元、 $\dots$ 、最终消到 $1$ 元 $1$ 次，方程就解出来了。

这就是高斯消元的主要步骤。

Part 4. 代码实现

高斯消元的代码是基于矩阵的。
还是这个方程：

$\begin{cases} a_{1,1}x_1+a_{1,2}x_2+\dots+a_{1,n}x_n=b_1 \\ a_{2,1}x_1+a_{2,2}x_2+\dots+a_{2,n}x_n=b_2 \\ \dots\\ a_{n,1}x_1+a_{n,2}x_2+\dots+a_{n,n}x_n=b_n \end{cases}$

在代码中，会表示为如下矩阵：

$\begin{pmatrix} a_{1,1},a_{1,2},\dots,a_{1,n},\color{red}{b_1} \\ a_{2,1},a_{2,2},\dots,a_{2,n},\color{red}{b_2} \\ \dots\\ a_{n,1},a_{n,2},\dots,a_{n,n},\color{red}{b_n} \end{pmatrix}$

既然表示出来了，余下就很简单了，分为两个部分：

消元
回代（可以递归实现）

要注意一些代码的细节，高斯消元的代码还是比较难写的

Part 5. 初级应用

给出一道例题
这是一道模板题，直接给出代码。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+9;
const int mod=998244353;
const double eps=1e-8;
int n;
double a[501][501];
bool gauss() {
	int now=1,to;
	for(int i=1; i<=n; i++) {
		now=i;
		for(to=now; to<=n; to++)
			if(fabs(a[to][i])>eps)
				break;
		if(to>n) 
			return 0;
		if(to!=now)
			swap(a[now],a[to]);
		double t=a[now][i];
		for(int j=1; j<=n+1; j++)
			a[now][j]/=t;
		for(int j=1; j<=n; j++) {
			if(j!=now) {
				t=a[j][i];
				for(int k=1; k<=n+1; k++)
					a[j][k]-=t*a[now][k];
			}
		}
	}
	return 1;
}
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()==0)
		cout<<"No Solution"<<endl;
	else
		for(int i=1;i<=n;i++)
			cout<<fixed<<setprecision(2)<<a[i][n+1]<<endl;
	return 0;
}