第二章線性代數(shù)方程組的直接解法

1、數(shù)數(shù) 值值 分分 析析武武 漢漢 大大 學(xué)學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院基礎(chǔ)數(shù)學(xué)系數(shù)學(xué)與統(tǒng)計(jì)學(xué)院基礎(chǔ)數(shù)學(xué)系劉丁酉 主頁主頁2 2 線性代數(shù)方程組的直接解法線性代數(shù)方程組的直接解法主頁主頁 2.1 2.1 引論引論 2.2 2.2 GaussGauss消去法消去法 2.3 2.3 直接三角分解方法直接三角分解方法 2.4 2.4 矩陣的條件數(shù)與病態(tài)方程組矩陣的條件數(shù)與病態(tài)方程組 2.1 2.1 引論引論主主nnnnnnnnnnbxaxaxabxaxaxabxaxaxa22112222212111212111 nnnnnnnnbbbbxxxXaaaaaaaaaA21212122221112112.2 Gaoss

2、2.2 Gaoss消去法消去法2.2.1 2.2.1 順序消去與回代過程順序消去與回代過程2.2.2 2.2.2 順序消去能實(shí)現(xiàn)的條件順序消去能實(shí)現(xiàn)的條件2.2.3 2.2.3 矩陣的三角分解矩陣的三角分解2.2.4 2.2.4 列主元素消去法列主元素消去法主頁主頁2.2.1 2.2.1 順序消去與回代過程順序消去與回代過程1,3322111, 223232221211, 11313212111nnnnnnnnnnnnnnaxaxaxaxaaxaxaxaxaaxaxaxaxa主頁主頁(0)(0)(0)(0)(0)111122133111(1)(1)(1)(1)222233221(2)(2)(2

3、)333331(1)(1)1nnnnnnnnnnnnnnnnaxaxaxaxaaxaxaxaaxaxaaxa主頁主頁消元公式消元公式( 1)( 1)(k)( 1)( 1)ij, 1 k n-1, k+1 i na, k+1 i n, k+1 j n+1kikikkkkkkijik kjalaal a 回代公式回代公式(1)1(1)(1)(1)11(1),1,2,1nnnnnnnniiinijjj iijiiaxaaaxxinna 在上面的消元過程中在上面的消元過程中,應(yīng)特別注意到元素應(yīng)特別注意到元素(稱之為主稱之為主元素元素).因?yàn)槿绻髟貫橐驗(yàn)槿绻髟貫?,消元過程將無法進(jìn)行下去消元過程

4、將無法進(jìn)行下去.如如果主元果主元 的絕對值較小的絕對值較小,作為除數(shù)也不合適作為除數(shù)也不合適.所以這種所以這種方法是不恰當(dāng)?shù)姆椒ㄊ遣磺‘?dāng)?shù)? 另外另外,我們總是通過乘數(shù)我們總是通過乘數(shù) 來消元來消元,從而稱從而稱 為乘為乘數(shù)數(shù).(1)kkka主頁主頁iklikl2.2.2 2.2.2 順序消去實(shí)現(xiàn)的條件順序消去實(shí)現(xiàn)的條件n nA R120,0,0k (0)(1)(1)11220,0,0kkkaaa主頁主頁定理定理2.2.12.2.1 設(shè)設(shè)，若對若對k=1,2,k=1,2,，n n，A A的順序主子式的順序主子式，則每步消去過程的對角元，則每步消去過程的對角元定理2.2.1的逆定理也成立，即若則

5、則120,0,0k (0)(1)(1)11220,0,0kkkaaa2.2.3 2.2.3 矩陣的三角分解矩陣的三角分解主頁主頁引理引理3.13.1 用用m m階單位下三角方陣階單位下三角方陣L L左乘左乘m mn n階矩陣階矩陣A A所得所得矩陣矩陣B,B,則則A A與與B B的的p p階主子式相等階主子式相等.21m m12,10010 L1m nm nmmBlll 證 設(shè)A11111211122122212221220BB, , B=BBLAALALLAA11111112211122212112222211122122LALALALALALALABBBB111111,L A B11111

