1、5.4 矩陣三角分解法矩陣三角分解法 5.4.1 直接三角分解法 將高斯消去法改寫為緊湊方式，可以直接從矩陣 的元素得到計算 元素的遞推公式，而不需任何中間步驟，AUL , 一旦實現(xiàn)了矩陣 的 分解，那么求解 的問題就等價于求解兩個三角形方程組 ALUbAx 求,bLy ;y 求 ,yUx. x這就是直接三角分解法. 1. 不選主元的三角分解法 設(shè) 為非奇特矩陣，且有分解式 A,LUA .111222112112121nnnnnnuuuuuulllA4.1其中 為單位下三角陣， 為上三角陣，即 LU 的元素可以由 步直接計算定出，其中第 步定出 的第 行和 的第 列元素. UL ,nrUrLr

2、；的第1行元素得U),2, 1(11niuaii 設(shè)曾經(jīng)定出 的第1行到第 行元素與 的第1列到第 列元素. U1rL1r由(4.1)有 的第1列元素.得L), 2(/,11111111niualulaiiii 由(4.1)，利用等式兩邊元素比較及當(dāng) 時， kr ,0rkl有 nkkirkriula1.11rirkkirkuul故 .111222112112121nnnnnnuuuuuulllA4.1.111222112112121nnnnnnuuuuuulllA4.1),1,(11nrriulaurkkirkriri又由(4.1)有 nkkrikirula1 用直接三角分解法解 (要求 的一

3、切順序主子式都不為零)的計算公式. bAxA ), 2(/), 2 , 1(111111niualniauiiii 計算 的第 行和 的第 列元素 UrLr).,3,2(nr );,1,(11nrriulaurkkirkriri4.2.11rrirrkkrikulul.111222112112121nnnnnnuuuuuulllA4.1 );, 1(/ )(11nrnriuulalrrrkkrikirir且4.3 求解 的計算公式： yUxbLy, ,11by,/nnnnuyx 4.4);,3 ,2(11niylbyikkikiiiinikkikiiuxuyx/14.5).1 ,2, 1(nn

4、i 例5.201814513252321321xxx 解用直接三角分解法解 用分解公式(4.2)(4.3)計算 ,11111 au,11/2/112121ual,122512212222ulau,21212 au,31313 au，31/3/113131ual,432213212323ulau,51/)231(/)(2212313232uulal);,1,(11nrriulaurkkirkriri4.2);, 1(/ )(11nrnriuulalrrrkkrikirir且4.32400410321153012001A按(4.4)求解 ,)20,18,14(TyL,)72,10,14(TxU.L

5、U.24)4()5(335233213313333ululau從而,)72,10,14(Ty得求解.)3,2, 1(Tx得;11by4.4);,3 ,2(11niylbyikkikii 當(dāng) 計算好后 就不用了，故可將 仍存放在 的相應(yīng)位置. riuriariuria例如 44434241343332312423222114131211aaaaaaaaaaaaaaaaA最后在存放 的數(shù)組中得到 的元素. UL ,A 直接分解法大約需求 次乘除法，和高斯消去法計算量根本一樣. 3/3n 再思索存儲問題44434241343332312423222114131211ullluulluuuluuuu

6、假設(shè)曾經(jīng)有了 的 分解，那么求解具有一樣系數(shù)的方程組 是相當(dāng)方便的，每解一個方程組 僅需求添加 次乘除法運算. ALU)(21mbbbAxjbAx 2n 矩陣 的分解公式(4.2)，(4.3)又稱為杜利特爾分解. A 2. 選主元的三角分解法 從直接三角分解公式可看出當(dāng) 時計算將中斷，0rru或者當(dāng) 絕對值很小時，按分解公式計算能夠引起舍入誤差的累積. rru 假設(shè) 非奇特，可經(jīng)過交換 的行實現(xiàn)矩陣 的 分解.AAPALU);,1,(11nrriulaurkkirkriri4.2);, 1(/ )(11nrnriuulalrrrkkrikirir且4.3 采用與列主元消去法類似的方法，將直接三

7、角分解法修正為(部分)選主元的三角分解法. 設(shè)第 步分解已完成，這時有 1r.1,211,21,1,11,12,11 ,1221,22221111,11211nnnrrnnnrnrrrrrrnrrrrrrrnrrnrraalllaallluuulluuuuluuuuuA第 步分解需用到(4.2)及(4.3)式，r)., 1(11nriulasrkkrikiri于是有 )., 1(/,nrisslsuriirrrr為了防止用小的數(shù) 作rru除數(shù)，引進(jìn)量 取 交換 的 行與 行元素，,maxriinirssArri將 調(diào)到ris),(rr位置(將 位置的新元素仍記為 及 )，),(jiijlija

8、于是有),1(1nrilir 由此再進(jìn)展第 步分解計算. r);,1,(11nrriulaurkkirkriri4.2);, 1(/ )(11nrnriuulalrrrkkrikirir且4.3 算法4 1. 對于 nr,2,1 (1) 計算 is),1,(11nrriulasarkkrikiriir (2) 選主元 riniriirssr)(Ip,max(選主元的三角分解法)設(shè) ，其中 為bAxA非奇特矩陣.),2,1(,niaaiirir (4) 計算 的第 行元素， 的第 列元素 UrLr (3) 交換 的 行與 行元素Arrirrrrrsua 求解 .,yUxbLy 2. 對于 1,2

9、,1ni (1) )(Ip it (2) 假設(shè) 那么轉(zhuǎn)(3) ti tibb), 1(/nrnriaauslarrirrriirir且), 1(11nrnriulauarkkirkririri且 (3) (繼續(xù)循環(huán)) 3. ),3,2(11niblbbikkikii 4. )1 ,2, 1(/,/1nniububbubbiinikkikiinnnn.111PLUA 利用算法4的結(jié)果 可以計算 的逆矩陣 A,LUPA 步驟： (1) 計算上三角矩陣的逆陣;1U;11LU(2) 計算 上述方法求 大約需求 次乘法運算. 1A3n(3) 交換 列(利用 最后記錄). 11LU)(Ip n 5.4.2

10、 5.4.2 平方根法平方根法 平方根法是利用對稱正定矩陣的三角分解而得到的求解對稱正定方程組的一種有效方法. 設(shè) 為對稱矩陣，且 的一切順序主子式均不為零，由AA定理7知， 可獨一分解為 A.111222112112121nnnnnnuuuuuulllA 為了利用 的對稱性，將 再分解為 AU111222222311111122211uuuuuuuuuuunnnnU其中 為對角陣， 為單位上三角陣. D0U.0LDULUA4.6又 TAA 于是 ,0DU),(TT0DLU由分解的獨一性, 得 .T0LU代入(4.6)得到對稱矩陣 的分解式 A.TLDLA 定理10設(shè) 為 階對稱陣，An且 的

11、一切順序主子式均不為零，A那么 可獨一分解為 A,TLDLA 其中 為對角陣， 為單位下三角陣. DL 設(shè) 為對稱正定矩陣，那么在分解式 中， 的對角元素 均為正數(shù). ATLDLA Did 現(xiàn)實上，由 的對稱正定性，有 A).,3,2(0/,01niddi 1ii1DDD于是 (對稱陣的三角分解定理)ndd1Dnndddd11,2121DD由定理6得到 TLDLA 其中 為下三角矩陣. 211LDLT2121LDLDT2121)(LDLD,T11LL 定理11假設(shè) 為 階對稱正定矩陣，那么存在一個實的非奇特下三角陣An,L 可以用直接分解方法來確定計算 元素的遞推公式. L(對稱正定矩陣的三角

12、分解或Cholesky分解),TLLA 使當(dāng)限定 的對角元素為正時，這種L分解是獨一的. 由于 ,2221211121222111nnnnnnnnllllllllllllA其中).,2,1(0niliinkjkikijlla1于是得到解對稱正定方程組 的平方根法計算公式： bAx 對于 nj,2,1 l. .21112jkjkjjjjlal4.7),(0時當(dāng)kjljk由矩陣乘法及 按等式兩邊對應(yīng)元素相等，得 ,11ijjjjkjkikllll).,1(/11njilllaljjjkjkikijij 2. 求解 即求解兩個三角形方程組： ,bAx;,1ybLy求）（ 4. ).1 , 1,(/1

13、nnilxlbxiinikkkiii 3. ).,2,1(/11nilylbyiiikkikii4.8由計算公式1知 ),2,1(12nilajkjkjj所以 .,)2(TxyxL求,max12jjnjjjjkaal于是 .maxmax12,jjnjjkkjal 這個結(jié)果闡明，分解過程中元素 的數(shù)量級不會增長jkl且對角元素 恒為正數(shù). jjl 當(dāng)求出 的第 列元素時， 的第 行元素也算出. LjTLj所以平方根法約需 次乘除法，大約為普通直接分解法計算量的一半. 6/3n 于是不選主元素的平方根法是一個數(shù)值穩(wěn)定的方法. 由于 為對稱陣，因此在計算機實現(xiàn)時只需存儲 的下三角部分.AA 下三角部

14、分共需存儲 個元素，可按行主序用一維數(shù)組存放，2/)1(nn即.,)2/)1(21222111nnnnaaaaaannA矩陣元素 在一維數(shù)組中表示為 的元素存放在 的相應(yīng)位置. ijaL),2/)1(jiiAA 用平方根法解對稱正定方程組時，需求用到開方運算.為了防止開方，用定理10的分解式 ,TLDLA 即 .1111112121212121nnnnnllldddlllA由矩陣乘法，并留意 得 ),(0, 1kjlljkjjnkkjikija1T)()(LLDnkjkkikldl111.jkjjjijjkkikldlldl于是得到計算 的元素及 的對角元素公式： LD l. );1,2, 1

