矩阵的三角分解

1、矩阵的三角分解主讲 孟纯军3.2 矩阵的三角分解法n我们知道对矩阵进行一次初等变换，就相当于用相应的初等矩阵去左乘原来的矩阵。因此我们这个观点来考察Gauss消元法用矩阵乘法来表示，即可得到求解线性方程组的另一种直接法：矩阵的三角分解。 3.2.1 Gauss消元法的矩阵形式)2() 1 (1)2()2(2)2()2() 1 () 1 () 1 () 1 () 1 () 1 () 1 () 1 () 1 () 1 () 1 () 1 (131211) 1 (11) 1 (1111131121) 1 (11.1.00.1011.,32i)()(1),.,0:1222112112122221112

2、11AALaaaaaaaaaaaaaaaalllni-laalaaaannnnnnnnnnnniiin，其矩阵形式为，行行令消零时，将步等价于第则）（）（）（)3()3()3(3)3(3)3(33)2(2)2(23)2(22)1(1)1(13)1(12)1(11222)2(22)2(222322)2(22.00.00.0.:),.,4 , 3(1.00.0.100.0100.00102AaaaaaaaaaaaALAniaalllLannnnnn)()(iin，即有左乘时，用矩阵步等价于：若同理第1.1111.11.000.00.0.2321212111)()3(3)3(33)2(2)2(23)

3、2(22)1(1)1(13)1(12)1(111221nnnnnnnnnnllLllLUaaaaaaaaaaALLLL因为以此类推可得为上三角阵为单位下三角阵，其中所以U1.111.).(1213231211112121111221LLUUllllllULLLLULLLLAnnnnnnnn分解。行直接进否对矩阵因此，关键问题在于能个三角方程：就等价于解两由此解线性方程组LUAyUxbLyULAbxbx)(3.2.2 Doolittle分解1131313111311121212111211111232322131211323121333231232221131211)3 , 2 , 1(1111

4、3,ualluaualluajauuakuuuuuulllaaaaaaaaanULjjjj得由；得由时：为例的各元素，以此分解在于如何算出)(322332133133333323321331332212313232233212313213212323231321231221222222122122ululauuululakuulalululaulauuulaulauuulak得时：由得由；得由；得时：Doolittle分解n若矩阵A有分解：A=LU，其中L为单位下三角阵，U为上三角阵，则称该分解为Doolittle分解，可以证明，当A的各阶顺序主子式均不为零时，Doolittle分解可以实现并

5、且唯一。nA的各阶顺序主子式均不为零，即),.2 , 1(0.1111nkaaaaAkkkkkDoolittle分解各元素方法逐行逐列求解用比较等式两边元素的令ULuuuuuulllaaaaaaaaannnnnnnnn,.1.11.222112112121n2n1n2222112111Doolittle分解。得再由；得由时：。得再由；得由时),.,4 , 3(),.,3 , 2(12),.,3 , 2(),.2 , 1(1:12212122222121212222121211111111 i1111niuulalululanjulauuulakniualluanjauuakiiiiiijijj

6、jjjiiijjjjDoolittle分解1111211211,.1,000.10.,.,kttjktkjkjktkjtjktjjjjkkkkkjknkkkknkkjulauuuluuulllakjuuuk）（有步时：计算第Doolittle分解11111111,.1/)(000.0, 1 ,.,.,ktkktkitikikktkkiktkitkkkikiiknkkknkiuulalululuullakill）（得，于是由由于计算Doolittle分解nnnnnnkkkttkitikikkttjktkjkjulluuluuunkuulalnkinkjulau.A,.,2 , 1/ )(),.,

7、1;,.,(2122221112111111的各位各元素在计算机内存于即Doolittle分解。可获解得及再由TniinijjijiiijjijiixxxnniuxuyxniylbyULxyxby),.,(1,.1,/ )(,.,2 , 121111例题30191063619134652.D. 1321xxxoolittle分解求解方程组试用例例题。，；，令、分解解：326246521101001636191346521311121131211332322131211323121luluuukuuuuuulllALU例题LUAululaukuulalulauulauk4736521431214

8、34/ )(7)6(21935213223321331333322123132321321232312212222所以时：，时：例题TyyyyyyybLy)4 , 1,10(43034, 12019,1030191014312112321321即得）解（、解方程组例题。所以方程组的解为解得：解TxxxxxxxyUx) 1 , 2 , 3(3, 2,2(123321Doolittle分解).,.,2 , 1()4() 1 , 2,.,1(/ )(;/)2),.,2(;) 1)3(),.,1(/ )(),.1,(,.3 , 2)2),.,3 , 2(/) 1)2(),.,

