矩陣三角分解法

1、一、直接法概述直接法是將原方程組化為一個(gè)或若干個(gè)三角形方程組的方法，共有若干種對(duì)于線性方程組bAx nnnnnnaaaaaaaaaA212222111211nxxxx21nbbbb21其中系數(shù)矩陣未知量向量常數(shù)項(xiàng)根據(jù)Cramer(克萊姆)法則,若0)det(A有唯一解則方程組bAx determinantal|)det(AA 行列式的記號(hào)若用初等變換法求解,則對(duì)其增廣矩陣作行初等變換:),(bAA),()1()1(bA),()2()2(bA經(jīng)過n-1次),()()(nnbA為上三角陣目標(biāo)：)(nA的解不難得到則方程組)()(nnbxAbAx bAx )()(nnbxA同解即以上求解線性方程組的

2、方法稱為Gauss消去法即和兩個(gè)三角形矩陣分解成的系數(shù)矩陣如果將線性方程組,ULAbAx LUA 則bLUx bLy yUx 都是三角形方程組上述方法稱為直接三角形分解法2 Matrix Factorization Doolittle 道立特分解法道立特分解法 /* Doolittle Factorization */： LU 分解的緊湊格式分解的緊湊格式 /* compact form */反復(fù)計(jì)算反復(fù)計(jì)算,很浪費(fèi)哦很浪費(fèi)哦 通過比較法直接導(dǎo)出通過比較法直接導(dǎo)出L 和和 U 的計(jì)算公式。的計(jì)算公式。思思路路 nnnnnnnnuuullaaaa.1.11.1111211111 ),min(1j

3、ikjkkiul jia2 Matrix Factorization Doolittle固定固定 i : :對(duì)對(duì) j = i, i+1, , n 有有ijkjikikijuula 11lii = 1kjikikijijulau 11a固定固定 j ，對(duì)，對(duì) i = j, j+1, , n 有有jjijkjjkikijulula11jjjkkjikijijuulal/ )(11bju1ja11111ualii上述解線性方程組的方法稱為直接三角分解法的 Doolittle法例1. 用Doolittle法解方程組1391444321131243301024321xxxx72510解:由Doolitt

4、le分解14131211uuuu30102Tlll4131211T25 . 05 . 112423220uuu5 . 812110Tll423210T11/611/310343300uu11/211/300Tl43100T910044000u4000得解, bLy Tyyyy4321T1611/17201011rkkjrkrjrjulaurrrkkrikiriruulal11得解, yUx Txxxx4321T4321nnnnuyx rrnrjjrjrruxuyx1Doolittle法在計(jì)算機(jī)上實(shí)現(xiàn)是比較容易的但如果按上述流程運(yùn)算仍需要較大的存儲(chǔ)空間:都需要單獨(dú)的存儲(chǔ)空間yULxbA,式可知的

5、計(jì)算過程而從)4()1(,ijijul的存儲(chǔ)位置即不再需要后的第一行求出)1(11jauUjj的存儲(chǔ)位置即不再需要后的第一列求出)2(11ialLii的存儲(chǔ)位置即不再需要后行的第求出)(rjaurUrjrj的存儲(chǔ)位置即不再需要后列的第求出)1( rialrLirir因此可按下列方法存儲(chǔ)數(shù)據(jù):nrrjuarjrj,2 , 1),(1,2 , 1),1(nrrilairir有如下特點(diǎn)：時(shí)解三角形方程組同樣,bLy 的存儲(chǔ)位置即不再需要后求出11by的存儲(chǔ)位置即不再需要后求出)2( ibyiiniybii,2 , 1,空出的存儲(chǔ)位置的存儲(chǔ)可以使用因此)1( ibyii直接三角分解的Doolittle

6、法可以用以下過程表示:432144434241343332312423222114131211bbbbaaaaaaaaaaaaaaaa4535251544434241343332312423222114131211aaaaaaaaaaaaaaaaaaaa存儲(chǔ)單元(位置)4321444342413433323124232221141312111bbbyaaalaaalaaaluuuur4321444342413433323124232221141312112bbyyaallaalluuuluuuur4321444342413433323124232221141312113byyyallluull

7、uuuluuuur4321444342413433323124232221141312114yyyyullluulluuuluuuuryUL,可知從上式最后一個(gè)矩陣中yUx 然后解線性方程組緊湊格式的Doolittle法例2. 用緊湊格式的Doolittle法解方程組(例1)解:4535251544434241343332312423222114131211aaaaaaaaaaaaaaaaaaaaA7251013914443211312433010272510139142432211312423301021rju1ja11111ualii11rkkjrkrjrjulaurrrkkrikirir

8、uulal1172201013911624311321217121123301022r11rkkjrkrjrjulaurrrkkrikiriruulal11711172010139116211211311321217121123301023r161117201049116211211311321217121123301024rLxU43214911621121131132121712112330102yUx解4321xxxxx4321所以yMatrix Factorization Choleski 平方根法平方根法 /* Choleskis Method */： 對(duì)稱對(duì)稱 /* symmetr

9、ic */ 正定正定 /* positive definite */ 矩陣的分解法矩陣的分解法定義定義一個(gè)矩陣一個(gè)矩陣 A = ( aij )n n 稱為稱為對(duì)稱陣對(duì)稱陣，如果，如果 aij = aji 。定義定義一個(gè)矩陣一個(gè)矩陣 A 稱為稱為正定陣正定陣，如果，如果 對(duì)任意非對(duì)任意非零向量零向量 都成立。都成立。0 xAxTx回顧：回顧：對(duì)稱正定陣的幾個(gè)重要性質(zhì)對(duì)稱正定陣的幾個(gè)重要性質(zhì) A 1 亦對(duì)稱正定，且亦對(duì)稱正定，且 aii 0若不然，則若不然，則0 xA存在非零解，即存在非零解，即0 xAxT存在非零解。存在非零解。1111)()(, AAIAAIAATTT對(duì)任意對(duì)任意 , 存在存在

10、 , 使得使得 ,即即 。0 x0 yxyA xAy1 011 yAyyAAAyxAxTTT 其中其中0 xAxaTiiTx)0.1.0( 第第 i 位位 A 的順序主子陣的順序主子陣 /* leading principal submatrices */ Ak 亦對(duì)亦對(duì) 稱正定稱正定對(duì)稱性顯然。對(duì)任意對(duì)稱性顯然。對(duì)任意 有有 , 其中其中 。kkRx 00 xAxxAxTkkTknkRxx 00 A 的特征值的特征值 /* eigen value */ i 0 設(shè)對(duì)應(yīng)特征值設(shè)對(duì)應(yīng)特征值 的非零特征向量的非零特征向量為為 ，則，則 。20 xxxxAxTT x A 的全部順序主子式的全部順序主

11、子式 det ( Ak ) 0因?yàn)橐驗(yàn)?niiA1)det( 一、對(duì)稱正定矩陣的三角分解(Cholesky分解)nkAAk,2 , 1,0det的順序主子式且為對(duì)稱正定矩陣階矩陣若AnAAAT,0)det(則)(分解或分解可以進(jìn)行因此DoolittleLUA記為L(zhǎng)UA 為上三角陣為單位下三角陣其中UL,nnnnnuuuuuuuuuuU333223221131211nnuuuu33221111111, 1, 1222222311111131112nnnnnnuuuuuuuuuuuu0 DU),(2211nnuuudiagD0DUU 02121UDDLUA 02121UDLD22211),(nnu

12、uudiagDiagonal:對(duì)角)(02121UDLD是單位下三角陣是單位上三角陣，唯一，由于TUULDULUA000AAAT,為對(duì)稱正定陣而TTLDUA)(0因此TTTLDU0TLDL所以002121)( ,UDLDULTT綜合以上分析,211LDLAn為對(duì)稱正定矩陣，令階矩陣若則有TLLA11定理1. (Cholesky分解)使得正數(shù)的下三角陣元全是則一定存在一個(gè)主對(duì)角為對(duì)稱正定矩陣設(shè),LATLLA 且該分解式唯一這種關(guān)于對(duì)稱正定矩陣的分解稱為Cholesky分解nnnrnrrrllllllL1111nnnrnrnrrrnraaaaaaaaaA111111設(shè)jiijaa irarArL列

13、元素的第考察列已求出的第假設(shè),11nnnrnrrrllllll1111nnnrnrnrrrnraaaaaaaaa111111nnnrrrnrllllll1111111111lla112121lla1111llaiini,2 , 1可以求出的第一列元素1ilLrkrkrkrrlla12112rrrkrkllrkrkikirlla1rrirrkrkikllll11nrri, 1,的元素的計(jì)算公式式可得由L)8()6(1111al1111laliini, 3 ,2112rkrkrrrrlalnr,2 rrrkrkikirirlllal11nri, 1 二、對(duì)稱正定線性方程組的解法bAx 線性方程組階

14、對(duì)稱正定矩陣為其中nA使得的下三角陣則存在主對(duì)角元為正數(shù),LTLLA 則線性方程組(10)可化為兩個(gè)三角形方程組bLy yxLTbxLLT)(bLy 解. 1nnniniiillllllL11111111lby iiikkikiilylby11ni, 3 ,2yxLT解. 2nnniiiniTllllllL1111nnnnlyx iinikkkiiilxlyx1對(duì)稱正定方程組的平方根法1 ,2 , 1 ni例1.用平方根法解對(duì)稱正定方程組91096858137576321xxx解:A先分解系數(shù)矩陣6858137576Arrrkrkikirirrkrkrrrriilllallallalal111

15、1211111111 29251741365629676分解TLLLbLy 其次解91091111lby 692212122lylby62969*71017433321333lylbykkk29101111lby iiikkikiilylby1129251741365629676),(bL即Tyyyy),(321T)2910,1743,69(yxLT最后解291017436929251741362965676nnnnlyx iinikkkiiilxlyx13333lyx 1132111lxlyxkkk22233222lxlyx11),(yLT三、平方根法的數(shù)值穩(wěn)定性用平方根法求解對(duì)稱正定方程組

16、時(shí)不需選取主元TLLA 由可知rkrkrkrrlla1rkrkl12因此rrrkal2|不會(huì)放大得以控制中間量,rklnr,2 , 1rk,2 , 1平方根法是數(shù)值穩(wěn)定的事實(shí)上,對(duì)稱正定方程組也可以用順序Gauss消去法求解而不必加入選主元步驟2 Matrix Factorization Tridiagonal System 追趕法解追趕法解三對(duì)角三對(duì)角方程組方程組 /* Crout Reduction for Tridiagonal Linear System */ nnnnnnnfffxxxbacbacbacb212111122211Step 1: 對(duì)對(duì) A 作作Crout 分解分解 11

17、1121nnnA 直接比較等式兩邊直接比較等式兩邊的元素，可得到計(jì)的元素，可得到計(jì)算公式。算公式。Step 2: 追追即解即解 ：fyL ,111 fy ),.,2()(1niyrfyiiiii Step 3: 趕趕即解即解 ：yxU )1,., 1(,1 nixyxyxiiiinn 與與G.E.類似，一旦類似，一旦 i = 0 則算法中斷，故并非任何則算法中斷，故并非任何三對(duì)角陣都可以用此方法分解。三對(duì)角陣都可以用此方法分解。有一類方程組,在今后要學(xué)習(xí)的插值問題和邊值問題中有著重要的作用,即三對(duì)角線方程組,其形式為:nnnnnbacbacbacbA11122211nxxxx21fAx 其中n

18、ffff21并且滿足稱為三對(duì)角線矩陣,A0|)1(11 cb-(1)0,|)2(iiiiicacab1,2ni0|)3(nnab.線矩陣稱為對(duì)角占優(yōu)的三對(duì)角A0det,AA即非奇異顯然0det,kAkA即階順序主子式非零的任意因此分解進(jìn)行可以將所以LUA,分解為為上三角陣時(shí)為單位下三角陣DoolittleUL,分解為為單位上三角陣時(shí)為下三角陣CroutUL,以下以Crout分解導(dǎo)出三對(duì)角線方程組的解法設(shè)LUA nnnnnbacbacbacbA1112221111111111221nnnnn),.,2( ),.,2( ,111nicniabbiiiiiiiii1111 ,iiiiiiiibbb),.,2( niaaiiii),.,2(c c 1nibciiiiiiiiii11111111221nnnnnnnnnnbacbacbacb11122211例1.用追趕法解三對(duì)角線方程組010131132132134321xxxx解:Taaaa),(432設(shè)T)1 ,2 ,2(Tbbbbb),(4321T)3 , 3 , 3 , 3(Tfffff),(4321T)0