毕业论文矩阵分解方法的探讨.docx

《毕业论文矩阵分解方法的探讨.docx》由会员分享，可在线阅读，更多相关《毕业论文矩阵分解方法的探讨.docx（51页珍藏版）》请在三一办公上搜索。

1、毕业论文矩阵分解方法的探讨矩阵分解方法的探讨 The discussion about decomposition of Matrix 专 业: 数学与应用数学 作 者: 指导老师: 学校 二一 摘 要 矩阵是数学研究中一类重要的工具之一, 有着非常广泛的应用, 矩阵分解对矩阵理论及近代计算数学的发展起了关键作用. 本文从矩阵的LU分解、 矩阵的QR分解、 矩阵的满秩分解等几个方面对矩阵分解方法进行了论述: 给出了矩阵分解的几种方法. 关键词: 矩阵, 对称正定矩阵,矩阵的三角分解；矩阵的满秩分解；矩阵的QR分解. I Abstract The matrix is a important to

2、ol in class of mathematical research, and it has a very wide range of applications, matrix decomposition plays a key role in matrix theory and development of modern computational mathematics. This article begin at the discuss from the matrix of LU decomposition、Matrix of the QR Decomposition、Matrix

3、decomposition of full rank and so on. given a matrix factorization method. Keywords: Matrix; Symmetric positive definite matrix, Triangular decomposition of matrix; matrix full rank decomposition; QRdecomposition of matrix. II 目 录 摘 要 . I Abstract . 错误！未定义书签。 0 引言 . 1 1 矩阵的三角(LU)分解 . 1 1.1 矩阵的三角分解基本

4、概念与定理 . 1 1.2 常用的三角分解公式 . 7 1.2.1 杜利特分解 . 7 1.2.2 克劳特分解 . 7 1.2.3 乔累斯基分解 . 8 2 矩阵的满秩分解 . 15 2.1 矩阵的满秩分解基本概念与定理 . 15 3.1 矩阵的QR分解基本概念与定理 . 18 3.2 矩阵QR分解的常用方法 . 20 3.2.1利用Householder矩阵变换. 20 3.2.2利用QR分解公式 . 20 3.2.3利用列初等变换法 . 21 参考文献 . 243 矩阵的QR分解 . 18 0 引言 矩阵的三角分解、正交三角分解、满秩分解将矩阵分解为形式比较简单或性质比较熟悉的一些矩阵的乘

5、积,这些分解式能够明显地反映出原矩阵的许多数值特征,如矩阵的秩、行列式、特征值及奇异值等. 另一方面, 构造分解式的方法和过程也能够为某些数值计算方法的建立提供了理论依据. 本文从矩阵的LU分解； 矩阵的QR分解； 矩阵的满秩分解等几个方面对矩阵分解方法进行论述: 探讨矩阵分解的方法. 1 矩阵的三角分解 1.1 矩阵的三角分解基本概念与定理 定义1.1 设ACmn,如果存在下三角矩阵LCmn和上三角矩阵UCnm, 使5得A=LU, 则称A可作三角分解或LU分解. 定义1.2 设A为对称正定矩阵, D为行列式不为零的任意对角矩阵,则A=AT, U为一个单位上三角矩阵, 且有A=LDU成立： 1

6、) 如果L是单位下三角矩阵, D是对角矩阵, U是单位上三角矩阵, 则称分解A=LDU为LDU分解. %为2) 如果L=LD是下三角矩阵, 而U是单位上三角矩阵, 则称三角分解A=LU克劳特(Crout)分解; %=DU是单位下三角矩阵, U%为%为上三角矩阵, 则称三角分解A=LU3) 如果U杜利特(Doolittle)分解; %-1U%, 称为不带平方根的乔累斯基(Cholesky)4) 如果A=LDU=LDD-1DU=LD分解; %, 则A=LDU=LDDU=LU%, 由于U%=L%T, 则L, DU=U5) 如果LD=%T, 称为带平方根的乔累斯基(Cholesky)分解. A=LL1

