高斯消元（Gaussian elimination）

大家好，欢迎来到IT知识分享网。

我们将分两个部分来说明高斯消去，第一部分是数学方面，第二个部分是如何用 C++ 来实现。

第一部分 数学知识

什么是高斯消去

高斯消元法（或译：高斯消去法），是线性代数规划中的一个算法，可用来为线性方程组求解。

高斯消元的目标是将矩阵变为上三角矩阵，例如，对应的矩阵为就是一个上三角矩阵（upper triangular matrix）。

对于一个线性方程组，我们可以写出两个矩阵（系数矩阵 coefficient matrix 和增广矩阵 Augmented Matrix），如下图所示。

下面我们用一个图片简单的说明一下高斯消去。

当形成上图所示的上三角形状，我们可以非常简单的解出方程的解。这样的方法就是高斯消去法。

高斯消去步骤

高斯消去法的过程可以分为以下几步：

（一）、构造增广矩阵。即系数矩阵 A 加上常数向量 b，也就是 (A|b)。

（二）、通过以交换行、某行乘以非负常数和两行相加这三种初等变化将原系统转化为更简单的三角形式

（三）、得到简化的三角方阵组。

（四）、使用向后替换算法（Algorithm for Back Substitution）求解得。

高斯消去步骤总结

方法一：原线性方程组 高斯消元法 上三角形式的线性方程组前向替换算法求解。

方法二：原线性方程组 高斯消元法下三角形式的线性方程组后向替换算法求解。

高斯消去细节

顺序消去法虽然编程操作简单，但是存在以下两方面限制:

(1).每次运算时，必须保证对角线上的元素不为0(即运算中的分母不为0)，否则算法无法继续进行。

(2).即使的值不为零，但如果绝对值很小，由于第k次运算中在分母位置，因此作除数会引起很大的误差，从而影响算法的稳定性。

正是由于顺序消去法会因为的值过小而引入计算误差，为了减少计算过程中舍入误差对方程组求解的影响，因此是否可以选择绝对值尽可能大的主元作为除数。基于这种思想就有了高斯消去法的改进型：部分主元消去法（Gaussian Elimination with Partial Pivoting）。

Gaussian Elimination with Partial Pivoting

下面我们使用一个详细的例子，来说明一下整个过程。假设我们有这样一个方程：

这样，我们可以得到对应的增广矩阵为，我们将使用列主元的方法。

Step 0a

找主元。主元就是左边矩阵的第一列绝对值最大的数。

Step 0b

如果需要，进行行交换，这样保证主元在第一行。

如上图所示的增广矩阵，第一列的主元为 1，因此我们需要进行行交换。交换后的矩阵如下图。

Step 1

对第一列进行高斯消去，这样我们可以得到下图的增广矩阵。

这样，我们就完成了第一列的高斯消去。

Step 2

查找下一列（第二列）的主元。注意已经完成的列不需要参与。

Step 3

交换行，如果需要。我们必须保证这个主元在这列的对角线位置。

如上图所示，我们可以看到第二列的主元为 1，因为第一行已经完成消元，不需要参与。

Step 4

对第二列进行高斯消去，这样我们可以得到下图的增广矩阵。

Step 5

查找下一列（第三列）的主元。注意已经完成的列不需要参与。

Step 6

交换行，如果需要。

Step 7

对第三列进行高斯消去，这样我们可以得到下图的增广矩阵。

Step 8

到这里，我们就形成了上三角矩阵，下面我们用后向替换算法求解。

利用主元法，我们可以消除舍入误差（rounding errors）。

第二部分 算法实现

C++

Python

模板题

洛谷 P3389 【模板】高斯消元法，https://www.luogu.com.cn/problem/P3389。