高斯消元--模板,原理

2018-06-17 21:24:51来源:未知 阅读 ()

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

现在正式开始第一篇博客。

先看一个式子:

x+y+z=5

2*x+3*y+z=11

x+4*y+z=11

如果问人怎么解,人家肯定会告诉你,消元啦~

实际上消元有两种:加减消元和带入消元

在电脑上编程实现的话,加减消元会简单一些。

这样就有了我们的高斯消元法。

高斯消元就是有多个加减消元构成的,能够解出线性方程组,时间复杂度为o(n*n*n)(还是挺大的)。

网上有些大佬们讲什么行列式,什么矩阵上三角,实在是难以理解,我就尽量用最简洁明了的语言来解释。

现在就开始讲讲操作吧。

大家应该知道,我们解方程的最终想要的结果就是要有一个这样的形式:a*x=y

但是我们却无法对于每一个未知数进行消元,如果那样,时间复杂度就太高了。那么怎么办呢?

我们如果构造出了另一个线性方程组(特殊的):

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)*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

我们就可以从下往上,依次递推求出未知数。

那么问题来了,怎么求呢?

仔细一看就会发现,实际上,矩阵对角线以下的系数均为0。

所以我们可以这样来构造:

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

每次寻找一个a[k][i]不为0的k行;(注意:必须不为0),然后与i行交换。

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

如果发现系数都为0,则有自由元,解不唯一。

如何最后发现最后的行有系数全为0但和不为0的,则无解。

这样就可以把它构造出来了!!

剩下的我就不用多说了吧。

下面我以洛谷P3389为例,贴一份模板代码:

 

 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

 

标签:

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

上一篇:动态绑定与静态绑定

下一篇:苹果和虫子问题C++