算法基础课 第四讲 数学知识——高斯消元

时间复杂度: $ O(n^3) $

应用

可以用来求解一个包含$ n $个方程$ n $个未知数的线性方程组。
$ a_{1_1} + a_{1_2} + ...... + a_{1_n} = b_1 $
$ a_{2_1} + a_{2_2} + ...... + a_{2_n} = b_2 $
$ ...... $
$ a_{n_1} + a_{n_2} + ...... + a_{n_n} = b_n $
最后解为：
$ x_1 = $
$ x_2 = $
$ .... $
$ x_n = $

解的情况：

1. 唯一解
2. 无解
3. 任意解

原理(核心)

初等行列变换
1. 两方程互换，解不变；
2. 一方程乘以非零数k，解不变；
3. 一方程乘以数k加上另一方程，解不变

变化之后

矩形变成一个上三角矩阵（阶梯性）
1. 恰好是一个完美的阶梯性———有唯一解
2. 出现了$0 = a(a ≠ 0)$,矛盾———无解
3. 出现了很多$0 = 0$的等式———任意解

具体步骤

一.枚举每一列c
1. 找到当前这一列绝对值最大的数的所在行
2. 将该行移到最上面
3. 将该行的第一个数变成1
4. 将下面的所有行的的第C列消成0
二.回过头求出解

具体代码实现

(注意：883. 高斯消元解线性方程组的数据已加强，可能会输出-0.00，需要特判。)

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#pragma GCC optimize(2)

using namespace std;

const int N = 110;
const double eps = 1e-8;

int n;
double a[N][N];

int gauss()  // 高斯消元，答案存于a[i][n]中，0 <= i < n
{
    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; // 有唯一解
}


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

    int t = gauss();
    if (t == 2) puts("No solution");
    else if (t == 1) puts("Infinite group solutions");
    else
    {
        for (int i = 0; i < n; i ++ )
        {
            if (fabs(a[i][n]) < eps) a[i][n] = 0;  // 去掉输出 -0.00 的情况
            printf("%.2lf\n", a[i][n]);
        }
    }

    return 0;
}