計(jì)算方法 解線性方程組的直接法

1、第8次 線性方程組的直接解法計(jì)算方法(Numerical Analysis)1）高斯消去法2）高斯主元素消去法3）方程組的性態(tài)4) 高斯消去法算法構(gòu)造（編程）本講內(nèi)容高斯消去法5.1 引言 在工程技術(shù)、自然科學(xué)和社會(huì)科學(xué)中，許多問(wèn)題最終都可歸結(jié)為求解線性方程組的數(shù)學(xué)問(wèn)題。 線性方程組的求解對(duì)于實(shí)際問(wèn)題是極其重要的。 解線性方程組的直接法nnnn2n21n12n2n2221211n1n212111bxa.xaxa.bxa.xaxabxa.xaxan21n21nnn2n12n22211n1211b.bbB,x.xxx,.aaa.aaa.aaaA解線性方程組的直接法可簡(jiǎn)記為 Ax=b，其中 ( 6.

2、1 ) 常見(jiàn)的nxn線性方程組，一般形式為 線性方程組的數(shù)值解法一般有兩類(lèi)：1. 直接法：就是經(jīng)過(guò)有限步算術(shù)運(yùn)算，可求得方程組精確解的方法（若計(jì)算過(guò)程中沒(méi)有舍入誤差），如克萊姆法則就是一種直接法，直接法中具有代表性的算法是Gauss消去法。2. 迭代法: 就是用某種極限過(guò)程去逐步逼近線性方程組的精確解的方法。也就是從解的某個(gè)近似值出發(fā)，通過(guò)構(gòu)造一個(gè)無(wú)窮序列去逼近精確解的方法。(一般有限步內(nèi)得不到精確解)(4) 4 x (3) 7x x (2) 9xx x(1) 10 xxxx4434324321例子：求解如下的上三角線性方程組：解：由（4），得4x43x3將（4）帶入（3），得將結(jié)果代入（2）

3、， 得2x2將結(jié)果代入（1）， 得1x1 5.2 高斯消去法 5.2 高斯消去法 5.2.1 高斯消去法的基本思想72xx45x2x4x13xx2x21321321 解:高斯消去法包括如下的消元和迭代的兩個(gè)過(guò)程。 先用一個(gè)簡(jiǎn)單實(shí)例來(lái)說(shuō)明Gauss法的基本思想例5.1 解線性方程組 （1）消元過(guò)程)21(1x213x23x25 2x4x 13xx2x3232321第1步:將方程乘上(-2)加到方程 上去,將方程 乘上 加到方程 上去,這樣就消去了第2、3個(gè)方程的 項(xiàng),于是就得到等價(jià)方程組 第2步：將方程 乘上 加到方程 上去，這樣就消去了第3個(gè)方程的 項(xiàng)，于是就得到等價(jià)方程組 )85(2x421

4、x872x4x13xx2x332321這樣，消元過(guò)程就是把原方程組化為上三角形方程組，其系數(shù)矩陣是上三角矩陣。 （2）回代過(guò)程將上述三角形方程組自下而上求解得：9x1x6x123從而求得原方程組的解： 6x1,x9,x321前述的消元過(guò)程相當(dāng)于對(duì)原方程組的增廣矩陣進(jìn)行下列行變換702145241312bAA2132325021401312421870021401312同樣可得到與原方程組等價(jià)的方程組 122)r(r13)r21(r23)r85(r高斯消去法的基本思想：這種求解上三角方程組的方法稱為回代, 通過(guò)一個(gè)方程乘或除以某個(gè)常數(shù),利用矩陣行的初等變換將原方程組Ax=b系數(shù)矩陣化為上三角形矩

5、陣,然后從最后一個(gè)方程開(kāi)始,依次向前代入求出未知變量：將兩個(gè)方程相加減,逐步減少方程中的變?cè)獢?shù),最終將方程組化成上三角方程組,一般將這一過(guò)程稱為消元,然后再回代求解。11nnx,x,x5.2.3 高斯消去法的適用條件 注2： 設(shè)系數(shù)矩陣A為非奇異矩陣，則若a11 =0，則可以通過(guò)調(diào)換行的方法，使得在第一行的第一個(gè)元素非0。其它在消元過(guò)程中，kk位置的情形類(lèi)似處理。則高斯消元法可以進(jìn)行。注1：設(shè)系數(shù)矩陣A為非奇異矩陣，直接使用高斯消元法（不進(jìn)行行的交換）對(duì)于某些簡(jiǎn)單的矩陣可能失敗，例如：0 11 0A證明：上三角形方程組是從原方程組出發(fā)，通過(guò)逐次進(jìn)行“一行乘一數(shù)加到另一行”而得出的，該變換不改變

