高斯消元法
基本性質:
把某一行乘一個非 0 0 0的數 (方程的兩邊同時乘上一個非 0 0 0數不改變方程的解)
交換某兩行 (交換兩個方程的位置)
把某行的若干倍加到另一行上去 (把一個方程的若干倍加到另一個方程上去)
算法步驟
枚舉每一列c
-
- 找到絕對值最大的一行
-
- 將該行換到最上面
-
- 將該行第1個數變成1
-
- 將下面所有行的第
c
列清成0
- 將下面所有行的第
例題如下:
高斯消元法解線性方程組
代碼如下
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 110;
double a[N][N];
int n;
const double eps = 1e-8; //浮點型存在精度誤差,容易
/*枚舉每一列
- 1. 找到絕對值最大的一行
- 2. 將該行換到最上面(第r行)
- 3. 將該行第1個數變成1
- 4. 將下面所有行的第`c`列清成0*/
int gauss() {int c, r;//首先開始枚舉每一列進行“清零”操作for(c = 0, r = 0; c < n; c ++) {int mx_r = r;for(int i = r; i < n; i++) //找到絕對值最大的一行if(fabs(a[i][c]) > fabs(a[mx_r][c]))mx_r = i;if(fabs(a[mx_r][c]) < eps) continue; //判斷最大如果為0,那么沒有算的必要for(int i = c; i <= n; i++) swap(a[mx_r][i], a[r][i]); //換到第r行for(int i = n; i >= 0; i-- ) a[r][i] /= a[r][c]; //第”首位(c)“變為1for(int i = r + 1; i < n; i++ ) {// 將下面所有行的第`c`列清成0if(fabs(a[i][c]) > eps) //若是=0則沒必要操作for(int j = n; j >= c; j--)a[i][j] -= a[i][c] * a[r][j]; //a[r][c]為1,故這樣可以消0}r++; //該方程式固定好,進行下一個方程式行的操作}//判斷無解和無限解的情況if(r < n) { //這樣的話,那么說明未知數方程式個數不足n,則無法構成完美梯形for(int i = r; i < n; i++ )if(fabs(a[i][n]) > eps) //多出的答案bi若是不等于0return 2; //無解return 1; //無限解 0 == 0} //進行上三角矩陣的方程化簡for(int i = n - 1; i >= 0; i -- ) { //從后往前,anxn = bn,一步一步推前方的方程式未知數for(int j = i + 1; j < n; j++) //每i到最后只需保留第i個數(1),其它數全清零a[i][n] -= a[i][j] * a[j][n]; //這里第j行的答案已經算出,后續數(清零)的同步操作}return 0; //有唯一解
}int main() {cin >> n;for(int i = 0; i < n; i++ )for(int j = 0; j < n + 1; j++ )cin >> a[i][j];int r = gauss();if(r == 0) {for(int i = 0; i < n; i ++) printf("%.2lf\n", a[i][n]);} else if(r == 1) puts("Infinite group solutions");else puts("No solution");return 0;
}