矩阵的三角分解（基础课堂）

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

2、 . . . . . . . . . . 1.00 . 10 1 1 .,32i)()(1) ,.,0:1 222 11211 21 22221 112 11 AAL aa aa aaa aaa aaa aaa l l l ni-l a a laaaa nn n n nnnn n n nn i i in ，其矩阵形式为，行行 令消零时，将步等价于第 则 ）（）（）（ 3应用分析 )3( )3()3( 3 )3( 3 )3( 33 )2( 2 )2( 23 )2( 22 )1( 1 )1( 13 )1( 12 )1( 11 2 2 2 )2( 22 )2( 2 2 2 322 )2( 22 .0

3、0 . .00 .0 . : ),.,4 , 3( 1.00 . 0.10 0.010 0.001 02 A aa aa aaa aaaa ALA ni a a l l lL a nnn n n n )()( i i n ，即有左乘 时，用矩阵步等价于：若同理第 4应用分析 1 . 1 1 1 1. . 1 1 .000 . .00 .0 . . 2 32 1 2 1 211 1 )( )3( 3 )3( 33 )2( 2 )2( 23 )2( 22 )1( 1 )1( 13 )1( 12 )1( 11 1221 n n n nn n n n nn l lL l l L U a aa aaa

4、aaaa ALLLL 因为 以此类推可得 5应用分析 为上三角阵为单位下三角阵，其中 所以 U 1. . 1 1 1 .).( 121 3231 21 1 1 1 2 1 2 1 1 1 1221 L LUU lll ll l ULLLLULLLLA nnnn nnnn 6应用分析 分解。行 直接进否对矩阵因此，关键问题在于能 个三角方程： 就等价于解两由此解线性方程组 LU A yUx bLy UL A bx bx )( 7应用分析 3.2.2 Doolittle分解 11 31 31311131 11 21 21211121 1111 23 2322 131211 3231 21 3332

5、31 232221 131211 )3 , 2 , 1(1 1 1 1 3, u a llua u a llua jauuak u uu uuu ll l aaa aaa aaa nUL jjjj 得由 ；得由 时： 为例的各元素，以此分解在于如何算出 8应用分析 )( 3 2 233213313333 332332133133 22 123132 322332123132 1321232323132123 1221222222122122 ululau uululak u ula lulula ulauuula ulauuulak 得 时：由 得由 ；得由 ；得时： 9应用分析 Doolit

6、tle分解 n若矩阵A有分解：A=LU，其中L为单位下 三角阵，U为上三角阵，则称该分解为 Doolittle分解，可以证明，当A的各阶顺 序主子式均不为零时，Doolittle分解可以 实现并且唯一。 10应用分析 nA的各阶顺序主子式均不为零，即 ),.2 , 1(0 . . . 1 111 nk aa aa A kkk k k 11应用分析 Doolittle分解 各元素方法逐行逐列求解用比较等式两边元素的 令 UL u uu uuu ll l aaa aaa aaa nn n n nnn n n , . . 1. 1 1 . . . 222 11211 21 21 n2n1n 2222

7、1 12111 12应用分析 Doolittle分解 。得再由 ；得由 时： 。得再由 ；得由 时 ),.,4 , 3( ),.,3 , 2(1 2 ),.,3 , 2( ),.2 , 1(1 :1 22 1212 22221212 122221212 11 1 11111 i 1111 ni u ula lulula njulauuula k ni u a llua njauua k ii iiii jijjjjj i ii jjjj 13应用分析 Doolittle分解 1 1 1 1 2 1 121 1 ,.1, 0 0 0.10. ,., k t tjktkjkj k t kjtjkt

8、jj j j kkkkkj knkkkk nkkjulau uulu u u llla kjuuuk ）（有 步时：计算第 14应用分析 Doolittle分解 1 1 1 1 1 11 1 ,.1/)( 0 0 0.0, 1 ,., ,., k t kktkitikik k t kkiktkit kk k ikiik nkkk nkiuulal ulul u u lla kill ）（得 ，于是由由于计算 15应用分析 Doolittle分解 nnnn n n kk k t tkitikik k t tjktkjkj ull uul uuu nkuulal nkinkjulau . . .

9、A ,.,2 , 1/ )( ),.,1;,.,( 21 22221 11211 1 1 1 1 的各位各元素在计算机内存于 即 16应用分析 Doolittle分解 。可获解 得及再由 T n ii n ij jijii i j jijii xxx nniuxuyx niylby UL x yxby ),.,( 1,.1,/ )( ,.,2 , 1 21 1 1 1 17应用分析 例题 30 19 10 636 19134 652 .D. 1 3 2 1 x x x oolittle分解求解方程组试用例 18应用分析 例题 。， ；， ，令、分解解： 3 2 6 2 4 6521 1 01

10、001 636 19134 652 1 31 11 21 131211 33 2322 131211 3231 21 l u l uuuk u uu uuu ll l ALU 19应用分析 例题 LUA ululauk uulal ulau ulauk 4 73 652 143 12 1 43 4/ )( 7)6(219 352132 233213313333 2212313232 13212323 12212222 所以 时： ，时： 20应用分析 例题 T y yyy y y y bLy )4 , 1,10( 43034, 12019,10 30 19 10 143 12 1 1 2 32

11、1 3 2 1 即 得 ）解（ 、解方程组 21应用分析 例题 。所以方程组的解为 解得： 解 T x xxx x x x yUx ) 1 , 2 , 3( 3, 2, 1 4 1 10 4 73 652 )2( 123 3 2 1 22应用分析 Doolittle分解 ).,.,2 , 1()4( ) 1 , 2,.,1(/ )(;/)2 ),.,2(;) 1 )3( ),.,1(/ )( ),.1,( ,.3 , 2)2 ),.,3 , 2(/) 1 )2( ),.,2 , 1(),.,2 , 1,() 1 ( 1 1 1 11 1 1 1 1 11111 nix niuxuyxayx n

12、iylbyby yUxbLy nkiuulala nkkjulaua nk niaala LUA nibnjia i ii n ij jijiinmnn i j jijii kk k t tkitikikik k t tjktkjkjkj iii iij 输出：方程组的解 ； ； 和解 ； ； 做对 ； 分解 输入： 23应用分析 Crout分解 n若矩阵A有分解：A=LU，其中L为下三角 阵，U为单位上三角阵，则称该分解为 Crout分解，若矩阵A的Doolitlle分解为 A=LU ，则矩阵AT的Crout分解为UTLT。 n所以得到计算Crout分解的计算方法如下： 24应用分析 Cru

13、ou分解 各元素方法逐行逐列求解用比较等式两边元素的 令 UL u uu lll ll l aaa aaa aaa n n nnnnn n n , 1 .1 .1 . . . 2 112 21 2221 11 n2n1n 22221 12111 25应用分析 Crout分解 nnnn n n ii k t tjitijij k t tijtjiji lll ull uul ninijlulau ninijulal . . . A ),.,1;,.,1(/ )( ),.,1;,.,1( 21 22221 11211 1 1 1 1 的各位各元素在计算机内存于 即 26应用分析 3.2.3 对称正

14、定矩阵的Cholesky分解 n在应用数学中，线性方程组大多数的系 数矩阵为对称正定这一性质，因此利用 对称正定矩阵的三角分解式求解对称正 定方程组的一种有效方法，且分解过程 无需选主元，有良好的数值稳定性。 27应用分析 对称正定矩阵的Cholesky分解 n A对称：AT=A A正定：A的各阶顺序主子式均大于零。 即 ),.2 , 1(0 . . . 1 111 nk aa aa A kkk k k 28应用分析 对称正定矩阵的Cholesky分解 全正。为下三角矩阵，对角元其中，L LL T A 29应用分析 对称矩阵的Cholesky分解 n定理3.2.4 设A为对称正定矩阵，则存在

15、唯一分解A=LDLT，其中L为单位下三角 阵，D=diag(d1,d2,dn)且di0(i=1,n) 30应用分析 对称矩阵的Cholesky分解 n证明： n d d d U ULLUA Doolittle 2 1 1 11 , A 令 非奇异的上三角阵。 为为单位下三角阵，其中分解为 分解可唯一是对称正定，由因为 31应用分析 对称矩阵的Cholesky分解 均大于零即 。得由；得 ；由得故有 的顺序主子式均大于零是正定的，则又因为 n nnn ddd ddddd dddd A ,., 00.;0 000 A 21 212 212111 32应用分析 对称矩阵的Cholesky分解 。所以

16、 为单位上三角阵。为对角阵其中 故 LDUA UD DUdd dd d d d U n , 1 . .1 * . * 1 * . * 1 22 11 2 1 1 33应用分析 对称矩阵的Cholesky分解 。，所以故有 对称，即又因为 TT TTTT LDLAUL ADLULDUA A )( 推论：设A为对称正定矩阵，则存在唯一分解 其中L为具有主对角元素为正数的下三角矩 阵。 T LLA 34应用分析 对称矩阵的Cholesky分解 n证明： 0,.,0, 0 )( 4 . 2 . 3 ),.,( 21 2 1 2 1 21 2 1 n T TT n dddL LLLDLDLDLA ddd

17、diagD 的主对角元素为其中 则由定理 令 35应用分析 Cholesky分解的求法 33 2322 131211 333231 2221 11 333231 232221 131211 21 2221 11 3? . . , l ll lll lll ll l aaa aaa aaa nl lll ll l L LLAA ij nnnn T 为例。以如何求 令 则对称正定设 36应用分析 Cholesky分解的求法 。，得由 ；，得时：由 。；同理得，得由 ；，得时：由 22 213132 322232213132 2 212222 2 22 2 2122 11 31 31 11 21 2

18、1112121 1111 2 1111 2 1 l lla llllla lalllak l a l l a llla allak 37应用分析 Cholesky分解的求法 njnji lllal lal n lallllak jj j k jkikijij j k jkjjjj i i ,.,2 , 1,.,1 / )( )( , 3 1 1 2 1 1 1 2 2 1 2 33333 2 33 2 32 2 3133 有阶行列式推广到 ，得时：由 38应用分析 Cholesky分解法 T T LLA yxL bLy bAX cholesky 其中 分解法解线性方程组用 Cholesky分解

19、法缺点及优点 优点：可以减少存储单元。 缺点：存在开方运算，比较耗时。 39应用分析 改进Cholesky分解法 n改进的cholesky分解A=LDLT n n n n nnnn T nnnnnn d ldd ldldd ldldldd lll ll l DLLA d d d D lll ll l L . . . . 1. . 1 1 1 )( 1. . 1 1 1 333 223222 113112111 121 3231 21 2 1 121 3231 21 由 40应用分析 改进的cholesky分解 1 1 2 1 1 1 1 2 1 1 ,.,2 , 1 ) 1,.,2 , 1(/

20、 )( ),.,2 , 1( ) 1,.,2 , 1( j k kikiii j j k jkkikijij j k ikikii jij j k jkkikij nidlad ijdldlal niddla ijdlldla ji 由此可得 有逐行相乘，并注意到 41应用分析 改进的cholesky分解 ) 1,.,2 , 1,.,3 , 2( , 1 1 1 1 ijni lcad d c l lcac d c ldlc i k ikikiii j ij ij j k jkikijij j ij ijjijij ， 成所以可将上述公式改写 ，则可令为减少计算量 42应用分析 T n n n

21、 T d y d y d y yD d d d D DL L ACholesky yx by bx ),.,( 1 1 1 2 2 1 1 1 2 1 1 1 故 即等价于求 分解法解线性方程组用 43应用分析 改进的cholesky分解算法 ； ； 做对 做对 分解 ，输入 1 1 1 1 )2( 1,.,2 , 1) 1 ( ,.,3 , 2 . 2 );,.2 , 1(),.,2 , 1(. 1 i k ikikiiiii j ij ijij j k ikikijij T iij lcada d c lalcac ij ni LDLA nibni,ja 44应用分析 改进的cholesk

22、y分解算法 。输出： ； 解 ； 解 解 ),.,2 , 1()3( ) 1,.,1( )2( ),.,2( ) 1 ( . 3 1 1 1 1 11 nix nixl d y x d y x yDxL niylbyby bLy A i n ik kki i i i n n n T i k kikii bx 45应用分析 例题 分解做解：对系数矩阵 算法解方程组 分解试用改进的例 DoolitteA x x x Choleskey 6 3 5 321 221 114 2 . 2 . 3 3 2 1 46应用分析 例题 T LDL A 1 11 25. 025. 01 1 1.75 4 1125. 0 25. 0 1 1 75. 11.75 114 1125. 0 25. 0 1 1125. 0 75. 175. 125. 0 114 3125. 0 75. 175. 125. 0 114 3225. 0 2225. 0 114 321 221 114 47应用分析 例题 T y by yyy y y y L )3 , 4 7 , 5( 3,75. 1, 5 6 3 5 110.25 125 . 0 1 32