高斯消元--模板，原理

現在正式開始第一篇博客。

先看一個式子：

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 }

這樣就講完了模板啦～。

謝謝大家支持。

如何可以指出我有哪些寫得不好的地方，本人感激不盡！！

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