矩阵三角分解法

1、一、直接法概述直接法是将原方程组化为一个或若干个三角形方程组的方法，共有若干种对于线性方程组bAx nnnnnnaaaaaaaaaA212222111211nxxxx21nbbbb21其中系数矩阵未知量向量常数项根据Cramer(克莱姆)法则,若0)det(A有唯一解则方程组bAx determinantal|)det(AA 行列式的记号若用初等变换法求解,则对其增广矩阵作行初等变换:),(bAA),()1()1(bA),()2()2(bA经过n-1次),()()(nnbA为上三角阵目标：)(nA的解不难得到则方程组)()(nnbxAbAx bAx )()(nnbxA同解即以上求解线性方程组的

2、方法称为Gauss消去法即和两个三角形矩阵分解成的系数矩阵如果将线性方程组,ULAbAx LUA 则bLUx bLy yUx 都是三角形方程组上述方法称为直接三角形分解法2 Matrix Factorization Doolittle 道立特分解法道立特分解法 /* Doolittle Factorization */： LU 分解的紧凑格式分解的紧凑格式 /* compact form */反复计算反复计算,很浪费哦很浪费哦 通过比较法直接导出通过比较法直接导出L 和和 U 的计算公式。的计算公式。思思路路 nnnnnnnnuuullaaaa.1.11.1111211111 ),min(1j

3、ikjkkiul jia2 Matrix Factorization Doolittle固定固定 i : :对对 j = i, i+1, , n 有有ijkjikikijuula 11lii = 1kjikikijijulau 11a固定固定 j ，对，对 i = j, j+1, , n 有有jjijkjjkikijulula11jjjkkjikijijuulal/ )(11bju1ja11111ualii上述解线性方程组的方法称为直接三角分解法的 Doolittle法例1. 用Doolittle法解方程组1391444321131243301024321xxxx72510解:由Doolitt

4、le分解14131211uuuu30102Tlll4131211T25 . 05 . 112423220uuu5 . 812110Tll423210T11/611/310343300uu11/211/300Tl43100T910044000u4000得解, bLy Tyyyy4321T1611/17201011rkkjrkrjrjulaurrrkkrikiriruulal11得解, yUx Txxxx4321T4321nnnnuyx rrnrjjrjrruxuyx1Doolittle法在计算机上实现是比较容易的但如果按上述流程运算仍需要较大的存储空间:都需要单独的存储空间yULxbA,式可知的

5、计算过程而从)4()1(,ijijul的存储位置即不再需要后的第一行求出)1(11jauUjj的存储位置即不再需要后的第一列求出)2(11ialLii的存储位置即不再需要后行的第求出)(rjaurUrjrj的存储位置即不再需要后列的第求出)1( rialrLirir因此可按下列方法存储数据:nrrjuarjrj,2 , 1),(1,2 , 1),1(nrrilairir有如下特点：时解三角形方程组同样,bLy 的存储位置即不再需要后求出11by的存储位置即不再需要后求出)2( ibyiiniybii,2 , 1,空出的存储位置的存储可以使用因此)1( ibyii直接三角分解的Doolittle

6、法可以用以下过程表示:432144434241343332312423222114131211bbbbaaaaaaaaaaaaaaaa4535251544434241343332312423222114131211aaaaaaaaaaaaaaaaaaaa存储单元(位置)4321444342413433323124232221141312111bbbyaaalaaalaaaluuuur4321444342413433323124232221141312112bbyyaallaalluuuluuuur4321444342413433323124232221141312113byyyallluull

7、uuuluuuur4321444342413433323124232221141312114yyyyullluulluuuluuuuryUL,可知从上式最后一个矩阵中yUx 然后解线性方程组紧凑格式的Doolittle法例2. 用紧凑格式的Doolittle法解方程组(例1)解:4535251544434241343332312423222114131211aaaaaaaaaaaaaaaaaaaaA7251013914443211312433010272510139142432211312423301021rju1ja11111ualii11rkkjrkrjrjulaurrrkkrikirir

8、uulal1172201013911624311321217121123301022r11rkkjrkrjrjulaurrrkkrikiriruulal11711172010139116211211311321217121123301023r161117201049116211211311321217121123301024rLxU43214911621121131132121712112330102yUx解4321xxxxx4321所以yMatrix Factorization Choleski 平方根法平方根法 /* Choleskis Method */： 对称对称 /* symmetr

9、ic */ 正定正定 /* positive definite */ 矩阵的分解法矩阵的分解法定义定义一个矩阵一个矩阵 A = ( aij )n n 称为称为对称阵对称阵，如果，如果 aij = aji 。定义定义一个矩阵一个矩阵 A 称为称为正定阵正定阵，如果，如果 对任意非对任意非零向量零向量 都成立。都成立。0 xAxTx回顾：回顾：对称正定阵的几个重要性质对称正定阵的几个重要性质 A 1 亦对称正定，且亦对称正定，且 aii 0若不然，则若不然，则0 xA存在非零解，即存在非零解，即0 xAxT存在非零解。存在非零解。1111)()(, AAIAAIAATTT对任意对任意 , 存在存在

10、 , 使得使得 ,即即 。0 x0 yxyA xAy1 011 yAyyAAAyxAxTTT 其中其中0 xAxaTiiTx)0.1.0( 第第 i 位位 A 的顺序主子阵的顺序主子阵 /* leading principal submatrices */ Ak 亦对亦对 称正定称正定对称性显然。对任意对称性显然。对任意 有有 , 其中其中 。kkRx 00 xAxxAxTkkTknkRxx 00 A 的特征值的特征值 /* eigen value */ i 0 设对应特征值设对应特征值 的非零特征向量的非零特征向量为为 ，则，则 。20 xxxxAxTT x A 的全部顺序主子式的全部顺序主

11、子式 det ( Ak ) 0因为因为 niiA1)det( 一、对称正定矩阵的三角分解(Cholesky分解)nkAAk,2 , 1,0det的顺序主子式且为对称正定矩阵阶矩阵若AnAAAT,0)det(则)(分解或分解可以进行因此DoolittleLUA记为LUA 为上三角阵为单位下三角阵其中UL,nnnnnuuuuuuuuuuU333223221131211nnuuuu33221111111, 1, 1222222311111131112nnnnnnuuuuuuuuuuuu0 DU),(2211nnuuudiagD0DUU 02121UDDLUA 02121UDLD22211),(nnu

12、uudiagDiagonal:对角)(02121UDLD是单位下三角阵是单位上三角阵，唯一，由于TUULDULUA000AAAT,为对称正定阵而TTLDUA)(0因此TTTLDU0TLDL所以002121)( ,UDLDULTT综合以上分析,211LDLAn为对称正定矩阵，令阶矩阵若则有TLLA11定理1. (Cholesky分解)使得正数的下三角阵元全是则一定存在一个主对角为对称正定矩阵设,LATLLA 且该分解式唯一这种关于对称正定矩阵的分解称为Cholesky分解nnnrnrrrllllllL1111nnnrnrnrrrnraaaaaaaaaA111111设jiijaa irarArL列

13、元素的第考察列已求出的第假设,11nnnrnrrrllllll1111nnnrnrnrrrnraaaaaaaaa111111nnnrrrnrllllll1111111111lla112121lla1111llaiini,2 , 1可以求出的第一列元素1ilLrkrkrkrrlla12112rrrkrkllrkrkikirlla1rrirrkrkikllll11nrri, 1,的元素的计算公式式可得由L)8()6(1111al1111laliini, 3 ,2112rkrkrrrrlalnr,2 rrrkrkikirirlllal11nri, 1 二、对称正定线性方程组的解法bAx 线性方程组阶

14、对称正定矩阵为其中nA使得的下三角阵则存在主对角元为正数,LTLLA 则线性方程组(10)可化为两个三角形方程组bLy yxLTbxLLT)(bLy 解. 1nnniniiillllllL11111111lby iiikkikiilylby11ni, 3 ,2yxLT解. 2nnniiiniTllllllL1111nnnnlyx iinikkkiiilxlyx1对称正定方程组的平方根法1 ,2 , 1 ni例1.用平方根法解对称正定方程组91096858137576321xxx解:A先分解系数矩阵6858137576Arrrkrkikirirrkrkrrrriilllallallalal111

15、1211111111 29251741365629676分解TLLLbLy 其次解91091111lby 692212122lylby62969*71017433321333lylbykkk29101111lby iiikkikiilylby1129251741365629676),(bL即Tyyyy),(321T)2910,1743,69(yxLT最后解291017436929251741362965676nnnnlyx iinikkkiiilxlyx13333lyx 1132111lxlyxkkk22233222lxlyx11),(yLT三、平方根法的数值稳定性用平方根法求解对称正定方程组

16、时不需选取主元TLLA 由可知rkrkrkrrlla1rkrkl12因此rrrkal2|不会放大得以控制中间量,rklnr,2 , 1rk,2 , 1平方根法是数值稳定的事实上,对称正定方程组也可以用顺序Gauss消去法求解而不必加入选主元步骤2 Matrix Factorization Tridiagonal System 追赶法解追赶法解三对角三对角方程组方程组 /* Crout Reduction for Tridiagonal Linear System */ nnnnnnnfffxxxbacbacbacb212111122211Step 1: 对对 A 作作Crout 分解分解 11

17、1121nnnA 直接比较等式两边直接比较等式两边的元素，可得到计的元素，可得到计算公式。算公式。Step 2: 追追即解即解 ：fyL ,111 fy ),.,2()(1niyrfyiiiii Step 3: 赶赶即解即解 ：yxU )1,., 1(,1 nixyxyxiiiinn 与与G.E.类似，一旦类似，一旦 i = 0 则算法中断，故并非任何则算法中断，故并非任何三对角阵都可以用此方法分解。三对角阵都可以用此方法分解。有一类方程组,在今后要学习的插值问题和边值问题中有着重要的作用,即三对角线方程组,其形式为:nnnnnbacbacbacbA11122211nxxxx21fAx 其中n

18、ffff21并且满足称为三对角线矩阵,A0|)1(11 cb-(1)0,|)2(iiiiicacab1,2ni0|)3(nnab.线矩阵称为对角占优的三对角A0det,AA即非奇异显然0det,kAkA即阶顺序主子式非零的任意因此分解进行可以将所以LUA,分解为为上三角阵时为单位下三角阵DoolittleUL,分解为为单位上三角阵时为下三角阵CroutUL,以下以Crout分解导出三对角线方程组的解法设LUA nnnnnbacbacbacbA1112221111111111221nnnnn),.,2( ),.,2( ,111nicniabbiiiiiiiii1111 ,iiiiiiiibbb),.,2( niaaiiii),.,2(c c 1nibciiiiiiiiii11111111221nnnnnnnnnnbacbacbacb11122211例1.用追赶法解三对角线方程组010131132132134321xxxx解:Taaaa),(432设T)1 ,2 ,2(Tbbbbb),(4321T)3 , 3 , 3 , 3(Tfffff),(4321T)0