所謂高斯消元，就是一種解線性方程組的算法。

學(xué)過線性代數(shù)的同學(xué)都知道，線性方程組本質(zhì)就是一個向量X1左乘一個系數(shù)矩陣A得到另一個向量X2，我們要求解的就是所有未知數(shù)構(gòu)成的向量X1。

設(shè)一個n元一次方程組，我們把所有未知數(shù)的系數(shù)以及等號右邊的常數(shù)在保持相對位置不變的情況下組成一個n行n+1列的矩陣，

a₁₁ a₁₂ a₁₃ ...... a_1n b₁
a₂₁ a₂₂ a₂₃ ...... a_2n b₂
...
...
a_n1 a_n2 a_n3 ...... a_nn b_n

然后我們通過矩陣的初等變換，每個方程選擇一個未知數(shù)的系數(shù)（我們稱為主元），然后把其余方程同一個未知數(shù)的系數(shù)變?yōu)?strong>0，最終將該矩陣的未知數(shù)系數(shù)部分變成每行只有一個非零的數(shù)，每列只有一個非零的數(shù)的鬼畜矩陣，這樣很顯然每個未知數(shù)最終的值都可以直接求出來啦。

當然這里有兩個問題

一是精度誤差。眾所周知浮點數(shù)會有精度誤差的，精度要依題而定。精度過小會導(dǎo)致較小的系數(shù)誤以為0，而精度過大則可能導(dǎo)致本該為0的誤判為不為0，故而精度要有把握，一般在1e-4~1e-10

二是主元的選擇，我們要想辦法避免或者減少精度誤差，我們可以選擇一個方程里系數(shù)最大的那個作為主元，這樣的精度誤差可以減少，因為在浮點數(shù)除法運算時，一個較大的數(shù)除以一個較小的數(shù)的誤差是個玄學(xué)大。

枚舉行，先掃一遍得到該行系數(shù)最大值，再枚舉剩下(n-1)行，然后對每行n個數(shù)進行運算，故而高斯消元的時間復(fù)雜度就是O(n³）

最后這個方程組如果是在模2的意義下的話，也就是說方程未知數(shù)的系數(shù)以及等號右邊的數(shù)不是0就是1的話，我們可以用bitset來加快對每行的運算操作從而時間復(fù)雜度降為而O(n²)。

洛谷P3389——高斯消元法模板題

1 #include <algorithm> 2 #include <cstring> 3 #include <cstdlib> 4 #include <cstdio> 5 #include <iostream> 6 #include <cmath> 7 #include <ctime> 8 #include <queue> 9 #define MIN(a,b) (((a)<(b)?(a):(b))) 10 #define MAX(a,b) (((a)>(b)?(a):(b))) 11 #define ABS(a) (((a)>0?(a):-(a))) 12 #define debug(a) printf("a=%d\n",a) 13 #define OK cout<<"QAQ"<<endl 14 #define fo(i,a,b) for (int i=(a);i<=(b);++i) 15 #define fod(i,a,b) for (int i=(a);i>=(b);--i) 16 #define rep(i,a,b) for (int i=(a);i<(b);++i) 17 #define red(i,a,b) for (int i=(a);i>(b);--i) 18 #define N 106 19 typedef long long LL; 20 using namespace std; 21 int n, w[N]; //w數(shù)組記錄第i行最大系數(shù)的位置 22 double v[N], a[N][N + 1]; //v數(shù)組記錄xi的解,a數(shù)組為相應(yīng)矩陣 23 void readint(int& x) { 24 x = 0; 25 char c; 26 int w = 1; 27 for (c = getchar(); c<'0' || c>'9'; c = getchar()) 28 if (c == '-') w = -1; 29 for (; c >= '0' && c <= '9'; c = getchar()) 30 x = (x << 3) + (x << 1) + c - '0'; 31 x *= w; 32 } 33 void readlong(long long& x) { 34 x = 0; 35 char c; 36 long long w = 1; 37 for (c = getchar(); c<'0' || c>'9'; c = getchar()) 38 if (c == '-') w = -1; 39 for (; c >= '0' && c <= '9'; c = getchar()) 40 x = (x << 3) + (x << 1) + c - '0'; 41 x *= w; 42 } 43 int read() { 44 int x = 0; 45 char c; 46 int w = 1; 47 for (c = getchar(); c<'0' || c>'9'; c = getchar()) 48 if (c == '-') w = -1; 49 for (; c >= '0' && c <= '9'; c = getchar()) 50 x = (x << 3) + (x << 1) + c - '0'; 51 x *= w; 52 return x; 53 } 54 bool gauss() { 55 int p; //p為最大系數(shù)的位置 56 double mx = 0; //mx為最大系數(shù) 57 double eps = 1e-6; //eps為精度控制 58 fo(i, 1, n) { 59 p = 0; 60 mx = 0; 61 fo(j, 1, n) if (fabs(a[i][j]) - eps > mx) { mx = fabs(a[i][j]); p = j; } //fabs函數(shù)是浮點數(shù)的絕對值函數(shù) 62 if (p == 0) return 0; //這個情況下，該行未知數(shù)系數(shù)全為0，若等號右邊的常數(shù)不為0，則該方程組無解，若為0，則有無數(shù)組解 63 fo(j, 1, n) 64 if (i != j) { //枚舉其他行進行運算 65 double qwq = a[j][p] / a[i][p]; //主元選最大的可以在作商時相對地減少精度誤差 66 fo(k, 1, n + 1) a[j][k] -= qwq * a[i][k]; //注意這里是n+1 67 } 68 w[i] = p; 69 } 70 fo(i, 1, n) v[w[i]] = a[i][n + 1] / a[i][w[i]]; 71 return 1; 72 } 73 int main() { // by Lanly 74 readint(n); 75 fo(i, 1, n) fo(j, 1, n + 1) a[i][j] = read(); 76 //fo(i, 1, n) fo(j, 1, n + 1) printf("%.2lf%c", a[i][j], j == n + 1 ? '\n' : ' '); 77 if (gauss()) fo(i, 1, n) printf("%.2lf\n", v[i]); 78 else puts("No Solution"); 79 return 0; 80 } 神奇的代碼

?

轉(zhuǎn)載于:https://www.cnblogs.com/Lanly/p/11560151.html

總結(jié)

以上是生活随笔為你收集整理的高斯消元小小结的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。