7、2121212第1页,共24页 定理1.1 n阶非奇异矩阵A可作三角分解的充要条件是Ak0(k=1,2,L,n-1),这里Ak为A的k阶顺序主子阵, 以下同. 证明 必要性. 设非奇异矩阵A有三角分解A=LU, 将其写成分块形式 AA12Lk k=A21A22L210UkL220U12 U22这里Ak, Lk和Uk分别为A, L和U的k阶顺序主子阵. 首先由A0知L0, U0, 从而Lk0,Uk0; 因此Ak=LkgUk0(k=1,2,L,n-1). 充分性. 对阶数n作数学归纳法. 当n=1时, A1=,结论成立. 设对n=k结论成立, 即Ak=LkUk, 其中Lk和Uk分别是下三角矩阵和上

8、三角矩阵. 若Ak0,则由Ak=LkUk易知Lk和Uk可逆. 现证当n=k+1时结论也成立, 事实上 AkAk+1=Trk0UkLk=T-1Tak+1,k+1rU1kk0ckL-1kck. T-1-1ak+1,k+1-rkUkLkck由归纳法原理知A可作三角分解. 01定理 1.1 给出了非奇异矩阵可作三角分解的充要条件, 由于A=不满足定10理1.1的条件, 所以它不能作三角分解. 但 100001100A=12110112011. 2上例表明对于奇异矩阵,它还能作三角分解未必要满足定理1.1的条件. 首先指出,一个方阵的三角分解不是唯一的, 从上面定义来看,杜利特分解与克劳特分解就是两种不

9、同的三角分解,其实,方阵的三角分解有无穷多, 这是因为如果D是行列式不为零的任意对角矩阵, 有 %, A=LU(CD)(D-1U)=LU%也使A的一个三角分解. 因D的任意%,U%也分别是下、上三角矩阵, 从而A=LU其中L性, 所以三角分解不唯一. 这就是A的分解式不唯一性问题, 需规范化三角分解. 定理 1.2 设A为n阶方阵,则A可以唯一地分解为 第2页,共24页 A=LDU (1.1) 的充分必要条件是A的前n-1个顺序主子式Ak0(k=1,2,L,n-1). 其中L,U分别是单位下、上三角矩阵, D是对角矩阵D=diag(d1,d2,L,dn), dk=Ak(k=1,2,L,n),

10、A0=1. Ak-1证明 充分性. 若Ak0(k=1,2,L,n-1), 则由定理1.1, 即实现一个杜利特分%, 其中L为单位下三角矩阵, U%为上三角矩阵,记 解A=LU(1)u11u12Lu1na11u22Lu2nU=OMunn()a12La1(n)(2)(2)a22La2n(n)=A, OM(n)ann11(i)因为uiiaii0(i=1,2,L,n-1). 下面分两种情况讨论： (1)(2)(n)(n)1) 若A非奇异,由式(1)有Dn=a11=A0, 所以anna22Lann=unn0, 这时 111(1)(2)(n),L,a22Lann令D=diaga11, 则D-1=diag.

11、 (n)a(1)a(2)ann1122()于是有 %=LD(D-1U%)=LDU (1.2) A=LU是A的一个LDU分解. (i)(1)(2)(n-1)2)若A奇异,则uiiaii=0,此时令D=diag(a11,a22,L,an-1,n-1,0), (1)(2)(n-1)Dn-1=diaga11,a22,L,an-1,n-1, a=(u1n,L,un-1,n), T()则 -1%UaU0Dnn-1n-1-1Un-1%UT=T0000T0-1Dn-1a=DU, 1因此不论哪种情况, 只要Ak0(k=1,2,L,n-1), 总存在一个LDU分解式(1.1), 第3页,共24页 kdk=akk=

