高斯消元
greater_than
·
·
算法·理论
高斯消元的定义：通过多次变换把方程组转化为多个一元一次方程。
操作有三种：
- 交换某两行的位置
- 用一个 k(k\ne0) 乘以某一个方程
- 把某行乘以 k(k\ne0) 然后加到另一个方程上
有三种解：
- 唯一解
- 有无穷多解
- 无解
An Sample（唯一解）:
3x_1+7x_2-5x_3=47 \\
x_1+4x_2+x_3=58 \\
8x_1-3x_2+9x_3=88
\end{cases}
可以转换为：
\begin{bmatrix} 3 & 7 & -5 & | & 47 \\ 1 & 4 & 1 & | & 58 \\ 8 & -3 & 9 & | & 88 \end{bmatrix}
可以对此增广矩阵进行初等变换
\begin{bmatrix} 3 & 7 & -5 & | & 47 \\ 1 & 4 & 1 & | & 58 \\ 0 & 35 & -1 & | & 376 \end{bmatrix}
\begin{bmatrix} 3 & 7 & -5 & | & 47 \\ 0 & 5 & 8 & | & 127 \\ 0 & 35 & -1 & | & 376 \end{bmatrix}
\begin{bmatrix} 3 & 7 & -5 & | & 47 \\ 0 & 5 & 8 & | & 127 \\ 0 & 0 & 57 & | & 513 \end{bmatrix}
\begin{bmatrix} 3 & 7 & -5 & | & 47 \\ 0 & 5 & 8 & | & 127 \\ 0 & 0 & 1 & | & 9 \end{bmatrix}
\begin{bmatrix} 3 & 7 & -5 & | & 47 \\ 0 & 5 & 0 & | & 55 \\ 0 & 0 & 1 & | & 9 \end{bmatrix}
\begin{bmatrix} 3 & 7 & -5 & | & 47 \\ 0 & 1 & 0 & | & 11 \\ 0 & 0 & 1 & | & 9 \end{bmatrix}
\begin{bmatrix} 1 & 0 & 0 & | & 5 \\ 0 & 1 & 0 & | & 11 \\ 0 & 0 & 1 & | & 9 \end{bmatrix}
解得： x_1 =5 , x_2 = 11 , x_3 = 9 。这是唯一解，称最后的矩阵为简化阶梯矩阵，特征是左半部分是一个单位矩阵。
An Sample（有无数解）：
3x_1+7x_2-5x_3=47 \\
x_1+4x_2+x_3=58 \\
2x_1+3x_2-6x_3=-11
\end{cases}
\begin{bmatrix} 3 & 7 & -5 & | & 47 \\ 1 & 4 & 1 & | & 58 \\ 2 & 3 & -6 & | & -11 \end{bmatrix}
经过一次操作后得到:
\begin{bmatrix} 3 & 7 & -5 & | & 47 \\ 0 & 5 & 8 & | & 127 \\ 0 & 0 & 0 & | & 0 \end{bmatrix}
综上可得：
### An Sample （无解）：
$ \begin{cases}
3x_1+7x_2-5x_3=47 \\
x_1+4x_2+x_3=58 \\
2x_1+3x_2-6x_3=5
\end{cases}
\begin{bmatrix} 3 & 7 & -5 & | & 47 \\ 1 & 4 & 1 & | & 58 \\ 2 & 3 & -6 & | & 5 \end{bmatrix}
经过一次操作后得到：
\begin{bmatrix} 3 & 7 & -5 & | & 47 \\ 0 & 5 & 8 & | & 127 \\ 0 & 0 & 0 & | & 16 \end{bmatrix}
综上可得：
### 代码详解：
步骤如下：
1. 从第一列开始，选择一个非 $ 0 $ 的系数的最大行并移到第一行：可取最大（避免出现过大数），也可不取。
2. 把 $ x_1 $ 的系数转化为 $ 1 $ 。
3. 利用这个 $ 1 $ 去消去其它行的地方。
**注：** $ x_2 $ 到 $ x_n $ 一样如此。
#### 时间复杂度：
由于有三重循环，所以时间复杂度为 $ O ( n^3 ) $ 。
#### Code：
```cpp
#include <bits/stdc++.h>
#define double long double
using namespace std;
double a[1005][1005],eps=1e-15;
signed main() {
int n;
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n+1;j++){
cin>>a[i][j];
}
}
for(int i=1;i<=n;i++){
int maxx=i;
for(int j=i+1;j<=n;j++){
if(fabs(a[j][i])>fabs(a[maxx][i])){
maxx=j;
}
}
for(int j=1;j<=n+1;j++){
swap(a[i][j],a[maxx][j]);
}
if(fabs(a[i][i])<eps){
cout<<"No Solution"<<'\n';
return 0;
}
for(int j=n+1;j>=1;j--){
a[i][j]=a[i][j]/a[i][i];
}
for(int j=1;j<=n;j++){
if(j!=i){
double t=a[j][i]/a[i][i];
for(int k=1;k<=n+1;k++){
a[j][k]-=t*a[i][k];
}
}
}
}
for(int i=1;i<=n;i++){
cout<<setprecision(2)<<fixed<<a[i][n+1]<<'\n';
}
}
```
例题:[模板高斯消元](https://www.luogu.com.cn/problem/P3389)
一道变化题，加法变成了异或[外星千足虫](https://www.luogu.com.cn/problem/P2447)