9、2 , 1(),.,2 , 1,() 1 (11111111111111nixniuxuyxayxniylbybyyUxbLynkiuulalankkjulauankniaalaLUAnibnjiaiiinijjijiinmnnijjijiikkkttkitikikikkttjktkjkjkjiiiiij输出：方程组的解；和解；做对；分解输入：Crout分解n若矩阵A有分解：A=LU，其中L为下三角阵，U为单位上三角阵，则称该分解为Crout分解，若矩阵A的Doolitlle分解为A=LU ，则矩阵AT的Crout分解为UTLT。n所以得到计算Crout分解的计算方法如下：Cruou分解各元素

10、方法逐行逐列求解用比较等式两边元素的令ULuuullllllaaaaaaaaannnnnnnnn,1.1.1.211221222111n2n1n2222112111Crout分解nnnnnniikttjitijijkttijtjijilllulluulninijlulauninijulal.A),.,1;,.,1(/ )(),.,1;,.,1(2122221112111111的各位各元素在计算机内存于即3.2.3 对称正定矩阵的Cholesky分解n在应用数学中，线性方程组大多数的系数矩阵为对称正定这一性质，因此利用对称正定矩阵的三角分解式求解对称正定方程组的一种有效方法，且分解过程无需选主元

11、，有良好的数值稳定性。 对称正定矩阵的Cholesky分解n A对称：AT=A A正定：A的各阶顺序主子式均大于零。即 ),.2 , 1(0.1111nkaaaaAkkkkk对称正定矩阵的Cholesky分解 全正。为下三角矩阵，对角元其中，LLLTA 对称矩阵的Cholesky分解n定理3.2.4 设A为对称正定矩阵，则存在唯一分解A=LDLT，其中L为单位下三角阵，D=diag(d1,d2,dn)且di0(i=1,n)对称矩阵的Cholesky分解n证明： ndddUULLUADoolittle21111,A令非奇异的上三角阵。为为单位下三角阵，其中分解为分解可唯一是对称正定，由因为对称矩

12、阵的Cholesky分解均大于零即。得由；得；由得故有的顺序主子式均大于零是正定的，则又因为nnnnddddddddddddA,.,00.;0000A21212212111对称矩阵的Cholesky分解。所以为单位上三角阵。为对角阵其中故LDUAUDDUdddddddUn,1.1*.*1*.*12211211对称矩阵的Cholesky分解。，所以故有对称，即又因为TTTTTTLDLAULADLULDUAA)(推论：设A为对称正定矩阵，则存在唯一分解 其中L为具有主对角元素为正数的下三角矩阵。TLLA 对称矩阵的Cholesky分解n证明： 0,.,0, 0)(4 . 2 . 3),.,(212

13、1212121nTTTndddLLLLDLDLDLAddddiagD的主对角元素为其中则由定理令Cholesky分解的求法332322131211333231222111333231232221131211212221113?.,llllllllllllaaaaaaaaanlllllllLLLAAijnnnnT为例。以如何求令则对称正定设Cholesky分解的求法。，得由；，得时：由。；同理得，得由；，得时：由2221313232223221313222122222222212211313111212111212111112111121lllalllllalalllaklallalllaall

14、akCholesky分解的求法njnjilllallalnlallllakjjjkjkikijijjkjkjjjjii,.,2 , 1,.,1/ )()(,311211122123333323323223133有阶行列式推广到，得时：由Cholesky分解法TTLLAyxLbLybAXcholesky其中分解法解线性方程组用Cholesky分解法缺点及优点 优点：可以减少存储单元。 缺点：存在开方运算，比较耗时。改进Cholesky分解法n改进的cholesky分解A=LDLTnnnnnnnnTnnnnnndlddldlddldldlddllllllDLLAdddDllllllL.1.111)

15、(1.11133322322211311211112132312121121323121由改进的cholesky分解1121111211,.,2 , 1) 1,.,2 , 1(/ )(),.,2 , 1() 1,.,2 , 1(jkkikiiijjkjkkikijijjkikikiijijjkjkkikijnidladijdldlalniddlaijdlldlaji由此可得有逐行相乘，并注意到改进的cholesky分解) 1,.,2 , 1,.,3 , 2(,1111ijnilcaddcllcacdcldlcikikikiiijijijjkjkikijijjijijjijij，成所以可将上述公

16、式改写，则可令为减少计算量TnnnTdydydyyDdddDDLLACholeskyyxbybx),.,(111221112111故即等价于求分解法解线性方程组用改进的cholesky分解算法；做对做对分解，输入1111)2(1,.,2 , 1) 1 (,.,3 , 2. 2);,.2 , 1(),.,2 , 1(. 1ikikikiiiiijijijijjkikikijijTiijlcadadclalcacijniLDLAnibni,ja改进的cholesky分解算法。输出：；解；解解),.,2 , 1()3() 1,.,1()2(),.,2() 1 (. 3111111nixnixldyx

17、dyxyDxLniylbybybLyAinikkkiiiinnnTikkikiibx例题分解做解：对系数矩阵算法解方程组分解试用改进的例DoolitteAxxxCholeskey6353212211142 . 2 . 3321例题TLDLA11125. 025. 0111.7541125. 025. 01175. 11.751141125. 025. 011125. 075. 175. 125. 01143125. 075. 175. 125. 01143225. 02225. 0114321221114例题TybyyyyyyyL)3 ,47, 5(3,75. 1, 5635110.25125. 01321321即得得由例题TTTxyxyxxxxxxDLD)3 , 2 , 1 (1, 2, 33125. 111125. 025. 01)3 , 1,45(12332111所以方程的解：得得，由而nA=LDLT分解，既适合于解对称正定方程组，也适合求解A为对称，而各阶顺序主子式不为零的方程组n而对A=LLT只适合于对称正定方程组3.2.4 三对角方程组求解的追赶法nnnnnijnnijabcabcabcaAajaA11122211, 01|i |)(即有，对一切设三对角矩阵