打开APP
userphoto
未登录

开通VIP,畅享免费电子书等14项超值服

开通VIP
Python实现所有算法-高斯消除法
userphoto

2022.07.07 内蒙古

关注

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

这里再细写一下:

在数学中,高斯消元法,也称为行约简,是一种求解线性方程组的算法。它由对相应的系数矩阵执行的一系列操作组成。此方法还可用于计算矩阵的秩、方阵的行列式和可逆矩阵的逆矩阵。该方法以卡尔·弗里德里希·高斯 ( 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
本站仅提供存储服务,所有内容均由用户发布,如发现有害或侵权内容,请点击举报
打开APP,阅读全文并永久保存 查看更多类似文章
猜你喜欢
类似文章
【热】打开小程序,算一算2024你的财运
高斯消元求解线性方程组
SIFT算法详解
行列式的来历与克拉默法则
迭代法求解线性方程组的收敛问题总结
【数学史】矩阵和线性代数原来是这么来的
关于矩阵分解的一切
更多类似文章 >>
生活服务
热点新闻
分享 收藏 导长图 关注 下载文章
绑定账号成功
后续可登录账号畅享VIP特权!
如果VIP功能使用有故障,
可点击这里联系客服!

联系客服