12、Ak(k=1,2,L,n-1),A0=1. Ak-1再证这个分解是唯一的, 仍分两种情况讨论： 1) 当A非奇异时,有A0, D0, U0, L0, 所以L、D、U均非奇异. 若还存在另一个LDU分解A=L1DU11, 这里L1, U1也非奇异, 于是有 1, D LDU=L1DU11 (1.3) -1上式两端左乘以L1以及右乘以U-1和D-1, 得 -1-1-1 L1L=DU11UD, (1.4) 但式(1.4)左端是单位下三角矩阵, 右端是单位上三角矩阵, 所以都应该是单位阵, 因此 -1-1L-1L=I, DU=I, 11UD即L1=L,U1U-1=D1-1D. 由后一个等式类似地可得U

13、1U-1=I, D1-1D=I, 即有 U1=U, D1=D. 2) 若A奇异, 则式(1.3)可写成分块形式 %L1Tb1%0U%aL%0D111TT=T10001b%0U%0D1000Ta, 1%, D%, U%, L%是n-1阶单位下三角阵; U%是n-1阶上三角阵; D%是n-1阶对其中L1111角阵; a, a1, b, b1是n-1维列向量. 由此得出 %D%L11U1T%b1D1U1%D%aLDULLD11a1=T%, T%T%b1D1a1bDUbDa%, D%, U%均非奇异, 类似于前面的推理, 可得 %, D%, U%和L其中L111%=L%, D%=D%, U%=U%,

14、a=a, bT=bT. L11111必要性. 假定A有一个唯一的LDU分解, 写成分块的形式便是 第4页,共24页 xLn-10Dn-10Un-1aA n-1, (1.5) =TTannbdn0101y其中Ln-1, Dn-1, Un-1, An-1分别是L, D, U, A的n-1阶顺序主子矩阵; x, y, a, b为n-1维列向量. 由式(1.5)有下面的矩阵方程: An-1=Ln-1Dn-1Un-1, (1.6) yT=bTDn-1Un-1, (1.7) x=Ln-1Dn-1a, (1.8) ann=bTDn-1a+dn. (1.9) 否则, 若An-1=0, 则由式(1.6)有An-

15、1=Ln-1Dn-1Un-1=Dn-1=0. 于是有Ln-1Dn-1=Dn-1=0, 即Ln-1Dn-1奇异. 那么对于非其次线性方程组(1.8)有无穷多非零解, 不妨设有a, 使Ln-1Dn-1a=x, 而a=a. TT同理, 因Dn-1Un-1奇异, (Ln-1Dn-1)=Un-1Dn-1也奇异, 故有bb, 使TTTTTTUn-1Dn-1b=y, 或bDn-1Un-1=y. 取dn=ann-bDn-1a, 则有 An-1xLn-10Dn-10Un-1a, =TT0dn101yannb这与A的LDU分解的唯一性矛盾, 因此An-10. 考察n-1阶顺序主子矩阵An-1由式(1.6)写成分块

16、形式, 同样有An-2=Ln-2Dn-2Un-2. 由于Dn-10, 所以Dn-20, 可得An-2=Ln-2Dn-2Un-2=Dn-20, 从而An-20. 依此类推可得Ak0(k=1,2,L,n-1). 综上所述, 定理证明完毕. 推论 1 设A是n阶方阵, 则A可惟一进行杜利特分解的充分必要条件是A的前3n-1个顺序主子式 第5页,共24页 a11La1kAk=MM0,k=1,2,L,n-1, ak1Lakk其中L为单位上三角矩阵, 即有 1u11u12Lu1nl121uLu222nA=l31l32O OMMMO1unnllLl1n1n2n,n-1并且若A为非奇异矩阵, 则充要条件可换为

17、: A的各阶顺序主子式全不为零, 即: Ak0,k=1,2,L,n. 推论 2 n阶方阵A可惟一地进行克劳特分解 3l111u12Lu1nll1Lu21222n %=A=LUMMOOMllLl1nnn1n2的充要条件为 a11La1kAk=MM0, k=1,2,L,n-1. ak1Lakk若A为奇异矩阵, 则lnn=0, 若A为非奇异矩阵, 则充要条件也可换为 Ak0, k=1,2,L,n. 定理 1.3 设A为对称正定矩阵, 则A可惟一地分解为A=LDLT, 3其中L为下三角矩阵, D为对角矩阵, 且对角元素是L对角线元素的倒数. 即 1l11, D=OLlnn. O1lnnl11llL=2

