高斯消元

plafle · 2020-11-14 20:08:48 · 个人记录

高斯消元

高斯消元适用于求解线性方程组。

一般的，对于线性方程组：

a_{1,1}x_1 + a_{1,2}x_2 + a_{1,3}x_3 + ……a_{1,n}x_n = b_1\\ a_{2,1}x_1 + a_{2,2}x_2 + a_{2,3}x_3 + ……a_{2,n}x_n = b_2\\ ……\\ a_{n,1}x_1 + a_{n,2}x_2 + a_{n,3}x_3 + ……a_{n,n}x_n = b_n\\

我们用下面这个矩阵来表示这个线性方程组：

\left \{ \begin{array}{ccccc|c} a_{1,1} & a_{1,2} & a_{1,3} & \cdots & a_{1,n}&b_1\\ a_{2,1} & a_{2,2} & a_{2,3} & \cdots & a_{2,n}&b_2\\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots\\ a_{n,1} & a_{n,2} & a_{n,3} & \cdots & a_{n,n}&b_n\\ \end{array} \right \}

我们循环一个变量i（从1到n）

先在矩阵中找到一行（设这行是第x行），使得a_{x,1},a_{x,2},……,a_{x,i-1}都为0，但a_{x,i} = 0。

然后用这一行矩阵，用简单行变换的方式将矩阵其他行的第i项的系数消为0。

最后我们就得到一个“阶梯矩阵”，然后就可以愉快地求解了。

Code

#include<iostream>
#include<cstdio>
#include<cmath>

using namespace std;

const int maxn = 1e3 + 5;
double a[maxn][maxn],b[maxn];
int n;

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

    for (int i=1; i<=n; i++) {
        for (int j=i; j<=n; j++)
            if (fabs(a[j][i]) > 1e-10) {
                for (int k=1; k<=n; k++)
                    swap(a[i][k],a[j][k]);
                swap(b[i],b[j]);
                break;
            }
        for (int j=1; j<=n; j++) {
            if (j == i)
                continue;
            double rate = a[j][i] / a[i][i];
            for (int k=1; k<=n; k++)
                a[j][k] -= rate * a[i][k];
            b[j] -= rate * b[i];
        }
    }
    for (int i=1; i<=n; i++) 
        printf("x%d = %.2lf\n",i,b[i] / a[i][i]);

    return 0;
}