C＋数学与算法系列之高斯消元法求解线性方程组

1. 前言

什么是消元法？

是指将多个组成的方程组中的若干个变量通过有限次地变换，消去方程式中的变量，通过简化方程式，从而获取结果的一种解题方法。

消元法主要有、、、、、、、等。

对方程式消元时，是基于如下的规则：

改变中的顺序，或者说无论先求解方程组中哪一个方程式，不影响方程组的解。

对一个方程式中的所有系数乘以或除以某一个非零数，不影响方程组的解。

方程式之间可以倍乘后相加或相减，不影响解。

其中最常用的为和，简要介绍一下。

代入消元法

如求解 和; 个方程式中的 ,变量时。

可以把第 个方程式变换成 。

然后代入到第 个方程中，。可求解出 。

加减消元法

还是求解如上的方程组。

可以把第 个方程式乘以 后再去减第 个方程式，或者说让第 个方程式减去第 个方程式乘以 。

。可以求解 。

本文主要和大家聊聊高斯消元法，高斯消元法也称为简单消元法，是求解一般线性方程组的经典算法。

2. 高斯消元法

在理解高斯消元化之前，先理解几个基本概念：

什么是增广矩阵？

增广矩阵是线性代数中的概念，如下线性方程组：

使用每个方程式的系数构建的矩阵，称为，表示为：

用方程式的和构建的矩阵称为方程组的。如下图所示：

当方程组中的每一个方程的结果都为 时, 即 ，称这样的方程组为。

2.1 高斯消元法的思想

高斯消元的基本思想：

对于一个有 个变量、有个方程式的方程组。

把方程组中除了第 个方程式外的其它方程式中的 消去，同理，再把除了第 个方程式以下的方程组中其它方程式中的 消去，依次类推，直到最后 个方程式中只留下 。

目的：通过一系列的变换，让变换成一个稀疏的。

现通过具体的案例，理解高斯消元法。

如求解如下图所示的方程组：

用方程组中的所有方程式的系数和结果构建，此矩阵有 行，为了描述方便，用 。

利用初等行变换规则将增广矩阵转换成行阶梯矩阵。

首先，定位至行（当前行）的第 列()，以行（列号不变）扫描方式(从上向下)查找到本列中绝对值最大的数据，然后把最大值所在的行和当前行交换。如下图，因当前行所在列中的值就是最大值，故不需要交换。

Tips：为什么要交换？是不是一定要交换行？

消元过程，从方程组角度而言，消去第 个方程后面 变量。从矩阵角度而言，让后面行中的 列中的数据变为 。如消去 中列中数据，可以使用倍数相加（减)变换方案，消元表达式：。

定位到行的第 列（）。逻辑如上，以行扫描方式查找到本列中绝对值最大的数据，然后把最大值所在的行和当前行交换。因当前行的值 最大，不需要交换。

消去 中的 变量，让行中只保留变量。消元表达式：。

最终会得到一个的系数矩阵，最后可以对矩阵以反序方式迭代求解。如下图所示：

最终可以得到 。

问题思考

变换过程中，是不是一定需要？

答案：不一定。

当方程组中的方程式不多时，换不换行其实并不重要。如下方程组。

其增广矩阵如下图所示。

可以先消去行中的变量。即。

再消去行中的变量。即。

使用消元求解过程中，没有对行交换，同样能求解方程组中各变量的值。但是，当方程组中方程式的数量非常多时，如果不提供统一的处理规则，则无法对大量数据进行迭代处理。

的本质是或者为数据统一的。前文所述高斯消元法中之所以交换行，是保证最后生成矩阵的前提，从而让算法更稳定。

求解方程组时，其解有 种情况：

无解，如果最后一行形如： 则无解。

唯一解。消元后，最后生成标准的。

无穷解。消元后，不是标准的矩阵即不可确定。

2.2 编程实现

代码的主题是讨论高斯消元算法，只考虑了和 种情况且假设所有解都是整数。

输出结果：

3. 总结

本文讨论了高斯消元法的算法思想，基于此思想编码实现了对方程组的求解。本文旨在讲清楚高斯消元的核心逻辑，有兴趣者可在此代码的基础上继续研究、扩展。