15、(/11ijdldlaljjkjkkikijij4.9nj,2,1 對于 2. .112ikkikiiidlad 為防止反復(fù)計算，引進(jìn) ,jijijdlt由(4.9)得到按行計算 元素的公式： TL,111ad.,3,2nj 對于 1. );1,2, 1(11ijltatjkjkikijij 2. );1,2, 1(/ijdtljijij 計算出 的第 行元素 后，LDT i)1,2, 1(ijtij存放在 的第 行相應(yīng)位置，iA然后再計算 的第 行元素，Li存放在 的第 行. Ai 的對角元素存放在 的相應(yīng)位置. DA 3. 11ikikikiiiltad4.1044434241333231

16、222111aaaaaaaaaa對稱A 對稱正定矩陣 按 分解和按 分解計算量差不多，但 分解不需求開方計算. ATLDLTLLTLDL例如 44434241332312211atttdlldld.4434241332312211dllldlldld 5. ).1 ,2,1(/;/1nixldyxdyxnikkkiiiinnn 4. ).,2(;1111niylbybyikkikii4.11 計算公式(4.10)，(4.11)稱為改良的平方根法. 求解 計算公式 yxDLbLyT,);1,2, 1(11ijltatjkjkikijij);1,2, 1(/ijdtljijij11ikikikii

17、iltad4.10 5.4.3 5.4.3 追逐法追逐法 實踐問題中，通常要求解系數(shù)矩陣為對角占優(yōu)的三對角線方程組 ,12112111122211nnnnnnnnnffffxxxxbacbacbacb4.12簡記為 .fAx其中，當(dāng) ：，且時,01ijaji 0; )a(11 cb);1,3,2(0, )b(nicacabiiiii0. )c(nnab 利用矩陣的直接三角分解法推導(dǎo)解三對角線方程組4.12)的計算公式. ,LUA 其中 為下三角矩陣， 為單位上三角矩陣. LU 由系數(shù)陣 的特點，可以將 分解為兩個三角陣的乘積，AA即 設(shè) nnnnnbacbacbacb11122211A4.13

