浅谈矩阵的LU分解和QR分解及其应用

1浅谈矩阵的LU分解和QR分解及其应用基于理论研究和计算的需要，往往有必要把矩阵分解为具有某种特性的矩阵之积，这就是我们所说的矩阵分解.本文将介绍两种常用的矩阵分解方法，以及其在解线性方程组及求矩阵特征值中的应用.1.矩阵的LU分解及其在解线性方程组中的应用1.1高斯消元法通过学习，我们了解到利用Gauss消去法及其一些变形是解决低阶稠密矩阵方程组的有效方法.并且近些年来利用此类方法求具有较大型稀疏矩阵也取得了较大进展.下面我们就通过介绍Gauss消去法，从而引出矩阵的LU分解及讨论其对解线性方程组的优越性.首先通过一个例子引入：例1,解方程组(1.1)(1. 2)(1.3)解.1Step(1.1)(2)(1.3)消去(1.3)中未知数,得到23411xx(1.4)2Shep.(1.2)(1.4)消去(1.4)中的未知数2x有12323364526xxxxxx显然方程组的解为*x 123上述过程相当于1116041522111116041504111116041500262（）+()iir表示矩阵的行2由此看出，消去法的基本思想是：用逐次消去未知数的方法把原方程化为与其等价的三角方程组.下面介绍解一般n阶线性方程组的Gauss消去法.设111nn1nnaaaaA1n  xXx1nbbb则n阶线性方程组AXb(1.5)并且A为非奇异矩阵.通过归纳法可以将AXb化为与其等价的三角形方程，事实上：及方程(1.5)为11AXb,其中1AA1bb(1)设(1)110a，首先对行计算乘数11i1111iamm.用1im乘(1.5)的第一个方程加到第2,3,,iin个方程上.消去方程(1.5)的第2个方程直到第n个方程的未知数1x.得到与(1.5)等价的方程组11n12n111nn0aaxxa112nbb简记作22Ab(1.6)其中211211111ijijiijiiiambbmaab(2)一般第11kkn次消去，设第1k步计算完成.即等价于kkAXb(1.7)且消去未知数121,,,kxxx.其中1111112122222kkkkkkknknknnannaaaaaAaaaa3设()0kkka计算(i=/1,,)kkikikkkaakmn,用(1,,)anikikkkkiknam消去第1k个方程直到第n个方程的未知数kx.得到与(1.7)等价的方程组1k1kAXb故由数学归纳法知，最后可以把原方程化成一个与原方程等价的三角方程组.但是以上分析明显存在一个问题，即使A非奇异也无法保证0iiia,需要把非奇异的条件加强.引理1约化主元素01,,)iiiak（i的充要条件是矩阵A的顺序主子式0iD.即1111110,0ikkkkkaaDaaDa证明利用数学归纳法证明引理的充分性.显然，当1k时引理的充分性是成立的，现在假设引理对1k是成立的，求证引理对k亦成立.有归纳法，设01,21iiiiak于是可用Gauss消去法将中，即11111121n22222n1kkkkkkkknnknnaaaaaAaaaaA即111212311122112231122332220aaDaDaaaaa11111122212222k11122kkkkkkkkaaaaaaDaaa(1.8)由设0(1,,)iiDk及式(1.8)有0kkka4显然，由假设01,2iiiika，利用(1.8)亦可以推出0(1,,)iiDk从而由此前的分析易得；定理1如果n阶矩阵A的所有顺序主子式均不为零，则可通过Gauss消去法（不进行交换两行的初等变换），将方程组(1.5)约化成上三角方程组，即1111111121122222222bbbnnnnnnnnaaaxxaaxa(1.9)1.2矩阵LU分解从而由以上讨论即能引出矩阵的LU分解，通过高等代数我们得知对A施行行初等变换相当于用初等矩阵左乘A，即121211LALbAb其中211n11101Lmm一般第k步消元，，相当于11kkkkkkLAALbb重复这一过程，最后得到11211121nnnnAbLLLALLLb(1.10)其中k1,111m1nkkkmL将上三角形矩阵nAU记作,由式(1.9)得到111121=UnALLLLU,其中5211111211211m1nnnmLLmLL由以上分析得；定理2（LU分解）设A为n阶矩阵，如果A的顺序主子式i0(1,2,,1)Din.则A可分解为一个单位下三角矩阵L和一个上三角矩阵U的乘积，且这种分解是唯一的.证明由先前的分析得出存在性是显然的，即ALU.下证唯一性,设ALUCD其中L,C为单位下三角矩阵，U,D为上三角矩阵.由于1D11DCLU上式右端为上三角矩阵，左端为单位下三角矩阵，从而上式两端都必须等于单位矩阵，故UD,LC.证毕.例2对于例子1系数矩阵矩阵111041221A由Gauss消去法，得结合例1，故100111010041211002ALU对于一般的非奇异矩阵，我们可以利用初等排列矩阵kkiI(由交换单位矩阵I的第k行与第ki行得到)，即111212111111,,kkkkkkikikkiikALbLIAIbLIAIbALb(1.11)利用(1.11)得1111,11nnnniiLILUIAA.简记做.其中下面就n情况来考察一下矩阵.4321444343544332211443443243)(iiiiiiiiiiILILILIAILIILIIAALLI4324324321432()iiiiiiIIILIII43214321 )(iiiiIIIIA6从而记从而容易的为单位下三角矩阵,总结以上讨论可得如下定理.定理3如果A非奇异矩阵，则存在排列矩阵P使PALU其中L为单位下三角矩阵，U为上三角矩阵.1.3矩阵LU分解的应用以上对非奇异矩阵A的LU分解进行了全面的讨论，一下我们就简单介绍一下应用.对于矩阵A一旦实现了LU分解，则解线性方程的问题,便可以等价于：(1)Lyb求y(2)=Uxy,求x(1.12)即，设A为非奇异矩阵，且有分解式ALU，其中L为单位下三角矩阵，U为上三角矩阵。即A111122212212111nnnnnnuuuulullu(1.13)下面说明L,的元素可以由n步直接计算出：由(1.13)有11iiau(1.14)再由矩阵乘法得1111iiaul,故有11iila/11u于是得U的第一列元素.7设已经得U的第一行到1r行元素与L的第一列到1r列元素，由(1.13)有111nrrirkkirkkirikklluuua故有11rririrkkikauul(i)(1.15)再由(1.13)得111irikkrikkrnrkkirrralulluu.得11()/iririkkrrrkralulu(1.16)故有以上分析结合(1.12)得；111ii1ikikkyylybb1//nnnniiikkniiikxxbuxyuu(1.18)例3．求解123123142521831520xxx解.由(1.15)，(1.16)计算，得1001232100143510024ALU求解141820Ly得141072y求解141072Ux得123x8以上便是通过介绍Gauss消去法，引出矩阵的LU分解，这种分解在数值分析中，在设计算法求解高维线性方程组能提高效率，不像Grammar法则只是从理论上解决了非奇异线性方程组的解法，实际操作起来是十分不方便的，而利用LU分解的基本原理能大大减少计算过程的繁琐.2．矩阵的QR分解及其在计算矩阵特征值的应用2.1转化非奇异矩阵为上Hessebberg定义1一方阵，如果1ij时有0ijb.则称矩阵B为上Hessebberg阵，即111212122232,10000bbnnnnnnbbbbbbbB定义2设向量w满足2w,矩阵2THIww称为初等反射矩阵，记作Hw,即21112222122n121222212122nnn其中定理2.1初等反射阵H是对称矩阵，正交矩阵和合同矩阵.定理2.2设,xy为两个不相等的n维向量，但22xy,则存在一个初等反射矩阵H，使Hxy.证明令2()/wxyxy,则得到一个初等反射矩阵2222/TTTHxxyIIywyxw而且92TT22222/TTHxxxyyxxxxxxxyxyxyy因为22(()2)()TTTxyxyyxyxxx所以()Hxxxyy.并且由代数学知识易知，2()/ywxyx.成立的唯一长度等于1的向量.推论设向量0nxRx,2σx,且1σxe则存在一个初等反射矩阵212,/2ITTHIuuuuu使1σeHx,其中1σuex,22/2u设123,,,,nx12,,,nuuuu,则12n(σ,,,)u，212/2σσu.如果σ，那么计算1σ时有效数字可能损失，取有相同符号，即取12σsgnx有了以上关于初等反射矩阵的性质接下来讨论正交相似约化一般矩阵和对角矩阵.设11112122122111211212212nnnnnnAaaaaaaaAaAaaa,不妨设1210a，否则这一步不需约化，选择初等矩阵1R使1R121a，其中122121121121112111121211111σsgn(),σ,1,.σσ2niiTaaIaaueuRuu(2.1)令11100UR则21221311211121121112112231211221220AaARaAAAUARaRARaU，10其中22111AR,