5.1高斯消去法解析
- 格式:ppt
- 大小:1.68 MB
- 文档页数:38
高斯消除法高斯消除法是一种解线性方程组的常用方法。
它的基本思想是通过一系列的行变换将线性方程组化为上三角形式,从而求得方程组的解。
本文将详细介绍高斯消除法的原理和步骤,并通过一个具体的例子来演示其应用。
一、高斯消除法的原理高斯消除法的核心思想是利用行变换将线性方程组化为上三角形式。
其基本原理可以概括为以下几点:1. 首先,将线性方程组的系数矩阵进行增广,得到一个增广矩阵。
2. 选择一个主元素,一般选择第一行的第一个非零元素作为主元素。
3. 通过行变换,将主元素所在列的其他元素消为零。
4. 重复上述步骤,选择一个新的主元素,直到将矩阵化为上三角形式。
5. 对上三角矩阵进行回代,得到线性方程组的解。
下面我们通过一个具体的例子来演示高斯消除法的步骤。
假设有如下线性方程组:2x + 3y - z = 10x - y + 2z = -13x + 2y - 3z = 51. 首先,将系数矩阵进行增广,得到增广矩阵:[ 2 3 -1 | 10 ][ 1 -1 2 | -1 ][ 3 2 -3 | 5 ]2. 选择第一行的第一个非零元素2作为主元素。
3. 第一步消元:将第二行乘以2,减去第一行,得到新的第二行:[ 2 3 -1 | 10 ][ 0 -7 4 | 19 ][ 3 2 -3 | 5 ]将第三行乘以3,减去第一行,得到新的第三行:[ 2 3 -1 | 10 ][ 0 -7 4 | 19 ][ 0 -7 0 | -5 ]4. 选择第二行的第二个非零元素-7作为主元素。
5. 第二步消元:将第三行乘以(-1),加上第二行,得到新的第三行:[ 2 3 -1 | 10 ][ 0 -7 4 | 19 ][ 0 0 4 | 14 ]6. 至此,已将矩阵化为上三角形式。
接下来进行回代,求解方程组的解。
由最后一行可知,4z = 14,即z = 14/4 = 3.5。
将z的值代入第二行的方程中,可得-7y + 4z = 19,即-7y + 4*3.5 = 19,解得y = -3。
数值计算高斯消去法和高斯-塞德尔迭代法摘要虽然已学过加减消元法、代入消元法、矩阵变换法和Cramer 法则等,但是无法满足实际计算需要,故在此讨论在计算机上实现的有效而实用的解法。
线性方程组的解法大致分2类:直接法(高斯消去法)和迭代法(高斯-赛德尔迭代法),在此对着此类算法进行比较分析。
一、算法设计当计算线性方程组如下时,11112211211222221122n n n n n n nn n na x a x a xb a x a x a x b a x a x a x b +++=⎧⎪+++=⎪⎨⎪⎪+++=⎩ (1-1)为方便起见,常将线性方程组表示成矩阵形式Ax b=其中1111n n nn a a A a a ⎡⎤⎢⎥=⎢⎥⎢⎥⎣⎦1n x x x ⎡⎤⎢⎥=⎢⎥⎢⎥⎣⎦1n b b b ⎡⎤⎢⎥=⎢⎥⎢⎥⎣⎦并始终假定A 是非奇异的,即方程组的解存在且唯一。
1.1高斯消去法消去法就是按特定顺序进行的矩阵初等变换法,当消元按自然顺序进行时,称为高斯顺序消去法。
一般情况下的高斯顺序消去法的计算机算法如下,现将方程组(1-1)的增广矩阵记作(0)(0)(0)11111(0)(0)(0)11n n n nn nn a a a a a a ++⎡⎤⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦假设经k-1步消元后,增广矩阵化为(0)(0)(0)(0)1112111(1)(1)(1)22221(1)(1)(1)1(1)(1)(1)1nn nn k k k kk knkn k k k nk nnnn a a a a a a a a a a a a a ++---+---+⎡⎤⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦其中()s ij a 的上标表示是由s 步消元得到的植。
第k 步消元:设(1)0k kk a -≠,以第k 行为基础,将以后各行中的(1)k ik a -化为0,为此先计算(1)(1)/k k ik ik kk l a a --=然后以第i 行减去第k 行乘以ik l ,即以()(1)(1)k k k ij ij ik kj a a l a --=-()()1,,11,,j k n i k n =++=+于是得(0)(0)(0)11111(1)(1)(1)(1)11()()()11111()()()11n n k k k k kkkk knkn k k k k k k nk n k k k k nnnnn a a a a a a a a a a a a a +----+++++++++⎡⎤⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦经n-1步消元后,增广矩阵化为(0)(0)(0)11111(1)(1)(1)1(1)(1)1n n k k k kk knkn n n nn nn a a a a a a a a +---+--+⎡⎤⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦自下往上逐步回代即可求得其解(1)(1)1(1)(1)(1)11/()/(1,2,,1)n n n nn nnnk k k k kn kj j kk j k x a a x aax a k n n --+---+=+==-=--∑由行列式的初等变换和矩阵初等变换的关系可知,顺序消元法的每一步系数行列式之值不变,因此原方程组之系数行列式的值为(0)(2)(1)1122n nn a a a - ,可在求解过程中逐步累乘求得。
高斯消去法高斯消去法,又称高斯消元法,实际上就是我们俗称的加减消元法。
数学上,高斯消去法或称高斯-约当消去法,由高斯和约当得名(很多人将高斯消去作为完整的高斯-约当消去的前半部分),它是线性代数中的一个算法,用于决定线性方程组的解,决定矩阵的秩,以及决定可逆方矩阵的逆。
当用于一个矩阵时,高斯消去产生“行消去梯形形式”。
目录例如信息学方面的应用下面介绍一下矩阵的初等行变换:对于增广矩阵A求解线性方程组的步骤:历史编辑本段例如一个二元一次方程组,设法对每个等式进行变形,使两个等式中的同一个未知数的系数相等,这两个等式相减,得到一个新的等式,在这个新的等式中,系数相等的未知数就被除去了(系数为0)。
同样的也适合多元多次方程组。
编辑本段信息学方面的应用高斯消元是求解线性方程组的重要方法,在OI中有广泛的应用。
本文就来讨论这个方法。
什么是线性方程组?含m个方程和n个未知量的方程组定义为a(11)x(1)+a(12)x(2)+...+a(1n)x(n)=b(1)a(21)x(1)+a(22)x(2)+...+a(2n)x(n)=b(2)...a(m1)x(1)+a(m2)x(2)+...+a(mn)x(n)=b(m)这个方程组称为m*n线性方程组,其中a(ij)和b(i)为实数,括号中为下标。
这个方程组有多种表示方法。
例如,我们知道m*n矩阵(用大写字母表示)是一个m行n列的数阵,n维向量(用加粗的小写字母表示)是n个数的数组,也就是一个n*1矩阵(列向量。
我们不考虑行向量)。
另外,大家也都知道矩阵乘法。
因此一个m*n线性方程组可以表示为Ax=b,其中A是由系数aij组成的m*n矩阵即系数矩阵,x是n维的未知数向量,b是m维的结果向量。
如果把向量b写到A的右边得到m*(n+1)的矩阵,得到的新矩阵称为这个方程组的增广矩阵。
每一个方程组均对应于一个增广矩阵。
编辑本段下面介绍一下矩阵的初等行变换:1 交换两行2 用非零实数乘以任一行3 把某一行的倍数加到另一行上同理可以定义初等列变换。
高斯消元法线性方程组的解法高斯消元法是一种常用于解决线性方程组的方法,能够有效地求解方程组的解。
它利用矩阵的初等行变换将方程组转化为简化的阶梯型矩阵,进而求得方程组的解。
本文将介绍高斯消元法的原理和步骤,并通过一个具体的例子来演示如何使用高斯消元法求解线性方程组。
一、高斯消元法的原理高斯消元法基于以下原理:通过矩阵的初等行变换,可以将线性方程组转化为行简化阶梯型矩阵,从而得到方程组的解。
其基本思想是通过逐行消元,将矩阵的主对角线以下的元素全部变为0,最终得到行简化阶梯型矩阵。
二、高斯消元法的步骤1. 将线性方程组的系数矩阵和常数矩阵合并为增广矩阵;2. 选择一个元素作为主元,并将该列的其他元素消为0;3. 逐行进行行交换,使主元非零;4. 重复上述步骤,直到将增广矩阵转化为行简化阶梯型矩阵。
三、高斯消元法的具体操作为了更好地理解高斯消元法,我们将通过一个具体的例子来演示其求解过程。
考虑以下线性方程组:```2x + 3y - z = 13x - 2y + 5z = -2x + y - z = 0```首先将系数矩阵和常数矩阵合并为增广矩阵:```[2 3 -1 | 1][3 -2 5 | -2][1 1 -1 | 0]```选择第一行的第一个元素2作为主元,通过初等行变换将主元所在列的其他元素消为0:```[2 3 -1 | 1][0 -13 7 | -5][0 -1 1 | -1]```接下来选择第二行的第二个元素-13作为主元,通过初等行变换继续消元:```[2 3 -1 | 1][0 1 -7/13 | 5/13][0 0 -6/13 | -8/13]```最后一次消元选择第三行的第三个元素-6/13作为主元:```[2 3 -1 | 1][0 1 -7/13 | 5/13][0 0 1 | 4/3]```现在我们得到了行简化阶梯型矩阵,接下来可以使用回代法求解方程组。
从最后一行开始,依次代入上一行的解,最终求得方程组的解为:```x = 5/6y = 3/2z = 4/3```四、总结高斯消元法是一种常用的线性方程组解法,通过矩阵的初等行变换将方程组转化为行简化阶梯型矩阵,进而求得方程组的解。
高斯消去法解方程组
高斯消去法是数值计算中一种解线性方程组的标准算法,由查尔斯·高斯在 18 年发明,是向量空间下线性方程组的计算最有效的算法。
它利用线性变换(例如交换、加减乘除),逐步将线性方程组化简成上三角形形式进而得到解,称为高斯消去法。
其核心思想是:由方程组的关系式可得出系数矩阵,采用层层消去的方法使其变成上三角矩阵,再解出解向量。
高斯消去法的具体步骤是:
(1)以第一列为基元,化为消去向量,即第一列第一项(用a表示)对应的消去系数,然后将其他行的第一项做除法,消去第一列。
(2)以第二列为基元,化为消去向量,消去其余行第二项。
(3)以此类推,以每一列为基元,化为消去向量,将其
余行此列之项全部消去;直至消去完毕。
(4)最后一步是逆序求出解向量。
由最后一个方程式,
可直接求出最后一列解向量(用x表示)特征值,若n表示方程组的阶数,则n=1时即可求得解向量的所有特征值,若n>1,则逆序回代求出前面的特征值。
高斯消去法解线性方程组的算法比较简单,易于理解,
但它会遇到数值误差、文本输入错误等问题,所以在使用高斯消去法时,应当注意它的准确性,以及在使用这种解法时可能出现的数值不稳定性。
此外,高斯消去法的效率较低,其计算
时间与方程组系数的规模呈指数增长关系,因此也可以通过其他算法来求解线性方程组,如 LU 分解等。