方程组-Gauss消去法.ppt

引言,高斯消去法,选主元素的高斯消去法,矩阵的三角分解,解三对角方程组的追赶法,第六章 方程组的数值解法,解对称正定方程组的平方根法,解线性方程组的迭代法,病态方程组和迭代改善法,向量和矩阵的范数,第一节 引言,实际问题中的线性方程组分类：,按系数矩阵中零元素的个数：,稠密线性方程组,稀疏线性方程组,按未知量的个数：,高阶线性方程组,低阶线性方程组,(如1000),(80%),按系数矩阵的形状,对称正定方程组,三角形方程组,三对角占优方程组,1、消元与回代计算,对线性方程组,对其增广矩阵施行行初等变换:,1、Gauss消去法直接法,定义行乘数,且,定义行乘数,上述过程的求解过程叫做回代过程,定理1：如果A为n阶非奇异矩阵，则可通过Gauss消去法将方程组的系数阵化为三角型系数阵。,定理2：如果n阶矩阵A的所有顺序主子式均不为零，则可通过Gauss消去法，将方程组的系数阵化为三角型系数阵。,直接法是将原方程组化为一个或若干个三角形方程组的方法，共有若干种,对于线性方程组,系数矩阵,未知量向量,常数项,2、矩阵的三角分解直接法,根据Cramer(克莱姆)法则,若,若用初等变换法求解,则对其增广矩阵作行初等变换:,同解,即,以上求解线性方程组的方法称为Gauss消去法,则,都是三角形方程组,上述方法称为直接三角形分解法,-(2),Gauss消元过程与系数矩阵的分解,Gauss消去法消元过程的矩阵描述,行变换相当于左乘初等矩阵,由于,令,则,显然若令,故:,因此:,从而:,即,且,顺序主元,定义1.不带行交换的Gauss 消去法的消元过程,产生一个单位下三角矩阵L和一个上三角矩阵U,即该过程称之为,由上述分析不难得到,Gauss消去法可以执行,定理1.,在定理中,可能注意到,可能存在,不论是Gauss消去法还是直接三角形分解法,最都归结为解三角形方程组,2、三角形线性方程组的解法,若记,下三角形线性方程组,上三角形线性方程组,其解为,其解为:,3、Gauss消去法的运算量,计算机作乘除运算所耗时间要远远多于加减运算,且在一个算法中，加减运算和乘除运算次数大体相当,故在衡量一个算法的运算量时只需统计乘除的运算次数,乘法次数：,除法次数：,全部回代过程需作乘除法的总次数为,于是Gauss消去法的乘除法运算总的次数为,数级,Gauss消去法乘除法约为2700次,而如果用Cramer法则的乘除法运算次数约为,或,用行列式定义,用行列式性质,例1.,用Gauss消去法解线性方程组(用3位十进制浮点数计算）,解:,本方程组的精度较高的解为,用Gauss消去法求解(用3位十进制浮点数计算),1、Gauss列主元消去法的引入,3 选主元素的Gauss消去法,9999,回代后得到,与精确解相比,该结果相当糟糕,究其原因,在求行乘数时用了很小的数0.0001作除数,主元,如果在求解时将1,2行交换,即,0.9999,回代后得到,这是一个相当不错的结果,例2.,解线性方程组(用8位十进制尾数的浮点数计算),解:,这个方程组和例1一样,若用Gauss消去法计算会有小数作除数的现象,若采用换行的技巧,则可避免,经过回代后可得,事实上,方程组的准确解为,例2所用的方法是在Gauss消去法的基础上,利用换行避免小主元作除数,该方法称为Gauss列主元消去法,开始,输出无解信息,消元,换行,停机,回代求解,Gauss列主元消去法的算法设计,(一)流程图,