前言

学了才发现这玩意贼简单虽然据说是复习。

直接来

高斯消元用于解一个线性方程组，就是：
$$\{\begin{array}{l}{a}_{1,1}\cdot x_1+a_{1,2}\cdot x_2+\cdots +a_{1,n}\cdot x_n=a_{1,n+1}\\ a_{2,1}\cdot x_1+a_{2,2}\cdot x_2+\cdots +a_{2,n}\cdot x_n=a_{2,n+1}\\ \cdots \\ a_{n,1}\cdot x_1+a_{n,2}\cdot x_2+\cdots +a_{n,n}\cdot x_n=a_{n,n+1}\end{array}$$（其中$a$是已知量）

我们接下来都用系数表达式（注意所有的$a_{i,n+1}$与其他$a$的含义有不同，但我们将它们放在一起）：
$$\begin{array}{ccccccc}{a}_{1,1}& a_{1,2}& a_{1,3}& \cdots & a_{1,n-1}& a_{1,n}& a_{1,n+1}\\ a_{2,1}& a_{2,2}& a_{2,3}& \cdots & a_{2,n-1}& a_{2,n}& a_{2,n+1}\\ a_{3,1}& a_{3,2}& a_{3,3}& \cdots & a_{3,n-1}& a_{3,n}& a_{3,n+1}\\ & & & \cdots & & & \\ a_{n,1}& a_{n,2}& a_{n,3}& \cdots & a_{n,n-1}& a_{n,n}& a_{n,n+1}\end{array}$$

高斯消元的目的是把原方程变成这样：
$$\begin{array}{ccccccc}1& {a_{1,2}}^{\prime }& {a_{1,3}}^{\prime }& \cdots & {a_{1,n-1}}^{\prime }& {a_{1,n}}^{\prime }& {a_{1,n+1}}^{\prime }\\ 0& 1& {a_{2,3}}^{\prime }& \cdots & {a_{2,n-1}}^{\prime }& {a_{2,n}}^{\prime }& {a_{2,n+1}}^{\prime }\\ 0& 0& 1& \cdots & {a_{3,n-1}}^{\prime }& {a_{3,n}}^{\prime }& {a_{3,n+1}}^{\prime }\\ & & & \cdots & & & \\ 0& 0& 0& \cdots & 0& 1& {a_{n,n+1}}^{\prime }\end{array}$$

那么从下往上依次回代，就能得到所有的$x$值了，代码如下：

for(int i = N; i >= 1; i--) {
    Ans[i] = A[i][N + 1];
    for(int j = N; j >= i + 1; j--)
        Ans[i] -= Ans[j] * A[i][j];
}

所以我们枚举$i$：将$a_{i,i}$变为$1$（①），然后把$a_{j,i}(j>i)$全部变成$0$（②）。

• 对于①操作，非常简单，把第$i$行的系数全部除以$a_{i,i}$即可；
• 对于②操作，你要根据加减消元法，用第$i$行的系数去把$a_{j,i}(i+1\le j\le n)$消为$0$，其他不管。那就给把$a_{i,i}$变成$a_{j,i}$（$i$行其他系数按等式的性质依次变），再将第$j$行的每个系数$a_{j,k}$减掉$a_{i,k}$。即：第$j$行的每个系数$a_{j,k}$都减去$\frac{a_{j,i}}{a_{i,i}}\cdot a_{i,k}=a_{j,i}\cdot a_{i,k}$。

以上就是高斯消元的过程，自己照着代码打一遍，模拟一下过程就能够很好地理解了。

还有一个细节，我们每次在操作①和操作②之前把$\underset{j=i}{\overset{n}{\max }}{a}_{j,i}$所在的那行跟第$i$行换一个位置，可以减少精度误差。

还有一个细节，判断无解：若当前$a_{i,i}=0$，那么高斯消元就无法继续了（操作②无法进行），且$x_i$也不能确定，输出No Solution（但并不一定无解）。

代码

洛谷 P3389【模板】高斯消元法

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>

int Read() {
    int x = 0;
    char c = getchar();
    while (c < '0' || c > '9')
        c = getchar();
    while (c >= '0' && c <= '9')
        x = x * 10 + (c ^ 48), c = getchar();
    return x;
}

const double eps = 1e-7;

inline double Abs(const double &x) {
    return x < 0 ? -x : x;
}

inline int Comp(const double &x,const double &y) {
    if (Abs(x-y) < eps)
        return 0;
    return Abs(x) > Abs(y) ? 1 : -1;
}

const int MAXN = 100;

int N;
double A[MAXN + 5][MAXN + 5], Ans[MAXN + 5];

int main() {
    N = Read();
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N + 1; j++)
            scanf("%lf", &A[i][j]);
    for(int i = 1; i <= N; i++) {
        int pos = i;
        for(int j = i + 1; j<= N; j++)
            if(Comp(A[j][i], A[pos][i]) == 1)
                pos = j;
        // 这里找A[j][i]最大的是为了减少精度误差 与算法正确性无关
        if(Comp(A[pos][i], 0) == 0) {
            puts("No Solution");
            return 0;
        }
        for(int j = 1; j <= N + 1; j++)
            std::swap(A[pos][j], A[i][j]);
        // 把A[j][i]最大的那行换上去
        double tmp = A[i][i];
        for(int j = i; j <= N + 1; j++)
            A[i][j] /= tmp;
        // 操作一
        for(int j = i + 1; j <= N; j++){
            tmp = A[j][i];
            for(int k = i; k <= N + 1; k++)
                A[j][k] -= A[i][k] * tmp;
        }
        // 操作二
    }
    for(int i = N; i >= 1; i--) {
        Ans[i] = A[i][N + 1];
        for(int j = N; j >= i + 1; j--)
            Ans[i] -= Ans[j] * A[i][j];
    }
    for(int i = 1; i <= N; i++)
        printf("%.2f\n", Ans[i]);
    return 0;
}