Eternity

Until The End

高斯消元

发表于 更新于 分类于 ，
本文字数： 2.7k 阅读时长 ≈ 2 分钟

“一列一列的消失，所有绝铭将会被破解。”

高斯消元

消元法说明

消元法是将方程组中的一方程的未知数用含有另一未知数的代数式表示，并将其带入到另一方程中，这就消去了一未知数，得到一解；或将方程组中的一方程倍乘某个常数加到另外一方程中去，也可达到消去一未知数的目的。消元法主要用于二元一次方程组的求解。

消元法理论的核心

消元法理论的核心主要如下：

  • 两方程互换，解不变；
  • 一方程乘以非零数 ，解不变；
  • 一方程乘以数 加上另一方程，解不变。

高斯消元法思想概念

德国数学家高斯对消元法进行了思考分析，得出了如下结论：

  • 在消元法中，参与计算和发生改变的是方程中各变量的系数；
  • 各变量并未参与计算，且没有发生改变；
  • 可以利用系数的位置表示变量，从而省略变量；
  • 在计算中将变量简化省略，方程的解不变。

高斯消元五步骤法

高斯消元法在将增广矩阵化为最简形后对于自由未知量的赋值，需要掌握线性相关知识，且赋值存在人工经验的因素，使得在学习过程中有一定的困难，将高斯消元法划分为五步骤，从而提出五步骤法，内容如下：

  1. 增广矩阵行初等行变换为行最简形；
  2. 还原线性方程组；
  3. 求解第一个变量；
  4. 补充自由未知量；
  5. 列表示方程组通解。

在说这些之后，包括 OI-Wiki 和《进阶指北》，我也都没有搞懂，所以建议像我这样蒟蒻的人，还是多背背模板好。

约旦消元法

大致思路如下：

  1. 选择一个尚未被选过的未知数作为主元，选择一个包含这个主元的方程。

  2. 将这个方程主元的系数化为 $1$ 。

  3. 通过加减消元，消掉其它方程中的这个未知数。

  4. 重复以上步骤，直到把每一行都变成只有一项有系数。

我们用矩阵表示每一项系数以及结果。

洛谷模板题 
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
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define underMax(x,y) ((x)>(y)?(x):(y))
#define underMin(x,y) ((x)<(y)?(x):(y))
typedef long long LL;
using namespace std;
const int MAXN=1001;
const double Eps=1e-6;
template<class T>
inline void underRead(T &x)
{
    x=0;
    char ch=gh(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
    if(t) x=-x;
}
int N;
double Matrix[MAXN][MAXN];
inline double underFabs(double x)
{
    return (x>0?x:-x);
}
inline void underSwap(double &a,double &b)
{
    double t=a;a=b;b=t;
}
inline bool underGauss()
{
    for(int i=1;i<=N;++i)
    {
        int t=i;
        for(int j=i+1;j<=N;++j)
        {
            if(underFabs(Matrix[j][i])>underFabs(Matrix[t][i])) t=j;
        }
        for(int j=1;j<=N+1;++j) underSwap(Matrix[t][j],Matrix[i][j]);
        if(!Matrix[i][i]) return 0;
        for(int j=1;j<=N;++j)
        {
            if(j!=i)
            {
                double temp=Matrix[j][i]/Matrix[i][i];
                for(int k=i+1;k<=N+1;++k)
                {
                    Matrix[j][k]-=Matrix[i][k]*temp;
                }
            }
        }
    }
    for(int i=N;i>0;--i)
    {
        for(int j=i+1;j<=N;++j)
        {
            Matrix[i][N]-=Matrix[i][j]*Matrix[j][N];
        }
    }
    return 1;
}
int main()
{
//  freopen("Gauss.in","r",stdin);
//  freopen("Gauss.out","w",stdout);
    underRead(N);
    for(int i=1;i<=N;++i)
    {
        for(int j=1;j<=N+1;++j)
        {
            scanf("%lf",&Matrix[i][j]);
        }
    }
    bool t=underGauss();
    if(!t) printf("No Solution");
    else for(int i=1;i<=N;++i) printf("%.2lf\n",Matrix[i][N+1]/Matrix[i][i]);
    return 0;
}
/*
3
1 3 4 5
1 4 7 3
9 3 2 2
*/
相关文章