18、122MMln1ln21l22第6页,共24页 j-1其中lij=aij-likljk/lkk, i=1,2,L,n, j=1,2,L,i. k=11.2 常用的三角分解公式 1.2.1 杜利特分解 设A为n阶方阵, 如何确定L和U这两个三角矩阵呢, 设A=LU, 其中 l11u11u12Lu1nL=l21l22u22Lu2nMMO, U= ln1ln2LlOMnnunn按矩阵的乘法, 有 min(i,j)aij=lisusj,i,j=1,2,Ln s=1k-1由于lkk=1, 所以有akj=ukj+lksusj, j=k,k+1,Ln. s=1故得 k-1ukj=akj-lksusj,j=k

19、,k+1,Ln. s=1同理 k-1lik=aik-lisuskukk, i=k+1,k+2,Ln s=1即得到三角矩阵L和U. 1.2.2 克劳特分解 设A为n阶方阵, 有分解式A=LU, 即 a11La1jLa1nMMMl111u12Lu1jLaLa=MOlOMi1ijLaini1Llii=1uj-1,jLMMMMOOan1LanjLannln1LLLlnn1当ij时, 有 第7页,共24页 u1nMuj-1,nM1 aij=likukj=likukj+lij, k=1k=1ji-1得 lij=aij-likukj, i=1,2,Ln, j=1,2,L,i; k=1j-1当ij时, 有 a

20、ij=likukj=likukj+liiuij, i=1,2,Ln, j=1,2,L,i; k=1k=1ji-1得 iuij=aij-likukj/lii, i=1,2,Ln-1, j=i+1,i+2,Ln. k=1这样即可得到三角矩阵L和U. 1.2.3 乔累斯基(Cholesky)分解 设A为对称正定矩阵, 存在一个实的非奇异下三角矩阵L, 且L的对角元素为正时, 有惟一的分解式 A=LLT. 即 a11l11l11Llj1Lln1MOMOOMMai1Laii=li1LliiljjLlnj, MMOMMOOMaLaLalLlLllnnninnninnn1n1当ij时, 有 j-1aij=l

21、ikljk=likljk+lijljj, 也即lij=aij-likljk/ljj, ij. k=1k=1k=1jj-1特别地, 当i=j时, 有 2lij=aii-lik,i=1,2,L,n. k=1i-1例 1.1 求矩阵 第8页,共24页 52-421-2A=-4-25010的LDU分解和Doolittle分解. 解 对A作矩阵 01 02计算 对A(1)作矩阵 计算 对A(2)作矩阵 1122L=51-1-511, 所以4-01L1=405-500010052-4001-2L-1A=551129=A(1) 0-550010211L012=, L-1012=0-2102101020-50

22、52-401L-1(1)05-251=A(2)2A= 0012002-3第9页,共24页 101 1 110101, L-1=, L3=3001001000100-21计算 52-4012-1(3)-1(2)L3A=55=A 12-7令 1215L=L1L2L3= 4-21-50521可得A的Doolittle分解为A=LA(3), A的LDU分解为 2451-05511-25A=L5. 112-71例 1.2 求三阶方阵 2-13A=121 243的LU分解与LDU分解. 解 因为 2-1=50, A3=A=50 A1=20, A2=12所以A有唯一的LU分解和LDU分解. 且 第10页,共

