高斯消元专题
高斯消元法可用來找出下列方程組的解或其解的限制：
這個算法的原理是：
首先，要將L1以下的等式中的x消除，然后再將L2以下的等式中的y消除。這樣可使整個方程組變成一個三角形似的格式。之后再將已得出的答案一個個地代入已被簡化的等式中的未知數(shù)中，就可求出其余的答案了。
第二步，就是由尾至頭地將已知的答案代入其他等式中的未知數(shù)。第一個答案就是：
然后就可以將z代入L2中，立即就可得出第二個答案：
之后，將z和y代入L1之中，最后一個答案就出來了：
就是這樣，這個方程組就被高斯消元法解決了
下面是n元線性方程組的一般形式：
我們可以把它表示為增廣矩陣的形式：
然后就可以用高斯消元法在計算機上求解方程組了
對于剛才的例子，我們把它寫成增廣矩陣的形式：
跟著以上的方法來運算，這個矩陣可以轉(zhuǎn)變?yōu)橐韵碌臉幼?#xff1a;
這矩陣叫做“行梯陣式”。
最后，可以利用同樣的算法產(chǎn)生以下的矩陣，便可把所得出的解或其限制簡明地表示出來：
最后這矩陣叫做“簡化行梯陣式”，亦是高斯－約當消元法指定的步驟。
自由變元（有效的方程個數(shù)-變量數(shù)）：
例子：x+y+z=1，這個方程是有無數(shù)解的，但是自由變元只有兩個，但是每個變量都是無法確定的，只有當把兩個自由變元的值確定了，這個方程便有了唯一解。
模板講解：
普通版
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 | constint MAXN=50; int a[MAXN][MAXN];//增廣矩陣 int x[MAXN];//解集 boolfree_x[MAXN];//標記是否是不確定的變元 inlineintgcd(inta,int b) { ????int t; ????while(b!=0) { ????????t=b; ????????b=a%b; ????????a=t; ????} ????return a; } inlineint lcm(inta,int b) { ????return a/gcd(a,b)*b;//先除后乘防溢出 } ?// 高斯消元法解方程組(Gauss-Jordan elimination).(-2表示有浮點數(shù)解，但無整數(shù)解， //-1表示無解，0表示唯一解，大于0表示無窮解，并返回自由變元的個數(shù)) //有equ個方程，var個變元。增廣矩陣行數(shù)為equ,分別為0到equ-1,列數(shù)為var+1,分別為0到var. int Gauss(intequ,intvar) { ????inti,j,k; ????intmax_r;// 當前這列絕對值最大的行. ??? int col;//當前處理的列 ??? intta,tb; ????int LCM; ????int temp; ????intfree_x_num; ????intfree_index; ????for(inti=0; i<=var; i++) { ????????x[i]=0; ????????free_x[i]=true; ????} ????//轉(zhuǎn)換為階梯陣. ??? col=0; // 當前處理的列 ??? for(k = 0; k <equ&& col <var; k++,col++) { ????????// 枚舉當前處理的行. // 找到該col列元素絕對值最大的那行與第k行交換.(為了在除法時減小誤差) ??????? max_r=k; ????????for(i=k+1; i<equ; i++) { ????????????if(abs(a[i][col])>abs(a[max_r][col])) max_r=i; ????????} ????????if(max_r!=k) { ????????????// 與第k行交換. ??????????? for(j=k; j<var+1; j++) swap(a[k][j],a[max_r][j]); ????????} ????????if(a[k][col]==0) { ????????????// 說明該col列第k行以下全是0了，則處理當前行的下一列. ??????????? k--; ????????????continue; ????????} ????????for(i=k+1; i<equ; i++) { ????????????// 枚舉要刪去的行. ??????????? if(a[i][col]!=0) { ????????????????LCM = lcm(abs(a[i][col]),abs(a[k][col])); ????????????????ta = LCM/abs(a[i][col]); ????????????????tb = LCM/abs(a[k][col]); ????????????????if(a[i][col]*a[k][col]<0)tb=-tb;//異號的情況是相加 ??????????????? for(j=col; j<var+1; j++) { ????????????????????a[i][j] = a[i][j]*ta-a[k][j]*tb; ????????????????} ????????????} ????????} ????} ?? ????// 1. 無解的情況: 化簡的增廣陣中存在(0, 0, ..., a)這樣的行(a != 0). ??? for (i = k; i<equ; i++) { ????????if (a[i][col] != 0) return -1; ????} ????// 2. 無窮解的情況: 在var * (var + 1)的增廣陣中出現(xiàn)(0, 0, ..., 0)這樣的行，即說明沒有形成嚴格的上三角陣. ??? // 且出現(xiàn)的行數(shù)即為自由變元的個數(shù). ??? // 對于無窮解來說，如果要判斷哪些是自由變元，那么初等行變換中的交換就會影響，則要記錄交換. ??? if (k <var) { ????????// 首先，自由變元有var - k個，即不確定的變元至少有var - k個. ??????? for (i = k - 1; i>= 0; i--) { ????????????// 第i行一定不會是(0, 0, ..., 0)的情況，因為這樣的行是在第k行到第equ行. ??????????? // 同樣，第i行一定不會是(0, 0, ..., a), a != 0的情況，這樣的無解的. ??????????? free_x_num = 0; // 用于判斷該行中的不確定的變元的個數(shù)，如果超過1個，則無法求解，它們?nèi)匀粸椴淮_定的變元. ??????????? for (j = 0; j <var; j++) { ????????????????if (a[i][j] != 0 &&free_x[j]) free_x_num++, free_index = j; ????????????} ????????????if (free_x_num> 1) continue; // 無法求解出確定的變元. ??????????? // 說明就只有一個不確定的變元free_index，那么可以求解出該變元，且該變元是確定的. ??????????? temp = a[i][var]; ????????????for (j = 0; j <var; j++) { ????????????????if (a[i][j] != 0 && j != free_index) temp -= a[i][j] * x[j]; ????????????} ????????????x[free_index] = temp / a[i][free_index]; // 求出該變元. ??????????? free_x[free_index] = 0; // 該變元是確定的. ??????? } ????????return var - k; // 自由變元有var - k個. ??? } ????// 3. 唯一解的情況: 在var * (var + 1)的增廣陣中形成嚴格的上三角陣. ??? // 計算出Xn-1, Xn-2 ... X0. ??? for (i = var - 1; i>= 0; i--) { ????????temp = a[i][var]; ????????for (j = i + 1; j <var; j++) { ????????????if (a[i][j] != 0) temp -= a[i][j] * x[j]; ????????} ????????if (temp % a[i][i] != 0) return -2; // 說明有浮點數(shù)解，但無整數(shù)解. ??????? x[i] = temp / a[i][i]; ????} ????return 0; } |
解浮點數(shù)方程
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 | double a[MAXN][MAXN],x[MAXN];//方程的左邊的矩陣存在a中和等式右邊的值存在x中，求解之后x存的就是結(jié)果 intequ,var;//方程數(shù)和未知數(shù)個數(shù) /* *返回0表示無解，1表示有解 */ int Gauss() { ????inti,j,k,col,max_r; ????for(k=0,col=0; k<equ&&col<var; k++,col++) { ????????max_r=k; ????????for(i=k+1; i<equ; i++) ????????????if(fabs(a[i][col])>fabs(a[max_r][col])) ????????????????max_r=i; ????????if(fabs(a[max_r][col]) <eps)return 0; ????????if(k!=max_r) { ????????????for(j=col; j<var; j++) ????????????????swap(a[k][j],a[max_r][j]); ????????????swap(x[k],x[max_r]); ????????} ????????x[k]/=a[k][col]; ????????for(j=col+1; j<var; j++)a[k][j]/=a[k][col]; ????????a[k][col]=1; ????????for(i=0; i<equ; i++) ????????????if(i!=k) { ????????????????x[i]-=x[k]*a[i][k]; ????????????????for(j=col+1; j<var; j++)a[i][j]-=a[k][j]*a[i][col]; ????????????????a[i][col]=0; ????????????} ????} ????return 1; } |
對2取模的01方程組
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 | constint MAXN = 40; //有equ個方程，var個變元。增廣矩陣行數(shù)為equ,列數(shù)為var+1,分別為0到var intequ,var; int a[MAXN][MAXN]; //增廣矩陣 int x[MAXN]; //解集 intfree_x[MAXN];//用來存儲自由變元（多解枚舉自由變元可以使用） intfree_num;//自由變元的個數(shù) //返回值為-1表示無解，為0是唯一解，否則返回自由變元個數(shù) int Gauss() { ????intmax_r,col,k; ????free_num = 0; ????for(k = 0, col = 0 ; k <equ&& col <var ; k++, col++) { ????????max_r = k; ????????for(inti = k+1; i<equ; i++) { ????????????if(abs(a[i][col]) > abs(a[max_r][col])) ????????????????max_r = i; ????????} ????????if(a[max_r][col] == 0) { ????????????k--; ????????????free_x[free_num++] = col;//這個是自由變元 ??????????? continue; ????????} ????????if(max_r != k) { ????????????for(int j = col; j < var+1; j++) ????????????????swap(a[k][j],a[max_r][j]); ????????} ????????for(inti = k+1; i<equ; i++) { ????????????if(a[i][col] != 0) { ????????????????for(int j = col; j < var+1; j++) ????????????????????a[i][j] ^= a[k][j]; ????????????} ????????} ????} ????for(inti = k; i<equ; i++) ????????if(a[i][col] != 0) ????????????return -1;//無解 ??? if(k <var) return var-k;//自由變元個數(shù) ??? //唯一解，回代 ??? for(inti = var-1; i>= 0; i--) { ????????x[i] = a[i][var]; ????????for(int j = i+1; j <var; j++) ????????????x[i] ^= (a[i][j] && x[j]); ????} ????return 0; } |
推薦專題練習：hust
Click here！！！
總結(jié)