6、1L AB111111111111L ALAAB1112112122, 0,0aaAaAaa證 設(shè)依條件1112(0)(0)11121221(1)22221100aaaaAa aaaa(0)(0)111221(1)221110aa, U=10aLaaALU所以,當(dāng)n=2時(shí),定理成立. 設(shè)當(dāng)n=k時(shí),定理成立. 則,當(dāng)n=k+1時(shí),有:11,1,11,11,12,13,11,1 (i=2,3,k+1) a0(,)TkiiTkarASAalamlll11121,k+121222,k+1k+1,1k+1,2k+1,k+1aaaaaaaaa其中 1,1110TkkkarAmESB于是,kkL Ukkk

7、BL U11010kkm Em E11111111111101000101000100TTkkkkkkTkkkTkkkkararAmEmEBLUarmELUarL UmLUkB又所以,.ALU ALULULU11U ULL1-1, LUUELE由于此式左邊上三角矩陣由于此式左邊上三角矩陣, ,右邊為下三角矩陣右邊為下三角矩陣, ,所所以必有以必有, U=ULL1122nnALUL UUu uu 此定理是矩陣分解的重要定理,稱作矩陣的LU分解,也叫杜利特爾分解. 它是用直接法解線性方程組的理論基礎(chǔ).此外,可利用LU分解來計(jì)算A的行列式的值.即:), 3 , 2(111niylbybykikiki

8、i) 1, 2, 1(1niuxuyxuyxiiknikikiinnnn（4）（5）進(jìn)而,由 LY=b, UX=Y, 有: 解決問題的方法是:在系數(shù)矩陣中按列選取絕對值最大的元素作為主元素進(jìn)行消元.以后每一步都作一次這樣的調(diào)整.直至將系數(shù)矩陣化為上三角矩陣.稱這種消元法為: 列主元消元法. 另外還有: 全主元消元法.2.2.4 2.2.4 列主元素消去法列主元素消去法主頁主頁2.3 2.3 直接三角分解方法直接三角分解方法2.3.1 Doolittle2.3.1 Doolittle分解方法分解方法2.3.2 2.3.2 三對角方程組的追趕法三對角方程組的追趕法2.3.3 2.3.3 對稱正定矩

9、陣的對稱正定矩陣的CholeskyCholesky分解、分解、 平方根法平方根法主頁主頁 杜杜立特分解法立特分解法 / /* * Doolittle Factorization Doolittle Factorization LULU 分解的緊湊格式分解的緊湊格式反復(fù)計(jì)算反復(fù)計(jì)算,很浪費(fèi)哦很浪費(fèi)哦 通過比較法直接導(dǎo)出通過比較法直接導(dǎo)出L 和和 U 的計(jì)算公式。的計(jì)算公式。思思路路2.3.1 Doolittle2.3.1 Doolittle分解方法分解方法主頁主頁 nnnnnnnnuuullaaaa.1.11.1111211111 j ia ),min(1jikjkkiul直接三角分解法解直接三

10、角分解法解AX = b的計(jì)算公式的計(jì)算公式niauii, 2 , 111niualii, 2 , 11111對對于于r = 2, 3, , n計(jì)算計(jì)算（2 2）計(jì)算）計(jì)算U U的第的第r r行元素行元素 ), 1,( 11nrriulaurkkirkriri（3 3）計(jì)算）計(jì)算L L的第的第r r 列元素列元素 ( (r r n n) ), 1()(11nriuulalrrrkkrikirir(1)2.4 2.4 矩陣的條件數(shù)與病態(tài)方程組矩陣的條件數(shù)與病態(tài)方程組2.4.1 擾動(dòng)方程組、病態(tài)現(xiàn)象2.4.2 矩陣的條件數(shù)與擾動(dòng)方程組的 誤差分析2.4.3 病態(tài)方程組的解法主頁主頁2.4.1 2.4

11、.1 擾動(dòng)方程組、病態(tài)現(xiàn)象擾動(dòng)方程組、病態(tài)現(xiàn)象A,det0.n nRA,AAbb和()()AA xxbb 主頁主頁設(shè)方程組Ax=b的系數(shù)矩陣A和右端向量b若有擾動(dòng)，分別成為那么實(shí)際解的是方程組這里1.xA b我們要問，若|Ab和都是小的實(shí)數(shù)，|x是否也是小的？這就是擾動(dòng)方程組的誤差分析問題。主頁主頁例例2.4.1 方程組123143.0001 14.0001xx123142.99914.0002xx(1,1) .Tx ( 2,10) .Tx 的準(zhǔn)確解是若A及b有微小的變化，擾動(dòng)后方程組為則其解可見A,b的微小變化可以使解有很大的變化。從上面的例子可以看到，方程組的解對A或b的擾動(dòng)可能是敏感的，

12、這時(shí)稱方程組是病態(tài)方程組（或A是病態(tài)矩陣），病態(tài)與否決定于A。求解求解 時(shí)，時(shí)，A A 和和 的誤差對解的誤差對解 有何影響？有何影響？bxA bx 設(shè)設(shè) A 精確，精確， 有誤差有誤差 ，得到的解為，得到的解為 ，即，即bb xx bbxxA )(bAx 1 |1bAx 絕對誤差放大因子絕對誤差放大因子|xAxAb 又又|1bAx |1bbAAxx 相對誤差放大因子相對誤差放大因子2.4.2 2.4.2 矩陣的條件數(shù)與擾動(dòng)方程組的誤差分析矩陣的條件數(shù)與擾動(dòng)方程組的誤差分析bxxAA )( 設(shè)設(shè) 精確，精確，A有誤差有誤差 ，得到的解為，得到的解為 ，即，即bA xx bxxAxxA )()(

13、 )(1xxAAx |11AAAAAAxxx 是關(guān)鍵是關(guān)鍵的誤差放大因子，稱為的誤差放大因子，稱為A的的條件數(shù)條件數(shù)，記為，記為cond (A) ,越越 則則 A 越病態(tài)，越病態(tài)，難得準(zhǔn)確解。難得準(zhǔn)確解。|1 AA大大定義定義6 6：設(shè)設(shè)A A 為為n n 階非奇矩陣，稱數(shù)階非奇矩陣，稱數(shù) 為矩陣為矩陣A A的的 條件數(shù)，條件數(shù)，AA1條件數(shù)的性質(zhì)：條件數(shù)的性質(zhì)： ）cond ( A )1）cond ( kA )= cond ( A ) k k 為非零常數(shù)為非零常數(shù)）若若 ， 則則1A1)(cond AA記為記為cond( A )。 iv ) 設(shè)對角矩陣設(shè)對角矩陣D D非奇異非奇異, ,則則1

14、1max()minii nii ndcond Dd 定義7:設(shè)A是非奇異矩陣,若Cond(A)遠(yuǎn)大于1,則稱方程組AX=b是病態(tài)的,否則稱方程組是良態(tài)的.對于先前的例子114111.000111,11.0001110.0001()2.0001* 2.0001*10 40000AACond AAA所以是病態(tài)方程組,從而不能用直接法求解. 一個(gè)方程組是否病態(tài)，由一個(gè)方程組是否病態(tài)，由A的性質(zhì)決定，與用什么數(shù)值的性質(zhì)決定，與用什么數(shù)值解法無關(guān)。對于病態(tài)的方程組。數(shù)值求解要小心進(jìn)行，否解法無關(guān)。對于病態(tài)的方程組。數(shù)值求解要小心進(jìn)行，否則可能得不到所要求的精確度。則可能得不到所要求的精確度。 解病態(tài)方程組，可以采用高精度運(yùn)算，例如雙倍或更多解病態(tài)方程組，可以采用高精度運(yùn)算，例如雙倍或更多倍字長的運(yùn)算，使由于誤差放大而損失若干有效數(shù)位之倍字長的運(yùn)算，使由于誤差放大而損失若干有效數(shù)位之后，還能保留一些有效位。后，還能保留一些有效位。2.4.3 2.4.3 病態(tài)方程組的解法病態(tài)