23、24页 312-1(1)-1L1=0.51LA=00.25-0.5=A, 1010150由A(1)可计算L2及A(2)如下: 312-1(2)-1(1)L2=01LA=02.5-0.5=A, 2000211于是 1L=L1L2=0.51 121因此A的LU分解为 312-1A=0.5100.25-0.5 121001且A的LDU分解为 121-0.51.5A=0.512.51-0.2 121111a1a12例 1.3 已知范德蒙(Vandermonde)矩阵V=Ma1n-2an-11的三角分解. 11a2a22Ma3a32MLLLa2n-2a3n-2La2n-1a3n-1L1an2an, 求V

24、Mann-2n-1an解 由于范德蒙矩阵V满足定理1.2的条件, 于是有唯一的三角分解: V=LU, 结合范德蒙矩阵的特点, 先对范德蒙矩阵V进行一系列初等行变换. 用n阶矩阵 第11页,共24页 1-a1-1L1=左乘范德蒙矩阵V得, 1-a11OO-a11-a1 1111a2-a1a3-a100a2(a2-a1)a3(a3-a1)-1MML1V=Mn-40a2(a2-a1)a3n-4(a3-a1)n-3n-30a2(a2-a1)a3(a3-a1)0an-2(a-a)an-2(a-a)221331记 LLLLLLan-a1an(an-a1)M n-4an(an-a1)n-3an(an-a1)

25、n-2an(a3-a1)1101-a21-1L2=OO-a2则 1-a2 1111a3-a10a2-a100(a3-a2)(a3-a1)-1-1L2L1V=MMM00a3n-4(a3-a2)(a3-a1)n-300a(a3-a2)(a3-a1)3一般地,记 LLLMLLan-a1(an-a2)(an-a1) Mn-4an(an-a2)(an-a1)n-3an(an-a2)(an-a1)1第12页,共24页 1O1-ak-1Lk=1,k=1,2,L,n-1. -ak1OO-ak1-ak1L-1kd 左上角是k阶单位矩阵. 依次相乘有 111L1a2-a1a3-a1Lan-1-a12(2a3-aj

26、)L(2an-1-aj)an-aj)j=1j=1(j=1L-1LL-1-1n-12L1V=U=OLn-2(an-1-aj)j=1从而 V=L1L2LLn-1U, 其中 1O1 Lak1k=a2kak1, k=1,2,L,n-1. (1.10) LOOOLLLak1an-kkan-k-1kLa2kak1在对U进行一系列初等列变换. 记 第13页,共24页 1an-a1Ln-2(an-aj)j=1n-1(a)n-ajj=11-1-1L-1-111-1U1= O11D-1=diag1,11,11a2-a1a3-a,L,1a n-a1有 100L0011L11a3-a2Lan-1-a2an-a2UU-

27、1OLL1D-11=n-2(an-1-aj)j=1n-2(a)n-ajj=1n-1(an-aj)j=1一般地,记 1OU-11-11L-k=O 117k个8D-161k=diag1,1,L1,a,11k+1-aka,L,k+2-akan-ak 所以 1O111LD1kUk=ak+1-ak, k=1,2,L,n-1. (1.11) ak+2-akOan-ak第14页,共24页 于是 V=L1L2LLn-1(Dn-1Un-1)L(DU11). 其中Lk由式(1.10)给出, 为下三角矩阵. 而DkUk由式(1.11)给出, 为稀疏上三角矩阵. 2 矩阵的满秩分解 2.1 矩阵的满秩分解基本概念与定

28、理 定义2.1 若矩阵A的行(列)向量线性无关, 则称A为行(列)满秩矩阵. 4定义2.2 设A是秩为r的mn矩阵, 若存在mr列满秩矩阵F和rn行2满秩矩阵G, 使得 A=FG 则称式为矩阵A的满秩分解. 定义2.32 设H是mn的矩阵, rank(H)=r, 满足 1)H的前r行中每一行至少含有一个非零元素, 且每行第一个非零元素是1, 而后m-r行元素均为0; 2)设H中的第i行的第一个非零元素1位于第ji(i=1,2,L,r)列, 有j1j2L0. 则可通过初等变换将A化为阶梯形矩阵B, 即 GAB=, GPrn且秩(G)=r. 0行于是存在有限个m阶初等矩阵的乘积P, 使得 GPA=

