第6章3-4節(jié)矩陣三角分解法 與范數(shù)

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

2、,nrUrLr3；的第1行元素得U),2, 1(11niuaii 設已經(jīng)定出 的第1行到第 行元素與 的第1列到第 列元素. U1rL1r 的第1列元素.得L), 2(/,11111111niualulaiiii 利用等式兩邊元素比較及當 時， kr ,0rkl有 nkkirkriula1.11rirkkirkuul故 .111222112112121nnnnnnuuuuuulllA.111222112112121nnnnnnuuuuuulllA4),1,(11nrriulaurkkirkriri nkkrikirula1 用直接三角分解法解 (要求 的所有順序主子式都不為零)的計算公式. b

3、AxA ), 2(/), 2 , 1(111111niualniauiiii 計算 的第 行和 的第 列元素 UrLr).,3,2(nr );,1,(11nrriulaurkkirkriri.11rrirrkkrikulul.111222112112121nnnnnnuuuuuulllA );, 1(/)(11nriuulalrrrkkrikirir5 );, 1(/ )(11nrnriuulalrrrkkrikirir且 求解 的計算公式： yUxbLy, ,11by,/nnnnuyx );,3 ,2(11niylbyikkikiiiinikkikiiuxuyx/1).1 ,2, 1(nni

4、6 例例5 5.201814513252321321xxx 解解用Doolittle三角分解法解 ,11111 au,11/2/112121ual,122512212222ulau,21212 au,31313 au，31/3/113131ual,432213212323ulau,51/)231(/)(2212313232uulal);,1,(11nrriulaurkkirkriri);, 1(/ )(11nrnriuulalrrrkkrikirir且72400410321153012001A因為 ,)20,18,14(TyL,)72,10,14(TxU.LU.24)4()5(33523321

5、3313333ululau從而,)72,10,14(Ty得求解.)3,2, 1(Tx得;11by（4.4）);,3 ,2(11niylbyikkikii8 當 計算好后 就不用了，故可將 仍存放在 的相應位置. riuriariuria例如 44434241343332312423222114131211aaaaaaaaaaaaaaaaA最后在存放 的數(shù)組中得到 的元素. UL ,A 直接分解法大約需要 次乘除法，和高斯消去法計算量基本相同. 3/3n 再考慮存儲問題44434241343332312423222114131211ullluulluuuluuuu9 如果已經(jīng)有了 的 分解，則求

6、解具有相同系數(shù)的方程組 是相當方便的，每解一個方程組 僅需要增加 次乘除法運算. ALU)(21mbbbAxjbAx 2n10 若 A的各價順序主子式不為零，uii不為零.111222112112121nnnnnnuuuuuulllA2. LDR分解111.1.1.11111112111121uuuuuulllAnnnnnnLDR12定理4 設n階可逆矩陣A有唯一的LDR分解的充分必要條件是A的各價順序主子式不為零.133. Crout分解 在A的LDR分解中，將LD看成一個矩陣記為L1 A=L1R，為方便也可記為A=LR其中L下三角矩陣，R為單位上三角矩陣.這種分解稱為Crout分解.144

7、 平方根法平方根法(Cholesky(Cholesky分解法）分解法） 平方根法是利用對稱正定矩陣的三角分解而得到的求解對稱正定方程組的一種有效方法. 又因為A為對稱矩陣，A=LDR=AT=(LDR)T=RTDLT分解的唯一性，L=RT,LT=R所以A=LDLT設D=diag(d1,dn), 設 A為對稱正定矩陣，則 A 的所有順序主子式均大于零，由定理4知， A可唯一分解為 LDR.15因為A為正定矩陣，di0 (i=1,n)為下三角矩陣。其中表示為為方便計，也可將上式為下三角矩陣。其中令LLLALLLLGLGAdddiagGTTTn1111)(),.,(16 定理定理5 5如果 為 階對稱

8、正定矩陣，則存在一個實的非奇異下三角陣An,L 可以用直接分解方法來確定計算 元素的遞推公式. L(對稱正定矩陣的三角分解或Cholesky分解),TLLA 使當限定 的對角元素為正時，這種L分解是唯一的. 因為 ,2221211121222111nnnnnnnnllllllllllllA17其中).,2,1(0niliinkjkikijlla1于是得到解對稱正定方程組 的平方根法計算公式： bAx 對于 nj,2,1 l. .21112jkjkjjjjlal),(0時當kjljk由矩陣乘法及 按等式兩邊對應元素相等，得 ,11ijjjjkjkikllll)., 1(/11njilllaljj

9、jkjkikijij 2. 18求解 即求解兩個三角形方程組： ,bAx;,1ybLy求）（ 4. ).1 , 1,(/1nnilxlbxiinikkkiii 3. ).,2, 1(/11nilylbyiiikkikii由計算公式1知 ),2, 1(12nilajkjkjj所以 .,)2(TxyxL求19jjjkjjjkalal|,2既 當求出 的第 列元素時， 的第 行元素也算出. LjTLj所以平方根法約需 次乘除法，大約為一般直接分解法計算量的一半. 6/3n 于是不選主元素的平方根法是一個數(shù)值穩(wěn)定的方法. 這個結果說明，分解過程中元素 的數(shù)量級不會增長jkl20 由于 為對稱陣，因此在

10、計算機實現(xiàn)時只需存儲 的下三角部分.AA 下三角部分共需存儲 個元素，可按行主序用一維數(shù)組存放，2/)1(nn即.,)2/)1(21222111nnnnaaaaaannA矩陣元素 在一維數(shù)組中表示為 的元素存放在 的相應位置. ijaL),2/)1(jiiAA 215 追趕法追趕法 實際問題中，通常要求解系數(shù)矩陣為對角占優(yōu)的三對角線方程組 ,12112111122211nnnnnnnnnffffxxxxbacbacbacb簡記為 .fAx其中，當 ：，且時,01ijaji 0; )a(11 cb22);1,3,2(0, )b(nicacabiiiii0. )c(nnab 利用矩陣的直接三角分解

11、法推導解三對角線方程組的計算公式. ,LUA 其中 為下三角矩陣， 為單位上三角矩陣. LU 由系數(shù)陣 的特點，可以將 分解為兩個三角陣的乘積，AA即 23 設 nnnnnbacbacbacb11122211A,11111221nnn其中 為待定系數(shù). iii,24比較兩邊得,11111cb)1,2(niciii ),2(,1nibaiiiiii,/0 01111111bccbb，由得.101,11111221nnnA|10111iiiiiiiiiiicababab設),1,2,1(0nicii25 );,2(),2(1niabniaiiiiiiiiic01. |11均有界，這說明另外，iii

12、iiiiiiiiiiiababababc 由 此可得下列計算公式).1,3,2(/niciii26確定了 ，就實現(xiàn)了 的 分解. ,iiiA三角求解 等價于求解兩個三角形方程組： ,fAx ;,)1(yfLy求.,)2(xyUx求 解三對角線方程組的追趕法公式追趕法公式： iiiiiiiiibacnib1111111/1,.,1.1作對分解27 2. 解 fLy ,/111fy 3. 解 yUx);,3,2(/)(1niyfyiiiii,nnyx稱計算系數(shù) 及 121nnyyy21 稱計算方程組的解 的過程為趕的過程.共需5n-4次乘除法.11xxxnn).1 ,2,2,1(1nnixyxii

13、ii的過程為追的過程.);,3,2(/)(1niyafyaiiiiiii28 定理定理6 6設有三對角線方程組 , fAx其中 滿足條件A(a)，(b)，(c)，則 為非奇異矩陣且追趕法計算公式中的A);1, 3 , 2(0niababciiiiii ,ii滿足： );1,2, 110nii（.0nnnnnabab 追趕法公式實際上就是把高斯消去法用到求解三對角線方程組上去的結果. 29 計算機實現(xiàn)時只需用三個一維數(shù)組分別存儲 的三條線元素 ，此外再用兩組工作單元保存 或 A,iiicba,iiy.ix 由于 特別簡單，因此求解的計算公式也非常簡單，計算量也很小. A30將實數(shù)4 向量和矩陣的