6、系數(shù)矩陣順序主子式的值。 因此，需要對(duì)上述的高斯算法進(jìn)行修改，首先應(yīng)該研究原來(lái)的矩陣A在何條件下能夠保證 1n,1,2,對(duì)k0,a(k)kk定理1 若方程組系數(shù)矩陣的順序主子式全不為0，則高斯消去法能實(shí)現(xiàn)方程組的求解，即：1n,1,2,對(duì)k0,a(k)kk設(shè)方程組系數(shù)矩陣 ，其順序主子式 n ni ij j) )( (a aA A 0aaaaAmmm11m11m(m =1,2,，n) 經(jīng)變換得到的上三角形方程組的順序主子式 所以能實(shí)現(xià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 設(shè)矩陣 每一行對(duì)角元素的絕對(duì)值都大于同行其他元素絕對(duì)值之和 nij)(aA n,2, 1,i, |a|a|nij1jijii則稱A為嚴(yán)格對(duì)角占優(yōu)矩陣。 |)a|a|a(|a|1n131211|)a|a|a(|a|2n232122|)a|a|a(|a|1)-n(nn2n1nn 上述條件展開(kāi)以后為：定理1.1 若方程組 的系數(shù)矩陣A為嚴(yán)格對(duì)角占優(yōu)，則用高斯消去法求解時(shí)， 全不為0。因此，可以使用高斯消去法求解。 bAx (k)kka練習(xí)：用高斯消去法求解如下的線性方程組(3) 189x3x2x(2) 15x6x (1) 6xx3x32132321 1893-2151-606113bAA解：增

8、廣矩陣為1893-2151-606113bAA0 x3x3x12314325311-0151-606113422511-0151-6061132139613900151-606113Home高斯主元素消去法使用高斯消去法求解時(shí)，在消元過(guò)程中可能會(huì)出現(xiàn) 的情況，這時(shí)消去法將無(wú)法進(jìn)行；0a(k)kk5.3 高斯主元素消去法0a(k)kk即使 ，但它的絕對(duì)值很小時(shí)，用其作除數(shù)，會(huì)導(dǎo)致其他元素?cái)?shù)量級(jí)的嚴(yán)重增長(zhǎng)和舍入誤差的擴(kuò)散，將嚴(yán)重影響計(jì)算結(jié)果的精度。實(shí)際計(jì)算時(shí)必須避免這類(lèi)情況的發(fā)生。主元素消去法就可彌補(bǔ)這一缺陷。 例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位有效數(shù)字）： 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計(jì)算解為： 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。變換行，避免絕對(duì)值小的主元做除數(shù) 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這個(gè)解比解法1更加接近真實(shí)的解。)21(-rr12)20001(rr13)3.1762.001(-rr233 31 1r rr r 交換原則：通過(guò)方程或變量次序的交換，使在對(duì)角線位置上獲得絕對(duì)值盡可能大的系數(shù)作為akk(k)，稱這樣的akk(k) 為主元素，并稱使用主元素的消元法為主元素法 根據(jù)主元素選取范圍分為： 列主元素法 行主元素法(不講) 全主元素法(不講)5.3

12、高斯主元素消去法（續(xù)）5.3.2 列主元素法 列主元素法就是在待消元的所在列中選取主元（選取一列中絕對(duì)值最大的元素當(dāng)主元），經(jīng)方程的行交換，置主元于對(duì)角線位置后進(jìn)行消元的方法。 例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計(jì)算m32=1/6 =0.16667(11) 4.133322.34168x- (9) 5.2 5.05x 6x (4) 4 x 40 x 20 x-332321保留有主元素的方程進(jìn)行回代，得列選主元素的計(jì)算方法與高斯消去法完全一樣,不同的是在每步消元之前要按列選出主元4.41634x2.35230 x -1

14、.76511 x123 -1.76511 x 2.35230 x4.41634x321例5.5 用矩陣的初等行變換求解解方程組 75x4x2x17x7x4x 33x2x2x 321321321 解: 用矩陣的初等行變換求解,對(duì)增廣矩陣 (下面帶下劃線元素為主元素) 矩陣的列主元素計(jì)算方法可以用矩陣的初等行變換實(shí)現(xiàn)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,同學(xué)課堂練習(xí)：用列主元素法求解線性方程組：(3) 6xx3x(2) 189x3x2x(1) 15x6x 32132132 Home方程組的性態(tài)5.5 方程組的性態(tài)在建立方程組時(shí)，其系數(shù)往往含有誤差（如觀測(cè)誤差或計(jì)算誤差），即，所要求解的運(yùn)算是有擾動(dòng)的方程組，因此需要研究擾動(dòng)對(duì)解的影響。 例5.13 考察方程組 2.00011.0001xx2xx212121.0001xx2xx2121和上述方程組（1）是方程組（2）在右端項(xiàng)施加了微小的擾動(dòng), 但解大不相同. （1）（2）1xx21方程組（1）的解：0

16、 x2,x21方程組（2）的解： 這類(lèi)方程組稱為病態(tài)的。定義5.8 A或b的微小變化(又稱擾動(dòng)或攝動(dòng))引起方程組Ax=b解的巨大變化，則稱方程組為病態(tài)方程組，矩陣A稱為病態(tài)矩陣。否則方程組是良態(tài)方程組，矩陣A也是良態(tài)矩陣 。 為了定量地刻畫(huà)方程組“病態(tài)”的程度，要對(duì)方程組Ax=b進(jìn)行討論，考察A（或b）微小誤差對(duì)解的影響。為此先引入矩陣范數(shù)的概念： 矩陣范數(shù)的概念：n1jijni1|a|max|A|A的行范數(shù)矩陣A的無(wú)窮范數(shù)；n1iijnj11|a|max|A|A的列范數(shù)矩陣A的1范數(shù)；定義5.9 （矩陣條件數(shù)）設(shè)A為非奇異矩陣，稱 1 1A AA Ac co on nd d( (A A) )

17、 為矩陣A條件數(shù)。 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) )常用的條件數(shù)有條件數(shù)的性質(zhì)：1 1; ;c co on nd d( (A A) )v v對(duì)于任何非奇異矩陣A,都有：當(dāng)cond(A)v 1時(shí)，則方程組Ax=b是病態(tài)的；否則，Ax=b是良態(tài)的。病態(tài)方程組(矩陣)的定量描述：例6.13 線性方程組 20

