计算方法-解线性方程组的直接法ppt课件.ppt

《计算方法-解线性方程组的直接法ppt课件.ppt》由会员分享，可在线阅读，更多相关《计算方法-解线性方程组的直接法ppt课件.ppt（54页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第8次 线性方程组的直接解法计算方法(Numerical Analysis)1）高斯消去法2）高斯主元素消去法3）方程组的性态4) 高斯消去法算法构造（编程）本讲内容高斯消去法5.1 引言 在工程技术、自然科学和社会科学中，许多问题最终都可归结为求解线性方程组的数学问题。 线性方程组的求解对于实际问题是极其重要的。 解线性方程组的直接法nnnn2n21n12n2n2221211n1n212111bxa.xaxa.bxa.xaxabxa.xaxan21n21nnn2n12n22211n1211b.bbB,x.xxx,.aaa.aaa.aaaA解线性方程组的直接法可简记为 Ax=b，其中 ( 6.

2、1 ) 常见的nxn线性方程组，一般形式为 线性方程组的数值解法一般有两类：1. 直接法：就是经过有限步算术运算，可求得方程组精确解的方法（若计算过程中没有舍入误差），如克莱姆法则就是一种直接法，直接法中具有代表性的算法是Gauss消去法。2. 迭代法: 就是用某种极限过程去逐步逼近线性方程组的精确解的方法。也就是从解的某个近似值出发，通过构造一个无穷序列去逼近精确解的方法。(一般有限步内得不到精确解)(4) 4 x (3) 7x x (2) 9xx x(1) 10 xxxx4434324321例子：求解如下的上三角线性方程组：解：由（4），得4x43x3将（4）带入（3），得将结果代入（2）

