详解高斯消元

· · 算法·理论

详解高斯消元

\color {red} 好东西，可以求所有一次方程组的解。

前置知识

一般消元法的公理：

增广矩阵：

由一个矩阵A和一个常数列B组成的矩阵称为增广矩阵。

通常为一下格式：

\left ( \begin{matrix} A_{11}\dots A_{N1} \\ A_{21}\dots A_{N2} \\ \vdots\space\space\space\space\ddots\space\space\space\space\space\space \\ A_{N1}\dots A_{NN} \end{matrix} \middle| \begin{matrix} sum_1 \\ sum_2 \\ \vdots \\ sum_N \end{matrix} \right )

高斯消元的目标矩阵

即上三角矩阵：

\left ( \begin{matrix} \dots\space\space\space\space\space\space\space\space\space\space\space\space\\ 0\dots\space\space\space\space\space\space\space\space\space\space\\ 0\space 0\dots\space\space\space\space\space\space\space\\ \ddots\space\space\space\space\space\space\space\space\space\space\\ 0\space 0 \space 0\dots w \end{matrix} \middle| \begin{matrix} sum_1 \\ sum_2 \\ \vdots \\ sum_N \end{matrix} \right )

基本步骤

1.转化

把方程组转化为一下格式：

\begin{cases} A_{11}\times x_1 + A_{12}\times x_2 + \dots + A_{1N}\times x_N= sum_1 \\ A_{12}\times x_1 + A_{22}\times x_2 + \dots + A_{2N}\times x_N= sum_2 \\ \space\space\space\space\space\space\space\space\space\space\space\space\space\space\vdots \\ A_{N1}\times x_1 + A_{N2}\times x_2 + \dots + A_{1N}\times x_N= sum_N \\ \end{cases}

2.把系数写成增广矩阵

依据：

3.行变换消元

第i次消元选定第i行i列的元素为主元。

如果主元为0，那么就交换下一行，直到他遇到一个不为0的元素为止，如果全是0的话，就直接跳过。

然后，将第i\backsim n行的元素乘上lcm(a_i,a_{i+1}\dots a_n)。

再将第i+1\backsim n行都减去第i行，就完成了第i列的消元。

4.回带

傻子都会。

CODE

#include <cmath>
#include <cstdio>
#include <utility>

using namespace std;

const long double eps = 0.0000000000001L;

long double mat[101][102];

bool isZero(long double x)
{
    return fabs(x) < eps;
}

bool solve(int n)
{
    for (int i = 1; i <= n; i++)
    {
        int notZero = i;
        for (int j = i; j <= n; j++)
        {
            if (!isZero(mat[j][i]))
            {
                notZero = j;
                break;
            }
        }
        if (notZero != i)
        {
            swap(mat[i], mat[notZero]);
        }
        if (isZero(mat[i][i]))
        {
            return false;
        }
        for (int j = i + 1; j <= n + 1; j++)
        {
            mat[i][j] /= mat[i][i];
        }
        for (int j = i + 1; j <= n; j++)
        {
            for (int k = i + 1; k <= n + 1; k++)
            {
                mat[j][k] -= mat[j][i] * mat[i][k];
            }
        }
    }
    for (int i = n - 1; i >= 1; i--)
    {
        for (int j = i + 1; j <= n; j++)
        {
            mat[i][n + 1] -= mat[i][j] * mat[j][n + 1];
        }
    }
    return true;
}

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n + 1; j++)
        {
            scanf("%Lf", &mat[i][j]);
        }
    }
    if (solve(n))
    {
        for (int i = 1; i <= n; i++)
        {
            printf("%.2Lf\n", mat[i][n + 1]);
        }
    }
    else
    {
        puts("No Solution");
    }
    return 0;
}

完结撒花！！🎉🎉🎉