题解：P3389 【模板】高斯消元法
_Weslie_
·
·
题解
高斯消元法是求解线性方程组的经典算法，它在当代数学中有着重要的地位和价值，是线性代数课程教学的重要组成部分。
0x01 高斯消元法解决的问题
给定一个形如下的线性方程组，对其求解。
\begin{cases} a_{1, 1} x_1 + a_{1, 2} x_2 + \cdots + a_{1, n} x_n = b_1 \\ a_{2, 1} x_1 + a_{2, 2} x_2 + \cdots + a_{2, n} x_n = b_2 \\ \cdots \\ a_{n,1} x_1 + a_{n, 2} x_2 + \cdots + a_{n, n} x_n = b_n \end{cases}
这是一道非常经典的题目，即本题。
0x02 消元法
消元法是将方程组中的一方程的未知数用含有另一未知数的代数式表示，并将其带入到另一方程中，这就消去了一未知数，得到一解；或将方程组中的一方程倍乘某个常数加到另外一方程中去，也可达到消去一未知数的目的。消元法主要用于二元一次方程组的求解。
例如：在解二元一次方程组时，可以使用代入消元或者加减消元。
用代入消元举个例子：
\begin{cases}
2x+y=16\\
y=8
\end{cases}
将 y=8 代入 2x+y=16，那么得出 x=4。
而多元的线性方程组，我们一般使用代入消元。
但是显然，我们要把方程组化成这个样子才可能使用代入消元：
\begin{cases}
a_{1,1}x_1&+\ a_{1,2}x_2&+\cdots&+\ a_{1,n}x_n&=b_1\\
&\ \ \ \ a_{2,2}x_2&+\cdots &+\ a_{2,n}x_n&=b_2\\
&&&\ \cdots&\ =\cdots\\
&&&\ \ \ \ a_{n,n}x_n&=b_n
\end{cases}
但是非常不幸的是，一般情况下，给出的方程是这样的：
\begin{cases} a_{1, 1} x_1 + a_{1, 2} x_2 + \cdots + a_{1, n} x_n = b_1 \\ a_{2, 1} x_1 + a_{2, 2} x_2 + \cdots + a_{2, n} x_n = b_2 \\ \cdots \\ a_{n,1} x_1 + a_{n, 2} x_2 + \cdots + a_{n, n} x_n = b_n \end{cases}
所以我们要把下面的方程转化为上面的方程。
0x03 高斯消元法的线性代数基础
我们考虑丢掉未知量，把线性方程组的系数扔进一个矩阵里。
\begin{bmatrix}
a_{1,1}&a_{1,2}&a_{1,3}&\cdots&a_{1,n}\\
a_{2,1}&a_{2,2}&a_{2,3}&\cdots&a_{2,n}\\
a_{3,1}&a_{3,2}&a_{3,3}&\cdots&a_{3,n}\\
\vdots&\vdots&\vdots&\ddots&\vdots\\
a_{n,1}&a_{n,2}&a_{n,3}&\cdots&a_{n,n}
\end{bmatrix}
但是仅仅凭这么一个矩阵是解不出这个线性方程组的。
所以我们需要一个增广矩阵（一组向量）。
这意味着，我们解题时需要用到这样的矩阵：
\begin{bmatrix}
a_{1,1}&a_{1,2}&a_{1,3}&\cdots&a_{1,n}\\
a_{2,1}&a_{2,2}&a_{2,3}&\cdots&a_{2,n}\\
a_{3,1}&a_{3,2}&a_{3,3}&\cdots&a_{3,n}\\
\vdots&\vdots&\vdots&\ddots&\vdots\\
a_{n,1}&a_{n,2}&a_{n,3}&\cdots&a_{n,n}
\end{bmatrix}
\begin{bmatrix}
b_1\\b_2\\b_3\\\vdots\\b_n
\end{bmatrix}
合在一起，就是这样的：
\begin{bmatrix}
a_{1,1}&a_{1,2}&a_{1,3}&\cdots&a_{1,n}&b_1\\
a_{2,1}&a_{2,2}&a_{2,3}&\cdots&a_{2,n}&b_2\\
a_{3,1}&a_{3,2}&a_{3,3}&\cdots&a_{3,n}&b_3\\
\vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\
a_{n,1}&a_{n,2}&a_{n,3}&\cdots&a_{n,n}&b_n
\end{bmatrix}
这样一个 n\times (n+1) 的矩阵。
0x04 高斯消元法的理论依据
三条性质。
- 交换律：将第 i 个方程与第 j 个方程互换，方程的解不变。体现在矩阵上，就是你可以随意互换两行。
- 乘法律：将第 i 个方程左右两边乘以一个非零实数 k，方程的解不变。体现在矩阵上，就是你可以将一行里的全部元素全都乘一个非零实数。
- 加法律：将第 i 个方程的左右边分别加上第 j 个方程的左右边，方程的解不变。体现在矩阵上，就是你可以随意地把一行的所有元素加上另外一行的所有元素。
## 0x05 高斯消元法的过程
根据上面 0x02 章节的分析，我们发现矩阵要消成如下的形式：
$$
\begin{bmatrix}
a_{1,1}'&a_{1,2}'&a_{1,3}'&\cdots&a_{1,n}'&b_1'\\
0&a_{2,2}'&a_{2,3}'&\cdots&a_{2,n}'&b_2'\\
0&0&a_{3,3}'&\cdots&a_{3,n}'&b_3'\\
\vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\
0&0&0&\cdots&a_{n,n}'&b_n'
\end{bmatrix}
$$
这种矩阵我们叫做“上三角矩阵”。
而我们的终极目标是：
$$
\begin{bmatrix}
1&0&0&\cdots&0&b_1''\\
0&1&0&\cdots&0&b_2''\\
0&0&1&\cdots&0&b_3''\\
\vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\
0&0&0&\cdots&1&b_n''\\
\end{bmatrix}
$$
### 0x05a 上三角矩阵
$$
\begin{bmatrix}
a_{1,1}&a_{1,2}&a_{1,3}&\cdots&a_{1,n}&b_1\\
a_{2,1}&a_{2,2}&a_{2,3}&\cdots&a_{2,n}&b_2\\
a_{3,1}&a_{3,2}&a_{3,3}&\cdots&a_{3,n}&b_3\\
a_{4,1}&a_{4,2}&a_{4,3}&\cdots&a_{4,n}&b_4\\
a_{5,1}&a_{5,2}&a_{5,3}&\cdots&a_{5,n}&b_5\\
\end{bmatrix}
$$
首先，我们将第 $1$ 行都除以 $a_{1,1}$。
$$
\begin{bmatrix}
1&\frac{a_{1,2}}{a_{1,1}}&\frac{a_{1,3}}{a_{1,1}}&\cdots&\frac{a_{1,n}}{a_{1,1}}&\frac{b_1}{a_{1,1}}\\
a_{2,1}&a_{2,2}&a_{2,3}&\cdots&a_{2,n}&b_2\\
a_{3,1}&a_{3,2}&a_{3,3}&\cdots&a_{3,n}&b_3\\
a_{4,1}&a_{4,2}&a_{4,3}&\cdots&a_{4,n}&b_4\\
a_{5,1}&a_{5,2}&a_{5,3}&\cdots&a_{5,n}&b_5\\
\vdots&\vdots&\vdots&\ddots&\vdots&\vdots
\end{bmatrix}
$$
然后，将第 $2$ 行减掉 $a_{2,1}$ 与当前新的第一行对应位置元素的乘积。
$$
\begin{bmatrix}
1&\frac{a_{1,2}}{a_{1,1}}&\frac{a_{1,3}}{a_{1,1}}&\cdots&\frac{a_{1,n}}{a_{1,1}}&\frac{b_1}{a_{1,1}}\\
0&a_{2,2}-\frac{a_{2,1}a_{1,2}}{a_{1,1}}&a_{2,3}-\frac{a_{2,1}a_{1,3}}{a_{1,1}}&\cdots& a_{2,n}-\frac{a_{2,1}a_{1,n}}{a_{1,1}} &b_2-\frac{a_{2,1}b_1}{a_{1,1}}\\
a_{3,1}&a_{3,2}&a_{3,3}&\cdots&a_{3,n}&b_3\\
a_{4,1}&a_{4,2}&a_{4,3}&\cdots&a_{4,n}&b_4\\
a_{5,1}&a_{5,2}&a_{5,3}&\cdots&a_{5,n}&b_5\\
\vdots&\vdots&\vdots&\ddots&\vdots&\vdots
\end{bmatrix}
$$
同理，对第 $3$ 到 $5$ 行做同样的操作。
$$
\begin{bmatrix}
1&\frac{a_{1,2}}{a_{1,1}}&\frac{a_{1,3}}{a_{1,1}}&\cdots&\frac{a_{1,n}}{a_{1,1}}&\frac{b_1}{a_{1,1}}\\
0&a_{2,2}-\frac{a_{2,1}a_{1,2}}{a_{1,1}}&a_{2,3}-\frac{a_{2,1}a_{1,3}}{a_{1,1}}&\cdots& a_{2,n}-\frac{a_{2,1}a_{1,n}}{a_{1,1}} &b_2-\frac{a_{2,1}b_1}{a_{1,1}}\\
0&a_{3,2}-\frac{a_{3,1}a_{1,2}}{a_{1,1}}&a_{3,3}-\frac{a_{3,1}a_{1,3}}{a_{1,1}}&\cdots& a_{3,n}-\frac{a_{3,1}a_{1,n}}{a_{1,1}} &b_3-\frac{a_{3,1}b_1}{a_{1,1}}\\
0&a_{4,2}-\frac{a_{4,1}a_{1,2}}{a_{1,1}}&a_{4,3}-\frac{a_{4,1}a_{1,3}}{a_{1,1}}&\cdots& a_{4,n}-\frac{a_{4,1}a_{1,n}}{a_{1,1}} &b_4-\frac{a_{4,1}b_1}{a_{1,1}}\\
0&a_{5,2}-\frac{a_{5,1}a_{1,2}}{a_{1,1}}&a_{5,3}-\frac{a_{5,1}a_{1,3}}{a_{1,1}}&\cdots& a_{5,n}-\frac{a_{5,1}a_{1,n}}{a_{1,1}} &b_5-\frac{a_{5,1}b_1}{a_{1,1}}\\
\vdots&\vdots&\vdots&\ddots&\vdots&\vdots
\end{bmatrix}
$$
为了方便，我们把矩阵记为 $a'$ 矩阵。
$$
\begin{bmatrix}
1&a_{1,2}'&a_{1,3}'&\cdots&a_{1,n}'&b_1'\\
0&a_{2,2}'&a_{2,3}'&\cdots&a_{2,n}'&b_2'\\
0&a_{3,2}'&a_{3,3}'&\cdots&a_{3,n}'&b_3'\\
0&a_{4,2}'&a_{4,3}'&\cdots&a_{4,n}'&b_4'\\
0&a_{5,2}'&a_{5,3}'&\cdots&a_{5,n}'&b_5'\\
\vdots&\vdots&\vdots&\ddots&\vdots&\vdots
\end{bmatrix}
$$
然后用第二行消第三行。
先把第二行除掉 $a_{2,2}'$。
$$
\begin{bmatrix}
1&a_{1,2}'&a_{1,3}'&\cdots&a_{1,n}'&b_1'\\
0&1&\frac{a_{2,3}'}{a_{2,2}'}&\cdots&\frac{a_{2,n}'}{a_{2,2}'
}&\frac{b_2'}{a_{2,2}'}\\
0&a_{3,2}'&a_{3,3}'&\cdots&a_{3,n}'&b_3'\\
0&a_{4,2}'&a_{4,3}'&\cdots&a_{4,n}'&b_4'\\
0&a_{5,2}'&a_{5,3}'&\cdots&a_{5,n}'&b_5'\\
\vdots&\vdots&\vdots&\ddots&\vdots&\vdots
\end{bmatrix}
$$
然后第三、四、五行减掉第二行乘 $a_{3,2}'$。
$$
\begin{bmatrix}
1&a_{1,2}'&a_{1,3}'&\cdots&a_{1,n}'&b_1'\\
0&1&\frac{a_{2,3}'}{a_{2,2}'}&\cdots&\frac{a_{2,n}'}{a_{2,2}'
}&\frac{b_2'}{a_{2,2}'}\\
0&0&a_{3,3}'-\frac{a_{2,3}'a_{3,2}'}{a_{2,2}'}&\cdots&a_{3,n}'-\frac{a_{2,n}'a_{3,2}'}{a_{2,2}'}&b_3'-\frac{b_2'a_{3,2}'}{a_{2,2}'}\\
0&0&a_{4,3}'-\frac{a_{2,3}'a_{4,2}'}{a_{2,2}'}&\cdots&a_{4,n}'-\frac{a_{2,n}'a_{4,2}'}{a_{2,2}'}&b_4'-\frac{b_2'a_{4,2}'}{a_{2,2}'}\\
0&0&a_{5,3}'-\frac{a_{2,3}'a_{5,2}'}{a_{2,2}'}&\cdots&a_{5,n}'-\frac{a_{2,n}'a_{5,2}'}{a_{2,2}'}&b_5'-\frac{b_2'a_{5,2}'}{a_{2,2}'}\\
\vdots&\vdots&\vdots&\ddots&\vdots&\vdots
\end{bmatrix}
$$
一直消元下去。
最后你会得到一个这样的矩阵（下面矩阵中 $a'$ 及 $b'$ 与上文不同）：
$$
\begin{bmatrix}
a_{1,1}'&a_{1,2}'&a_{1,3}'&\cdots&a_{1,n}'&b_1'\\
0&a_{2,2}'&a_{2,3}'&\cdots&a_{2,n}'&b_2'\\
0&0&a_{3,3}'&\cdots&a_{3,n}'&b_3'\\
\vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\
0&0&0&\cdots&a_{n,n}'&b_n'
\end{bmatrix}
$$
恭喜你得到了上三角矩阵！
实际上，上面这些仅仅只是理论分析。具体实现上，我们仍然需要实际问题实际看。
举个例子：
$$
\begin{bmatrix}
12&24&18&36&72\\
6&12&8&4&2\\
3&6&2&4&9\\
2&4&9&12&24
\end{bmatrix}
$$
先第一行都除以 $12$。
$$
\begin{bmatrix}
1&2&\frac{3}{2}&3&6\\
6&12&8&4&2\\
3&6&2&4&9\\
2&8&9&12&24
\end{bmatrix}
$$
然后对后面几行乘加。
$$
\begin{bmatrix}
1&2&\frac{3}{2}&3&6\\
0&0&-1&-8&-34\\
0&0&-\frac{5}{2}&-5&-9\\
0&4&6&6&12
\end{bmatrix}
$$
问题出现了！第二行第二个数是 $0$！我们无法继续消元了！
别急。
还记得“交换律”吗？
我们只需要把第四行与第二行交换就可以继续啦！
$$
\begin{bmatrix}
1&2&\frac{3}{2}&3&6\\
0&1&\frac{3}{2}&\frac{3}{2}&3\\
0&0&-\frac{5}{2}&-5&-9\\
0&0&-1&-8&-34\\
\end{bmatrix}
$$
继续消元（这次消第三列）。
$$
\begin{bmatrix}
1&2&\frac{3}{2}&3&6\\
0&4&6&6&12\\
0&0&1&2&\frac{18}{5}\\
0&0&0&-5&-\frac{151}{5}\\
\end{bmatrix}
$$
最后是这样的：
$$
\begin{bmatrix}
1&2&\frac{3}{2}&3&6\\
0&4&6&6&12\\
0&0&1&2&\frac{18}{5}\\
0&0&0&1&\frac{151}{25}\\
\end{bmatrix}
$$
### 0x05b 答案矩阵
假设我们已经得到了这样一个“上三角矩阵”：
$$
\begin{bmatrix}
a_{1,1}&a_{1,2}&a_{1,3}&\cdots&a_{1,n}&b_1\\
0&a_{2,2}&a_{2,3}&\cdots&a_{2,n}&b_2\\
0&0&a_{3,3}&\cdots&a_{3,n}&b_3\\
\vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\
0&0&0&\cdots&a_{n,n}&b_n
\end{bmatrix}
$$
考虑将其转化为下面的形式：
$$
\begin{bmatrix}
1&0&0&\cdots&0&b_1'\\
0&1&0&\cdots&0&b_2'\\
0&0&1&\cdots&0&b_3'\\
\vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\
0&0&0&\cdots&1&b_n'\\
\end{bmatrix}
$$
首先，我们考虑把上面的矩阵转化成方程组形式。
那么最后一行对应的方程如下：
$$x_n=b_n$$
然后再看倒数第二行的方程：
$$x_{n-1}+a_{n-1,n}x_n=b_{n-1}$$
由于 $x_n$ 已经被解出来了，是已知量。所以可以移项，得到：
$$a_{n-1,n-1}x_{n-1}=b_{n-1}-a_{n-1,n}x_n$$
解得
$$x_{n-1}=b_{n-1}-a_{n-1,n}x_n$$
然后再看倒数第三行的方程：
$$x_{n-2}+a_{n-2,n-1}x_{n-1}+a_{n-2,n}x_n=b_{n-2}$$
解得
$$x_{n-2}=b_{n-2}-a_{n-2,n}x_n-a_{n-2,n-1}x_{n-1}$$
这样代入，可以解出所有的 $x_i$。
举个例子：假如我们消元消成了这样的“上三角矩阵”：
$$
\begin{bmatrix}
1&3&6&5&7&44\\
0&1&2&2&2&13\\
0&0&1&3&2&10\\
0&0&0&1&3&5\\
0&0&0&0&1&1\\
\end{bmatrix}
$$
那么：
先得出 $x_5=1$。
然后将 $x_5=1$ 代入方程 $x_4+3x_5=5$，得出 $x_4=2$。
然后将 $x_4=2,x_5=1$ 代入方程 $x_3+3x_4+2x_5=10$，得到 $x_3=2$。
然后将 $x_3=2,x_4=2,x_5=1$ 代入方程 $x_2+2x_3+2x_4+2x_5=13$，得到 $x_2=3$。
最后将 $x_2=3,x_3=2,x_4=2,x_5=1$ 代入方程 $x_1+3x_2+6x_3+5x_4+7x_5=44$ 中，得到 $x_1=6$。
最后解是：
$$
\begin{cases}
x_1&=6\\
x_2&=3\\
x_3&=2\\
x_4&=2\\
x_5&=1
\end{cases}
$$
完成！
## 0x06 无穷解与无解的判定
我们都知道，如果想要求一个 $n$ 元线性方程组的唯一解，那么必须要有 $n$ 个有意义的方程。
什么叫做无意义方程？
$$
\begin{cases}
4x_1&+5x_2&+6x_3&=3\\
2x_1&+3x_2&+3x_3&=6\\
7x_1&+8x_2&+9x_3&=9
\end{cases}
$$
第三个方程可以直接由前两个方程相加得到。所以第三个方程是“无意义”的。
如果在高斯消元的过程中，出现了 $0x=0$ 的情况，说明出现了无意义方程，那么就是无穷解。
如果出现了 $0x=k(k\ne 0)$ 的情况，就是无解。
## 0x07 代码实现
### 0x07a 小技巧
1. 在寻找某一行第 $i$ 位不为 $0$ 时，可以选择绝对值最大的一行。这样如果要判断无解或无穷解，直接判断绝对值最大的一行是否为 $0$ 即可。
2. 注意不要使用 $0$ 作为 $0$，而是一个极小常数——$10^{-7}$ 即可。
```
#include<bits/stdc++.h>
using namespace std;
double a[105][105];
double ans[105];
const double eps=1e-7;
int n;
double abss(double _) {
if(_<0)return -_;
return _;
}
int main(){
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 r=i;
for(int j=i+1;j<=n;j++){
if(abss(a[r][i])<abss(a[j][i]))r=j;//选择绝对值最大的一行
}
if(abss(a[r][i])<eps){
cout<<"No Solution";
return 0;
}
if(i!=r)swap(a[i],a[r]);
double div=a[i][i];
for(int j=i;j<=n+1;j++)a[i][j]/=div;
for(int j=i+1;j<=n;j++){
div=a[j][i];
for(int k=i;k<=n+1;k++){
a[j][k]-=a[i][k]*div;
}
}
}
ans[n]=a[n][n+1];
for(int i=n-1;i>=1;i--){
ans[i]=a[i][n+1];
for(int j=i+1;j<=n;j++){
ans[i]-=(a[i][j]*ans[j]);
}
}
for(int i=1;i<=n;i++){
printf("%.2lf\n",ans[i]);
}
return 0;
}
```
## 0x08 高斯消元法的时间复杂度分析
根据上文分析及代码，是 $\operatorname{O}(n^3)$ 的。
如果有特殊矩阵，可以更低。
## 0x09 高斯消元法的应用
- 求解线性方程组，如 [P3389](https://www.luogu.com.cn/problem/P3389)、[P2455](https://www.luogu.com.cn/problem/P2455)。
- 转移有后效性 dp，如 [CF24D](https://www.luogu.com.cn/problem/CF24D)。