高斯消去法PPT课件

5.2Gauss消去法,5.2.4Gauss-Jordan消元法,5.2.3主元素消去法,5.2.2矩阵的三角分解,5.2.1Gauss消去法的计算过程,第5章线性方程组的直接解法,教学目的1.掌握解线性方程组的高斯消去法、高斯选主元素消去法；2.掌握用直接三角分解法解线性方程组的方法；3.了解解对称正定矩阵线性方程组的平方根法与解三对角线方程组的追赶法；5.掌握向量，矩阵范数，矩阵的条件数等概念及方程组的扰动分析。教学重点及难点重点是1.解线性方程组的高斯消去法、高斯选主元素消去法；2.直接三角分解法解线性方程组的方法；3.向量，矩阵范数，矩阵的条件数等概念及方程组的扰动分析；难点是方程组的扰动分析。,在工程技术、自然科学和社会科学中，经常遇到的许多问题最终都可归结为解线性方程组，如电学中网络问题、用最小二乘法求实验数据的曲线拟合问题，工程中的三次样条函数的插值问题，经济运行中的投入产出问题以及大地测量、机械与建筑结构的设计计算问题等等，都归结为求解线性方程组或非线性方程组的数学问题。因此线性方程组的求解对于实际问题是极其重要的。,第5章线性方程组的直接解法,(DirectMethodforSolvingLinearSystems),在工程实际问题中产生的线性方程组，其系数矩阵大约有两种：一种是低阶稠密矩阵(阶数n150，矩阵的全部元素都可能贮在计算机中)；另一种是大型高阶稀疏矩阵(矩阵元素中零元素较多，阶数较高，如n=103或104等，这类矩阵一般要压缩存储或仅存储系数矩阵中的非零元素),关于线性方程组的数值解法有两大类：,直接法：就是经过有限步算术运算，可求得方程组精确解的方法(若计算过程中没有舍入误差)，如克莱姆法则就是一种直接法，但实际上由于舍入误差的存在，这类方法也只能求得线性方程组的近似解。直接法中具有代表性的算法是高斯(Gauss)消去法。其特点是准确，可靠，理论上得到的解是精确的.这类方法是解低阶稠密矩阵方程组的有效方法.,迭代法是解大型稀疏矩阵方程组的的重要方法.,迭代法：(第六章介绍）就是用某种极限过程去逐步逼近线性方程组的精确解的方法。也就是从解的某个近似值出发，通过构造一个无穷序列去逼近精确解的方法。(一般有限步内得不到精确解).特点是速度快，但有误差.,本章讲解直接法.,对于中小型方程组，常用直接解法。从本质上来说，直接方法的原理是找一个可逆矩阵M，使得MA是一个上三角阵，这一过程一般称为“消元”过程，消元之后再进行“回代”，即求解MAx=Mb。本章讨论Gauss消去法及其变形，以及一些情况下的特殊方法，最后进行误差分析。,设线性方程组为,或写成矩阵形式或简单地记为:,5.2Gauss消去法,1Gauss消去法的步骤,消元过程就是要按确定的计算过程对方程组进行初等行变换,将方程组化为上三角方程组.,步骤如下：,运算量：(n-1)*(1+n),第一步消元：设，计算因子,其中,运算量：(n-2)*(1+n-1)=(n-2)n,第二步：设，计算因子,其中,第k步：设，计算因子,将增广矩阵的第i行-lik第k行，得到：,其中,运算量：(nk)*(1nk1)=(nk)(nk2),(5.2.2),n1步以后，我们可以得到变换后的矩阵为：,这就完成了消元过程。,(5.2.3),回代过程：,以上由消去过程和回代过程合起来求解（5.2.1）的过程就称为Gauss消去法，或称为顺序Gauss消去法。,(5.2.5),总结上述讨论即有以下定理：,算法.,例5.1用Gauss消去法解方程组,解第一步消元,令得增广矩阵,第二步消元，令得增广矩阵,利用回代公式（5.2.4）依次得到,在这个例子中我们写出的是分数运算的结果。如果在计算机上进行计算，系数矩阵和中间结果都用经过舍入的机器数表示，中间结果和方程组的解都会有误差。,矩阵A在什么条件下才能保证,0,(k=1，2，n)?,下面的定理给出了这个条件。,引理5.1约化的主元素,O(i=1，2，n)的充要,条件是矩阵A的顺序主子式,Di0,(i=1,2,n)。,即:,约化的主元素,证先证必要性设，则可进行k-1步消元。显然，对，由于每步进行的初等变换不改变顺序主子式的值，所以第i-1步消元后有,用归纳法证充分性。k=1时，命题显然成立。设命题对m-1成立。已知由归纳假设有Gauss消去法可进行第m-1步，矩阵A变换为,其中是对角元素为的上三角阵。因是通过消元过程由A逐步经初等变换得到的，A的m阶顺序主子式等于的m阶顺序主子式，即由可推出，定理得证。,定理5.2:,如果n阶矩阵A的所有顺序主子式均不为零，,即Di0(i=1,2,n),，则可通过高斯,消去法(不进行交换两行的初等变换)求解方程组(5.2.1)。,特别地，若A为对称正定矩阵，则由对称正定矩阵的性质可知，对原方程组不必作任何处理，可直接用Gauss消去法求解方程组。,推论:若,高斯消元法运算量：,消元过程：乘：除：回代过程：运算量：,高斯消元法的局限性：,在高斯消元过程中，我们假定了对角元素由于每次消元时是按未知量的自然顺序进行的，而顺序消元不改变A的主子式的值，因此高斯消元法可行的充分必要条件为A的各阶主子式不为零。实际上只要detA0，方程组就有解。2.即使高斯消元法可行，如果很小，运算中用它作分母会导致其它元素数量计的严重增长和舍入误差的扩散。,例解方程组精确解为：x1=1/3，x2=2/3。计算取5位有效数字。,解1顺序消元：解2交换方程的顺序：经高斯消元：,这个例子告诉我们，在采用高斯消去法解方程组时，小主元可能导致计算失败，故在消去法中应避免采用绝对值很小的主元素。,方法1计算失败的原因，是用了一个绝对值很小的数作除数，乘数很大，引起约化中间结果数量误差很严重增长，再舍入就使得计算结果不可靠了。,对一般矩阵方程组，需要引进主元的技巧，即在高斯消去法的每一步应该选取系数矩阵或消元后的低阶矩阵中的绝对值最大的元素作为主元素，保持乘数，以便减少计算过程中的舍入误差对计算解的影响。,一、列主元消去法,设有线性方程组：AX=b,第一步:先在A的第一列选取绝对值最大的元素作主元素,然后交换第1行和第i1行(当i11时),再进行第1次消元.,第k步选主元素,然后交换第k行和第ik行(当ikk时),再进行第k次消元.,第n-1步,回代求解,算法(列主元消去法).,(见P李庆扬177),完成了n-1步主元，换行与消元运算后，得到，这是与原方程组等价的方程组,是一个上三角阵,再代回求解.这就是列主元素消去法的计算过程.,除了列主元素消去法外,还有一种完全主元素消去法.在其过程的第k步，不是按列来选主元，而是在右下角的n-k+1阶子阵中选主元,即然后将的第行与第k行交换，将第列与第k列交换,同时将自变量与的位置交换并记录自变量的排列次序.直到消去法完成后,再按记录恢复自变量为自然次序.完全主元法比列主元法运算量大得多,由于列主元法的舍入误差一般已较小,所以在实际计算中多用列主元法.,例5.3用列主元素消去法解方程组Ax=b,计算过程中五位有效数字进行运算,其中,消去过程至此结束。回代计算依次得到解这个例题的精确解是而用不选住主元的顺序Gauss消去法，则解得,这个结果误差较大，这是因为消去法的第1步中，按绝对值比其他元素小很多所引起的。从此例看到去列主元素消法是有效的方法。,解：精确解为（舍入值）：,例5.4：用列主元消去法去解方程组,本例是具有舍入的4位浮点数进行运算，所得的计算解还是比较准确的。,列主元素消去法步骤：,设Ax=b。对于具有行交换的列主元素消去法，消元结果冲掉A，乘数mij冲掉aij，计算解X冲掉常数项b,行列式存在det.,1,1det,k=1（对k=1n-1做27步。）,3，若aik,k=0,则0det.计算终止。,5，计算乘数mik,mik=aik/akkaik.(i=k+1n)(|mik|1),6,消元计算：aij-mikaijaij(i,j=k+1,n)bi-mikbkbi(i=k+1,n),优点：,数值稳定。,修正方法：,列主元高斯-约当（Gauss-Jordam）消去法。,缺点：,既消元；又回代。,5.2.4*Gauss-Jordan消元法（可不讲，自学）,高斯消去法有消元和回代两个过程，消去的是对角线下方的元素。当对消元过程稍加改变便可使方程组化为对角阵,（5.2.9）,这时求解就不需要回代了,这种将主元素化为1,并用主元将其所在列的冗余元素全都消为0,即消去对角线上方与下方的元素,这种方法称为高斯-约当消去法,这时等号右端即为方程组的解,在第k步计算时，考虑对上述矩阵的第k行上、下都进行消元计算（k=1,2n）,2，换行（当ikk）。交换A,b第k行与第ik行元素。,3，计算乘数mik=-aik/akk(i=1n,ik),mkk=1/akk(mik可存放在aik的单元中)（|mik|1）,上述过程全部执行完后有：,这表明用GJ方法将A约化为单位矩阵，计算解就在常数项位置得到，因此用不着回代求解。用GJ方法接方程组的计算量大约需要次乘除法，要比Gauss消去法大些。,例5.4用高斯-约当(Jordan)消去法求方程组的解,解方程组相应的增广矩阵,列选主元,故得,说明：,因此，可以用来求逆矩阵。,不用回代，将A化为单位矩阵，则解为常数项列。,优点：,缺点：,因为计算量太大，但是在解多个方程组而它们的系数矩阵相同时，,高斯-约当(Jordan)消去法,定理5.5设A为为n阶非奇异矩阵，方程组Ax=I的增广矩阵为C=（A，I）。如果对C用Gauss-Jordan消去法化为（I，T），则.,证设,则这里，为单位矩阵I的第j列，用Gauss-Jordan消去法解方程组,其解在C中I的第j列，即为T的第j列，即.因此.定理得证.,例5.用Gauss-Jordan消去法求矩阵的逆矩阵。,解用列主元素消去法有,在实际计算中，为了节省内存单元，单位矩阵不必存放。在上例中，可将的最后一列放在A第1列，将的第5列存放在A的第2列，将的第4列存在A的第3列。一般地，第k步消元时，可将A的第k列,5.基于初等变换的矩阵的三角分解,下面建立高斯消去法与矩阵的因式分解的关系.,称该式为A的LU分解。,分解式A=LU也称为杜里特尔(Doolittle)分解。由A=LU式可求出A的行列式，即,若将上三角U写成，其中D是对角阵，是单位上三角阵，则有称该式为A的LDU分解，显然，这种分解具有唯一性。,（5.2.9）,如果A的各阶主子式不为零，则可以实现：,一旦实现A=LU，则Ax=b可以化为LUx=b。令Ux=y，则Ly=b。由Ly=b，解出y；再由Ux=y，解出x。,（）库朗(Courant)分解：如果L为下三角矩阵，U为单位上三角矩阵。,（）多利特尔(Doolittl