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

原创 云深之无迹 2022-07-07 23:32


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


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


这里再细写一下:


在数学中,高斯消元法,也称为行约简,是一种求解线性方程组的算法。它由对相应的系数矩阵执行的一系列操作组成。此方法还可用于计算矩阵的秩、方阵的行列式和可逆矩阵的逆矩阵。该方法以卡尔·弗里德里希·高斯 ( 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


评论
  •  在全球能源结构加速向清洁、可再生方向转型的今天,风力发电作为一种绿色能源,已成为各国新能源发展的重要组成部分。然而,风力发电系统在复杂的环境中长时间运行,对系统的安全性、稳定性和抗干扰能力提出了极高要求。光耦(光电耦合器)作为一种电气隔离与信号传输器件,凭借其优秀的隔离保护性能和信号传输能力,已成为风力发电系统中不可或缺的关键组件。 风力发电系统对隔离与控制的需求风力发电系统中,包括发电机、变流器、变压器和控制系统等多个部分,通常工作在高压、大功率的环境中。光耦在这里扮演了
    晶台光耦 2025-01-08 16:03 80浏览
  • 根据环洋市场咨询(Global Info Research)项目团队最新调研,预计2030年全球无人机锂电池产值达到2457百万美元,2024-2030年期间年复合增长率CAGR为9.6%。 无人机锂电池是无人机动力系统中存储并释放能量的部分。无人机使用的动力电池,大多数是锂聚合物电池,相较其他电池,锂聚合物电池具有较高的能量密度,较长寿命,同时也具有良好的放电特性和安全性。 全球无人机锂电池核心厂商有宁德新能源科技、欣旺达、鹏辉能源、深圳格瑞普和EaglePicher等,前五大厂商占有全球
    GIRtina 2025-01-07 11:02 128浏览
  • 在智能网联汽车中,各种通信技术如2G/3G/4G/5G、GNSS(全球导航卫星系统)、V2X(车联网通信)等在行业内被广泛使用。这些技术让汽车能够实现紧急呼叫、在线娱乐、导航等多种功能。EMC测试就是为了确保在复杂电磁环境下,汽车的通信系统仍然可以正常工作,保护驾乘者的安全。参考《QCT-基于LTE-V2X直连通信的车载信息交互系统技术要求及试验方法-1》标准10.5电磁兼容试验方法,下面将会从整车功能层面为大家解读V2X整车电磁兼容试验的过程。测试过程揭秘1. 设备准备为了进行电磁兼容试验,技
    北汇信息 2025-01-09 11:24 22浏览
  • 村田是目前全球量产硅电容的领先企业,其在2016年收购了法国IPDiA头部硅电容器公司,并于2023年6月宣布投资约100亿日元将硅电容产能提升两倍。以下内容主要来自村田官网信息整理,村田高密度硅电容器采用半导体MOS工艺开发,并使用3D结构来大幅增加电极表面,因此在给定的占位面积内增加了静电容量。村田的硅技术以嵌入非结晶基板的单片结构为基础(单层MIM和多层MIM—MIM是指金属 / 绝缘体/ 金属) 村田硅电容采用先进3D拓扑结构在100um内,使开发的有效静电容量面积相当于80个
    知白 2025-01-07 15:02 150浏览
  • By Toradex 秦海1). 简介嵌入式平台设备基于Yocto Linux 在开发后期量产前期,为了安全以及提高启动速度等考虑,希望将 ARM 处理器平台的 Debug Console 输出关闭,本文就基于 NXP i.MX8MP ARM 处理器平台来演示相关流程。 本文所示例的平台来自于 Toradex Verdin i.MX8MP 嵌入式平台。  2. 准备a). Verdin i.MX8MP ARM核心版配合Dahlia载板并
    hai.qin_651820742 2025-01-07 14:52 115浏览
  • 本文介绍编译Android13 ROOT权限固件的方法,触觉智能RK3562开发板演示,搭载4核A53处理器,主频高达2.0GHz;内置独立1Tops算力NPU,可应用于物联网网关、平板电脑、智能家居、教育电子、工业显示与控制等行业。关闭selinux修改此文件("+"号为修改内容)device/rockchip/common/BoardConfig.mkBOARD_BOOT_HEADER_VERSION ?= 2BOARD_MKBOOTIMG_ARGS :=BOARD_PREBUILT_DTB
    Industio_触觉智能 2025-01-08 00:06 100浏览
  • 根据环洋市场咨询(Global Info Research)项目团队最新调研,预计2030年全球中空长航时无人机产值达到9009百万美元,2024-2030年期间年复合增长率CAGR为8.0%。 环洋市场咨询机构出版了的【全球中空长航时无人机行业总体规模、主要厂商及IPO上市调研报告,2025-2031】研究全球中空长航时无人机总体规模,包括产量、产值、消费量、主要生产地区、主要生产商及市场份额,同时分析中空长航时无人机市场主要驱动因素、阻碍因素、市场机遇、挑战、新产品发布等。报告从中空长航时
    GIRtina 2025-01-09 10:35 21浏览
  • 一个真正的质量工程师(QE)必须将一件产品设计的“意图”与系统的可制造性、可服务性以及资源在现实中实现设计和产品的能力结合起来。所以,可以说,这确实是一种工程学科。我们常开玩笑说,质量工程师是工程领域里的「侦探」、「警察」或「律师」,守护神是"墨菲”,信奉的哲学就是「墨菲定律」。(注:墨菲定律是一种启发性原则,常被表述为:任何可能出错的事情最终都会出错。)做质量工程师的,有时会不受欢迎,也会被忽视,甚至可能遭遇主动或被动的阻碍,而一旦出了问题,责任往往就落在质量工程师的头上。虽然质量工程师并不负
    优思学院 2025-01-09 11:48 27浏览
  • 故障现象一辆2017款东风风神AX7车,搭载DFMA14T发动机,累计行驶里程约为13.7万km。该车冷起动后怠速运转正常,热机后怠速运转不稳,组合仪表上的发动机转速表指针上下轻微抖动。 故障诊断 用故障检测仪检测,发动机控制单元中无故障代码存储;读取发动机数据流,发现进气歧管绝对压力波动明显,有时能达到69 kPa,明显偏高,推断可能的原因有:进气系统漏气;进气歧管绝对压力传感器信号失真;发动机机械故障。首先从节气门处打烟雾,没有发现进气管周围有漏气的地方;接着拔下进气管上的两个真空
    虹科Pico汽车示波器 2025-01-08 16:51 92浏览
  • 在过去十年中,自动驾驶和高级驾驶辅助系统(AD/ADAS)软件与硬件的快速发展对多传感器数据采集的设计需求提出了更高的要求。然而,目前仍缺乏能够高质量集成多传感器数据采集的解决方案。康谋ADTF正是应运而生,它提供了一个广受认可和广泛引用的软件框架,包含模块化的标准化应用程序和工具,旨在为ADAS功能的开发提供一站式体验。一、ADTF的关键之处!无论是奥迪、大众、宝马还是梅赛德斯-奔驰:他们都依赖我们不断发展的ADTF来开发智能驾驶辅助解决方案,直至实现自动驾驶的目标。从新功能的最初构思到批量生
    康谋 2025-01-09 10:04 23浏览
  • 大模型的赋能是指利用大型机器学习模型(如深度学习模型)来增强或改进各种应用和服务。这种技术在许多领域都显示出了巨大的潜力,包括但不限于以下几个方面: 1. 企业服务:大模型可以用于构建智能客服系统、知识库问答系统等,提升企业的服务质量和运营效率。 2. 教育服务:在教育领域,大模型被应用于个性化学习、智能辅导、作业批改等,帮助教师减轻工作负担,提高教学质量。 3. 工业智能化:大模型有助于解决工业领域的复杂性和不确定性问题,尽管在认知能力方面尚未完全具备专家级的复杂决策能力。 4. 消费
    丙丁先生 2025-01-07 09:25 123浏览
  • 「他明明跟我同梯进来,为什么就是升得比我快?」许多人都有这样的疑问:明明就战绩也不比隔壁同事差,升迁之路却比别人苦。其实,之间的差异就在于「领导力」。並非必须当管理者才需要「领导力」,而是散发领导力特质的人,才更容易被晓明。许多领导力和特质,都可以通过努力和学习获得,因此就算不是天生的领导者,也能成为一个具备领导魅力的人,进而被老板看见,向你伸出升迁的橘子枝。领导力是什么?领导力是一种能力或特质,甚至可以说是一种「影响力」。好的领导者通常具备影响和鼓励他人的能力,并导引他们朝着共同的目标和愿景前
    优思学院 2025-01-08 14:54 82浏览
  • 1月7日-10日,2025年国际消费电子产品展览会(CES 2025)盛大举行,广和通发布Fibocom AI Stack,赋智千行百业端侧应用。Fibocom AI Stack提供集高性能模组、AI工具链、高性能推理引擎、海量模型、支持与服务一体化的端侧AI解决方案,帮助智能设备快速实现AI能力商用。为适应不同端侧场景的应用,AI Stack具备海量端侧AI模型及行业端侧模型,基于不同等级算力的芯片平台或模组,Fibocom AI Stack可将TensorFlow、PyTorch、ONNX、
    物吾悟小通 2025-01-08 18:17 29浏览
  • 光伏逆变器是一种高效的能量转换设备,它能够将光伏太阳能板(PV)产生的不稳定的直流电压转换成与市电频率同步的交流电。这种转换后的电能不仅可以回馈至商用输电网络,还能供独立电网系统使用。光伏逆变器在商业光伏储能电站和家庭独立储能系统等应用领域中得到了广泛的应用。光耦合器,以其高速信号传输、出色的共模抑制比以及单向信号传输和光电隔离的特性,在光伏逆变器中扮演着至关重要的角色。它确保了系统的安全隔离、干扰的有效隔离以及通信信号的精准传输。光耦合器的使用不仅提高了系统的稳定性和安全性,而且由于其低功耗的
    晶台光耦 2025-01-09 09:58 21浏览
我要评论
0
点击右上角,分享到朋友圈 我知道啦
请使用浏览器分享功能 我知道啦