• 通过初等行变换把 增广矩阵 化为 阶梯型矩阵 并回代 得到方程的解
• 适用于求解 包含$n$个方程，$n$ 个未知数的多元线性方程组

消元法理论的核心

消元法理论的核心主要如下：

• 两方程互换，解不变；

• 一方程乘以非零数 $k$，解不变；

• 一方程乘以数 $k$ 加上另一方程，解不变。

---

对于方程组

$$\{\begin{array}{}& a_{11}{x}_1+& a_{12}{x}_2+\dots +& a_{1n}{x}_n=& b_1\\ & a_{21}{x}_1+& a_{22}{x}_2+\dots +& a_{2n}{x}_n=& b_2\\ & ⋮& ⋮& ⋮& ⋮\\ & a_{n1}{x}_1+& a_{n2}{x}_2+\dots +& a_{nn}{x}_n=& b_n\end{array}$$

增广矩阵为

$$\left(\begin{array}{ccccc}{a}_{11}& a_{12}& \cdots & a_{1n}& b_1\\ a_{21}& a_{22}& \cdots & a_{2n}& b_2\\ ⋮& ⋮& ⋮& ⋮& ⋮\\ a_{n1}& a_{n2}& \cdots & a_{nn}& b_n\end{array}\right)$$

---

初等行（列）变换

1. 把某一行乘一个非0的数 (方程的两边同时乘上一个非0数不改变方程的解)
2. 交换某两行 (交换两个方程的位置)
3. 把某行的若干倍加到另一行上去 (把一个方程的若干倍加到另一个方程上去)

---

用初等行（列）变换将增广矩阵变为阶梯型矩阵:

$$\left(\begin{array}{ccccc}{a}_{11}& a_{12}& \cdots & a_{1n}& b_1\\ & a_{2i}& a_{2(i+1)}& a_{2n}& b_2\\ & & & ⋮& ⋮\\ & & & a_{nn}& b_n\end{array}\right)$$

最后再把阶梯型矩阵从下到上回代到第一层即可得到方程的解

---

解的个数

• 完美阶梯型: 唯一解
• $0=a,a\ne 0$: 无解
• $0=0$: 无穷组解

---

算法步骤

枚举每一列 $c$，

1. 找到当前列绝对值最大的一行
2. 用初等行变换 $(2)$ 把这一行换到最上面（未确定阶梯型的行，并不是第一行）
3. 用初等行变换 $(1)$ 将该行的第一个数变成 $1$（其余所有的数字依次跟着变化）
4. 用初等行变换 $(3)$ 将下面所有行的当且列的值变成 $0$

---

例子: 利用高斯消元法五步骤法求解线性方程组

$$\{\begin{array}{rl}2x_1+5x_3+6x_4& =9\\ x_3+x_4& =-4\\ 2x_3+2x_4& =-8\end{array}$$

增广矩阵行（初等）变换为行最简形

所谓增广矩阵，即为方程组系数矩阵 $A$ 与常数列 $b$ 的并生成的新矩阵，即 $(A|b)$，增广矩阵行初等变换化为行最简形，即是利用了高斯消元法的思想理念，省略了变量而用变量的系数位置表示变量，增广矩阵中用竖线隔开了系数矩阵和常数列，代表了等于符号。

$$\left(\begin{array}{cccc}2& 0& 5& 6\\ 0& 0& 1& 1\\ 0& 0& 2& 2\end{array}\right|\begin{array}{c}9\\ -4\\ -8\end{array})$$$$\stackrel{r_3-2r_2}{\to }\left(\begin{array}{cccc}2& 0& 5& 6\\ 0& 0& 1& 1\\ 0& 0& 0& 0\end{array}\right|\begin{array}{c}9\\ -4\\ 0\end{array})$$

化为行阶梯形

$$\stackrel{\frac{r_1}{2}}{\to }\left(\begin{array}{cccc}1& 0& 2.5& 3\\ 0& 0& 1& 1\\ 0& 0& 0& 0\end{array}\right|\begin{array}{c}4.5\\ -4\\ 0\end{array})$$$$\stackrel{r_1-r_2\times 2.5}{\to }\left(\begin{array}{cccc}1& 0& 0& 0.5\\ 0& 0& 1& 1\\ 0& 0& 0& 0\end{array}\right|\begin{array}{c}14.5\\ -4\\ 0\end{array})$$

化为最简形

还原线性方程组

$$\{\begin{array}{rl}{x}_1+0.5x_4& =14.5\\ x_3+x_4& =-4\end{array}$$

解释

所谓的还原线性方程组，即是在行最简形的基础上，将之重新书写为线性方程组的形式，即将行最简形中各位置的系数重新赋予变量，中间的竖线还原为等号。

---

代码模板

// a[N][N]是增广矩阵
int gauss()
{
    int c, r;
    for (c = 0, r = 0; c < n; c ++ )
    {
        int t = r;
        for (int i = r; i < n; i ++ )   // 找到绝对值最大的行
            if (fabs(a[i][c]) > fabs(a[t][c]))
                t = i;

        if (fabs(a[t][c]) < eps) continue;

        for (int i = c; i <= n; i ++ ) swap(a[t][i], a[r][i]);      // 将绝对值最大的行换到最顶端
        for (int i = n; i >= c; i -- ) a[r][i] /= a[r][c];      // 将当前行的首位变成1
        for (int i = r + 1; i < n; i ++ )       // 用当前行将下面所有的列消成0
            if (fabs(a[i][c]) > eps)
                for (int j = n; j >= c; j -- )
                    a[i][j] -= a[r][j] * a[i][c];

        r ++ ;
    }

    if (r < n)
    {
        for (int i = r; i < n; i ++ )
            if (fabs(a[i][n]) > eps)
                return 2; // 无解
        return 1; // 有无穷多组解
    }

    for (int i = n - 1; i >= 0; i -- )
        for (int j = i + 1; j < n; j ++ )
            a[i][n] -= a[i][j] * a[j][n];

    return 0; // 有唯一解
}

参考

[1] 高斯消元 - OI Wiki