710官方网站高斯消元可用于解多元线性方程组,加减消元会轻松一些

明天正规伊始率先篇博客。

至于高斯消元

先看一个姿态:

定义

来自百度健全

数学上,高斯消元法,是线性代数规划中的几个算法,可用来为线性方程组求解。但其算法12分复杂,不常用于加减消元法,求出矩阵的秩,以及求出可逆方阵的逆矩阵。可是,若是有过百万条等式时,那些算法会10分节约财富。一些庞然大物的方程组常常会用迭代法以及花式消元来缓和。当用于二个矩阵时,高斯消元法会发生出一个“行梯阵式”。高斯消元法能够用在Computer中来减轻数千条等式及未知数。亦有局地措施特地用来解决一部分有尤其排列的周密的方程组。

没啥用

x+y+z=5

适用范围

高斯消元的时日复杂度是O,一般数量范围在十0左右。

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

2*x+3*y+z=11

具体方法

高斯消元能够作为模拟解方程的历程,就像是小学生那样,最后要削的每四个未知数只在三个姿势里冒出,就能够得出个中壹项的解,回代得出全体解。

在2个架子里,用这几个姿势的x消去别的姿势里的x,然后在余下的四个姿态里再选拔1个架子里的y,用这一个y消去最终剩余的架子里的y。那么今后最后二个方程里就唯有三个未知数z了。若是z的周到是一,那么我们就足以向来得出答案来了。

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

x+4*y+z=11

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 > abs(a[det][x])) det = i;    }    if 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;        if(fabs <= eps) {            puts("No Solution");            exit(0);        }        for(int j = i+1;j <= n;j++) {            if(fabs > 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;}

设若问人怎么解,人家鲜明会报告你,消元啦~

实在消元有二种:加减消元和带入消元

在计算机上编程落成的话,加减消元会简单一些。

如此就有了作者们的高斯消元法。

高斯消元便是有多少个加减消元构成的,可以解出线性方程组,时间复杂度为o(n*n*n)(依旧挺大的)。

互连网有个别大佬们讲怎么行列式,什么矩阵上三角,实在是为难知晓,小编就硬着头皮用最简洁明了的语言来解释。

现行反革命就起来说讲操作吧。

我们应该驾驭,大家解方程的结尾想要的结果正是要有二个那样的花样:a*x=y

不过大家却不或许对于每几个未知数举行消元,倘若那样,时间复杂度就太高了。那么如何是好呢?

咱俩只要组织出了另2个线性方程组(特殊的):

a(1,1)*x1+a(1,2)*x2+……………………………………….+a(1,n-1)*xn-1+a(1,n)*xn=b1

                  a(2,2)*x2+……………………………………….+a(2,n-1)*710官方网站,xn-1+a(2,n)*xn=b2 

                                     
a(3,3)*x3+…………………………+a(3,n-1)*xn-1+a(3,n)*xn=b3

             ……………………………………………………………

              
 ……………………………………………………………

                   
                                  
a(n,n)*xn=bn

作者们就能够从下往上,依次递推求出未知数。

这正是说难题来了,怎么求呢?

周到1看就能够意识,实际上,矩阵对角线以下的周详均为0。

故此大家得以如此来布局:

先是for循环,i=1~n。

历次搜寻3个a[k][i]不为0的k行;(小心:必须不为0),然后与i行交换。

然后将那一行与下部的(n-i+一)行实行加减消元,将每一行的那1项都消成0。

举个例子发现周全都为0,则有自由元,解不唯1。

何以最后开掘最后的行有周详全为0但和不为0的,则无解。

诸如此类就足以把它构造出来了!!

剩下的笔者就毫无多说了吗。

上面笔者以洛谷P338九为例,贴1份模板代码:

 

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<cmath>
 6 using namespace std;
 7 int n,m;
 8 double a[110][110];
 9 int main()
10 {
11     cin>>n;
12     for(int i=1;i<=n;i++)
13       for(int j=1;j<=n+1;j++)  cin>>a[i][j];
14     for(int i=1;i<=n;i++)
15       for(int j=1;j<=n+1;j++)  a[i][j]*=1.000;
16     for(int i=1;i<=n;i++)
17     {
18         int now=i;
19         for(int j=i+1;j<=n;j++)
20           if(fabs(a[now][i])<fabs(a[j][i]))    now=j;//找到一行绝对值最大的(这样可以在double中减小误差)
21         for(int j=i;j<=n+1;j++)  
22            swap(a[now][j],a[i][j]);//交换
23         if(a[i][i]==0)//代表有多组解,最大值为0即都为0
24         {
25             cout<<"No Solution"<<endl;
26             return 0;
27         }
28         for(int j=i+1;j<=n+1;j++)  a[i][j]/=a[i][i];//把它除掉,好消元
29         a[i][i]=1;
30         for(int j=i+1;j<=n;j++)
31         {
32             for(int k=i;k<=n+1;k++)  a[j][k]-=a[i][k]*a[j][i];//消元
33         }
34     }
35     for(int i=n;i>=1;i--)//回代过程
36     {
37         for(int j=i+1;j<=n;j++)
38         {
39             a[i][n+1]-=a[i][j]*a[j][n+1];
40             a[i][j]=0;
41         }
42         a[i][n+1]/=a[i][i];
43         a[i][i]=1;
44     }
45     for(int i=1;i<=n;i++)  printf("%.2f\n",a[i][n+1]);输出答案
46     return 0;
47 }

 

这么就讲完了模版啦~。

谢谢我们辅助。

何以得以提议本身有哪些写得不得了的地点,本身谢谢不尽!!

模板题:https://www.luogu.org/problemnew/show/P3389

 

相关文章