关于高斯消元

2018-10-19 06:11:27来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

关于高斯消元

定义

来自百度百科

数学上,高斯消元法(或译:高斯消去法),是线性代数规划中的一个算法,可用来为线性方程组求解。但其算法十分复杂,不常用于加减消元法,求出矩阵的秩,以及求出可逆方阵的逆矩阵。不过,如果有过百万条等式时,这个算法会十分省时。一些极大的方程组通常会用迭代法以及花式消元来解决。当用于一个矩阵时,高斯消元法会产生出一个“行梯阵式”。高斯消元法可以用在电脑中来解决数千条等式及未知数。亦有一些方法特地用来解决一些有特别排列的系数的方程组。

没啥用

适用范围

高斯消元的时间复杂度是O(n3),一般数据范围在100左右。

高斯消元可用于解多元线性方程组。

具体方法

高斯消元可以看作模拟解方程的过程,就像小学生那样,最终要削的每一个未知数只在一个式子里出现,就可以得出其中一项的解,回代得出全部解。

在一个式子里,用这个式子的x消去其他式子里的x,然后在剩下的两个式子里再选择一个式子里的y,用这个y消去最后剩下的式子里的y。那么现在最后一个方程里就只有一个未知数z了。倘若z的系数是1,那么我们就可以直接得出答案来了。

(摘自luogu高斯消元模板的题解)

Code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath> 
using namespace std;

const int MAXN = 100 + 5;
const double eps = 0.00001;

int n;
double a[MAXN][MAXN];
double ans[MAXN];

inline void swap_judge(int x) {
    int det = x;
    for(int i = x+1;i <= n;i++) {
        if(abs(a[i][x]) > abs(a[det][x])) det = i;
    }
    if(det == x) return;
    for(int i = x;i <= n+1;i++) {
        swap(a[x][i],a[det][i]);
    }
    return;
}

inline void Gauss() {
    double tmp;
    for(int i = 1;i <= n;i++) {
        swap_judge(i);
        if(fabs(a[i][i]) <= eps) {
            puts("No Solution");
            exit(0);
        }
        for(int j = i+1;j <= n;j++) {
            if(fabs(a[j][i]) > eps) {
                tmp = a[i][i] / a[j][i];
                for(int k = i;k <= n+1;k++) {
                    a[j][k] = a[j][k] * tmp - a[i][k];
                }
            }
        }
    }
    for(int i = n;i;i--) {
        for(int j = i+1;j <= n;j++) {
            a[i][n+1] -= a[i][j] * a[j][n+1];
        }
        a[i][n+1] /= a[i][i];
    }
    return;
}

int main() {
    scanf("%d",&n);
    for(int i = 1;i <= n;i++) {
        for(int j = 1;j <= n + 1;j++) {
            scanf("%lf",&a[i][j]);
        }
    }
    Gauss();
    for(int i = 1;i <= n;i++) {
        printf("%.2lf\n",a[i][n+1]);
    }
    return 0;
}

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:2018-10-15 00:41:45 c language

下一篇:C++基础 C++对类的管理——封装