高斯消元
高斯消元
高斯消元适用于求解线性方程组。
一般的，对于线性方程组： \[ a_{1,1}x_1 + a_{1,2}x_2 + a_{1,3}x_3 + ……a_{1,n}x_n = b_1 \] \[ a_{2,1}x_1 + a_{2,2}x_2 + a_{2,3}x_3 + ……a_{2,n}x_n = b_2 \]
\[ …… \]
\[ a_{n,1}x_1 + a_{n,2}x_2 + a_{n,3}x_3 + ……a_{n,n}x_n = b_n \]
我们用下面这个矩阵来表示这个线性方程组： \[ \left \{ \begin{array}{ccccc|c} a_{1,1} & a_{1,2} & a_{1,3} & \cdots & a_{1,n} & b_1 \\ a_{2,1} & a_{2,2} & a_{2,3} & \cdots & a_{2,n} & b_2 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ a_{n,1} & a_{n,2} & a_{n,3} & \cdots & a_{n,n} & b_n \\ \end{array} \right \} \]
我们循环一个变量\(i\)（从\(1\)到\(n\)）
先在矩阵中找到一行（设这行是第\(x\)行），使得\(a_{x,1},a_{x,2},……,a_{x,i-1}\)都为\(0\)，但\(a_{x,i} = 0\)。
然后用这一行矩阵，用简单行变换的方式将矩阵其他行的第\(i\)项的系数消为0。
最后我们就得到一个“阶梯矩阵”，然后就可以愉快地求解了。
Code
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
using namespace std;
const int maxn = 1e3 + 5;
double a[maxn][maxn],b[maxn];
int n;
int main() {
scanf("%d",&n);
for (int i=1; i<=n; i++) {
for (int j=1; j<=n; j++)
scanf("%lf",&a[i][j]);
scanf("%lf",&b[i]);
}
for (int i=1; i<=n; i++) {
for (int j=i; j<=n; j++)
if (fabs(a[j][i]) > 1e-10) {
for (int k=1; k<=n; k++)
swap(a[i][k],a[j][k]);
swap(b[i],b[j]);
break;
}
for (int j=1; j<=n; j++) {
if (j == i)
continue;
double rate = a[j][i] / a[i][i];
for (int k=1; k<=n; k++)
a[j][k] -= rate * a[i][k];
b[j] -= rate * b[i];
}
}
for (int i=1; i<=n; i++)
printf("x%d = %.2lf\n",i,b[i] / a[i][i]);
return 0;
}