[科技点] 高斯消元

· · 题解

对于方程

\begin{cases} a_{1,1}x_1 + a_{1,2}x_2 + a_{1,3}x_3 = b_1 \\ a_{2,1}x_1 + a_{2,2}x_2 + a_{2,3}x_3 = b_2 \\ a_{3,1}x_1 + a_{3,2}x_2 + a_{3,3}x_3 = b_3\end{cases}

可以通过高斯消元求解。

其实如果手解这个方程还是很简单的，但是程序并不会手解，所以就得用通用方法来解这种方程。先看样例：

\begin{cases} 1x_1 + 3x_2 + 4x_3 = 5 \\ 1x_1 + 4x_2 + 7x_3 = 3 \\ 9x_1 + 3x_2 + 2x_3 = 2\end{cases}

首先转化成矩阵

\begin{bmatrix} 1 & 3 & 4 & 5 \\ 1 & 4 & 7 & 3 \\ 9 & 3 & 2 & 2\end{bmatrix}

然后从小到大枚举列，先到第一列，找到这一列最大的系数 9，把 9 所在的那一列换到第一列。

\begin{bmatrix} 9 & 3 & 2 & 2 \\ 1 & 4 & 7 & 3 \\ 1 & 3 & 4 & 5\end{bmatrix}

然后进行方程之间的加减，根据系数获得一个比值，让第 i 项刚好可以消到 0 比如此时第二行的第一项可以由第一列 * 1/9 然后相间得出，所以令 t = (第二行系数）/ (第一行系数) = 1/9 ,然后把第二列的每一项都减去[第一列的每一项乘上比值]，所以此时第二列的第一项的系数就消到 0 了。

\begin{bmatrix} 9 & 3 & 2 & 2 \\ 1 - 1 / 9 * 9 & 4 - 1 / 9 * 3 & 7 - 1 / 9 * 2 & 3 - 1 / 9 * 2 \\ 1 - 1 / 9 * 9 & 3 - 1 / 9 * 3 & 4 - 1 / 9 * 2 & 5 - 1 / 9 * 2\end{bmatrix} =\begin{bmatrix} 9 & 3 & 2 & 2 \\ 0 & 11 / 4 & 61 / 9 & 7 / 9 \\ 0 & 0 & 34 / 9 & 43 / 9\end{bmatrix}

然后接着继续下去，依次消去第二项的系数，第三项的系数，就最后可以得到一个之和一个 x 有关的方程，和常数项相除得出解。

要注意寻找最大系数的那一步只能从没做过的行中来选，不然会打乱最后的答案矩阵，这就不好了。但是进行相减消元的时候还是得减到处理过的行里去，这样可以消去方里还不为零的系数，主要是能对常数项做出贡献，最后得出答案。

关于无解：只要一列还没有做过的出现了全 0 的系数，显然这个对应的 x 不是无解就是自由元，自由元琉璃酱现在还不会，所以也一起当成无解就行。

P3389 【模板】高斯消元法

#include <bits/stdc++.h>
using namespace std;
#define esp 1e-15
int n;
double a[107][107];

void Gauss() {
    for (int i = 1; i <= n; ++i) {
        int p = i;
        for (int j = i + 1; j <= n; ++j) 
            if (fabs(a[j][i]) > fabs(a[j][p]))
                p = j;
        if (-esp < a[i][i] && a[i][i] < esp) {
            puts("No Solution");
            return ;
        }
        for (int j = 1; j <= n + 1; ++j)
            swap(a[i][j], a[p][j]);
        for (int j = 1; j <= n; ++j) {
            if (i == j) continue;
            double t = a[j][i] / a[i][i];
            for (int k = i; k <= n + 1; ++k)
                a[j][k] -= a[i][k] * t;
        }
    }
    for (int i = 1; i <= n; ++i)
        printf("%.2f\n", a[i][n + 1] / a[i][i]);
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) 
        for (int j = 1; j <= n + 1; ++j)
            scanf("%lf", &a[i][j]);
    Gauss();
    return 0;
}