高斯消元（by wyx）

引入

高斯消元法（Gauss–Jordan elimination）是求解线性方程组的经典算法，它在当代数学中有着重要的地位和价值，是线性代数课程教学的重要组成部分。

高斯消元法除了用于线性方程组求解外，还可以用于行列式计算、求矩阵的逆，以及其他计算机和工程方面。

正题

前置知识：解方程组

比如说现在有一个方程组：

$\begin{cases} 4x+3y=10 \\ 2x+5y=12 \end{cases}$

第一步，将第一个方程 $\times$ 2 可得 $4x+10y=24$

然后把第二个方程与第一个方程相减得 $7y=14$

这个时候，我们可以直接得出 $y=2$

然后把 $y=2$ 会带到第一个方程中得 $4x+6=10$

可以得出 $x=1$

$\therefore$ 方程的解是

$\begin{cases} x=1\\y=2 \end{cases}$

高斯消元

上述得方法是解方程组得基本方法，即带入消元和加减消元。

这个方法得通用性很强，而高斯消元就是这两种方法得应用。

下面举一个例子

$\begin{cases} 6x_1+8x_2+4x_3=22 \\ 3x_1+2x_2+12x_3=29 \\ 2x_1+4x_2+6x_3=18 \end{cases}$

把上面得方程组转化为矩阵是

$\begin{bmatrix} 6 & 8 & 4 & | & 22 \\ 3 & 2 & 12 & | & 29 \\ 2 & 4 & 6 & | & 18 \\ \end{bmatrix}$

矩阵左边表示每一项得系数，右边表示结果。

首先，我们可以通过第一行消掉第二行和第三行得第一项

具体的，就是说先把第二行 $\times$ $2$ ，然后和第一行减法消元，第三行也是一样的做法，先 $\times$ $3$ 再减法消元。

然后，我们就得到了一个新的矩阵

$\begin{bmatrix} 6 & 8 & 4 & | & 22 \\ 0 & -4 & 20 & | & 36 \\ 0 & 4 & 14 & | & 32 \\ \end{bmatrix}$

这个时候，发现只有第一行含有 $x_1$ 这一项，同时我们也处理完了第一条方程，之后就先不管它。

接着我们用相同得办法解决 $x_2$ 这一项。

把第三行 $\times$ $(-1)$ ，再和第二行做减法消元得

$\begin{bmatrix} 6 & 8 & 4 & | & 22 \\ 0 & -4 & 20 & | & 36 \\ 0 & 0 & -34 & | & -68 \\ \end{bmatrix}$

关键

这个时候，把矩阵重新转化为方程组得到

$\begin{cases} 6x_1+8x_2+4x_3=22 \\ -4x_2+20x_3=36 \\ -34x_3=-68 \end{cases}$

根据第三条方程可得 $x_3=2$

接着把 $x_3=2$ 带入上面一条方程中得 $-4x_2+40=36$

解得 $x_2=1$

然后把 $x_2$ , $x_3$ 一起带入第一条方程中

解得 $x_1=1$

$\therefore$ 方程的解是

$\begin{cases} x_1=1\\x_2=1\\x_3=2 \end{cases}$

总结方法

首先，先把方程变成一个矩阵

$\begin{bmatrix} a_{1,1} & a_{1,2} & a_{1,3} & \ldots & a_{1,n} & | & a_{1,n+1} \\ a_{2,1} & a_{2,2} & a_{2,3} & \ldots & a_{2,n} & | & a_{2,n+1} \\ \vdots & \vdots & \vdots & \ddots & \vdots & | & \vdots \\ a_{n,1} & a_{n,2} & a_{n,3} & \ldots & a_{n,n} & | & a_{n,n+1}\end{bmatrix}$

然后，我们把它变成上三角矩阵，即

$\begin{bmatrix} a_{1,1}' & a_{1,2}' & a_{1,3}' & \ldots & a_{1,n}' & | & a_{1,n+1}' \\ 0 & a_{2,2}' & a_{2,3}' & \ldots & a_{2,n}' & | & a_{2,n+1}' \\ \vdots & \vdots & \vdots & \ddots & \vdots & | & \vdots \\ 0 & 0 & 0 & \ldots & a_{n,n}' & | & a_{n,n+1}'\end{bmatrix}$

接着，我们可以从下往上依次求解每个未知数。

判断无解或有无数解

前置知识 含参方程

对于一个一元一次方程

$ax=b$

• 当 $a \neq 0$ 时，方程有唯一解。

• 当 $a=0$ 且 $b=0$ 时，方程有无数个解。

• 当 $a=0$ 且 $b \neq 0$ 时，方程无解。

把上面三条性质扩展到高斯消元中。

如果有一行在消元后左边的系数全变成了 $0$

• 当右边的结果等于 $0$ 时，方程有无数个解。

• 当右边的结果不等于 $0$ 时，方程无解。

切记，无解的优先级高于有无数个解。

例题

P3389 【模板】高斯消元法

P2455 [SDOI2006] 线性方程组

P2447 [SDOI2010] 外星千足虫

[ABC366G] XOR Neighbors