第二章线性方程组的直接解法

第二章线性方程组的直接解法§1引很多工程问题的计算最终都归结为解线性方程组。虽然有些数学模型中不直接表现为解线性方程组,但其数值解法中将问题“离散化”或“线性化”将成为线性方程组。线性方程组的求解是数值分析课程中最基本的、最重要的内容之一。设线性方程组:(1)11112211211222221122nnnnnnnnnnaxaxaxbaxaxaxbaxaxaxb记为矩阵形式为Ax=b(2)11其中A是一个n阶方阵,x和b是n维列向量。由Cramer法则，若系数行列式det(A)≠0,线性方程组(2)存在唯一的一组解其中D是系数行列式，Dj是用右端向量b代替D的第j列后的行列式。线性方程组的解法一般分为两大类,一类是直接法,经过有限次的运算,即可求得线性方程组的解，本章主要介绍直接解法。另一类是迭代法,将方程组变形为某种等价的迭代公式,给出初值x（0）,产生迭代序列｛x(k)｝,k=0,1,2,,在一定的条件下x(k)→x*(准确解)。迭代法是下一章介绍的重点。1,2,,jjjnDxD2§2高斯(Gauss)消去法一、Gauss消元法的基本思想Gauss消去法的基本思想是对方程组所对应的增广矩阵进行一系列的初等行变换，将其转化为上三角矩阵，通过回代求得线性方程组的解。例解方程组3946572132321321321xxxxxxxxx第一步,第一个方程乘-2加到第二个方程；第一个方程乘-1加到第三个方程,得到462431323232321xxxxxxx3第二步,第二个方程乘-2/3加到第三个方程得到32032043132332321xxxxxx回代:解第三个方程得x3,将x3代入第二个方程得x2,将x2,x3代入第一个方程得x1,得到解x*=(2,1,-1)T容易看出第一步和第二步相当于增广矩阵［Ａ:b］在作行变换,用ri表示增广阵［Ab］的第i行221331212311231:2756031414930264rrrrrrAb4332231231031420200033rrr二、Gauss消元法公式记Ax=b为A(1)x=b(1),A(1)和b(1)的元素记为和,i,j=1,2,,n。第一次消元的目的是消掉第二个方程到第n个方程中的x1项,即将增广矩阵第一列的后面n-1个元素化为0。得到A(2)x=b(2),这个过程须假定≠0。)1(ija)1(ib)1(11a511(1)(1)(1)(1)111211(1)(1)(1)(1)(1)(1)212222(2,3,,)(1)(1)(1)(1)12(1)(1)(1)(1)111211(2)(2)(2222(2)(2)200iiinrrlrninnnnnnnnnnnaaabaaabAbaaabaaabaabaa2)(2)(2)(2)nAbb在［A(1):b(1)］中,红方框中的元素是要转化为0的部分；［A(2):b(2)］中,红方框中的元素全部已发生变化,故上标由(1)改(2),计算公式为6(1)11(1)11(2)(1)(1)11(2)(1)(1)112,3,,,2,3,,2,3,,iiijijijiiiinijninalaaalabblb设前k-1次消元已完成,且≠0,此时增广矩阵如下:)(kkka)()()2(2)1(1)()()2(2)1(1)()()2(2)2(22)1(1)1(12)1(11)()(:knkkknnkknnnknkkkkkkkkbbbbaaaaaaaaaaabA7第k次消元的目的是对框内部分作类似第一次消元的处理,消掉第k+1个方程到第n个方程中的xk项,即把化为零。计算公式如下)(,1kkka)(knka()()(1)()()(1)()()1,,,1,2,,1,2,,kikikkkkkkkijijikkjkkkiiikkiknijkknikknalaaalabblb。（乘数因子)只要≠0,(k=1,2,,n-1)消元过程就可以一直进行下去。当k=n-1时,消元过程完成，得上三角形矩阵(1)(1)(1)(1)111112(2)(2)(2)()()2222()()nnnnnnnnnabaaabaAbab)(kkka8它的方阵部分A(n)是一个上三角形矩阵,它对应的方程组是一个上三角形方程组,只要≠0,就可以回代求解,公式为)(nnna()()()()1()nnnnnnniiiijjjiiiiibxabaxxa(i=n-1,n-2,,1)综合以上讨论,Gauss1①令(i,j=1,2,…,n)iiijijbbaa)1()1(,9()()(1)()()(1)()()kikikkkkkkkijijikkjkkkiiikkalaaalabblb(i,j=k+1,k+2,,n)(i=k+1,k+2,,n)2回代,若≠0)(nnna)(1)()()()(iiinijjiijiiinnnnnnaxabxabx(i=n-1,n-2,,1)②对k=1到n-1,若≠0,进行(i=k+1,k+2,,n))(kkka10三、Gauss消去法的条件以上消元过程中要求≠0(i=1,2,,n-1),回代过程则进一步要求≠0,但就方程组Ax=b讲,是否等于0是无法事先看出的。)(nnna)(iiia)(iiia因为消元运算所作的变换是“将某行的若干倍加到另一行”，所以A的顺序主子式Di(i=1,2,,n)在消元过程中是不变的。即此类变换不改变行列式的值。因此有定理Gauss消去法消元过程能进行到底的充要条件是系数阵A的1到n-1阶顺序主子式不为零；Ax=b能用Gauss消元法解的充要条件是A的各阶顺序主子式不为零.一般讲计算机进行一次乘除法的运算比加减法所用时间多,所以常常只统计乘除法次数作为一个计算公式或方法的计算工作量。称Gauss消去法的计算工作量为次.33n11§3Gauss主元素法在上节Gauss消去法中,消元时可能出现=0的情况,Gauss消去法将无法继续。即使≠0,但1,此时用它作除数,也会导致其它元素数量级严重增加,带来舍入误差的扩散,使解严重失真。)(kkka)(kkka()||kkka例采用三位有效数字计算，求解线性方程组1231231230.501.13.16.02.04.50.360.0205.00.966.50.96xxxxxxxxx12法1顺序消去法0.501.13.16.00.5001.103.106.002.04.50.360.02000.100-12.0-24.05.00.966.50.960-10.0-24.5-59.00.5001.103.106.0000.100-12.0-24.000-1220-2460解方程组的准确解是x=(-2.6,1,2)T。回代得解是x*=(-5.80,2.40,2.02)T。l21=4,l31=10。l32=-100。13法2列主元消去法0.501.13.16.05.00.966.50.962.04.50.360.0202.04.50.360.0205.00.966.50.960.501.13.16.05.000.9606.500.9605.000.9606.500.96004.12-2.24-0.36404.12-2.24-0.36401.002.455.90002.995.99回代得解是x*=(-2.60,1.00,2.00)T。l21=0.4,l31=0.1。l32=0.24272。14从例2可以看出,对方程组作简单的行交换有时会显著改善解的精度。在实际使用Gauss消去法时,常用“选主元”技巧以避免“小主元”的出现,从而保证Gauss消去法能顺利进行并保证解的数值稳定性。一、列主元消元法设已用列主元消去法完成前k-1次消元(1≤k≤n-1),此时方程组Ax=b→A(k)x=b(k)，有如下形式:)()()2(2)1(1)()()()()2(22)1(12)1(11)()(:knkkknnkknknkkkkkkbbbbaaaaaaabA15进行第k次消元前,先进行①、②两个步骤①在方框内的一列内选出绝对值最大者,即确定ik。若=0,则det(A)=｜A(k）｜=0,即方程组Ax=b不满足Cramer法则的条件。()(),||max||kkkikikkinaa)(,kkika②若ik≠k,则交换第ik行和k行元素即)(,)(kjikkjkaa)()(kikkkbb(kjn)然后用Gauss消去法进行消元运算。这样从k=1做到k=n-1,就完成了整个消元过程,只要｜A｜≠0,Gauss列主元消去法必可进行下去。16算法（Gauss列主元素法）１．选主元，对k=1,2,···,n-1确定ik，使若=0，则A为奇异矩阵，停机。２．若，转３。否则换行３．消元,||max||kikikkinaa,kikakikkkjijaa)()(kikkkbb(kjn)ikikkkaaa1,2,,ikkn,ijijikkjaaaaiiikkbbab17４．若，停机．=0nna12,,3,2,11,nnnnniijjjiiiibxababxinna５．６．（b1,b2,···,bn)T18二、Gauss全主元消去法在Gauss消去法中,若每次选主元不局限在方框列中，而在整个主子矩阵)()()()(knnknkkknkkkaaaa中选取,便称为全主元Gauss消去法,此时增加的步骤为:①,确定ik,jk,若,给出|Ａ|=0的信息，停止计算。()(),,||||maxkkkkijijkijnaa,0kkija行交换:)(,)(kjikkjkaa)()(kikkkbb(kjn)列交换:)(,)(kjikikkaa(kin)19②值得注意的是,在全主元的消去法中,由于进行了列交换,x各分量的顺序已被打乱。因此必须在每次列交换的同时,让机器存储列交换的信息,在回代得出解后再将x的各分量换回到原来相应的位置处。这样增加了程序设计的复杂性，同时比较大小选全主元时,将耗费更多的计算工作量。但全主元消去法比列主元消去法精度更好一些。实际应用中,这两种选主元技术都在使用。但全主元消去法用来求行列式的值效果更好。Gauss主元素法是一种实用的算法,可以应用到任意的方程组Ax=b，只要系数行列式｜A｜≠0。20§4Gauss-Jordan消去法一、Gauss-Jordan消去法Gauss-Jordan消去法是Gauss消去法的一种变形。Gauss消去法是消去对角线元素下方的元素。若同时也消去对角线元素上方的元素，而且将对角线元素化为1。就是Gauss-Jordan消去法。设Gauss-Jordan消去法已完成了前k-1步，于是Ax=b化为等价方程组A(k)x=b(k)，其增广矩阵为21在第k步计算时,考虑将第k行第k列上下的元素都化为0,且将akk化为1。对k=1,2,,n1按列选主元，确定ik使111()()1,1,11