29、B= 或者 A=P-1B. 0于是 GA=P-1B=P-1 0将P-1作相应的分块, P-1=(FS), FPmn, SP则有 m(n-r). A=PB=(F-1GS)=FG+S0=FG. 0其中F为列满秩矩阵,G为行满秩矩阵. 由于初等行变换有三种变换：1、调换两行;2、某一行乘以一个非零常数;3、某一行乘以一个非零常数加到另一行. 实际上只用第三种初等变换方法就可以将其化为阶第16页,共24页 梯形. 值得指出的是, A的满秩分解式为(2.1)与(2.2)并不是惟一的. 现对任一r阶可逆方阵H, 总有 % (2.3) A=FG=(FH)(H-1G)=FG%分别为mr列满秩矩阵与rn行满秩矩

30、阵. 因而(2.3)式也是A的一个%, G成立, 且F满秩分解式. 定理2.33 设ACrrr, 且 % A=BC=BC均为A的满秩分解, 则 1) 存在矩阵QCrrr, 使得 %. %, C=Q-1CB=BQ2) CH(CC)(BB)H-1H-1%HCC%HB=CH()(-1%HB%B)-1%H. B定理2.42 设A是mn的矩阵, rank(H)=r0, 其Hermite标准型为H, 则在A的满秩分解中, 可取F为由A的j1, j2, L, jr列构成的mr的矩阵, G为H的前r行构成的rn的矩阵. 定理2.5 矩阵满秩分解的存在性定理 1n1) 设ACm(r0), 则使用初等行变换可将A

31、化为Hermite标准型; rn2) 设ACm(r0), 则存在FCrmr和GCrrn, 使得A=FG. r12-3例 2.1 已知A是一个23矩阵, 则A的秩为1, 且它的满秩分解为 24-61A=FG=(12-3) 2显然, 分块矩阵 Er00Er=(Er000) 第17页,共24页 1332例 2.2 求矩阵A=2695的满秩分解. -1-330解 由题可知, rank(A)=20, 由定理2.4 可得 133213321332r3-2r2r1-r2Gr2-2r1A00310031，其中G= r3+r10003100620000100100100100P=E3E2E1=010010-21

32、0=-210 0-201010011-21100则P-1=210对单位下三角矩阵求逆矩阵等于把严格下三角部分元素变号即可. -12110101332取P-1的前两列构成F=21, 则A=FG=21. -12-1200311-111-11-1-1的满秩分解. 例2.3 求矩阵-1-11111-1-11-1111000-11-1-101-1-1行=B, rank(B)=2且B中的第1解 A=-1-111000011-1-100001-1-111000 列和第2列为单位矩阵的前两列, 故A=-1-101-1-111 3 矩阵的QR分解 3.1矩阵的QR分解基本概念与定理 第18页,共24页 定义3.

33、15 设uRn是单位列向量,即uTu=1, 称矩阵 H=I-2uuH 为Householder矩阵. 由Householder矩阵确定的Rn上的现线性变换y=Hx称为Household变换er. 若u不是单位向量, 则定义H=I-2u22uuT为Householder矩阵, 对应的变换成为Householder变换. Householder矩阵具有如下性质: 1)HT=H; 2)HTH=E; 3)H2=E; 4)H-1=H; E5)r00是n+1阶Householder矩阵; H6)H=-1. 定义3.2 如果实非奇异矩阵A能够转化成正交矩阵Q与实非5奇异上三角矩阵R的乘积, 即 A=QR, 则称上式为A的QR分解. 定理 3.1 任何实的非奇异n阶矩阵A可分解为正交矩阵Q和上三角矩阵R的乘5积,且除去相差一个对角线元素之绝对值全等于一定对角矩阵因子D外, 分解式A=QR是惟一的. 定理3.2 设A为mn复矩阵(mn), 且n个列向量线性无关, 则A有分解式 3A=UR