高斯消元算法

来自计算思维百科
跳转至: 导航搜索
高斯消元算法1.png

高斯消元法(又称高斯消去法,GaussElimination)以德国数学家高斯命名,通常用来求解线性方程组。

基本概念

算法思想:

高斯消元法的思路是把n个线性方程构成的n元线性方程组变换成一个等价的方程组(方程组的解和原来方程组的解一致),如下所示。该等价方程组有一个上三角系数矩阵即矩阵主对角线下方元素全为0。

高斯消元算法2.png

我们可以用矩阵的符号来表示,对于任意一个n元线性方程组,都可写成Ax=b形式,其中A代表方程组的系数矩阵,表示成高斯消元算法3.png,b代表列向量,表示成(b1,b2,...,bn)。经过矩阵的初等变换之后,系数矩阵A则变为上三角矩阵高斯消元算法4.png,列向量b随之也改变,但是该上三角矩阵所对应的方程组与原方程组等价。

接着根据变换后的方程组,从最后一个方程开始,可以计算出xn,将xn代入倒数第二个方程可以计算出xn-1,将xnxn-1代入倒数第三个方程可以计算出xn-2,依次类推可以将方程组的解求出,此过程叫做“回代法”。

运用举例:

利用高斯消元法解下列线性方程组。

高斯消元算法5.png

该线性方程组的增广矩阵为

高斯消元算法10.png

应用范围

高斯消元法是一种十分有用的算法,它可以解决应用数学中最重要的问题之一:解线性方程组。实际上,高斯消元法也可以应用于线性代数的其他若干问题,比如计算判断矩阵是否可逆,计算矩阵的逆。

应用1-鸡兔同笼

我们都知道鸡兔同笼问题,这个问题的解就是通过列方程求解的。但是如果笼子里关了很多种动物,列方程的方法就会得到一个很大的方程,求解这个方程就可以利用高斯消元来完成。

可以运用的计算思维

所谓变治就是打破固有思维,开辟新的解决方法。变治基于变换的思想分两个阶段,即“变”阶段和“治”阶段。变治法有三种类型:实例化简、改变表现、问题化简。高斯消元法主要体现变治法的“改变表现”类型,利用初等变换改变系数矩阵的表现形式使得问题得到更好地解决。美国漫画家Charles M.Schulz(史努比之父)是这样解释变治法的:That’s the secret to life…replace one worry with another。变治法不仅仅应用在计算机学科中,在其他领域,只要是遇到难以解决的问题,不妨打破固有思维,另辟蹊径,也许换种思考方式就能找到解决办法。高斯消元法体现的计算思维的转化特点。