南京大学计算机科学与技术系数值计算方法第3章2矩阵的三角分解法矩阵求逆ppt课件

1、3.2 矩阵的三角分解法n我们知道对矩阵进展一次初等变换，就相当于用相应的初等矩阵去左乘原来的矩阵。因此我们这个观念来调查Gauss消元法用矩阵乘法来表示，即可得到求解线性方程组的另一种直接法：矩阵的三角分解。n 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:122211211212222111211AALaaaaaaa

2、aaaaaaaaalllni-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)2(22)1(1)1(1

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

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

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

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

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

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

9、kiuulalankkjulauankniaalaLUAnibnjiaiiinijjijiinmnnijjijiikkkttkitikikikkttjktkjkjkjiiiiij2141212311323212212111111111111111输出：方程组的解；和解；做对；分解输入：3.2.3 对称矩阵的Cholesky分解n在运用数学中，线性方程组大多数的系数矩阵为对称正定这一性质，因此利用对称正定矩阵的三角分解式求解对称正定方程组的一种有效方法，且分解过程无需选主元，有良好的数值稳定性。 对称矩阵的Cholesky分解n A对称：AT=A n A正定：A的各阶顺序主子式均大于零。即n )

10、,.2 , 1(0.1111nkaaaaAkkkkk对称矩阵的Cholesky分解n由Doolittle分解，A有独一分解n 。，也就是所以，有即TTTTTTTTTLLAULULLULULULULUALU)(A对称矩阵的Cholesky分解n定理3.2.4 设A为对称正定矩阵，那么存在独一分解A=LDLT，其中L为单位下三角阵，D=diag(d1,d2,dn)且di0(i=1,n)对称矩阵的Cholesky分解n证明：n ndddUULLUADoolittle21111,A令非奇异的上三角阵。为为单位下三角阵，其中分解为分解可唯一是对称正定，由因为对称矩阵的Cholesky分解均大于零即。得由

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

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

13、jilllallalnlallllakjjjkjkikijijjkjkjjjjii,.,2 , 1,.,1/ )()(,311211122123333323323223133有阶行列式推广到，得时：由Cholesky分解法TTLLAyxLbLybAXcholesky其中分解法解线性方程组用Cholesky分解法缺陷及优点 优点：可以减少存储单元。 缺陷：存在开方运算，能够会出现根号下负数。改良Cholesky分解法n改良的cholesky分解A=LDLTnnnnnnnnTnnnnnndlddldlddldldlddllllllDLLAdddDllllllL.1.111)(1.111333223

14、22211311211112132312121121323121由改良的cholesky分解1121111211,.,2 , 1) 1,.,2 , 1(/ )(),.,2 , 1() 1,.,2 , 1(jkkikiiijjkjkkikijijjkikikiijijjkjkkikijnidladijdldlalniddlaijdlldlaji由此可得有逐行相乘，并注意到改良的cholesky分解) 1,.,2 , 1,.,3 , 2(,1111ijnilcaddcllcacdcldlcikikikiiijijijjkjkikijijjijijjijij，成所以可将上述公式改写，则可令为减少计算

15、量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 (. 3111111nixnixldyxdyxyDxLniylb

16、ybybLyAinikkkiiiinnnTikkikiibx例题分解做解：对系数矩阵算法解方程组分解试用改进的例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即得

17、得由例题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 |)(即有，对一切设三对角矩阵三对角方程组求解的追逐法),.,3 , 2(1111,111111221132nicpaqqbpaqqcqcqcqpppALUDoolit

18、tleAiiiiiiinnnn其中则有分解满足如果三对角方程组求解的追逐法),.,2(1111),.,(1113213213221niypfyfyffffyyyypppfffULAiiiinnnTnfyxfyfx解得，故有其中等价于求则求三对角方程组求解的追逐法组的追赶法。以上称为解三对角方程解得再由) 1,.,1(1121121112211niqxcyxqyxyyyyxxxxqcqcqcqiiiiinnnnnnnnnn三对角方程组求解的追逐法n其计算任务量为5n-4次乘除法。任务量小，其实现的条件为qi不为零。有以下定理可得证三对角矩阵求解的充分性条件。且追赶法可以实现。非奇异则矩阵，且满足

19、形如设三对角矩阵定理,| |,|)3() 1,.,3 , 2(|)2(),.2 , 1(0) 1 (,11). 2 . 3(2 . 2 . 311AabcbnicabnicAnniiii解三对角矩阵线性方程组的追逐法程序框图3.3 矩阵求逆的解。个方程组的为单位向量，右端项分别均为问题等价于求系数矩阵解存在，求的逆矩阵非奇异，则设矩阵),.,2 , 1()0,.,1,.,0 , 0(11njAnAAAAAjjTjjexe矩阵求逆这就是原地求逆。个单元，则可节省放的单元，最后仍用来存如果将个单元还是很困难的。很大时，这但当个存储单元即可实现，。算法上增加了则）（）（式即为顺序消去法知，求解上由初

20、等变换21221|nAAnnnAXXIIAJordanGauss矩阵求逆111)()()()()()()(111.)(1)(1.1.:LLLAkiakiaallllLIALLLJordanGaussnnkkkkkkkikkikknkkkkkkKnn故其中消去法矩阵形式由实现n为使求逆过程不断提高求解精度，因此添加选主元任务，最常用的是选列主元求逆。因此添加一个数组Z(n)，记录选主元的交换号，最后在消元任务完成后，根据Z(n)对A中的元素进展相应的列交换，得到A-1GaussJordan原地求逆法算法原地求逆法);,.2 , 1() 3(;, 0)2(;)(|max|) 1 (),.2 , 1.