首页 > > 程序设计 > C/C++ >

高斯消元--模板，原理

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

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

先看一个式子：

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)*x₁+a_(1,2)*x₂+..............................................+a_(1,n-1)*x_n-1+a_(1,n)*x_n=b₁

a_(2,2)*x₂+..............................................+a_(2,n-1)*x_n-1+a_(2,n)*x_n=b₂

a_(3,3)*x₃+..............................+a_(3,n-1)*x_n-1+a_(3,n)*x_n=b₃

　　　　　　　　　　　　　.....................................................................

　　　　　　　　　　　　　　　　　　　　　　 a_(n,n)*x_n=b_n

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

那么问题来了，怎么求呢？

仔细一看就会发现，实际上，矩阵对角线以下的系数均为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 }