计算方法-解线性方程组的直接法

第8次线性方程组的直接解法计算方法(NumericalAnalysis)1）高斯消去法2）高斯主元素消去法3）方程组的性态4)高斯消去法算法构造（编程）本讲内容高斯消去法§5.1引言在工程技术、自然科学和社会科学中，许多问题最终都可归结为求解线性方程组的数学问题。线性方程组的求解对于实际问题是极其重要的。解线性方程组的直接法nnnn2n21n12n2n2221211n1n212111bxa...xaxa......bxa...xaxabxa...xaxan21n21nnn2n12n22211n1211b...bbB,x...xxx,...aaa.........aaa...aaaA解线性方程组的直接法可简记为Ax=b，其中(6.1)常见的nxn线性方程组，一般形式为线性方程组的数值解法一般有两类：1.直接法：就是经过有限步算术运算，可求得方程组精确解的方法（若计算过程中没有舍入误差），如克莱姆法则就是一种直接法，直接法中具有代表性的算法是Gauss消去法。2.迭代法:就是用某种极限过程去逐步逼近线性方程组的精确解的方法。也就是从解的某个近似值出发，通过构造一个无穷序列去逼近精确解的方法。(一般有限步内得不到精确解)(4)4x(3)7xx(2)9xxx(1)10xxxx4434324321例子：求解如下的上三角线性方程组：解：由（4），得4x43x3将（4）带入（3），得将结果代入（2），得2x2将结果代入（1），得1x1§5.2高斯消去法§5.2高斯消去法5.2.1高斯消去法的基本思想72xx45x2x4x13xx2x21321321①②③解:高斯消去法包括如下的消元和迭代的两个过程。先用一个简单实例来说明Gauss法的基本思想例5.1解线性方程组（1）消元过程)21(1x④⑤213x23x252x4x13xx2x3232321第1步:将方程①乘上(-2)加到方程②上去,将方程①乘上加到方程③上去,这样就消去了第2、3个方程的项,于是就得到等价方程组第2步：将方程④乘上加到方程⑤上去，这样就消去了第3个方程的项，于是就得到等价方程组)85(2x421x872x4x13xx2x332321⑥这样，消元过程就是把原方程组化为上三角形方程组，其系数矩阵是上三角矩阵。（2）回代过程将上述三角形方程组自下而上求解得：9x1x6x123从而求得原方程组的解：6x1,x9,x321前述的消元过程相当于对原方程组的增广矩阵进行下列行变换702145241312bAA~2132325021401312421870021401312同样可得到与原方程组等价的方程组⑥122)r(r13)r21(r23)r85(r高斯消去法的基本思想：•这种求解上三角方程组的方法称为回代,通过一个方程乘或除以某个常数,•利用矩阵行的初等变换将原方程组Ax=b系数矩阵化为上三角形矩阵,然后从最后一个方程开始,依次向前代入求出未知变量：•将两个方程相加减,逐步减少方程中的变元数,最终将方程组化成上三角方程组,一般将这一过程称为消元,然后再回代求解。11nnx,,x,x…5.2.3高斯消去法的适用条件注2：设系数矩阵A为非奇异矩阵，•则若a11=0，则可以通过调换行的方法，使得在第一行的第一个元素非0。•其它在消元过程中，kk位置的情形类似处理。则高斯消元法可以进行。注1：设系数矩阵A为非奇异矩阵，直接使用高斯消元法（不进行行的交换）对于某些简单的矩阵可能失败，例如：0110A证明：上三角形方程组是从原方程组出发，通过逐次进行“一行乘一数加到另一行”而得出的，该变换不改变系数矩阵顺序主子式的值。因此，需要对上述的高斯算法进行修改，首先应该研究原来的矩阵A在何条件下能够保证1n,1,2,对k0,a(k)kk…定理1若方程组系数矩阵的顺序主子式全不为0，则高斯消去法能实现方程组的求解，即：1n,1,2,对k0,a(k)kk…设方程组系数矩阵，其顺序主子式nij)(aA0aaaaAmmm11m11m(m=1,2,…，n)经变换得到的上三角形方程组的顺序主子式所以能实现高斯消去法求解（m=1,2,…，n）………0aaaaaaaaaA(m)mm(2)22(1)11(m)mm(2)2m(2)22(1)1m(1)12(1)11m…………...定义5.1设矩阵每一行对角元素的绝对值都大于同行其他元素绝对值之和nij)(aAn,2,1,i,|a||a|nij1jijii则称A为严格对角占优矩阵。|)a||a||a(||a|1n131211|)a||a||a(||a|2n232122|)a||a||a(||a|1)-n(nn2n1nn……上述条件展开以后为：定理1.1若方程组的系数矩阵A为严格对角占优，则用高斯消去法求解时，全不为0。因此，可以使用高斯消去法求解。bAx(k)kka练习：用高斯消去法求解如下的线性方程组(3)189x3x2x(2)15x6x(1)6xx3x321323211893-2151-606113bAA~解：增广矩阵为1893-2151-606113bAA~0x3x3x12314325311-0151-606113422511-0151-6061132139613900151-606113Home高斯主元素消去法•使用高斯消去法求解时，在消元过程中可能会出现的情况，这时消去法将无法进行；0a(k)kk§5.3高斯主元素消去法0a(k)kk•即使，但它的绝对值很小时，用其作除数，会导致其他元素数量级的严重增长和舍入误差的扩散，将严重影响计算结果的精度。•实际计算时必须避免这类情况的发生。主元素消去法就可弥补这一缺陷。例4求解如下的方程组解法1使用Gauss消去法求解3.0002.0001.000xxx5.6431.0722.000-4.6233.7121.000-3.0002.0000.001321其精确解为（舍入到4位有效数字）：3.0005.6431.0722.000-2.0004.6233.7121.000-1.0003.0002.0000.001b)|(A0.3675)0.05104,0.4904,(xT*3.0005.6431.0722.000-2.0004.6233.7121.000-1.0003.0002.0000.001b)|(A计算解为：0.4000)0.09980,0.400,(xT2.0005.0000010023005200401.0003.0002.0000.001)20044001-(rr23200360064001010023005200401.0003.0002.0000.001)0.0011(rr12)0.0012(rr13解法2。变换行，避免绝对值小的主元做除数1.0003.0002.0000.0012.0004.6233.7121.000-3.0005.6431.0722.000-b)|(A1.0023.0032.00100.50001.8013.17603.0005.6431.0722.000-0.68701.868000.50001.8013.17603.0005.6431.0722.000-解为：*Tx0.3678)0.05113,0.4900,(x这个解比解法1更加接近真实的解。)21(-rr12)20001(rr13)3.1762.001(-rr2331rr•交换原则：通过方程或变量次序的交换，使在对角线位置上获得绝对值尽可能大的系数作为akk(k)，称这样的akk(k)为主元素，并称使用主元素的消元法为主元素法•根据主元素选取范围分为：–列主元素法–行主元素法(不讲)–全主元素法(不讲)§5.3高斯主元素消去法（续）5.3.2列主元素法•列主元素法就是在待消元的所在列中选取主元（选取一列中绝对值最大的元素当主元），经方程的行交换，置主元于对角线位置后进行消元的方法。例5.4用列主元素法解下列线性方程组(3)55x4xx(2)4x40x20x-(1)32x-19x-10x321321321解：选择-20作为该列的主元素，交换方程(1)和(2)得m21=10/-20=-0.5m31=1/-20=-0.05(6)55x4xx(5)32x-19x-10x(4)4x40x20x-321321321(5)-m21(4),(6)-m31(4)得(8)5.25.05x6x(7)51.5x-x3232选6为主元素，交换方程（7）与（8），得：(10)-m32(9)得-2.34168x3=4.13332(11)记笔记(10)51.5x-x(9)5.25.05x6x3232计算m32=1/6=0.16667(11)4.133322.34168x-(9)5.25.05x6x(4)4x40x20x-332321保留有主元素的方程进行回代，得列选主元素的计算方法与高斯消去法完全一样,不同的是在每步消元之前要按列选出主元4.41634x2.35230x-1.76511x123-1.76511x2.35230x4.41634x321例5.5用矩阵的初等行变换求解解方程组75x4x2x17x7x4x33x2x2x321321321解:用矩阵的初等行变换求解,对增广矩阵(下面带下划线元素为主元素)矩阵的列主元素计算方法可以用矩阵的初等行变换实现754233221774754217743322bAA(1)~6.58.57.502.50.51.50177412r21r13r21r12rr2.50.51.506.58.57.50177423rr1.21.2006.58.57.50177423r51rT2,1)得解：(2,同学课堂练习：用列主元素法求解线性方程组：(3)6xx3x(2)189x3x2x(1)15x6x32132132Home方程组的性态5.5方程组的性态•在建立方程组时，其系数往往含有误差（如观测误差或计算误差），即，所要求解的运算是有扰动的方程组，因此需要研究扰动对解的影响。例5.13考察方程组2.00011.0001xx2xx212121.0001xx2xx2121和•上述方程组（1）是方程组（2）在右端项施加了微小的扰动,但解大不相同.（1）（2）1xx21方程组（1）的解：0x2,x21方程组（2）的解：这类方程组称为病态的。定义5.8A或b的微小变化(又称扰动或摄动)引起方程组Ax=b解的巨大变化，则称方程组为病态方程组，矩阵A称为病态矩阵。否则方程组是良态方程组，矩阵A也是良态矩阵。•为了定量地刻画方程组“病态”的程度，