高斯消元 | Codeboy's Blog

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

消元法理论的核心

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

两方程互换，解不变；
一方程乘以非零数 $k$ ，解不变；
一方程乘以数 $k$ 加上另一方程，解不变。

对于方程组

\left\{ \begin{array}{} &a_{11}x_1+&a_{12}x_2+\ldots+&a_{1n}x_n=&b_1 \\ &a_{21}x_1+&a_{22}x_2+\ldots+&a_{2n}x_n=&b_2 \\ &\vdots &\vdots &\vdots&\vdots \\ &a_{n1}x_1+&a_{n2}x_2+\ldots+&a_{nn}x_n=&b_n \\ \end{array} \right.

增广矩阵为

\begin{pmatrix} a_{11} & a_{12} & \cdots &a_{1n} & b_1 \\ a_{21} & a_{22} & \cdots &a_{2n} & b_2 \\ \vdots & \vdots & \vdots & \vdots& \vdots \\ a_{n1} & a_{n2} & \cdots &a_{nn} & b_n \\ \end{pmatrix}

初等行（列）变换

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

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

\begin{pmatrix} a_{11} & a_{12} & \cdots &a_{1n} & b_1 \\ &a_{2i}&a_{2(i+1)}&a_{2n} & b_2 \\ &&&\vdots& \vdots \\ &&&a_{nn} & b_n \\ \end{pmatrix}

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

解的个数

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

算法步骤

枚举每一列 $c$ ，

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

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

\left\{\begin{aligned} 2x_1+5x_3+6x_4&=9 \notag \\ x_3+x_4&=-4 \notag \\ 2x_3+2x_4&=-8 \notag \end{aligned}\right.

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

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

\left(\begin{matrix} 2 & 0 & 5 & 6 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 2 & 2 \end{matrix} \middle| \begin{matrix} 9 \\ -4 \\ -8 \end{matrix} \right)

\xrightarrow{r_3-2r_2} \left(\begin{matrix} 2 & 0 & 5 & 6 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 \end{matrix} \middle| \begin{matrix} 9 \\ -4 \\ 0 \end{matrix} \right)

化为行阶梯形

\xrightarrow{\frac{r_1}{2}} \left(\begin{matrix} 1 & 0 & 2.5 & 3 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 \end{matrix} \middle| \begin{matrix} 4.5 \\ -4 \\ 0 \end{matrix} \right)

\xrightarrow{r_1-r_2 \times 2.5} \left(\begin{matrix} 1 & 0 & 0 & 0.5 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 \end{matrix} \middle| \begin{matrix} 14.5 \\ -4 \\ 0 \end{matrix} \right)

化为最简形

还原线性方程组

\left\{\begin{aligned} x_1+0.5x_4 &= 14.5 \notag\\ x_3+x_4 &= -4 \notag \\ \end{aligned}\right.

解释

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

代码模板

cpp

// 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

消元法理论的核心 ​

初等行（列）变换 ​

解的个数 ​

算法步骤 ​

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

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

化为行阶梯形 ​

化为最简形 ​

还原线性方程组 ​

代码模板 ​

参考 ​

讨论