3、， 得2x2将结果代入（1）， 得1x1 5.2 高斯消去法 5.2 高斯消去法 5.2.1 高斯消去法的基本思想72xx45x2x4x13xx2x21321321 解:高斯消去法包括如下的消元和迭代的两个过程。 先用一个简单实例来说明Gauss法的基本思想例5.1 解线性方程组 （1）消元过程)21(1x213x23x25 2x4x 13xx2x3232321第1步:将方程乘上(-2)加到方程 上去,将方程 乘上 加到方程 上去,这样就消去了第2、3个方程的 项,于是就得到等价方程组 第2步：将方程 乘上 加到方程 上去，这样就消去了第3个方程的 项，于是就得到等价方程组 )85(2x421

4、x872x4x13xx2x332321这样，消元过程就是把原方程组化为上三角形方程组，其系数矩阵是上三角矩阵。 （2）回代过程将上述三角形方程组自下而上求解得：9x1x6x123从而求得原方程组的解： 6x1,x9,x321前述的消元过程相当于对原方程组的增广矩阵进行下列行变换702145241312bAA2132325021401312421870021401312同样可得到与原方程组等价的方程组 122)r(r13)r21(r23)r85(r高斯消去法的基本思想：这种求解上三角方程组的方法称为回代, 通过一个方程乘或除以某个常数,利用矩阵行的初等变换将原方程组Ax=b系数矩阵化为上三角形矩

5、阵,然后从最后一个方程开始,依次向前代入求出未知变量：将两个方程相加减,逐步减少方程中的变元数,最终将方程组化成上三角方程组,一般将这一过程称为消元,然后再回代求解。11nnx,x,x5.2.3 高斯消去法的适用条件 注2： 设系数矩阵A为非奇异矩阵，则若a11 =0，则可以通过调换行的方法，使得在第一行的第一个元素非0。其它在消元过程中，kk位置的情形类似处理。则高斯消元法可以进行。注1：设系数矩阵A为非奇异矩阵，直接使用高斯消元法（不进行行的交换）对于某些简单的矩阵可能失败，例如：0 11 0A证明：上三角形方程组是从原方程组出发，通过逐次进行“一行乘一数加到另一行”而得出的，该变换不改变

6、系数矩阵顺序主子式的值。 因此，需要对上述的高斯算法进行修改，首先应该研究原来的矩阵A在何条件下能够保证 1n,1,2,对k0,a(k)kk定理1 若方程组系数矩阵的顺序主子式全不为0，则高斯消去法能实现方程组的求解，即：1n,1,2,对k0,a(k)kk设方程组系数矩阵 ，其顺序主子式 n ni ij j) )( (a aA A 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

7、.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解：增

8、广矩阵为1893-2151-606113bAA0 x3x3x12314325311-0151-606113422511-0151-6061132139613900151-606113Home高斯主元素消去法使用高斯消去法求解时，在消元过程中可能会出现 的情况，这时消去法将无法进行；0a(k)kk5.3 高斯主元素消去法0a(k)kk即使 ，但它的绝对值很小时，用其作除数，会导致其他元素数量级的严重增长和舍入误差的扩散，将严重影响计算结果的精度。实际计算时必须避免这类情况的发生。主元素消去法就可弥补这一缺陷。 例4 求解如下的方程组解法1 使用Gauss消去法求解3.0002.0001.000

9、xxx 5.643 1.072 2.000-4.623 3.712 1.000-3.000 2.000 0.001 321其精确解为（舍入到4位有效数字）： 3.000 5.643 1.072 2.000-2.000 4.623 3.712 1.000-1.000 3.000 2.000 0.001 b)|(A 0.3675) 0.05104, 0.4904,(xT* 3.000 5.643 1.072 2.000-2.000 4.623 3.712 1.000-1.000 3.000 2.000 0.001 b)|(A计算解为： 0.4000) 0.09980, 0.400,(xT 2.00

10、0 5.000 0 0 1002 3005 2004 0 1.000 3.000 2.000 0.001 )20044001-(rr23 2003 6006 4001 0 1002 3005 2004 0 1.000 3.000 2.000 0.001 )0.0011(rr12)0.0012(rr13解法2。变换行，避免绝对值小的主元做除数 1.000 3.000 2.000 0.001 2.000 4.623 3.712 1.000- 3.000 5.643 1.072 2.000-b)|(A 1.002 3.003 2.001 0 0.5000 1.801 3.176 0 3.000 5.

11、643 1.072 2.000- 0.6870 1.868 0 0 0.5000 1.801 3.176 0 3.000 5.643 1.072 2.000-解为：*Tx 0.3678) 0.05113, 0.4900,(x这个解比解法1更加接近真实的解。)21(-rr12)20001(rr13)3.1762.001(-rr233 31 1r rr r 交换原则：通过方程或变量次序的交换，使在对角线位置上获得绝对值尽可能大的系数作为akk(k)，称这样的akk(k) 为主元素，并称使用主元素的消元法为主元素法 根据主元素选取范围分为： 列主元素法 行主元素法(不讲) 全主元素法(不讲)5.3

12、高斯主元素消去法（续）5.3.2 列主元素法 列主元素法就是在待消元的所在列中选取主元（选取一列中绝对值最大的元素当主元），经方程的行交换，置主元于对角线位置后进行消元的方法。 例5.4 用列主元素法解下列线性方程组(3) 55x 4x x(2)4 x 40 x 20 x-(1) 32x - 19x - 10 x 321321321解：选择-20作为该列的主元素，交换方程(1)和(2)得m21 =10/-20=-0.5m31=1/-20=-0.05(6) 55x 4x x(5) 32x - 19x - 10 x (4) 4 x 40 x 20 x-321321321 (5)- m21(4),

13、(6)- m31(4)得(8) 5.25.05x 6x(7) 5 1.5x - x3232 选6为主元素，交换方程（7）与（8），得： (10)- m32(9) 得 -2.34168x3 = 4.13332 (11)记笔记(10) 5 1.5x - x(9) 5.25.05x 6x3232计算m32=1/6 =0.16667(11) 4.133322.34168x- (9) 5.2 5.05x 6x (4) 4 x 40 x 20 x-332321保留有主元素的方程进行回代，得列选主元素的计算方法与高斯消去法完全一样,不同的是在每步消元之前要按列选出主元4.41634x2.35230 x -1

14、.76511 x123 -1.76511 x 2.35230 x4.41634x321例5.5 用矩阵的初等行变换求解解方程组 75x4x2x17x7x4x 33x2x2x 321321321 解: 用矩阵的初等行变换求解,对增广矩阵 (下面带下划线元素为主元素) 矩阵的列主元素计算方法可以用矩阵的初等行变换实现754233221774754217743322bAA(1)6.58.57.502.50.51.5017741 12 2r r2 21 1r r1 13 3r r2 21 1r r1 12 2r rr r 2.50.51.506.58.57.5017742 23 3r rr r 1.2

15、1.2006.58.57.5017742 23 3r r5 51 1r rT2,1)得解：(2,同学课堂练习：用列主元素法求解线性方程组：(3) 6xx3x(2) 189x3x2x(1) 15x6x 32132132 Home方程组的性态5.5 方程组的性态在建立方程组时，其系数往往含有误差（如观测误差或计算误差），即，所要求解的运算是有扰动的方程组，因此需要研究扰动对解的影响。 例5.13 考察方程组 2.00011.0001xx2xx212121.0001xx2xx2121和上述方程组（1）是方程组（2）在右端项施加了微小的扰动, 但解大不相同. （1）（2）1xx21方程组（1）的解：0

16、 x2,x21方程组（2）的解： 这类方程组称为病态的。定义5.8 A或b的微小变化(又称扰动或摄动)引起方程组Ax=b解的巨大变化，则称方程组为病态方程组，矩阵A称为病态矩阵。否则方程组是良态方程组，矩阵A也是良态矩阵 。 为了定量地刻画方程组“病态”的程度，要对方程组Ax=b进行讨论，考察A（或b）微小误差对解的影响。为此先引入矩阵范数的概念： 矩阵范数的概念：n1jijni1|a|max|A|A的行范数矩阵A的无穷范数；n1iijnj11|a|max|A|A的列范数矩阵A的1范数；定义5.9 （矩阵条件数）设A为非奇异矩阵，称 1 1A AA Ac co on nd d( (A A) )

17、 为矩阵A条件数。 1 11 11 11 1| | |A A| | | | |A A| | |c co on nd d( (A A) )| | |A A| | | | |A A| | |c co on nd d( (A A) )1 12 21 12 22 2| | |A A| | | | |A A| | |c co on nd d( (A A) )常用的条件数有条件数的性质：1 1; ;c co on nd d( (A A) )v v对于任何非奇异矩阵A,都有：当cond(A)v 1时，则方程组Ax=b是病态的；否则，Ax=b是良态的。病态方程组(矩阵)的定量描述：例6.13 线性方程组 20

18、 xx111121的系数矩阵带误差，成为如下方程组 20 xx1.000511121求方程组系数矩阵的条件数, 并说明方程组的性态. 解： 因为 1111A111121A1212AAcond(A)1所以 因此方程组是良态的 例9 Hilbert矩阵Hn的定义如下1113336cond()408748.HHH12n11n1 n11n1 31 21n1 21 1Hn 求H3 的条件数。结论：Hilbert矩阵H3 是病态矩阵；可以证明，当n越大的时候， Hn的 病态越严重。1123111133234111345193630, 36192180 , 30180180 HH解：本次小结 直接法是一种计

19、算量小而精度高的方法。直接法中具有代表性的算法是高斯（Gauss）消去法；克莱姆算法也是一种直接法，但该算法用于高阶方程组时计算量太大而不实用；选主元的算法有很好的数值稳定性。从计算简单出发实际中多选用列主元法；注意线性方程组有的时候具有病态；线性方程组的病态程度是其本身的固有特性，因此即使用数值稳定的方法求解，也难以克服严重病态导致的解的失真。Home高斯消去法算法构造5.2.2 高斯消去法算法构造(Matlab 编程使用) n21n21nnn2n12n22211n1211bbbxxxaaaaaaaaa( 6.3 ) Gauss消去法的消元过程：对( 6.3 )的增广矩阵进行行初等变换。将例

20、6.1中解三阶线性方程组的消去法推广到一般的 阶线性方程组，并记n nn n n),1,2,j(i,bb,aai(1)iij(1)ij线性方程组(6.1)用矩阵形式表示为 则高斯消去法的算法构造归纳为： Gauss消去法的消元过程(由n-1步组成)： 0，a(1)11n2,3,.,i,aam(1)11(1)i1i1用 乘以第1个方程后加到第 个方程上去,消去第2到第n个方程的未知数 ,得到i i1 1mmi i1 1x x(2)n(2)2(1)1n21(2)nn(2)n2(2)2n(2)22(1)1n(1)12(1)11bbbxxxaaaaaaa第1步 设 (2)(2)bxA记为： 第k步 （

21、k=2, 3, n-1）继续上述消元过程，设第k-1次消元已经完成，得到与原方程组等价的方程组 kn(k)k(2)2(1)1nk21(k)nn(k)nk(k)kn(k)kk(2)2n(2)22(1)1n(1)12(1)11bbbbxxxxaaaaaaaaa记为 (k)(k)bxAn,1kji,bmbbamaa(k)kik(k)i1)(ki(k)kjik(k)ij1)(kijn1,.,k，iaam(k)kk(k)ikik设 ，计算乘数 0 0a a( (k k) )k kk k用 乘以以上方程组的第k个方程加到第i个方程(i=k+1,n),消去从第k+1个方程到第n个方程中的未知数xk,得到与方

22、程组(6.3)等价的线性方程组 i ik kmm- -1)(k1)(kbxA中的元素的计算公式为与bA1)(k1)(k只要 ,消元过程就可以进行下去,直到经过n-1次消元之后，消元过程结束，得到与原方程组等价的上三角形方程组,记为 0a(k)kk(n)(n)bxA或者写成 (n)n(2)2(1)1n21(n)nn(2)2n(2)22(1)1n(1)12(1)11bbbxxxaaaaaa(n)nn(n)nn(2)2n(2)2n2(2)22(1)1n(1)1n2(1)121(1)11bxa bxaxabxaxaxa即 (6.7) （2）回代过程：是对上三角方程组（6.7）自下而上逐步回代解方程组计

23、算，即 ， abx(n)nn(n)nn,axabx(i)iijn1ij(i)ij(i)ii1 1,2,2,1,1,n ni i（3）高斯消去法的计算步骤：1n,1,2,k0,a(k)kkn,2,k1,kji, bmbbamaaaam(k)kik(k)i1)(ki(k)kjik(k)ij1)(kij(k)kk(k)ikik编程 消元过程; 设计算: 回代过程 ,1，2,n1,niaxab，xabx(i)iijn1ij(i)ij(i)ii(n)nn(n)nn编程算法. 覆盖A则An,1,2,.,k0,若a(k)(k)kkn，,1,2,消去：对于k 1.则停止计算.0,若a (1)kkn1,.,k对于i (2)kikiikkikikbmbb /aam (i)kjikijijamaa n1,.,k(ii)对于j,1,n,回代：对于i 2.iiii/ax x(3)iib x(1)n1,.,i(2)对于jjijiixax x上面这一段用于Matlab编程。Gauss消去法计算量(加法与乘法) n3Home