4线性方程组的直接解法.

北京科技大学数理学院卫宏儒[e-mail]计算方法第4章:线性方程组的直接解法关键词：高斯消元法主元消元法高斯消元法与主元消元法高斯消元法是一个古老的直接法,由它改进得到的选主元的消元法,是目前计算机上常用于求低阶稠密矩阵方程组的有效方法,其特点就是通过消元将一般线性方程组的求解问题转化为三角方程组的求解问题(一)引言为便于以下讨论,把涉及到的有关名词及问题的引出暂介绍如下:如果未知量的个数为n,而且关于这些未知量x1,x2,…,xn的幂次都是一次的(线性的),那么,n个方程a11x1+a12x2+…+a1nxn=b1┆┆┆(1)an1x1+an2x2+…+annxn=bn构成一个含n个未知量的线性方程组,称为n阶线性方程组。其中,系数a11,…,a1n,a21,…,a2n,…,an1,…,ann是给定的常数;b1,…,bn也是给定的常数,通常称为常数项,或称为方程组的右端.方程组(1)也常用矩阵的形式表示,写为Ax=b其中,A是由系数按次序排列构成的一个n阶矩阵，称为方程组的系数矩阵，x和b都是n维向量，称为方程组的右端向量。.使方程组(1)中每一个方程都成立的一组数x1*,x2*,…,xn*称为式(1)的解，把它记为向量的形式，称为解向量。nnnnnnnnxxxxbbbbaaaaaaaaaA2121212222111211我们总是希望方程组有解,且有唯一解.由线性代数的克莱姆(cramer)规则可知,如果方程组(1)的系数矩阵A的行列式(一般记为D=ⅠAⅠ)不等于零,那么,这个方程组有唯一解,而且它们可以表示为xi=Di/D(i=1,…,n)这里,Di是指D中第i列元素用右端b1,…bn代替构成的行列式.如果方程组(1)有唯一解,我们按上面的等式求解,就必须计算n+1个n阶行列式.由行列式的定义,n阶行列式包含有n!项,每一项含有n个因子,计算一个n阶行列式就需要做(n-1)n!次乘法.而我们一共要计算n+1个n阶行列式,共需做(n2-1)n!次乘法.此外,还要做n次除法才能算出xi(i=1,…n).也就是说,用这个办法求解就要做N=(n2-1)n!+n次乘除法运算,这个计算量是大得惊人的.例如,当n=10(即求解一个含10个未知量的方程组),乘除法的运算次数共为32659210次;当n=40，乘除法运算次数可达3.181049次。对于上百个未知量的方程组，次数运算量就更大了。因此可莱姆规则在理论上尽管是完善的，但在实际计算中却没有什么实用价值。我们将重点讨论求解线性方程组的一种有效的数值方法。(二)求解线性方程组的消元法消(元)去法是求解线性方程组Ax=b(2)和满秩矩阵的逆阵A-1的一种直接方法.尽管它比较古老,但它具有演算步骤,推算公式都系统化的特点(对其中选主元消去法,还可以证明是稳定的).因此,它至今仍然是求解方程组的一种有效的方法.消去法可以引出几种计算方法,下面按三角形方程组和一般线性方程组的顺序来讨论。1.三角形方程组的解法三角形方程组包括上三角形方程组和下三角形方程组，是最简单的线性方程组之一，实际上消元法就是通过简化一般线性方程组为三角形方程组后再求解的。上三角方程组的一般形式是：nnnniinnnnnnnnnnnbxaniabxaxabxaxabxaxaxa),......,2,1(0....................................................................................................111112222211212111其中1211/,,,....,/()/nnnnknnnnnnniiikkiikixbaxxxxxbaxbaxa为求解上面的上三角方程组，从最后一个方程开始，先解出然后按方程从后向前的顺序，用已求出的值，从方程中依次解出。这样就完成了上三角方程组的求解过程。这个过程的计算公式为：nikiiikikinnnnxaxabnniForxab1/)(1.21,,2,1.2/.1步骤：1111211222211221211110,1,2,,,,,,/()/(2,3,,)nnnnnniiniiikkiikaxbaxaxbaxaxaxbainxxxxbaxbaxain下三角方程组的一般形式为：其中下三角形方程组可以参照上三角形方程组的解法来求解，下三角形方程组的求解顺序是从第一个方程开始，按照从上到下的顺序，依次解出：其计算公式为：11i如上解三角形方程组的方法称为回代法。11212312223249xxxxxx例、用回代法求解线性方程组12312321:2/21(21)/11(93121)/41,,)(1,1,1)111)(1)22nixxxxxxninnn解所以，解为（求解一个三角形方程组需个除法与（次加法与乘法。2.Gauss消元法(一)高斯消去法的求解过程：分为两个阶段:首先，把原方程组化为上三角形方程组，称之为“消去”过程；然后，用逆次序逐一求出三角方程组(原方程组的等价方程组)的解，并称之为“回代”过程。下面分别写出“消去”和“回代”两个过程的计算步骤。消去过程:第一步:设a110,取做(消去第i个方程组的x1)mi1第一个方程+第i个方程i=2,3,…n则第i个方程变为：1111aamii)1()1(2)1(1)1(21inbxaxaxainii因为可得第一步消元后的方程组为：)1()1(2)1(2)1(2)1(22)1(22)0(1)0(12)0(121)0(11nnnnnnnnnbxaxabxaxabxaxaxai,j=2,3,…,niiijijiiijiijijbbaabmbbamaa)0()0()0(11)0()1()0(11)0()1(,,,i,j=2,3,…,n1111111111110iiiiiaaamaaaa第二步:设,取做(消去第i个方程组的x2,i=3,4,…n)mi2第二个方程+第i个方程i=3,4,…n类似可得第二步消元后的方程组为：0)1(22a)1(22)1(22aamii)2()2(3)2(3)2(3)2(33)2(33)1(2)1(22)1(22)0(1)0(12)0(121)0(11nnnnnnnnnnnbxaxabxaxabxaxabxaxaxanjibmbbamaaiiijiijij,...,4,3,,)1(22)1()2()1(22)1()2(第k步:设,取做(消去第i个方程组的xk,i=k+1,k+2,…,n)mik第k个方程+第i个方程i=k+1,k+2,…n类似可得第k步消元后的方程组为：0)1(kkka)1()1(kkkkikikaam)()(1)(1)(1)(11)(11)1(2)1(22)1(22)0(1)0(12)0(121)0(11knnknnkkknkknknkkkkknnnnbxaxabxaxabxaxabxaxaxankkjibmbbamaakkikkikikkjikkijkij,...,2,1,,)1()1()()1()1()(继续下去到第n-1步消元，可将线性方程组化为如下上三角方程组:nkkjibmbbamaaaamnkkkbabxabxaxabxaxaxakkikkikikkjikkijkijkkkkikikkikijnnnnnnnnnn,...,2,1,/1,,3,21)1()1()()1()1()()1()1()()()1()1()1(2)1(22)1(2211212111，对计算公式为次消元后的系数，表示第的上标和其中12,,,(,1,2,,),,,11,2,,11.101.21,2,,1.2.1/1.2.2(1,2,,)1.2.3ijinkkikkkikijikkjijiikkGaussGaussnabijnxxxForknIfathenstopForikknaaaaaaajkknbabb消元法算法：说明本算法用消元法来求线性方程组的解。输入输出步骤输出“不能消元”，12/31,2,,13.1()/4innnnkkjjkkkjbaxForknnbaxaxEnd1231231232362349326Gaussxxxxxxxxx为了具体认识这种方法，下面给出例题。例用消元发求解方程组完成第一步消元得。个方程）第个方程）做（第解3,21(i11/1/21/2/01,3111313111212111imaamaamani1232323(1)(1)(1)2232322212323332312312323623010,/1/1123623333/31(32)(321)16236213111,1,1xxxxxxxamaaxxxxxxxxxxxxxxx完成第二步消元得回代求得故所求解为3.主元消元法例1:考虑如下线性方程组的Gauss消元法求解性2x2=12x1+3x2=2解:因为a11=0,故此题不能用Gauss消元法求解,但交换方程组的顺序后,就可用Gauss消元法求解了.例题2:讨论下面方程组的解法0.0001x1+x2=1x1+x2=2假设求解是在四位浮点十进制数的计算机上进行。0.100010-3x1+0.1000101x2=0.10001010.1000101x1+0.1000101x2=0.2000101解:本题的计算机机内形式为因为a11=0.00010,故可用Gauss消元法求解,进行第一次消元时有a22(1)=0.1000101-1040.1000101(m21=a21/a11=1/0.0001=104)=0.00001105-0.1000105(对阶计算)=0.0000-0.1000105=-0.1000105,得三角方程组0.100010-3x1+0.1000101x2=0.1000101-0.1000105x2=-0.1000105回代解得x2=1,x1=0严重失真!(因为本题的准确解为x1=10000/9999,x2=9998/9999）列主元基本思想及程序框图用高斯消去法求解线性方程组时,应避免小的主元.在实际计算中,进行第k步消去前,应该在第k列元素aik(i=k,…,n)中找出绝大值最大者,例如∣a∣=max∣a∣再把第p个方程与第k个方程组进行交换,使apk(k-1)成为主元.我们称这个过程为选主元.由于只在第k列元素中选主元,通常也称为按列选主元(或称部分选主元).如果在第k步消去前,在第k个方程到第n个方程所有的xk到xn的系数a(i=k,…,n;j=k,…,n)中,找出绝对值最大者,例如∣a∣=max∣a∣再交换第k,p两个方程和第k,q两个未知量的次序,使a成为主元.称这个过程为完全选主元。不论是哪种方式选出主元,而后再按上面介绍的计算步骤进行消去的计算,一般都称为选主元的高斯消去法。在实际计算中,常用按列选主元的高斯消去法。(k-1)(k-1)pk(k-1)ikk