资源描述
单击以编辑,母版标题样式,单击以编辑母版文本样式,第二级,第三级,第四级,第五级,*,关键词:,高斯消去法,主元消去法,高斯消元法与选主元,高斯消元法是一种古老的直接法,由它改进得到的选主元消元法,是目前计算机上常用于求解低阶稠密矩阵方程组的有效方法,其特点就是通过消元将,一般线性方程组,的求解问题转化为,三角方程组,的求解问题,一 问题的描述,(,一,),引言,为便于以下讨论,把涉及到的有关名词及问题的引出暂介绍如下,:,如果未知量的个数为,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,方法的特点,由具体计算结果可知,全主元素法的精度优于列主元素法,这是由于全主元素是在全体系数中选主元,故它对控制舍入误差十分有效,.,但全主元素法在计算过程中,需同时作行与列的互换,因而程序比较复杂,计算时间较长,.,列主元素法的精度虽稍低于全主元素法,但其计算简单工作量大为减少,且计算经验与理论分析均表明,它与全主元素法同样具有良好的数值稳定性,列主元素法是求解中小型稠密性方程组的最好方法之一,.,选主元消去法,(,包括解线性方程组的所有直接的方法,),比较适用于中小型方程组,.,对高阶方程组,即使系数矩阵是稀疏的,但在计算中很难保持稀疏性,因而有存储量大,程序复杂等不足,所幸的是这一缺点可用,迭代法,解决,.,另外,高斯选主元消去法还可技巧性的解决一些特殊线性方程组,如三对角方程组等,.,由于误差的影响
展开阅读全文