高斯消元模板

法1 高斯消元

初始形式：

\[ \begin{cases} x_{1,1} \quad x_{1,2} \quad \dots\quad x_{1,n} \ |\ x_{1,n+1}\\ x_{2,1} \quad x_{2,2} \quad \dots\quad x_{2,n} \ |\ x_{2,n+1}\\ \dots \\ x_{n,1} \quad x_{n,2} \quad \dots\quad x_{n,n} \ |\ x_{n,n+1}\\ \end{cases} \]

结束形式：

\[ \begin{cases} x_{1,1}^{'} \quad x_{1,2}^{'} \quad \dots\quad x_{1,n}^{'} \ |\ x_{1,n+1}^{'}\\ 0 \ \ \ \ \quad x_{2,2}^{'} \quad \dots\quad x_{2,n}^{'} \ |\ x_{2,n+1}^{'}\\ \dots \\ 0 \ \ \ \ \quad 0 \ \ \ \ \quad \dots\quad x_{n,n}^{'} \ |\ x_{n,n+1}^{'}\\ \end{cases} \]

即化为上三角形式

时间复杂度：\(O(n^3)\)

由于最多也只能用double型存储，所以必然会有精度误差。但如果我们每次都选用最大系数的来消掉其他系数，就可以最大程度地来减小误差。

对于无解的判断：某一行前 \(n\) 个数均为 0，最后的结果却不为 \(0\)。
对于无数解的判断：某一行 \(n+1\) 个数均为 \(0\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

void gauss() {
    for(int i=1;i<=n;i++) {
        int now=i;
        for(int j=i+1;j<=n;j++) {
            if(fabs(g[j][i])>fabs(g[now][i])) now=j;
        } swap(g[now],g[i]);
        if(g[i][i]==0) {
            puts("No Solution");
            exit(0);
        }
        for(int j=i+1;j<=n+1;j++) g[i][j]/=g[i][i];
        g[i][i]=1;
        for(int j=i+1;j<=n;j++) {
            for(int k=i+1;k<=n+1;k++) {
                g[j][k]-=g[j][i]*g[i][k];
            }g[j][i]=0;
        }
    }
    //回带操作
    for(int i=n;i>=1;i--) {
        ans[i]=g[i][n+1];
        for(int j=i-1;j>=1;j--) {
            g[j][n+1]-=ans[i]*g[j][i];
        }
    }
}

法2：高斯-约旦消元

初始形式：

\[ \begin{cases} x_{1,1} \quad x_{1,2} \quad \dots\quad x_{1,n} \ |\ x_{1,n+1}\\ x_{2,1} \quad x_{2,2} \quad \dots\quad x_{2,n} \ |\ x_{2,n+1}\\ \dots \\ x_{n,1} \quad x_{n,2} \quad \dots\quad x_{n,n} \ |\ x_{n,n+1}\\ \end{cases} \]

结束形式： \[ \begin{cases} 1\ \ \quad 0 \quad \dots\quad 0 \ \ |\ x_{1,n+1}^{'}\\ 0 \ \ \quad 1 \quad \dots\quad 0\ \ |\ x_{2,n+1}^{'}\\ \dots \\ 0 \ \ \quad 0 \quad \dots\quad 1 \ \ |\ x_{n,n+1}^{'}\\ \end{cases} \]

即化为对角线形式

复杂度：\(O(n^3)\)

缺点：只能判断是否有唯一解，无法判断究竟是无解还是无数解。