第四章 高斯消元法与选主元

单击以编辑,母版标题样式,单击以编辑母版文本样式,第二级,第三级,第四级,第五级,*,关键词：,高斯消去法，主元消去法,高斯消元法与选主元,高斯消元法是一种古老的直接法,由它改进得到的选主元消元法,是目前计算机上常用于求解低阶稠密矩阵方程组的有效方法,其特点就是通过消元将,一般线性方程组,的求解问题转化为,三角方程组,的求解问题,一 问题的描述,(,一,),引言,为便于以下讨论,把涉及到的有关名词及问题的引出暂介绍如下,:,如果未知量的个数为,n ,而且关于这些未知量,x,1,x,2,x,n,的幂次都是一次的,(,线性的,),那末,n,个方程,a,11,x,1,+a,12,x,2,+ +a,1n,x,n,=b,1, ,(1),a,n1,x,1,+a,n2,x,2,+ ,+a,nn,x,n,=,b,n,构成一个含,n,个未知量的线性方程组,称为,n,阶线性方程组,其中,系数,a,11,a,1n,a,21, ,a,2n, ,a,n1, ,a,nn,是给定的常数;,b1, ,b,n,也是给定的常数,通常称为,常数项,或称为,方程组的右端,.,方程组,(1),也常用矩阵的形式表示,写为,Ax=b,其中,A,是由系数按次序排列构成的一个,n,阶矩阵,称为方程组的,系数矩阵,x,和,b,都是,n,维向量,称为方程,组的解向量和右端向量，即,使方程组,(1),中每一个方程都成立的一组数,x,1,*,x,2,*,x,n,*,称 为式,(1),的解,把它记为向量的形式,称为,解向量,.,我们总是希望方程组有解,且有唯一解,.,由线性代数的,克莱姆,(,cramer),规则,可知,如果方程组,(1),的系数矩阵,A,的行列式(一般记为,D=|A|),不等于零,那末,这个方程组有唯一解,而且它们可以表示为,x,i,=,D,i,/,D,(i=1,2,n),这里,D,i,是指,D,中第,i,列元素用右端,b,1,b,2,b,n,代替构成的行列式,.,如果方程组,(1),有唯一解,我们按上面的等式求解,就必须计算,n+1,个,n,阶行列式,.,由行列式的定义,n,阶行列式包含有,n!,项,每一项含有,n,个因子,计算一个,n,阶行列式就需要做,(,n-1)n!,次乘法,.,而我们一共要计算,n+1,个,n,阶行列式,共需做,(,n,2,-1)n!,次乘法,.,此外,还要做,n,次除法才能算出,x,i,(i=1,2,n,).,也就是说,用这个办法求解就要做,N,=(n,2,-1)n!+n,次乘除法运算,这个计算量是大得惊人的,.,例如,当,n=10(,即求解一个含,10,个未知量的方程组,),乘除法的运算次数共为,32659210,次,;,当,n=40,乘除法运算次数可达,3.18,10,49,次,.,对于上百个未知量的方程组,次数运算量就更大了,.,因此,克莱姆规则,在理论上尽管是完善的,但在实际计算中却没有什么实用价值,.,本文我们将重点讨论求解线性方程组的一种有效的数值方法,.,(,二,),求解线性方程组的消元法,消,(,元,),去法是求解线性方程组,Ax=b (3),和,满秩矩阵的逆阵,A,-1,的一种直接方法,.,尽管它比较古老,但它具有演算步骤,推算公式都系统化的特点,(,对其中选主元消去法,还可以证明是稳定的,).,因此,它至今仍然是求解方程组的一种有效的方法,.,消去法可以引出几种计算方法,下面按三角形方程组和一般线性方程组的顺序来讨论,.,1.,三角形方程组的解法,三角形方程组包括上三角形方程组和下三角形方程组，它是最简单的线性方程组之一，实际上消元法就是通过简化一般线性方程组为三角形方程组后再求解的。上三角方程组的一般形式是,：,2.,Gauss,消元法,(,一,),高斯消去法的求解过程,可大致分为两个阶段,:,首先,把原方程组化为上三角形方程组,称之为,“,消去,(,消元,)”,过程,;,然后,用逆次序逐一求出三角方程组,(,原方程组的等价方程组,),的解,并称之为,“回代,”,过程,.,下面分别写出,“消去,(,消元,),”,和,“回代,”,两个过程的计算步骤,.,消去,(,消元,),过程,:,第一步,:,设,a,11,0,取,做(消去第,i,个方程组的,x,1,),m,i1,第一个方程+第,i,个方程,i=2,3,n,则第,i,个方程变为,因为,可得第一步消元后的方程组为,i,j=2,3,n,i,j=2,3,n,第二步,:,设,取,做(消去第,i,个方程组的,x,2,i=3,4,n),m,i2,第二个方程 + 第,i,个方程,i=3,4,n,类似可得第二步消元后的方程组为,第,k,步,:,设,取,做(消去第,i,个方程组的,x,k,i=k+1,k+2,n),m,ik,第,k,个方程 + 第,i,个方程,i=,k+1,k+2,n,类似可得第,k,步消元后的方程组为,继续下去到第,n-1,步消元,可将线性方程组化为如下上三角方程组,:,3.,选主元,例,3:,考虑如下线性方程组的,Gauss,消元法,求解性,2x,2,=1,2x,1,+3x,2,=2,解,:,因为,a,11,= 0 ,故此题不能用,Gauss,消元,法求解,但交换方程组的顺序后,即,2x,1,+3x,2,=2,2x,2,=1,就可,用,Gauss,消元,法求解了,.,例题,4:,讨论下面方程组的解法,0.0001,x,1,+x,2,=1,x,1,+x,2,=2,假设,求解是在四位浮点十进制数的计算机上进行,0.1000,10,-3,x,1,+ 0.1000,10,1,x,2,= 0.1000,10,1,0.1000,10,1,x,1,+0.1000,10,1,x,2,= 0.2000,10,1,解,:,本题的计算机机内形式为,因为,a,11,=0.0001,0,故可用,Gauss,消元法求解,进行第一次消元时有,a,22,(1),=,0.1000,10,1,- 10,4,0.1000,10,1,(m,21,=a,21,/a,11,=1/0.0001= 10,4,),= 0.00001,10,5,- 0.1000,10,5,(,对阶计算),= 0.0000,-,0.1000,10,5,=,-,0.1000,10,5,得三角方程组,0.1000,10,-3,x,1,+ 0.1000,10,1,x,2,= 0.1000,10,1,-0.1000,10,5,x,2,= -0.1000,10,5,回代解得,x,2,=1 ,x,1,=0,严重失真,!,(,因为本题的准确解为,x,1,=10000/9999, x,2,=9998/9999,列主元基本思想及程序框图,用高斯消去法求解线性方程组时,应避免小的主元,.,在实际计算中,进行第,k,步消去前,应该在第,k,列元素,a,ik,(i=k,n),中找出绝大值最大者,例如,a = max a ,再把第,p,个方程与第,k,个方程组进行交换,使,a,pk,(k-1),成为主元,.,我们称这个过程为,选主元,.,由于只在第,k,列元素中选主元,通常也称为,按列选主元,(,或称,部分选主元,),.,如果在第,k,步消去前,在第,k,个方程到第,n,个方程所有的,x,k,到,x,n,的系数,a (i=k,n;j=k,n),中,找出绝对值最大者,例如,a =maxa ,再交换第,k,p,两个方程和第,k,q,两个未知量的次序,使,a,成为主元,.,称这个过程为,完全选主元,.,不论是哪种方式选出主元,而后再按上面介绍的计算步骤进行消去的计算,一般都称为,选主元的高斯消去法,.,在实际计算中,常用按列选主元的高斯消去法,.,(k-1),(k-1),pk,(k-1),ik,kin,(k-1),pq,(k-1),ij,ki,jn,(k-1),ij,(k-1),pq,如：经第一次消元后，增广矩阵为：,则：,列主元消元法：,从 这一列中选取一个主元,素，作为第二次消元的开始；,全主元消元法：,从,这一子矩阵中选取一个主元素，作为第二次消元的开始；,用列主元消去法解线性方程组,AX=b,的程序框图见右图,.,图中,w,作控制常数,通常为比较小的正实数,当某个选出的主元或完成消元后的系数,a,nn,的绝对值小于,w,时,就认为,detA0,从而终止计算,.,为了节省工作单元图中还用,A,(k),冲掉,A,b,(k),冲掉,b,并注意,A,到的下三角部分都应变为零,而且在第,k,次消元计算式算出乘数,m,ik,后,a,ik,不再起作用,故用,m,ik,冲掉,a,ik,回代后所得到的解放在数组,b,内,kn-1,输入,n,A,b,w,k=1,2,n-1,选主元,确定,i,k,使,|,a,i,k,k,(k),|= max |a,i,k,(k),| (kin,),i,k,=k,|a,i,k,k,(k),|w,交换行,a,i,k,k,a,kj,(j=1,2,n),b,i,k,b,k,消元计算,a,ik,a,ik,/,a,kk,a,ij,a,ij,-a,ik,a,kj,b,i,b,i,-a,ik,b,k,(i=k+1,n),(j=k+1,.n),|,a,nn,|w,Stop,输出,detA,=0,输出结果,bi,(i=1,2,n),回代求解,b,n,b,n,/,a,nn,b,i,(,b,i,-,a,ij,x,j,)/,a,ii,(i=n-1,.,2,1),是,否,是,是,否,例,5,用列主元消去法解方程组,解,第一次消元对,因列主元素为,a,31,(1),故先作行变换,r,2,_,r,3,然后进行消元计算可得,第二次消元对,A,(2),|,b,(2),因列主元素为,a,32,(2),故先作行变换,r,2,_,r,3,然后进行消元计算可得,由此回代,得,x,=(1.9272,-0.69841,0.90038),T,与精确解,x,=(1.9273,-0.69850,0.90042),T,相比较是比较准确的,.,-,0.002,x1+2x2+2x3 =0.4,x1+0.78125x2,=1.3816,3.996x1+5.5625x2+4x3=7.4178,-0.002 2 2 0.4,A,(1),|,b,(1),= 1 0.78125 0 1.3816,3.996,5.5625 4 7.4178,3.996 5.5625,4,7.4178,A,(2),|,b,(2),= 0 -0.61077 -1.0010 -0.47471,0 2.0029 2.0020,0.40371,3.996 5.5625 4 7.4178,A,(3),|,b,(3),= 0 2.0029 2.0020 0.40371,0,0,-0.39050 -0.35160,高斯消去法的计算量分析,高斯消去法的乘除总运算(由于计算机作乘除运算所需时间远大于作加减运算所需时间,故我们只讨论,乘除运算量,)分析为,消元次数,k,消元乘法次数 消元除法次数 回代乘除法总次数,1,n(n-1) n-1,2 (n-1)(n-2) n-2,.,.,.,k (n-k+1)(n-k) n-k,.,.,n-1 2*1 1 n(n+1)/2,故高斯消去法的计算量为,N=n(n,2,-1)/3+n(n-1)/2+n(n+1)/2=n,3,/3+n,2,-n/3,当,N,充分大时为,n,3,/3,方法的特点,由具体计算结果可知,全主元素法的精度优于列主元素法,这是由于全主元素是在全体系数中选主元,故它对控制舍入误差十分有效,.,但全主元素法在计算过程中,需同时作行与列的互换,因而程序比较复杂,计算时间较长,.,列主元素法的精度虽稍低于全主元素法,但其计算简单工作量大为减少,且计算经验与理论分析均表明,它与全主元素法同样具有良好的数值稳定性,列主元素法是求解中小型稠密性方程组的最好方法之一,.,选主元消去法,(,包括解线性方程组的所有直接的方法,),比较适用于中小型方程组,.,对高阶方程组,即使系数矩阵是稀疏的,但在计算中很难保持稀疏性,因而有存储量大，程序复杂等不足,所幸的是这一缺点可用,迭代法,解决,.,另外,高斯选主元消去法还可技巧性的解决一些特殊线性方程组，如三对角方程组等,.,由于误差的影响,计算过程中可能出现一些坏现象,要尽可能防止,表现在求解线性方程组的消元法比较上,则应该注意要简化运算,减小运算次数,提高效率,;,提高数值稳定性等,.,线性方程组解对系数的敏感性,在计算过程中，由于计算机字长的有限性，不可避免地产生所谓的舍入误差。同时，由于所求问题的初始数据（例如线性方程组的系数矩阵和右端项系数）往往是带有一定误差的。因此计算结果总是不可避免地带有误差，或者说，如果初始数据有扰动，势必将带来具有一定误差的计算结果。对于,A,x = b,来说，由于观测或计算等原因，线性方程组两端的系数,A,和,b,都带有误差,A,和,b,，,这样实际建立的方程组是近似方程组,(,A+,A)(x+,x)=b+,b,。,对近似方程组求出的解是原问题的真解,x,加上误差,x,即,x+,x,。,而,x,是由,A,及,b,引起的，它的大小将直接影响所求解的可靠性。,这种解依赖于方程组系数的误差,A,及,b,的问题，称为线性方程组解对系数的敏感性,。,方程组的系数矩阵发生微小扰动，就有可能引起方程组性质上的变化，这是方程组本身的“,条件问题,”。,相对误差关系式,：,设原线性方程组,A x= b,和近似方程组,(,A+,A)(x+,x)=b+,b,在,1,、,A=0,b,0,2,、,A,0,b=0,一般情形（,A,0,b,0,）,由这些关系式可看到，带有扰动的近似方程组中，扰动的大小直接影响着所求解的相对误差，故可作如下定义：,定义：设,A,非奇异，称,|A,-1,|A|,为矩阵,A,的条件数，记 为,C,ond,(A),，即,Cond,(A)= |A,-1,|A|.,Cond,(A),可反映出方程组解对系数的敏感性,。,对此，可通过下面的例子加以理解。,方程组,此方程组的准确解为,x,1,=0, x,2,=-1,。,现将其右端加以微小的扰动使之变为：,经计算可得准确解为,x,1,=2, x,2,=-3.,这两个方程组的解相差很大，说明方程组的解对常数项,b,的扰动很敏感。同时注意到,|,A|=4.0001, |A,-1,|=3.0001,10,4,故有,Cond,(A)=1.23,10,5,可见条件数很大,.,一般来说，方程组的条件数越小,求得的解就越可靠,;,反之，解的可靠性就越差。,通常当从方程组,A x = b,求出计算解,x,*,后，,有时用残向量,r = b-,A,x,*,的大小来检验,x,*,的精度,，认为如果对某种范数,|,r|,很小，就说明是好的。不过要记住这种处理在某些情况下是不准确的，,例如，对上述举例的方程组，当用某种方法求得计算解后，则有，显然,|,r|,是很小的，但与其真实解相差很大。为说明这方面的原因，我们可以把残向量,r,看成是,Ax,= b,的右端有扰动的,b,，,由相对误差关系式，有：,不可轻易用残向量,|,r|,的大小来判断计算解的精度！,本讲小结,本讲所讨论的,高斯消元法与选主元消元法,是求解线性方程组的常用方法，特别是,列主元素法是求解中小型稠密性方程组的最好方法之一，这些方法,的特点是，选定某种形式的直接解法以后，对于一个给定的线性代数系统，事先可以按规定的算法步骤计算出它所需要的算术运算操作数，直接给出最后的结果。这类方法还包括（块）三角分解法、波前法等。,由于实际问题的复杂性，需要求解的线性方程组的规模往往很大，利用直接法求解其计算效率将变得很差，甚至失效。这主要有两方面的困难：,1,）存储量太大；,2,）计算速度慢。,一种有效的方法是利用迭代法。,迭代解法,的特点是，对于一个给定的离散代数系统，首先假设一个初始解，然后按一定的算法公式进行迭代。在每次迭代过程中对解的误差进行检查，并通过增加迭代次数不断降低解的误差，直到满足解的精度要求，并输出最后的解答。这类方法包括常用的迭代方法，如,Jacobi,、,Gauss-Seidel,超松弛迭代（,SOR,）,共轭梯度法（,CG,），也包括现代计算方法中先进的迭代方法，如预处理共轭梯度法（,PCG,），多重网格法（,Multigrid method,）等。,