數(shù)值分析：2-2(b) Gauss列主元消去法

1、第二章第二章 解線性方程組的直接法解線性方程組的直接法 Gauss列主元列主元消去法消去法例例1.用用Gauss消去法解線性方程組消去法解線性方程組(用用3位十進(jìn)制浮位十進(jìn)制浮點(diǎn)數(shù)計算）點(diǎn)數(shù)計算）210001. 02121xxxx解:本方程組的精度較高的解為Tx)99989999. 0 ,00010001. 1 (*用Gauss消去法求解(用3位十進(jìn)制浮點(diǎn)數(shù)計算)一、一、Gauss列主元消去法的引入列主元消去法的引入),(bAA 21111000100. 01000021l441000. 111000. 101000100. 000. 1,00. 021xx回代后得到與精確解相比,該結(jié)果相當(dāng)糟

2、糕究其原因,在求乘數(shù)乘數(shù)時用了很小的數(shù)0.0001作除數(shù)主元),(bAA 121000100. 011 0001. 021l00. 1200. 1011如果在求解時將1,2行交換,即00. 1,00. 121xx回代后得到這是一個相當(dāng)不錯的結(jié)果),(bAA 例2.解線性方程組(用8位十進(jìn)制尾數(shù)的浮點(diǎn)數(shù)計算)321643. 5072. 12623. 4712. 3132103218xxx解:這個方程組和例1一樣,若用Gauss消去法計算會有小數(shù)作除數(shù)的現(xiàn)象,若采用換行的技巧,則可避免321643. 5072. 12623. 4712. 3132108行交換因此的列元素為絕對值最大很小3 , 1,

3、2,10138a 31rr1233210623. 4712. 31643. 5072. 12883121105 . 05 . 0ll101 . 05 . 03103 . 0102 . 001018015. 0103176. 00643. 5072. 12絕對值最大不需換行92722629. 032l54138685. 05 . 031041555186. 0001018015. 0103176. 00643. 5072. 12),()1()1(bA),()2()2(bA),()3()3(bA)3()3(3333abx 經(jīng)過回代后可得)1(113)1(132)1(12)1(11axaxabx54

4、138685. 01041555186. 039257367. 0)2(223)2(23)2(22axabx103176. 01018015. 05 . 03x05088607. 049105820. 0事實(shí)上,方程組的準(zhǔn)確解為Tx)367257384. 0 ,050886075. 0,491058227. 0(*),()1()1(bA例2所用的方法是在Gauss消去法的基礎(chǔ)上,利用換行避免小主元作除數(shù),該方法稱為Gauss列主元消去法列主元消去法二、二、Gauss消元過程與系數(shù)矩陣的分解消元過程與系數(shù)矩陣的分解1.Gauss消去法消元過程的矩陣描述)1()1()1(2)1(1)1(2)1(2

5、)1(22)1(21)1(1)1(1)1(12)1(11nnnnnnnbaaabaaabaaaniaalii, 3 , 2)1(11)1(11行變換相行變換相當(dāng)于左乘當(dāng)于左乘初等矩陣初等矩陣由于1111211nllL令則),()1()1(1bAL ),()2()2(bA1111, 1knkkkllL顯然若令則有),()()(kkkbAL ),()1()1(kkbA1, 3 ,2 , 1nk),()1()1(1bAL 2L1nL),()()(nnbA因此從而AL 12L1nL)(111211nnALLLA故為上三角矩陣)(nAU 為單位下三角矩陣111211nLLLLLU)(nA111111,3

6、 ,2,1 ,2, 12, 11 , 1323121nnnnnnnnllllllllllL即)()2(2)2(22)1(1)1(12)1(11nnnnnaaaaaa)(nAU 且UdetAdet順序主元niiiia1)(定義定義1. 不帶行交換的Gauss 消去法的消元過程,產(chǎn)生一個單位下三角矩陣L和一個上三角矩陣U,即該過程稱之為LUA .分解的矩陣LUA由上述分析不難得到nnnknknkkknkaaaaaaaaaA11111111111nknklll)()()()1(1)1(1)1(11nnnkknkkknkaaaaaak階順序主子陣kAkkkULA kAdetkUdetkiiiia1)(

7、kLkUnkAk,2 , 10detniaiii,2 , 10)(Gauss消去法可以執(zhí)行定理定理1. ,0detkkADAn的順序主子式階方陣若, 1,2 , 1nk存在且唯一分解結(jié)果的則LUALUA在定理中, 注意到0detnnAD0)(nnna即可能存在分解并不影響的這對LUA起決定作用消去法的回代能否進(jìn)行用但對方程組GaussbAx 矩陣的三種形式的分解Doolittle分解: A = LU (單位下三角與上三角) Crout分解: (下三角與單位上三角)LDU分解: A = LDU (單位下三角, 對角及單位上三角)ULA P58 習(xí)題習(xí)題 2.1(2)、2.3See you nex

8、t timeSee you next time！2.Gauss列主元消去法消元過程的矩陣描述（略去）列主元消去法消元過程的矩陣描述（略去）由于Gauss列主元消去法每一步都要選取列主元,因此不可避免要進(jìn)行行交換行交換后再消元行與的第要將步消元時設(shè)第kkkikbAk),(,)()(即),()()(kkbA),()1()1(kkbAkLkikI,kikI,101101行第k行第kikik 一般時kik IIkik,表示不換行初等矩陣因此,Gauss列主元消去法的消元過程為 :),()1()1(bA),()()(nnbA1 ,11iIL2,22iIL1,11ninnILA)(nA1 ,11iIL2,

9、22iIL1,11ninnIL顯然U上三角陣消元過程為時當(dāng)例如,4,nA)4(A1 ,11iIL2,22iIL3,33iILU3L3,23,33iiILI 3,2,12,3,3223iiiiIILII 1 ,2,3,123iiiIII AU3,23,233iiILIL 設(shè)3,2,12,3,13223iiiiIILIIL 仍然為單位下三角矩陣1 ,2,3,123iiiIIIP 初等矩陣的乘積,稱為排列陣排列陣則3L2L1LPAU推廣到一般情形1nL2L1LPAU2nLPA1(nL2L11)L2nLU1(nL2L11)L2nL令L仍然為單位下三角矩陣PALU則單位下三角陣與上三角陣的乘積分解的上述

10、過程稱為矩陣LUPA綜合以上討論,有定理定理2. ,0det,AAn即為非奇異矩陣階方陣若使得陣和一個非奇異上三角矩、一個單位下三角矩陣則必存在一個排列矩陣,ULPPALU開始EPSnbA,輸入輸出無解信息k1x輸出解EPSnnA|),(|nk kk1P選取主元素EPSP |消元換行停機(jī)回代求解TTTFFF三、三、Gauss列主元消去法的算法設(shè)計（略）列主元消去法的算法設(shè)計（略）(一) 流程圖(二) 自然語言n輸入方程組的維數(shù). 11,2 , 1,2 , 1,),(njniabAij的元素增廣矩陣EPS控制條件轉(zhuǎn)移精度1,2 , 1. 2nk對于PkkA),(1 . 2nkki, 1,2 .

11、2對于|),(|PkiA如果).(7,|3 . 2輸出無解信息則轉(zhuǎn)到如果EPSP 5 . 2,),(0否則轉(zhuǎn)則IiPkiA選主元1, 1,4 . 2nkkj對于wjkA),(),(),(0jkAjIA),(0jIAw, 16 . 2nki對于, 1, 1nkj對于),(),(/),(kimkkAkiA),(),(*),(),(jiAjkAkimjiA).(7,|),(|. 3無解則轉(zhuǎn)到如果EPSnnA).(7,|5 . 2輸出無解信息則轉(zhuǎn)到如果EPSP 換行消元)(),(/)1,(. 4nxnnAnnA1 ,2 , 1. 5 nk對于)(nnnnnabx )(1)()(iiinijjiijiiiaxabx),()(),()1.(1kkAjxjkAnkAxnkjk0Snkj, 1 對于SjxjkAS)(*),(S