18、,11111221nnn其中 為待定系數(shù). iii,比較(4.13)兩邊得,11111cb)1,2(niciii4.14 用歸納法可以證明 ),1,2,1(0nicii4.15即,10i),2(,1nibaiiiiii,/0 01111111bccbb，由得.101從而由(4.14)可求出 i,11111221nnnA 時由對角占優(yōu)的條件，(4.15)是成立的. 1i 現(xiàn)設(shè)(4.15)對 成立，求證對 也成立. 1ii 由歸納法假設(shè) 又由(4.15)及 的對角占優(yōu)條件，有 ,101iA1iiiiab也就是 .10i 由(4.14)得到 );,2(1niabiiii1iiiabiiab ,0ic

19、),1,2,1(0nicii4.15確定了 ，就實現(xiàn)了 的 分解. ,iiiALU).1,3,2()/(1niabciiiii求解 等價于求解兩個三角形方程組： ,fAx ;,)1(yfLy求.,)2(xyUx求 解三對角線方程組的追逐法公式： 1. 計算 的遞推公式 i111/bc);1,3,2()/(1niabciiiii 2. 解 fLy ,/111bfy 3. 解 yUx );,3,2()/()(11niabyafyiiiiiii,nnyx稱計算系數(shù) 及 121nnyyy21 稱計算方程組的解 的過程為趕的過程.11xxxnn).1 ,2,2,1(1nnixyxiiii的過程為追的過程

20、. 定理12 設(shè)有三對角線方程組 , fAx其中 滿足條件A(a)，(b)，(c)，那么 為非奇特矩陣且追逐法計算公式中的A);1, 3 , 2(0niababciiiiii ,ii滿足： );1,2, 110nii（.0nnnnnabab 追逐法公式實踐上就是把高斯消去法用到求解三對角線方程組上去的結(jié)果. 計算機實現(xiàn)時只需用三個一維數(shù)組分別存儲 的三條線元素 ，此外再用兩組任務(wù)單元保管 或 A,iiicba,iiy.ix 由于 特別簡單，因此求解的計算公式也非常簡單，計算量也很小. A將實數(shù)5.5 向量和矩陣的范數(shù)向量和矩陣的范數(shù) 向量范數(shù)概念是三維歐氏空間中向量長度概念的推行，在數(shù)值分析中