18、 xx111121的系數(shù)矩陣帶誤差，成為如下方程組 20 xx1.000511121求方程組系數(shù)矩陣的條件數(shù), 并說(shuō)明方程組的性態(tài). 解： 因?yàn)?1111A111121A1212AAcond(A)1所以 因此方程組是良態(tài)的 例9 Hilbert矩陣Hn的定義如下1113336cond()408748.HHH12n11n1 n11n1 31 21n1 21 1Hn 求H3 的條件數(shù)。結(jié)論：Hilbert矩陣H3 是病態(tài)矩陣；可以證明，當(dāng)n越大的時(shí)候， Hn的 病態(tài)越嚴(yán)重。1123111133234111345193630, 36192180 , 30180180 HH解：本次小結(jié) 直接法是一種計(jì)

19、算量小而精度高的方法。直接法中具有代表性的算法是高斯（Gauss）消去法；克萊姆算法也是一種直接法，但該算法用于高階方程組時(shí)計(jì)算量太大而不實(shí)用；選主元的算法有很好的數(shù)值穩(wěn)定性。從計(jì)算簡(jiǎn)單出發(fā)實(shí)際中多選用列主元法；注意線性方程組有的時(shí)候具有病態(tài)；線性方程組的病態(tài)程度是其本身的固有特性，因此即使用數(shù)值穩(wěn)定的方法求解，也難以克服嚴(yán)重病態(tài)導(dǎo)致的解的失真。Home高斯消去法算法構(gòu)造5.2.2 高斯消去法算法構(gòu)造(Matlab 編程使用) n21n21nnn2n12n22211n1211bbbxxxaaaaaaaaa( 6.3 ) Gauss消去法的消元過(guò)程：對(duì)( 6.3 )的增廣矩陣進(jìn)行行初等變換。將例

20、6.1中解三階線性方程組的消去法推廣到一般的 階線性方程組，并記n nn n n),1,2,j(i,bb,aai(1)iij(1)ij線性方程組(6.1)用矩陣形式表示為 則高斯消去法的算法構(gòu)造歸納為： Gauss消去法的消元過(guò)程(由n-1步組成)： 0，a(1)11n2,3,.,i,aam(1)11(1)i1i1用 乘以第1個(gè)方程后加到第 個(gè)方程上去,消去第2到第n個(gè)方程的未知數(shù) ,得到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步 設(shè) (2)(2)bxA記為： 第k步 （

21、k=2, 3, n-1）繼續(xù)上述消元過(guò)程，設(shè)第k-1次消元已經(jīng)完成，得到與原方程組等價(jià)的方程組 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設(shè) ，計(jì)算乘數(shù) 0 0a a( (k k) )k kk k用 乘以以上方程組的第k個(gè)方程加到第i個(gè)方程(i=k+1,n),消去從第k+1個(gè)方程到第n個(gè)方程中的未知數(shù)xk,得到與方程組(6.3)等價(jià)的線性方程組 i ik kmm- -1)(k1)(kbxA中的元素的計(jì)算公式為