第3章-解线性方程组的数值解法2-LU分解法

3.2矩阵的三角分解法我们知道对矩阵进行一次初等变换，就相当于用相应的初等矩阵去左乘原来的矩阵。因此我们这个观点来考察Gauss消元法用矩阵乘法来表示，即可得到求解线性方程组的另一种直接法：矩阵的三角分解。3.2.1Gauss消元法的矩阵形式)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:122211211212222111211AALaaaaaaaaaaaaaaaalllni-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(13)1(12)1(111221nnnnnnnnnnllLllLUaaaaaaaaaaALLLL因为以此类推可得为上三角阵为单位下三角阵，其中所以U1............111...)...(1213231211112121111221LLUUllllllULLLLULLLLAnnnnnnnn分解。行直接进否对矩阵因此，关键问题在于能个三角方程：就等价于解两由此解线性方程组LUAyUxbLyULAbxbx)(3.2.2Doolittle分解1112131112132122232122233132333132331111212111212111313111313111,31111(1,2,3)jjjjLUnaaauuuaaaluuaaallukauuajaaulluaaullu此分解在于如何算出的各元素，以为例时：由得；由得)(322332133133333323321331332212313232233212313213212323231321231221222222122122ululauuululakuulalululaulauuulaulauuulak得时：由得由；得由；得时：Doolittle分解若矩阵A有分解：A=LU，其中L为单位下三角阵，U为上三角阵，则称该分解为Doolittle分解，可以证明，当A的各阶顺序主子式均不为零时，Doolittle分解可以实现并且唯一。A的各阶顺序主子式均不为零，即),...2,1(0...............1111nkaaaaAkkkkkDoolittle分解各元素方法逐行逐列求解用比较等式两边元素的令ULuuuuuulllaaaaaaaaannnnnnnnn,......1...11.........222112112121n2n1n2222112111Doolittle分解。得再由；得由时：。得再由；得由时),...,4,3(),...,3,2(12),...,3,2(),...2,1(1:12212122222121212222121211111111i1111niuulalululanjulauuulakniualluanjauuakiiiiiijijjjjjiiijjjjDoolittle分解1111211211,...1,00]0...10...[,...,kttjktkjkjktkjtjktjjjjkkkkkjknkkkknkkjulauuuluuulllakjuuuk）（有步时：计算第Doolittle分解11111111,...1/)(00]0...0,1,...,[,...,ktkktkitikikktkkiktkitkkkikiiknkkknkiuulalululuullakill）（得，于是由由于计算Doolittle分解nnnnnnkkkttkitikikkttjktkjkjulluuluuunkuulalnkinkjulau.........A,...,2,1/)(),...,1;,...,(2122221112111111的各位各元素在计算机内存于即Doolittle分解。可获解得及再由TniinijjijiiijjijiixxxnniuxuyxniylbyULxyxby),...,,(1,...1,/)(,...,2,121111例题30191063619134652.D.1321xxxoolittle分解求解方程组试用例例题。，；，，，令、分解解：326246521101001636191346521311121131211332322131211323121luluuukuuuuuulllALU例题LUAululaukuulalulauulauk473652143121434/)(7)6(21935213223321331333322123132321321232312212222所以时：，时：例题TyyyyyyybLy)4,1,10(43034,12019,1030191014312112321321即得）解（、解方程组例题。所以方程组的解为解得：解TxxxxxxxyUx)1,2,3(3,2,14110473652)2(123321Doolittle分解).,...,,()(),,...,(/)(;/)2),...,)(;)1)(),...,(/)(),...,(,...,)2),...,,(/))(),...,,(),,...,,,()1(nixniuxuyxayxniylbybyyUxbLynkiuulalankkjulauankniaalaLUAnibnjiaiiinijjijiinmnnijjijiikkkttkitikikikkttjktkjkjkjiiiiij2141212311323212212111111111111111输出：方程组的解；；和解；；做对；分解输入：3.2.3对称矩阵的Cholesky分解在应用数学中，线性方程组大多数的系数矩阵为对称正定这一性质，因此利用对称正定矩阵的三角分解式求解对称正定方程组的一种有效方法，且分解过程无需选主元，有良好的数值稳定性。对称矩阵的Cholesky分解A对称：AT=AA正定：A的各阶顺序主子式均大于零。即),...2,1(0...............1111nkaaaaAkkkkk对称矩阵的Cholesky分解由Doolittle分解，A有唯一分解。，也就是所以，，有即TTTTTTTTTLLAULULLULULULULUALU)(A对称矩阵的Cholesky分解定理3.2.4设A为对称正定矩阵，则存在唯一分解A=LDLT，其中L为单位下三角阵，D=diag(d1,d2,…,dn)且di0(i=1,…,n)对称矩阵的Cholesky分解证明：ndddUULLUADoolittle21111,A令非奇异的上三角阵。为为单位下三角阵，其中分解为分解可唯一是对称正定，由因为对称矩阵的Cholesky分解均大于零即。得由；得；由得故有的顺序主子式均大于零是正定的，则又因为nnnnddddddddddddA,...,,00............;0000A21212212111对称矩阵的Cholesky分解。所以为单位上三角阵。为对角阵其中故LDUAUDDUdddddddUn,1.........1*...*1*.......*12211211对称矩阵的Cholesky分解。，所以故有对称，即又因为TTTTTTLDLAULADLULDUAA)(推论：设A为对称正定矩阵，则存在唯一分解其中L为具有主对角元素为正数的下三角矩阵。TLLA对称矩阵的Cholesky分解证明：0,...,0,0))((4.2.3),...,,(2121212121nTTTndddLLLLDLDLDLAddddiagD的主对角元素为其中则由定理令Cholesky分解的求法332322131211333231222111333231232221131211212221113?.........,llllllllllllaaaaaaaaanlllllllLLLAAijnnnnT为例。以如何求令则对称正定设Cholesky分解的求法。，得由；，得时：由。；同理得，得由；，得时：由2221313232223221313222122222222212211313111212111212111112111121lllalllllalalllaklallalllaallakCholesky分解的求法njnjilllallalnlallllakjjjkjkikijijjkjkjjjjii,...,2,1,,...,1/)()(,311211122123333323323223133有阶行列式推广到，得时：由Cholesky分解法TTLLAyxLbLybAXcholesky其中分解法解线性方程组用Cholesky分解法缺点及优点优点：可以减少存储单元。缺点：存在开方运算，可能会出现根号下负数。改进Cholesky分解法改进的c