c++用类实现高斯消元法求解线性方程组的解_算法学习笔记(38): 高斯消元

如果你学过《线性代数》课程，高斯消元对你来说应该很熟悉了，它可以通过行变换，把矩阵变换成行阶梯形矩阵。本文主要介绍高斯-约旦消元法，把矩阵变换成行最简形矩阵。用这种方法，可以求秩、求逆矩阵、解线性方程组等。

来看例题：

（洛谷P3389 【模板】高斯消元法）

题目描述

给定一个线性方程组，对其求解
输入格式

第一行，一个正整数

第二至

行，每行

个整数，为

和

，代表一组方程。

输出格式

共

行，每行一个数，第

行为

（保留2位小数）

如果不存在唯一解，在第一行输出”No Solution”.
输入输出样例
输入 #1

3

1 3 4 5

1 4 7 3

9 3 2 2
输出 #1

-0.97

5.18

-2.39
说明/提示

我们想想，这个题手算是怎样做的（高斯-约旦消元法）：

当然这是运气比较好的情况，有时候在消元途中会出现第

行

列的元素为0的情况，这时候需要交换行再继续消元。

完整的步骤大概是：

1. 枚举第
   列：
   1. 从第
      行开始，往下找一个非0数
      1. 如果没找到：
         1. 输出无解
      2. 如果找到了，设它在第
         行：
         1. 交换第
            行和第
            行
         2. 第
            行除以
            ，使
            
         3. 消掉第
            列的其他元素
2. 剩下的第
   列即为答案。

很容易翻译成代码：

for (int j = 0; j < n; ++j) // 枚举列
{
    int i;
    for (i = j; i < n; ++i) // 找到非0元素
        if (A[i][j])
            break;
    if (A[i][j] == 0) // 无解的情形
    {
        puts("No Solution");
        return 0;
    }
    for (int k = 0; k <= n; ++k) // 把非0元素所在行交换到当前行
        swap(A[i][k], A[j][k]);
    for (int k = n; k >= j; --k) // 把当前行除以A[j][j]，令A[j][j]归一，注意循环顺序
        A[j][k] /= A[j][j];
    for (int i = 0; i < n; ++i) // 对其他行消元
        if (i != j)
            for (int k = n; k >= j; --k) // 注意循环顺序
                A[i][k] -= A[j][k] * A[i][j];
}

这个代码解决这道题已经够了，但还是不够完善，因为无解的时候直接退出了，而有时候我们需要继续进行该过程，并对得到的行最简形矩阵进行判断。比如下面这道题：

题目描述

已知

元线性一次方程组。

请根据输入的数据，编程输出方程组的解的情况。
输入格式

第一行输入未知数的个数

。

接下来

行，每行

个整数，表示每一个方程的系数及方程右边的值。

输出格式

如果有唯一解，则输出解（小数点后保留两位小数）。

如果方程组无解输出

； 如果有无穷多实数解，输出

；

输入输出样例
输入

3

2 -1 1 1

4 1 -1 5

1 1 1 0
输出

x1=1.00

x2=0.00

x3=-1.00

现在我们需要判断是无解还是无穷多解，由线性代数知识，我们知道，对于

元线性方程组

，它的解的情况为：

• 若
  ，且
  时，原方程有唯一解
• 若
  ，且
  时，原方程有无穷多解
• 若
  ，原方程无解

所以我们需要把行变换进行到底，上面的步骤可以完善为：

1. 枚举第
   列：
   1. 从第
      行开始，往下找一个非0数
      1. 如果没找到：
         1. 开始枚举下一列
      2. 如果找到了，设它在第
         行：
         1. 交换第
            行和第
            行
         2. 第
            行除以
            ，使
            
         3. 消掉第
            列的其他元素
         4. 把
            加上1
2. 统计非0行的数量，即为矩阵的秩，然后判断解的情况
3. 如果有唯一解，剩下的第
   列即为答案。

主要代码（第1大步）如下：

// 高斯消元，把n行m列的矩阵化为行最简矩阵
for (int j = 0; j < m; ++j) // 枚举列
{
    int i;
    for (i = curi; i < n; ++i) // 找到非0元素
        if (A[i][j])
            break;
    if (A[i][j] == 0)
        continue;
    for (int k = 0; k < m; ++k) // 把非0元素所在行交换到当前行
        swap(A[i][k], A[curi][k]);
    for (int k = m - 1; k >= j; --k) // 把当前行都除以A[curi][j]，令A[curi][j]归一，注意循环顺序
        A[curi][k] /= A[curi][j];
    for (int i = 0; i < n; ++i) // 对其他行消元
        if (i != curi)
            for (int k = m - 1; k >= j; --k) // 注意循环顺序
                A[i][k] -= A[curi][k] * A[i][j];
    curi++;
}

这份代码可以作为高斯消元的模板。当然，有时候我们并不使用浮点数，而是求模意义下的除法。或者有时候，我们会对异或方程组进行高斯消元（无非就是

上的矩阵）。方法都是类似的。

Pecco：算法学习笔记（目录）​zhuanlan.zhihu.com