5.1高斯消去法解析

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,第五章,线性方程组的直接解法,第五章 线性方程组的直接解法,线性方程组的直接解法,高斯消去法,矩阵三角分解法,向量范数和矩阵范数,误差分析,3,1,2,3,3,4,线性方程组的概念,在科学研究和工程技术中所提出的计算问题中，线性,方程组的求解问题是基本的，常见的，很多问题如插值函,数，最小二乘数据拟合，构造求解微分方程的差分格式等,，都包含了解线性方程组问题，因此，线性方程组的解法,在数值计算中占有较重要的地位。,设,n,阶线性方程组,：,其矩阵形式为：,Ax=b,(5-2),其中：,求解,Ax,=,b,，,曾经学过高斯（,Gauss,）,消元法，克莱姆（,Cramer,）,法则，矩阵变换法等，但已远,远满足不了实际运算的需要，主要体现两个方面：一是运算的快速和准确，其次是方程组的个数增大时的计算问题。如何建立能在计算机上可以实现的有效而实用的解法，具有极其重要的意义，我们也曾指出过，,Cramer,法则在理论上是绝对正确的，但当,n,较大时，在实际计算中却不能用。,线性方程组的概念（续）,如果线性方程组,Ax,=,b,的系数行列式不为零，即,det(,A,),0,，,则该方程组有唯一解。,线性方程组的数值解法,解线性方程组的数值方法大致分为两类：,请注意：,由于在计算中某些数据实际上只能用有限位小,数，即不可避免地存在着舍入误差的影响，因,而即使是准确解法，也只能求到近似解。,直接法在求解中小型线性方程组（,100,个），特别是系数矩阵为稠密型时，是常用的、非常好的方法。,直接法：,指假设计算过程中不产生含入误差，经过有 限步四则运算可求得方程组准确解的方法。,2.,迭代法：,从给定的方程组的一个近似值出发，构造某种算法逐步将其准确化，一般不能在有限步内得到准确解,。,这一章介绍计算机上常用的直接法，它们都是以,Gauss,消元法为基本方法，即先将线性方程组化为等价的三角形方程组，然后求解。,AX,=,b,直接法,迭代法,是,列主元,消去法,Gauss,消去法,全主元,消去法,否,LU,分解法,是,知识结构框图,第,1,节,高斯,（,Gauss,）,消去法,高斯,（,Gauss,）,消元法,高斯消元法是一个古老的直接法,由它改进得到的选主元的消元法,是目前计算机上常用于求低阶稠密矩阵方程组的有效方法,其特点就是通过消元将,一般线性方程组,的求解问题转化为,三角方程组,的求解问题,高斯,（,Gauss,）,消去法,一、高斯消去法,，,下例说明其,基本思想,:,例,1,解线性方程组：,解：消去,x,1,，,进行第一次消元：首先找乘数，以,-12,乘第一个方程加到第二个方程，以,18,乘第一个方程加到第三个方程上可得同解方程组：,举 例,例,1,（续）,上述,Gauss,消元法的基本思想是：先逐次消去变量，将方程组化成同解的上三角形方程组，此过程称为,消元过,程,。然后按方程相反顺序求解上三角形方程组，得到原,方程组的解，此过程称为,回代过程,。,再消,一次元得：,二次消元后将方程化为,倒三角形式，然后进行,回代容易解出：,x,3,=3,x,2,=2,x,1,=1,。,我们的目的，是要总结归纳出一般情况下的,n,阶线性方程,组的消元公式和回代求解公式，从而得到求解,n,阶线性方,程组的能顺利在计算机上实现的行之有效的算法。,上三角方程组的一般形式是：,目标,高斯,（,Gauss,）,消去法,高斯,（,Gauss,）,消去法,对,n,阶线性方程组,转化为等价的,(,同解,),的三角方程组,.,称,消元过程,，逐次计算出 称,回代过程,。,高斯,（,Gauss,）,消去法,相当于第,i,个方程减第一个方程,数新的第,i,方程,同解！第一方程不动！,Gauss,消去法计算过程分析,Gauss,消去法计算过程分析,上述消元过程除第一个方程不变以外,第,2,第,n,个方程全消去了变量,1,，而系数 和常数项全得到新值：,高斯,（,Gauss,）,消去法,高斯,（,Gauss,）,消去法,高斯,（,Gauss,）,消去法,高斯,（,Gauss,）,消去法,高斯,（,Gauss,）,消去法,第,n-1,步消去过程后，得到等价三角方程组。,高斯,（,Gauss,）,消去法,高斯,（,Gauss,）,消去法,消去过程算法,高斯,（,Gauss,）,消去法,回代过程算法,高斯,（,Gauss,）,消去法,例,2,举 例,举 例,举 例,二,、,Gauss,消元法的计算量,由于在计算机中作乘除运算量所需时间远大于作加减运算所需时间，故只考虑作乘除运算量。,由消元法步骤知，第,k,次消元需作,n,k,次除法，作,(,n,k,)(,n,k,+1),次乘法，故消元过程中乘除法运算量为：,所以,Gauss,消去法的,乘除法,总运算量,为：,Gauss,法与,Cramer,法则的计算量比较,Gauss,消元法的乘,除法总运算量为,：,与我们曾经介绍的,Cramer,法则的乘除法总运算量,(,n,2,1),n,!+,n,相比，由下表可知,：,当阶数越高时，,Gauss,消,元法所需乘除法次数比,Cramer,法则要少得多：,方程组阶数,3,10,20,50,Gauss,消元法运算量,17,430,3060,44150,Cramer,法则运算量,51,359251210,9.710,20,7.610,67,Gauss,消元法的优缺点：,但其计算过程中，要求,a,kk,(,k,),（,称为主元素）均不为零，因而适用范围小，只适用于从,1,到,n,1,阶顺序主子式均不为零的矩阵,A,，,计算实践还表明，,Gauss,消元法的数值稳定性差，当出现小主元素时，会严重影响计算结果的精度，甚至导出错误的结果。,Gauss,消元法简单易行。,三、高斯消去法实现的条件,四、主元素法,4.1,引入主元素的必要性,对线性方程组,AX,=,b,，,若其系数行列式,det,(,A,),0,，,则该方程组有唯一 解，但是这一条件,不能保证所有主元素都不等于零，只要某一主元,素等于零，就不能用,Gauss,消元法求解该方程组，,即使所有主元素不等于零，但 某一主元素的绝对,值很小时，,Gauss,消元法也是不适用的。如下例,：,例,3,例,2,（续,1,）,解：为减小误差，计算过程中保留,3,位有效数字。,按,Gauss,消元法步骤：,第一次消元后得同解方程组：,第二次消元后得同解方程组,回代得解，,x,3,=2.02,，,x,2,=2.40,，,x,1,=,5.80,。,容易验证，方程组（,1,）的准确解为：,x,1,=,2.60,，,x,2,=1.00,，,x,3,=2.0,。,显然两种结果相差很大。,若在解方程组前，先交换方程的次序，如将（,1,）交换一行与二行改写成如下所示：,再用,Gauss,消元法，顺序消元后得同解方程组,：,回代得解：,x,3,=2.00,，,x,2,=1.00,，,x,1,=,2.60,与准确解相同。,例,3,（续,2,）,例,3,两种解法的误差分析,在例,3,中，对,(1),的方程进行顺序消元时，主元,a,(1),11,=0.50,，,a,(2),22,=0.100,都比较小，以它们作 除数就增长了舍入误差,而导致计算结果不准确。,产生上述现象的原因在于舍入误差，当,|,a,(,k,),kk,|,很小时，进行第,k,次消元，要用,|,a,(,k,),kk,|,作除数，这 样就可能增大舍入误差造成溢出停机，或者导致 错误的结果。,为了在计算过程中，抑制舍入误差的增长，应尽量避免小主元的出现。如例,3,的第二种解法,通过交换方程次序，选取绝对值大的元素作主元 基于这种思想而导出主元素法,。,4.2,列主元素法,为简便起见，对方,程组（,5-1,），用,其增 广矩阵：,表示，并直接在增广矩阵上进行运算。,列主元素法的具体步骤如下：,列主元素法,如此经过,n,1,步，增广矩阵（,5-3,）被化成上三角形，然后由回代过程求解,。,在上述过程中，主元是按列选取的，故称为,列主元法,。例,3,中的第二种解法就是按列主元法进行的。,4.3,全主元素法,经过,n,k,次消元后，得到与方程组（,5-1,）同解的上三角形方程组，再由回代过程求解。,主元素法举例,例,4,计算过程保留三位小数。,此例的计算结果表明，全主元素法的精度略优于列主元法，这是由于全主元法是在全体元素中选主元，故它对控制舍入误差十分有效。但是全主元法在计算过程中，需同时作行与列的互换，因而程序比较复杂,计算时间较长。列主元法的精度虽稍低于全主元法，但其计算简单，工作量大为减少，且计算经验与理论分析均表明，它与全主元法同样具有良好的数值稳定性，故列主元法是求解中小型稠密线性方程组的最好方法之一。,方法之一。,1.,用高斯消元法解方程组,2.,用列主元素法解方程组：,作 业,