14、范數(shù)向量和矩陣的范數(shù) 向量范數(shù)概念是三維歐氏空間中向量長度概念的推廣，在數(shù)值分析中起著重要作用. 定義定義1 1niiiyx1T),(xyyx（或 ）.T21T21),(,),(nnyyyxxxyxnRnC設（或復數(shù) ）niiiyx1H),(xyyx稱為向量 的數(shù)量積數(shù)量積. yx ,312112212),(niixxxx將非負實數(shù) 稱為向量 的歐氏范數(shù)歐氏范數(shù) . x 定理定理7 7 關于內積與歐氏歐氏范數(shù)，成立如下定理.),CR,nn或（yx設則 ；時成立當且僅當 ,),( .001xxx32nnnnCCRRyxyxyxyxyxyxyxyxyxyx, ),(),( ; ),(),(, ),

15、(),( ; ),(),( .3數(shù),為為實數(shù),復);,(),( (),(),( .2xyyxxyyx或);,(),(),( .42121yxyxyxx 5.5. (Cauchy-Schwarz不等式) ,),(22yxyx等號當且僅當 與 線性相關時成立； xy 6.6. 三角不等式 .222yyxx33 也可以用其他辦法來度量向量的“大小”. 向量的歐式范數(shù)可以看成是對 中向量“大小”的一種度量.nR 例如，對于 可以用一個 的函數(shù),R),(2T21xxxx 來度量 的“大小”，而且這種度量“大小”的方法計算起來比歐氏范數(shù)方便. iixN2,1max)(xx 一般要求度量向量“大小”的函數(shù)

16、滿足正定性、齊次性和三角不等式. )( xN34），正定條件當且僅當() 0 0(0 . 1xxx ),C(R , .2或xx），三角不等式( .3yxyx則稱 是 (或 )上的一個向量范數(shù)(或模). nR)(xNnC 由條件3 定義定義2 2如果向量 (或 )的某nRxnC個實值函數(shù) ，滿足條件：xx)(N(向量的范數(shù)). yyxyyxx35. .4yxyx. xxyxxyy從而有 幾種常用的向量范數(shù). 1. 向量的 -范數(shù)(最大范數(shù))： .max1inixx 2. 向量的1-范數(shù)： .11niixx36 3. 向量的2-范數(shù)： .)(),(1212212niixxxx也稱為向量 的歐氏范數(shù)

17、. x,)(/11pnipipxx 4. 向量的 -范數(shù)： p其中 .),1p 可以證明向量函數(shù) 是 上向量的范數(shù),pNxx)(nR且容易說明上述三種范數(shù)是 -范數(shù)的特殊情況.p37如果 例例6 6計算向量 的各種范數(shù). T)3 ,2, 1 ( x 解解 ,61x 定義定義3 3設 為 中一向量序列， )(kxnR,R*nx.),(*,),(T*2*1T)()(2)(1)(nknkkkxxxxxxxx),2, 1(lim*)(nixxikik則稱 收斂于向量 ，)(kx*x.lim*)(xxkk記記為 , 3x.142x38 定理定理8 8( 的連續(xù)性)( xN為 上任一向量范數(shù)，nR則 是

18、的分量)( xNxnxxx,21xx)(N 設非負函數(shù)的連續(xù)函數(shù).證明證明:,11niiniiiyxeyexi設),0 ,0 , 1 ,0(ie其中 只需證明當 時 . yx )()(yxNNyxyx)()(NNyx niiiiyx1)(e39niiiiyx1e,1niieyx,( 0)()(）時當yxyxyxcNN.1niice其中 40 定理定理9 9的任意兩種范數(shù)，設 為 上向量tsxx,nR則存在常數(shù),0,21cc 證明證明 只要就 證明上式成立即可，即證明xxs存在常數(shù) 使 ,0,21cc.R ,021xxxx且對一切ntcc考慮泛函 .R,0)(ntfxxx(向量范數(shù)的等價性),2

19、1stsccxxx有 nRx使得對一切41 由于 為 上的連續(xù)函數(shù)，所以 于 上達到最大、最小值，)( xfS)( xfS記 則 是一個有界閉集. ,R, 1nSxxxS即存在 使得S xx ,.)(max)(,)(min)(21cffcfxfSS xxxxx設 且nRx,0 x,Sxx則從而有 ,21cfcxx顯然 上式為 ,0,21cc42,21cctxx.R ,21ntccxxxx對一切 定理9不能推廣到無窮維空間. 由定理9可得到結論如果在一種范數(shù)意義下向量序列收斂時，則在任何一種范數(shù)意義下該向量序列均收斂. 43 定理定理1010,0*lim*lim)()(xxxxkkkk 其中為向

20、量的任一種范數(shù). ,0*lim*lim)()(xxxxkkkk證明：, 0,21cc由定理9，存在常數(shù)* *)(2)()(1xxxxxxkkkcc.0*lim0*lim)()(xxxxkkkk44 向量范數(shù)概念可以推廣到矩陣. 定義定義4 4(矩陣的范數(shù))如果矩陣 的某個非負的nn RA實值函數(shù) , AA)(N滿足條件 45正定條件);( ) 0 0(0 . 1AAA ( 2齊次條件);為實數(shù)ccc,.AA三角不等式);(. 3BABA . 4BAAB.則稱 是 上的一個矩陣范數(shù)(或模). )( ANnnR 由于在大多數(shù)與估計有關的問題中，矩陣和向量會同時參與討論，所以希望引進一種矩陣的范數(shù)，它和向量范數(shù)相聯(lián)系而且和向量范數(shù)相容.46 . xAAx 定義定義5 5設 , ，nRxnn RA給出一種向量范數(shù) (如 或)，相應地定義一個矩陣的非負函數(shù)vx2,1v即對任何向量 及 都成立nn RAnRx(矩陣的算子范數(shù)) . max 0vvxvxAxA可以驗證 滿足定義4，所以 是 上矩陣的一個范數(shù)，稱為 的算子范數(shù). vAvAnnRA