21、起著重要作用. 定義1niiiyx1T),(xyyx或 .T21T21),(,),(nnyyyxxxyxnRnC設(shè)或復(fù)數(shù) niiiyx1H),(xyyx稱為向量 的數(shù)量積. yx ,2112212),(niixxxx2112212),(niixxxx將非負(fù)實數(shù) 或稱為向量 的歐氏范數(shù) . x 定理13 關(guān)于范數(shù)，成立如下定理.),CR,nn或（yx設(shè)那么 ；時成立當(dāng)且僅當(dāng) ,),( .001xxx為實數(shù), ),(),( .2yxyx);,(),( (),(),( .3xyyxxyyx或);,(),(),( .42121yxyxyxx 5. (Cauchy-Schwarz不等式) ,),(22y

22、xyx等號當(dāng)且僅當(dāng) 與 線性相關(guān)時成立； xy）；為復(fù)數(shù)或 ),(),( (yxyx 6. 三角不等式 .222yyxx 也可以用其他方法來度量向量的“大小. 向量的歐式范數(shù)可以看成是對 中向量“大小的一種度量.nR 例如，對于 可以用一個 的函數(shù),R),(2T21xxxx 來度量 的“大小，而且這種度量“大小的方法計算起來比歐氏范數(shù)方便. iixN2,1max)(xx 普通要求度量向量“大小的函數(shù) 滿足正定性、齊次性和三角不等式. )( xN），正定條件當(dāng)且僅當(dāng)() 0 0(0 . 1xxx ),C(R , .2或xx），三角不等式( .3yxyx5.1那么稱 是 (或 )上的一個向量范數(shù)(

23、或模). nR)(xNnC 由條件3 定義2假設(shè)向量 (或 )的某nRxnC個實值函數(shù) ，滿足條件：xx)(N(向量的范數(shù)). yyxyyxx. .4yxyx5.2. xxyxxyy從而有 幾種常用的向量范數(shù). 1. 向量的 -范數(shù)(最大范數(shù))： .max1inixx 2. 向量的1-范數(shù)： .11niixx 3. 向量的2-范數(shù)： .)(),(1212212niixxxx也稱為向量 的歐氏范數(shù). x,)(/11pnipipxx 4. 向量的 -范數(shù)： p其中 .),1p 可以證明向量函數(shù) 是 上向量的范數(shù),pNxx)(nR且容易闡明上述三種范數(shù)是 -范數(shù)的特殊情況.p假設(shè) 例6計算向量 的各

24、種范數(shù). T)3 ,2, 1 ( x 解 ,61x 定義3設(shè) 為 中一向量序列， )(kxnR,R*nx.),(*,),(T*2*1T)()(2)(1)(nknkkkxxxxxxxx),2, 1(lim*)(nixxikik那么稱 收斂于向量 ，)(kx*x.lim*)(xxkk記記為 , 3x.142x 定理14 ( 的延續(xù)性)( xN為 上任一向量范數(shù)，nR那么 是 的分量)( xNxnxxx,21xx)(N 設(shè)非負(fù)函數(shù)的延續(xù)函數(shù). 證明,11niiniiiyxeyexi設(shè)),0 ,0 , 1 ,0(ie其中 只需證明當(dāng) 時 . yx )()(yxNN現(xiàn)實上 yxyx)()(NNyx ni

25、iiiyx1)(eniiiiyx1e即 ,( 0)()(）時當(dāng)yxyxyxcNN其中 .1niice,1niieyx 定理15的恣意兩種范數(shù)，設(shè) 為 上向量tsxx,nR那么存在常數(shù),0,21cc 證明只需就 證明上式成立刻可，即證明xxs存在常數(shù) 使 ,0,21cc.R ,021xxxx且對一切ntcc思索泛函 .R,0)(ntfxxx(向量范數(shù)的等價性),21stsccxxx有 nRx使得對一切 由于 為 上的延續(xù)函數(shù)，所以 于 上到達(dá)最大、最小值，)( xfS)( xfS記 那么 是一個有界閉集. ,R, 1nSxxxS即存在 使得S xx ,.)(max)(,)(min)(21cffc

26、fxfSS xxxxx設(shè) 且nRx,0 x,Sxx那么從而有 ,21cfcxx5.3顯然 上式為 ,0,21cc,21cctxx即 .R ,21ntccxxxx對一切 定理15不能推行到無窮維空間. 由定理15可得到結(jié)論：假設(shè)在一種范數(shù)意義下向量序列收斂時，那么在任何一種范數(shù)意義下該向量序列均收斂. 定理16,0*lim*lim)()(xxxxkkkk 證明,0*lim*lim)()(xxxxkkkk而對于 上任一種范數(shù)，nR *)()(1xxxxkkc于是又有 .0*lim0*lim)()(xxxxkkkk 其中其中為向量的任一種范為向量的任一種范數(shù)數(shù). . 顯然，使 , 0,21cc由定理

27、15，存在常數(shù) ,*)(2xkc 向量范數(shù)概念可以推行到矩陣. 視 中的矩陣為 中的向量，nnR2Rn那么由 上的2-范數(shù)2Rn可以得到 中矩陣的一種范數(shù) nnR,)(211,2,FnjijiaFAA稱為 的Frobenius范數(shù). A 顯然滿足正定性、齊次性及三角不等式. FA 定義4(矩陣的范數(shù))假設(shè)矩陣 的某個非負(fù)的nn RA實值函數(shù) , AA)(N滿足條件 正定條件);( ) 00 10(.AxAA ( 2齊次條件);為實數(shù)ccc,.AA三角不等式);(. 3BABA5.4 . 4BAAB.那么稱 是 上的一個矩陣范數(shù)(或模). )( ANnnR 上面定義的 就是 上的一個矩陣范數(shù).

28、F)(A FnnR 由于在大多數(shù)與估計有關(guān)的問題中，矩陣和向量會同時參與討論，所以希望引進(jìn)一種矩陣的范數(shù)，它和向量范數(shù)相聯(lián)絡(luò)而且和向量范數(shù)相容. . xAAx5.5 定義5設(shè) , ，nRxnn RA給出一種向量范數(shù) (如 或)，相應(yīng)地定義一個矩陣的非負(fù)函數(shù)vx2,1v即對任何向量 及 都成立nn RAnRx(矩陣的算子范數(shù)) . max 0vvxvxAxA5.6可以驗證 滿足定義4，所以 是 上矩陣的一個范數(shù)，稱為 的算子范數(shù). vAvAnnRA 定理17設(shè) 是 上一個向量范數(shù)，vxnR . vvvxAAx5.7 證明由(5.7)，有 vvvBxAABx 那么 是vAnnR上矩陣的范數(shù)，且滿足

29、相容條件 由(5.6)相容性條件(5.7)是顯然的.現(xiàn)只驗證定義4中條件4. . vvvxBA當(dāng) 時，有 0 x . vvvvBAxABx . max 0vvxvxAxA5.6故 vvvxABxABx0 max 顯然這種矩陣范數(shù) 依賴于詳細(xì)的向量范數(shù) .vvx也就是說，給出一種詳細(xì)的向量范數(shù) ，相應(yīng)地就可得到一種矩陣范數(shù) . vxvA 定理18 設(shè)設(shè) , , ，那么，那么nRxnn RA的行范數(shù)),稱為AA( max 1. 11njijnia. vvBA的列范數(shù)),稱為AA( max 2. 111niijnja. )( 3. Tmax2范數(shù)）的2(稱為AAAA其中 表示 的最大特征值. )(TmaxAAAAT 證明 1. 設(shè) , 無妨設(shè) . 01T),(nxxx0A,max1inixtx那么 只就1，3給出證明，2同理. 記 ,max11njijnianjjijnixa11maxAxnjjijixa1max.max1njij