高斯消元

发表于 更新于

高斯消元

高斯消元适用于求解线性方程组。

一般的，对于线性方程组：
$$
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
    #include<iostream>
    #include<cstdio>
    #include<cmath>

    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;
    }