高斯消元
高斯消元求解线性方程组
利用初等行变换将方程组变成行阶梯式矩阵 > 1. 交换任意两行 > 2. 将一行乘以一个非零常数 > 3. 将一行的若干倍加到另一行
得到行阶梯矩阵便可以逐一步求解
解的结构 \(\begin{cases} 无解 \\ \\ 有解 \begin{cases} 唯一解 \\ \\ 无穷多解 \\ \end{cases}\\ \end{cases}\)
算法步骤 > 枚举每一列，固定当前列 > 1. 枚举没固定的行，找到当前固定列绝对值最大的那行 > 2. 将当行放到本次要固定行的位置 > 3. 将该行将固定列的值变成1 > 4. 利用当前行将当前行下面的行的固定列值都变成0
相关例题
883.
高斯消元解线性方程组 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
using namespace std;
const int N = 110;
const double eps = 1e-8;
double matrix[N][N];
void print(int n) {
for (int i = 1; i <= n; ++i) {
auto &x = matrix[i][n + 1];
if (fabs(x) < eps) x = 0;
printf("%.2lf\n", x);
}
}
int gauss(int n) {
int rank = 1; // 矩阵的秩
// 变行阶梯矩阵
for (int col = 1; col <= n; ++col) { // 枚举列
int row = rank; // 要固定的行
for (int i = row; i <= n; ++i) // 找绝对值最大的列
if (fabs(matrix[i][col]) > fabs(matrix[row][col]))
row = i;
swap(matrix[rank], matrix[row]); // 将该行换过来
row = rank; // 当前操作的行
if (fabs(matrix[row][col]) < eps) continue; // 都是0无法归一
for (int i = n + 1; i > col; --i) matrix[row][i] /= matrix[row][col]; // 归一
matrix[row][col] = 1;
for (int i = row + 1; i <= n; ++i) { // 消元，将该行该列第一个数变成0
const double k = matrix[i][col];
if (fabs(k) < eps) continue; // 已经是0了
for (int j = n + 1; j > col; --j)
matrix[i][j] -= matrix[row][j] * k; // 减去k倍
matrix[i][col] = 0;
}
++rank; // 矩阵的秩+1
}
// cout << rank << '\n';
// for (int i = 1; i <= n; ++i)
// for (int j = 1; j <= n + 1; ++j)
// cout << matrix[i][j] << " \n"[j == n + 1];
if (rank < n + 1) { // 无解或者无穷解
for (int i = rank; i <= n; ++i)
if (fabs(matrix[i][n + 1]) > eps) // 该行的系数都是0，但常数项>0
return -1; // 无解
return 0; // 无穷多解
}
for (int row = n; row; --row) { // 从下往上求解
for (int col = n; col > row; --col) {
matrix[row][n + 1] -= matrix[row][col] * matrix[col][n + 1];
matrix[row][col] = 0;
}
}
return 1; // 唯一解
}
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n + 1; ++j)
cin >> matrix[i][j];
int f = gauss(n);
if (f == -1) cout << "No solution\n";
else if (f == 0) cout << "Infinite group solutions\n";
else print(n); // unique solution
return 0;
}
作者：rw-chen
链接：https://www.acwing.com/activity/content/code/content/5071614/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
883.
高斯消元解线性方程组 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
using namespace std;
const int N = 110;
bool matrix[N][N];
void print(int n) {
for (int i = 1; i <= n; ++i) cout << matrix[i][n + 1] << '\n';
}
int gauss(int n) {
// 求行阶梯矩阵
int rank = 1;
for (int col = 1; col <= n; ++col) {
int row = rank; // 固定的行
for (; row <= n && !matrix[row][col]; ++row); // 找一个1就好
if (row > n || !matrix[row][col]) continue; // 全都是0
swap(matrix[rank], matrix[row]); // 交换
row = rank;
for (int i = row + 1; i <= n; ++i) // 消元
if (matrix[i][col])
for (int j = col; j <= n + 1; ++j)
matrix[i][j] ^= matrix[row][j];
++rank;
}
// for (int i = 1; i <= n; ++i)
// for (int j = 1; j <= n + 1; ++j)
// cout << matrix[i][j] << " \n"[j == n + 1];
if (rank <= n) {
while (rank <= n)
if (matrix[rank++][n + 1] > 0)
return -1; // 无解
return 0; // 多组解
}
for (int row = n; row; --row) {
for (int col = n; col > row; --col) {
matrix[row][n + 1] ^= matrix[row][col] * matrix[col][n + 1];
matrix[row][col] = 0;
}
}
return 1; // 唯一解
}
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; ++i)
for (int j = 1;j <= n + 1; ++j)
cin >> matrix[i][j];
int f = gauss(n);
if (f == 1) print(n);
else if (f == 0) cout << "Multiple sets of solutions\n";
else cout << "No solution\n";
return 0;
}
作者：rw-chen
链接：https://www.acwing.com/activity/content/code/content/5071999/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
- 时间复杂度\(O(n^3)\) > 枚举列，利用每一行消元，所以\(O(n^3)\)