This page looks best with JavaScript enabled

高斯消元法学习笔记

 ·  ✏️ About  1641 words  ·  ☕ 4 mins read · 👀... views

高斯消元法是线性代数中的一个算法,可用来为线性方程组求解,求出矩阵的秩,以及求出可逆方阵的逆矩阵。当用于一个矩阵时,高斯消元法会产生出一个行梯阵式。

怎么消?

一个小小的例子

回想一下你的小学生活吧。

老师给了你一个方程组。

$$
\left\{
\begin{array}{rc}
2x+3y = 7 \\
4x-5y = 3
\end{array}
\right.
$$

聪慧如你当然能一眼看出来这个东西的答案是:$x = 2,y = 1$,可是你是怎么看出来的呢?老师告诉过你解二元一次方程组的标准做法:加减消元法。

具体来说,就是用一式乘以某比例之后去减二式,把方程组变成如下的样子:

$$
\left\{
\begin{array}{rc}
2x+3y = 7 \\
0x-11y = -11
\end{array}
\right.
$$

然后再把 $y$ 带回一式就可以得到 $x$ :

$$
\left\{
\begin{array}{rc}
2x+0y = 4 \\
0x-11y = -11
\end{array}
\right.
$$

从而你知道,$x = 2,y = 1$。

恭喜你,你已经完成了高斯消元。

再看上面的例子

如果我们把上面方程组的系数抽出来变成一个行列式,就会如下所示:
$$
\begin{array}{}
\left|\begin{array}{cccc}
2 & 3 \\
5 & -4
\end{array}\right|
\quad
\left|\begin{array}{cccc}
7 \\
3
\end{array}\right|
\end{array}
$$

那么我们消元的过程就会如下所示:

$$
\begin{array}{}
\left|\begin{array}{cccc}
2 & 3 \\
0 & -11
\end{array}\right|
\quad
\left|\begin{array}{cccc}
7 \\
-11
\end{array}\right|
\end{array}
$$

然后是

$$
\begin{array}{}
\left|\begin{array}{cccc}
2 & 0 \\
0 & -11
\end{array}\right|
\quad
\left|\begin{array}{cccc}
4 \\
-11
\end{array}\right|
\end{array}
$$

注意到,最后我们达成了一个目标:**使整个行列式只有对角线上的部分不为 $0$ ,其他部分均为 $0$ 。**这个条件的达成,让我们可以方便的计算出来这个方程组的解。

这也是我们在接下来设计的算法中需要达到的。

高斯-约旦消元法

运用上面提到的思想去解多元一次方程组的算法,叫做高斯-约旦消元法(Gauss-Jordan Elimination)。

它有着以下的优点:

  • 方便理解
  • 不用回代
  • 精度较高

它有着以下的缺点:

  • 运行较慢

实现

简单来说,它的运行过程是这个样子的:每次对于第 $i$ 行,让第 $i$ 列除了第 $i$ 行之外均成为 $0$ ,且不破坏前 $i-1$ 列的该性质。

具体来说,每次在处理第 $i$ 行时,将第 $i$ 行整行,乘以恰当比例后与除了第 $i$ 行之外的共 $n-1$ 行相减,使得除了第 $i$ 行之外的 $n-1$ 行的第 $i$ 列均为$0$。
(如果你对于第 $i$ 行第 $i$ 列的数万一是 $0$ 的情况感到困惑,请你先往下看,并假设这个位置上永远不会是 $0$ )

正确性的说明:

我们需要证明的,就是我们在循环中处理完第 $i$ 行时,不会破坏前 $i-1$ 行的该性质。注意到我们前 $i-1$ 次操作已经使得第 $i$ 行以后的前 $i-1$ 列均成为了 $0$ ,即为如下所示:(将要处理第4行)

$$
\begin{array}{}
\left|\begin{array}{cccc}
a & 0 & 0 & 3 & 2 & 3 & 2 & 3\\
0 & b & 0 & 5 & 2 & 3 & 2 & 3\\
0 & 0 & c & 3 & 2 & 3 & 2 & 3\\
0 & 0 & 0 & d & 2 & 3 & 2 & 3\\
0 & 0 & 0 & 7 & 2 & 3 & 2 & 3\\
0 & 0 & 0 & 5 & 2 & 3 & 2 & 3\\
0 & 0 & 0 & 3 & 2 & 3 & 2 & 3\\
0 & 0 & 0 & 8 & 2 & 3 & 2 & 3\\
\end{array}\right|
\end{array}
$$

这个时候我们拿第 $i$ 行无论如何与其他 $n-1$ 行相减,都不会使前 $i-1$ 列的数发生任何改变。这是因为第 $i$ 行的前 $i-1$ 列都是 $0$ 。

微小的优化

这个算法主要有两个微小的优化:一个是精度上的优化,一个是时间上的优化。

精度优化

注意到我们在处理第 $i$ 行的时候,在第 $i+1 \rightarrow n$ 行之间的这些行与第 $i$ 行完全是可以互换的。而这个时候我们用第 $i$ 行与其他行相减的时候,我们为了能获得更优秀的精度,往往会选择在第 $i$ 行到第 $n$ 行中,第 $i$ 列的数的绝对值最大的那一行,与第 $i$ 行交换,然后再进行后面的操作。

大家都知道,浮点数储存时有不可避免的误差,比如 $2.0000001$ 之类。这个时候如果我们需要对这行乘很多倍,就会导致误差的放大,而除法则不会。

时间优化

注意到事实上我们再处理第 $i$ 行的时候只需要处理第 $i+1$ 列之后的列,所以我们在行之间相减的时候,运用这个技巧大约可以减少一半的复杂度。

无解的判定

如果我们发现在处理第 $i$ 行的数的时候,所有能选的第 $i$ 列的数都是 $0$ ,那么这个时候,这个方程就是无解或者没有唯一解的。

代码

Luogu P3389 【模板】高斯消元法为例子

 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
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;

const int MAXN = 110;
const double eps = 1e-7;

bool gauss(double a[MAXN][MAXN],int n){
    for(int i = 1;i<=n;i++){
        int r = i;
        for(int j = i+1;j<=n;j++)
            if(fabs(a[r][i]) < fabs(a[j][i])) r = j;
        // 寻找a[r][i]使其绝对值最大
        if(r!=i)
            for(int j = 1;j<=n+1;j++) 
                swap(a[r][j],a[i][j]);
        // 交换两列
        if(fabs(a[i][i]) < eps) 
            return false;
        // 如果全部都是0,则无解
        for(int j = 1;j<=n;j++)if(j!=i){
            double t = a[j][i]/a[i][i];
            for(int k = i+1;k<=n+1;k++)
                a[j][k] -= a[i][k] * t;
        }
        //使第i个位置的所有其他数都为0
    }
    for(int i = 1;i<=n;i++)
        a[i][n+1]/=a[i][i];
    return true;
}
int n;
double num[MAXN][MAXN];

void init(){
    scanf("%d",&n);
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=n+1;j++){
            scanf("%lf",&num[i][j]);
        }
    }
}

void solve(){
    if(gauss(num,n))
        for(int i = 1;i<=n;i++)
            printf("%.2lf\n",num[i][n+1]);
    else
        printf("No Solution\n");
}

int main(){
    init();
    solve();
    return 0;
}

cqqqwq
WRITTEN BY
cqqqwq
A student in Computer Science.

评论: