数学知识之高斯消元

$问题$

$输入一个包含 n 个方程 n 个未知数的线性方程组。$

$方程组中的系数为实数。$

$求解这个方程组。$

$ \left\{ \begin{aligned} a_{11} x_1 + a_{12} x_2 + … + a_{1n} x_n = & b_1 \\ a_{21} x_1 + a_{22} x_2 + … + a_{2n} x_n = & b_2 \\ .......................\\ a_{n1} x_1 + a_{n2} x_2 + … + a_{nn} x_n = & b_n \\ \end{aligned} \right. $

可以将方程写成矩阵的形式

$ \left[ \begin{matrix} a_{11} & \cdots & a_{1n} & b_1 \\ a_{21} & \cdots & a_{2n} & b_2 \\ \vdots & \vdots & \vdots & \vdots \\ a_{n1} & \cdots & a_{nn} & b_n \\ \end{matrix} \right] $

等价变换

• 交换矩阵的两行,方程不变
• 将一行中的所有元素乘上一个相同的数,方程不变
• 将一行的元素与另一行相加,方程不变

将矩阵通过等价变换变成上三角的形式

$ \left[ \begin{matrix} a_{1,1} & \cdots & a_{2,n-1}& a_{1,n} & b_1 \\ 0 & \cdots & a_{2,n-1} &a_{2,n} & b_2 \\ \vdots & \vdots & \vdots & \vdots & \vdots \\ 0 & \cdots & 0 & a_{n,n} & b_n \\ \end{matrix} \right] $

$1.扫描每一列c$

$Code$

int t = r;
for (int i = r; i <= n; i ++ )
    if (abs(a[i][c]) > abs(a[t][c]))
        t = i;

$2.找到这一列中绝对值最大的数所对应的一行,通过等价变换1,把这一行换到第c行$

$Code$

for (int i = c; i <= n + 1; i ++ )
    swap(a[t][i], a[r][i]);

$3.通过等价变换2,把这一行的第c个数变成1$

$Code$

for (int i = n + 1; i >= c; i -- )
    a[r][i] /= a[r][c];

$4.通过等价变换3,把第c \sim n行的第c个数变成0$

$Code$

for (int i = r + 1; i <= n; i ++ )
    if (abs(a[i][c]) > eps)
        for (int j = n + 1; j >= c; j -- )
            a[i][j] -= a[r][j] * a[i][c] / a[r][c];

求解方程

• 从下往上解每一个等式
• 解一个等式时,只有一个未知数

$Code$

for (int i = n; i >= 1; i -- )
{
    for (int j = i + 1; j <= n; j ++ )
        a[i][n + 1] -= a[i][j] * a[j][n + 1];//求出第i个数的值
    if (abs(a[i][i]) < eps)
    {
        if (abs(a[i][n + 1]) < eps)return 1;// 0 = 0,有无穷个解
        return 2;//0 = k,无解
    }
    if (abs(a[i][n + 1]) < eps)a[i][n + 1] = 0;
}

return 0;//有且仅有一个解

$高斯消元模版$

#include <iostream>

using namespace std;

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

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

int guass()
{
    int r = 1;
    for (int c = 1; c <= n; c ++ )
    {
        int t = r;
        for (int i = r; i <= n; i ++ )
            if (abs(a[i][c]) > abs(a[t][c]))
                t = i;

        if (abs(a[t][c]) < eps)continue;

        for (int i = c; i <= n + 1; i ++ )
            swap(a[t][i], a[r][i]);

        for (int i = n + 1; i >= c; i -- )
            a[r][i] /= a[r][c];

        for (int i = r + 1; i <= n; i ++ )
            if (abs(a[i][c]) > eps)
                for (int j = n + 1; j >= c; j -- )
                    a[i][j] -= a[r][j] * a[i][c];

        r ++ ;
    }

    for (int i = n; i >= 1; i -- )
    {
        for (int j = i + 1; j <= n; j ++ )
            a[i][n + 1] -= a[i][j] * a[j][n + 1];
        if (abs(a[i][i]) < eps)
        {
            if (abs(a[i][n + 1]) < eps)return 1;
            return 2;
        }
        if (abs(a[i][n + 1]) < eps)a[i][n + 1] = 0;
    }

    return 0;
}

int main() 
{
    cin >> n;

    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n + 1; j ++ )
            cin >> a[i][j];

    int t = guass();

    if (t == 1)puts("Infinite group solutions");
    else if (t == 2)puts("No solution");
    else
    {
        for (int i = 1; i <= n; i ++ )
            printf("%.2lf\n", a[i][n + 1]);
    }


    return 0;
}