Python实现所有算法-高斯消除法

啊，我终于可以写文章了！最近两天好累哇，先继续写上面的算法文章。

这篇文章写的算法是高斯消元，是数值计算里面基本且有效的算法之一：是求解线性方程组的算法。

这里再细写一下：

在数学中，高斯消元法，也称为行约简，是一种求解线性方程组的算法。它由对相应的系数矩阵执行的一系列操作组成。此方法还可用于计算矩阵的秩、方阵的行列式和可逆矩阵的逆矩阵。该方法以卡尔·弗里德里希·高斯 ( Carl Friedrich Gauss ，1777-1855)的名字命名，尽管该方法的一些特例——尽管没有证明——早在公元 179 年左右就为中国数学家所知。

为了对矩阵执行行缩减，可以使用一系列基本行操作来修改矩阵，直到矩阵的左下角尽可能地用零填充。基本行操作分为三种类型：

1.交换两行，

2.将一行乘以一个非零数，

3.将一行的倍数添加到另一行。（减法可以通过将一行乘以 -1 并将结果添加到另一行来实现）

使用这些操作，矩阵总是可以转换为上三角矩阵，实际上是行梯形矩阵。一旦所有前导系数（每行中最左边的非零条目）都为 1，并且包含前导系数的每一列在其他地方都为零，则称该矩阵为简化行梯形形式。这种最终形式是独一无二的；换句话说，它与所使用的行操作序列无关。例如，在下面的行操作序列中（在第一步和第三步对不同行进行两个基本操作），第三和第四个矩阵是行梯形矩阵，最后一个矩阵是唯一的简化行梯队形式。

一个矩阵的简化

使用行操作将矩阵转换为简化的行梯形形式有时称为Gauss-Jordan 消元法。在这种情况下，术语高斯消元是指过程，直到它达到其上三角形或（未简化的）行梯形形式。出于计算原因，在求解线性方程组时，有时最好在矩阵完全约简之前停止行操作。

我们对其实现的操作只有这三个

如果矩阵与线性方程组相关联，则这些操作不会更改解集。因此，如果一个人的目标是求解线性方程组，那么使用这些行操作可以使问题变得更容易。

对于矩阵中的每一行，如果该行不只包含零，则最左边的非零条目称为该行的前导系数（或枢轴）。因此，如果两个前导系数在同一列中，则可以使用类型 3的行操作使这些系数之一为零。然后通过使用行交换操作，总是可以对行进行排序，以便对于每个非零行，前导系数位于上一行的前导系数的右侧。如果是这种情况，则称矩阵为行梯形. 所以矩阵的左下部分只包含零，并且所有的零行都在非零行的下方。这里使用“梯队”一词是因为可以粗略地认为行是按大小排列的，最大的位于顶部，最小的位于底部。

例如，下面的矩阵是行梯形的，它的前导系数用红色表示：

就像这样

它是梯形的，因为零行在底部，第二行（第三列）的领先系数在第一行（第二列）的领先系数的右侧。

如果矩阵的所有前导系数都等于 1（这可以通过使用类型 2 的基本行操作来实现），并且在包含前导系数的每一列中，则称矩阵为简化行梯形。该列中的其他条目为零（可以通过使用类型 3 的基本行操作来实现）。

假如我们求解这个方程的解

下表是同时应用于方程组及其相关增广矩阵的行缩减过程。在实践中，通常不会用方程来处理系统，而是使用更适合计算机操作的增广矩阵。行缩减过程可以概括如下：从L1以下的所有方程中消除x，然后从L2以下的所有方程中消除y。这将使系统变成三角形。然后，使用反向替换，可以解决每个未知数。

就好像这样

其实还有内容，但是公式编辑实在不会哇，这里给出程序的伪代码：

高斯消元法将给定的m × n矩阵A转换为行梯形矩阵。

在下面的伪代码中，A[i, j]表示矩阵A在第i行和第j列中的条目，索引从 1 开始。转换在原地执行，这意味着原始矩阵丢失，最终被其行梯形形式替换。

看不懂？没有关系，大致懂就行

程序的实现上面，我们导入这些内容

为了精度，导入float64

以及导入的一个N维的数组，在内部是所以ndarray封装的

这样学习的态度是不对的，我们需要看看Numpy文档写的：

64位精度浮点数类型：符号位、11位指数、52位尾数。

没关系，你不懂的官网文档满足你

NDarray在这里

可在运行时用于键入具有给定 dtype 和未指定形状的数组。

系数矩阵，向量是输入的参数，后面是返回的数据类型。

rows, columns = np.shape(coefficients)

对shape函数感兴趣不，内部是这样的

x: NDArray[float64] = np.zeros((rows, 1), dtype=float)

这个也是注解的写法，意思是返回一个数组，用0填充：

zeros函数的样子

第一个参数，元组，说明样子。后面参数是类型，这里写float。返回值是具有给定形状、数据类型和顺序的零数组。

首先，reversed 函数返回一个反转的迭代器。这个为什么倒着算呢？是因为倒着算对算法来讲有一些优点。

内部再套一个函数，内部对列处理，下面的代码就是实现使用倍数的关系对一整行处理，[]是相当于数组的index写法，下面是将处理结果应用到行，最后打印X。

上面这个函数是高斯函数的一个子函数，作用是给出最简的阶梯行列式。

我们要算这个

gaussian_elimination(
[[2, 2, -1],
[0, -2, -1], 
[0, 0, 5]], 
[[5], [-7], [15]])

输入的时候这样输入，先别继续看，我们看高斯分解

这个检查写的很简单

接下来

连接我们的矩阵，要求有相应的形状

这个例子不错

0是按照行展开，1是列，None是直接接龙。

这段实现的是上面的伪代码

一个很有趣的变量名

gaussian_elimination([[2, 2], [0, -2]], [[-1], [-1]])

调用的时候就是这样，输入一个大元组，里面有两个小元组

输出的结果

此篇文章的封面来自于图灵出版社

https://en.wikipedia.org/wiki/Gaussian_elimination

https://github.com/numpy/numpy