Sengxian's Blog

高斯消元法 (Gaussian Elimination)，是线性代数中的一个算法，可用来求解线性方程组。这里介绍一种运用较为普遍的消元方法，高斯约旦消元法。

思路

若有 $n$ 个方程，$n$ 个未知数，其核心思想是使得方程最后变为 $n$ 个等式，即：

这显然很容易做到，我们在中学的时候解方程，就使用过加减消元法。加减消元每次指定一个未知数，然后选定一个该未知数系数不为 $0$ 且之前未选过的方程，用这个方程乘相应的系数去减别的方程，使得有且仅有选定的方程的未知数的系数不为 $0$，$n$ 轮过后，方程自然得出解。

方程解的讨论

上面的过程，描述了一个美好的过程，不错，若有 $n$ 个方程，$n$ 个未知数，要是我们每次都能选定一个未知数，且总有一个且之前未选过的方程使得这个未知数的系数不为 0，那么所有的方程就一定会变成仅包含一个未知数的形式。使用反证法，若有一个方程包含两个未知数，说明要么这个方程两次被选中－这跟我们的思路违背，要么在算法进行过程中根本找不到更多该未知数的系数不为 0 的方程－这也跟我们的思路违背。所以，每次都能选定一个未知数是方程有解的充分必要条件！

方程无解又有几种情况，需要加以区别：

有矛盾方程：

这显然是不对的，如何辨别这个情况呢？我们模拟一下过程，首先消 $x$，用二分之一倍的 1 去减 2：

等等，$0x + 0y = 9$，这显然不合法，不难得出，存在矛盾方程当且仅当有一方程问未知数系数全为 0，但等号右边却不为 0。

有自由变量：自由变量听起来很高端，实际上，就是有重复的方程。

实际上我们只有一个方程，却有两个未知数，得到

这回 $0x + 0y = 0$，不矛盾了，可我们的方程也没解出来，只有 $2x + 4y = 10$，这时我们说，自由变量有 $1$ 个，因为确定任何一个变量，整个方程就解出来了。

代码

//a[i][n] 存放值
bool gauss_jordan(double a[maxn][maxn], int n) {
    for (int i = 0; i < n; ++i) {
        int idx = i; //选择当前未知数系数最大的一个方程，增加数值稳定性
        for (int j = i + 1; j < n; ++j)
            if (fabs(a[j][i]) > fabs(a[idx][i]))
                idx = j;
        if (fabs(a[idx][i]) < 1e-10)
            return false; //无解
        if (idx != i) for (int j = i; j <= n; ++j) swap(a[i][j], a[idx][j]);
        for (int j = 0; j < n; ++j) if(i != j)
            for (int k = n; k >= i; --k) //注意要逆序枚举，防止 a[j][i] 被覆盖
                a[j][k] -= a[i][k] / a[i][i] * a[j][i];
    }
    return true;
}

方程数跟未知数个数不相等

方程数跟未知数个数不相等怎么办？若有 $n$ 个未知数 $m$ 个方程，我们关心无解的情况（排除有解）：

有矛盾方程：只要解完后发现有不等的式子，就是矛盾。
有自由变量：当解完之后，用掉了 $k$ 个方程，说明有 $n - k$ 个自由变量。

证明：我们证明至少有 $n - k$ 个变量可自由取值，在前 $k$ 个方程中，已经被处理的 $k$ 个未知数仅存在与一个方程中，而余下的 $n - k$ 个变量存在与多个方程中，所以将 $n - k$ 个变量自由取值，可以不矛盾的解出 $k$ 个变量，所以至少有 $n - k$ 个变量可自由取值。
我们证明至多有 $n - k$ 个变量可自由取值，先将 $n - k$ 个变量自由取值，不矛盾的解出余下 $k$ 个变量，此时再让一个变量自由取值，那么就可能造成不等式，导致矛盾。所以这个命题被证明是正确的。