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

《浅谈矩阵的LU分解和QR分解及其应用.docx》由会员分享，可在线阅读，更多相关《浅谈矩阵的LU分解和QR分解及其应用.docx（14页珍藏版）》请在三一办公上搜索。

1、浅谈矩阵的2分解和。/?分解及其应用基于理论研究和计算的需要，往往有必要把矩阵分解为具有某种特性的矩阵之积，这就是我们所说的矩阵分解.本文将介绍两种常用的矩阵分解方法，以及其在解线性方程组及求矩阵特征值中的应用.1 .矩阵的LU分解及其在解线性方程组中的应用1.1 高斯消元法通过学习，我们了解到利用Gazs消去法及其一些变形是解决低阶稠密矩阵方程组的有效方法.并且近些年来利用此类方法求具有较大型稀疏矩阵也取得了较大进展.下面我们就通过介绍Gauss消去法，从而引出矩阵的LU分解及讨论其对解线性方程组的优越性.首先通过一个例子引入：(1) 1)例1,解方程组(1.2)(13)解.Step(1.1

2、)(-2)+(1.3)消去(1.3)中未知数,得到Shepl.(1.2)+(1.4)消去(1.4)中的未知数显然方程组的解为X* =上述过程相当于x1+x2+X3=6有，4x2-x3=56)( 5-0J10-2x3=-6(1104-1、2-21(-2) +&表示矩阵的i行)由此看出，消去法的根本思想是：用逐次消去未知数的方法把原方程化为与其等价的三角方程组.下面介绍解一般阶线性方程组的Gauss消去法.那么阶线性方程组并且A为非奇异矩阵.通过归纳法可以将4X=力化为与其等价的三角形方程，事实上:及方程(1.5)为AX=b，其中(1)设嫌)0,首先对行计算乘数叫=绘.用-外乘(1.5)的第一个方

3、程加到第i(i=2,3,个方程上.消去方程(L5)的第2个方程直到第个方程的未知数士.得到与(1.5)等价的方程组I 0W)、简记作其中4，)=砂一班碎W)=b，-%甘)(2)一般第攵(1攵-1)次消去，设第2-1步计算完成.即等价于且消去未知数百与，工5其中A0=设 O计算mjk =成）/或）（i= + 1,.,），用 tnik =Z + 1,消去第Z + 1个方程直到第个方程的未知数乙.得到与(1.7)等价的方程组AawX=卢W故由数学归纳法知，最后可以把原方程化成一个与原方程等价的三角方程组.但是以上分析明显存在一个问题，即使A非奇异也无法保证力)0,需要把非奇异的条件加强.引理1约化主

4、元素400(1=1,.)的充要条件是矩阵A的顺序主子式Di0.即证明利用数学归纳法证明引理的充分性.显然，当A=I时引理的充分性是成立的，现在假设引理对4-1是成立的，求证引理对我亦成立.有归纳法，设碍0(i=12.Z7)于是可用GcMS消去法将中，即即由设。0(i=l,幻及式(1.8)有成Zo显然，由假设砚0(i=l,2利用(1.8)亦可以推出。0(i=L.,Q从而由此前的分析易得；定理1如果阶矩阵A的所有顺序主子式均不为零，那么可通过GGS消去法(不进行交换两行的初等变换)，将方程组(1.5)约化成上三角方程组，即1.2 矩阵LU分解从而由以上讨论即能引出矩阵的LU分解，通过高等代数我们得

5、知对A施行行初等变换相当于用初等矩阵左乘A,即ZIH)=A()=/?(2)其中一般第攵步消元,，相当于重复这一过程，最后得到其中将上三角形矩阵A记作U,由式(1.9)得到A=AZ；.LU=LU,其中由以上分析得；定理2(LU分解)设A为阶矩阵，如果A的顺序主子式。尸0(，=1,2,-1).那么A可分解为一个单位下三角矩阵L和一个上三角矩阵U的乘积，且这种分解是唯一的.证明由先前的分析得出存在性是显然的，即A=LU.下证唯一性,设A=LU=8其中L,C为单位下三角矩阵，U,。为上三角矩阵.由于OTLTC=UZ尸上式右端为上三角矩阵，左端为单位下三角矩阵，从而上式两端都必须等于单位矩阵，故U=O,

6、L=C.证毕.111、例2对于例子1系数矩阵矩阵A=04-1由G3ss消去法，得7-2结合例1,故对于一般的非奇异矩阵，我们可以利用初等排列矩阵几(由交换单位矩阵/的第4行与第C行得到)，即利用(LIl)得L-J*z%A=A=U.简记做.其中下面就情况来考察一下矩阵.从而记从而容易的为单位下三角矩阵,总结以上讨论可得如下定理.定理3如果A非奇异矩阵，那么存在排列矩阵P使RA=LU其中L为单位下三角矩阵,U为上三角矩阵.1.3 矩阵LU分解的应用以上对非奇异矩阵A的LU分解进行了全面的讨论，一下我们就简单介绍一下应用.对于矩阵A一旦实现了LU分解，那么解线性方程的问题,便可以等价于：(1)Ly=

7、b求)，(2)Ur=y,求X(1.12)即，设A为非奇异矩阵，且有分解式A=LU,其中L为单位下三角矩阵，U为上三角矩阵。下面说明L的元素可以由步直接计算出:由(1.13)有再由矩阵乘法得见故有于是得U的第一列元素.设已经得U的第一行到r-1行元素与L的第一列到列元素，由(1.13)有故有1(1.15)”外,M,*=1再由(1.13)得M=IiMkr=lr+lirurr故有以上分析结合(1.12)得;例3.求解252X2=18解.由(1.15),(1.16)计算，得求解Ly=18得y=-10求解UX=-10得X=2l-72 Jl-72J以上便是通过介绍GaZS消去法，引出矩阵的LU分解，这种分

8、解在数值分析中，在设计算法求解高维线性方程组能提高效率，不像Gm制法那么只是从理论上解决了非奇异线性方程组的解法，实际操作起来是十分不方便的，而利用LU分解的根本原理能大大减少计算过程的繁琐.2.矩阵的QR分解及其在计算矩阵特征值的应用2.1 转化非奇异矩阵为上Hessebberg定义1一方阵，如果i+l时有=0.那么称矩阵3为上/essM%zg阵，即定义2设向量W满足IM2,矩阵H=2vv称为初等反射矩阵，记作”(w),即”（W）=其中1-2卬；-2W1W2.-2小吗、-2vv2W11-2域.-2w2wnk-2WnW1-l-2vr定理2.1初等反射阵”是对称矩阵，正交矩阵和合同矩阵.定理2.

9、2设x,y为两个不相等的维向量，但2=|)1，那么存在一个初等反射矩阵H,使Hr=y.证明令卬=(工-)/卜-刈2,那么得到一个初等反射矩阵而且以=x-2(x-y)IIy(X7一力=%-2(AyxXTTX)/卜一玳2因为所以=(x-y)=y并且由代数学知识易知，W=(X-月/卜-乂心成立的唯一长度等于1的向量.推论设向量r(o),0=M2，且-四那么存在一个初等反射矩阵H-I-2uu,w2=I一夕一，,使=-g,其中=x+o,p-u/2设x=（al,2,a3,.,azl）w=（wph2,.,h,j）,那么w=（l+,a2,.,an）,P=Mt2=o（+J.如果。，那么计算时有效数字可能损失，取

10、有相同符号，即取有了以上关于初等反射矩阵的性质接下来讨论正交相似约化一般矩阵和对角矩阵.设aa2anA_出1。22,。2niznn/不妨设否那么这一步不需约化，选择初等矩阵凡使RlM）,其中nL=sgn（%）（Zd）2,i=2场=制，+54，（2D1 II28=那$2=6（必+。21），RI=（10、令UHoRJ那么（碉.用【。卷幽J其中4甲RH一直重复这一过程得；定理2.1如果A=RnXn,那么存在初等反射矩阵,使4.2U_2=C（上Hessenberg）.推论A为对称矩阵，那么存在初等反射矩阵其中4小为2.2矩阵的QR分解有了以上的讨论我们知道任何一个方阵A都可以正交相似化为Hessenb

11、erg或更为特殊的对称三角矩阵，接下来便要使用矩阵的。R（。为正交矩阵，R为三角矩阵）分解来解决Hessenberg阵和对称角矩阵的全部特征值问题.引理1设,其中区,勺不全为零，那么可选取一平面矩阵与使尾X=y=(,%，城,壮,)丁，其中靖=；十名(2.2)证明事实上EN只改变X的第，个及第/个元素，且有靖=cai+saj,于是可选Pij即按式(2.4)求Gs，且有式(2.2)及(2.3).定理2.4如果A为非奇异矩阵，那么即存在平面旋转矩阵生.上一(一系列平面旋转矩阵)使且%0(i=l,2,.,-1).证明由于A第一列一定存在町工0,于是，如果旬。O(j=2,3,)，应用引理1,即存在平面旋

12、转矩阵匕,品，胃，使且记此./%=,同理重复上述过程，最后得到：存在正交矩阵匕,勺T使式(2.5)成立.定理2.5(矩阵的。R分解)如果阶方阵A为非奇异矩阵，那么A可分解为一正交矩阵。与一上三角矩阵R,且当R对角元素都为正数时分解唯一.证明由定理2.4知，存在正交矩阵6,Kt,使为上三角阵，记于是式(2.6)为0A,即A=QH,其中Q=于考以为正交矩阵.现证明唯一性.设有A=QIRl=Q2R2,其中飞，鸟为上三角矩阵(显然为非奇异矩阵)且对角元素都为正Q,0为正交矩阵于是由式(2.7)知上三角阵&R为正交矩阵，故&R为对角矩阵，即因为此父是正交矩阵,所以。2=/,又因为凡，R?对角元素都为正数

13、，故40(i=l,2,77),即。=/于是用=&,由式(2.6)得到。=Q.2.3矩阵特征值0R算法理论依据设A=A=(%)w/T”非奇异,且对A直接QR分解，即A=QR,其中R为上三角矩阵，Q为正交矩阵，于是得到一个新矩阵B=RQ=QZQ.显然，B是由A经过正交相似变换得到,因此A和8有相同的的特征值,在对B进行QR分解，又可得到一新矩阵,重复可得矩阵序列.设A=4，进行QR分解,得A=Q内，作矩阵A2=/?.0,=QrAQ,求得AK后将其进行QR分解,得A=04,作矩阵A+l=RAQk=QlAkQk而利用QR分解求矩阵的特征值,就是利用矩阵QR分解,按上述递推法那么构造矩阵序列A的过程,只

14、要A非奇异,利用上述方法就能构造出A.定理2.6(根本的Q?方法)设A=A=(4)Ri非奇异，QR根本方法为：且记二QIQ&,那么有；a: AN相似与A即A+=QXqb：4+=(1.Q尸A(QLQA)C：Ak的QR分解式为Ak证明a：Az=RkQk=QlAkQkb:C：显然，k=l时有A，设AI有分解式，于是=A.结合定理2.5,可以得出&讨可由4按下述方法求得.(1)左变换ElK-264=%(上三角阵)右变换RkP：P；以=A+引理2设M/,其中以，凡为具有正对角元素的上三角矩阵，如果(Ae),那么0/,及&证明设RtkRk=M：Mk/(火8),记Rk=(4),矩阵R；Rk,檎,因此有产(2

15、.8)利用式(2.8)的结果，那么有欧,，O(Zf8)对于R：Rk其他行同理可得,故&.,且易知有/(A，因此Qk=MkRFfMks).定理2.7设A=(%)wT如果A的特征值满足：；A有标准型A=XDXT其中()，且设XT有三角分解(L为单位下三角矩阵，U为单位上三角矩阵)，那么有QR算法产生4本质上收敛于上三角阵，即这个定理证明过程比拟繁琐，具体证明内容参考文献2,这里需要说明在证明过程中4的收敛速度依赖,=Av1,当匚越小时,收敛越快.推论2.1如果A是对称矩阵满足定理2.7条件,那么由QR方法产生A本质上收敛于对角矩阵.不管是上三角矩阵，还是对角矩阵，其特征值得计算是很方便的，注意到对

16、角矩阵或上三角矩阵是极限形式，故在给定的误差范围内，计算满足定理2.7的矩阵特征值是比拟容易的.以上对于理论知识的解释完毕，接下来看一下如何具体在应用这一原理计算矩阵特征值.2.3矩阵特征值OR算法实际操作在定理2.7的证明中，我们发现4?(Ze)速度很大程度依赖于比值rn=nn,当匚很小时，收敛很快.如果S为乙一个估计，且对A-S/应用QR方法，收敛速度恰当，收敛速度会更快.由于QR计算矩阵特征值是一种利用极限近似的方法，故如果A收敛的越快，计算将会更方便.为此，为了加速收敛，选择数列%,按照下述方法构造矩阵序列4.ShepX设A=A=(%)w/T”Shepl将进行QR分解，即=;Shep3

17、构造新矩阵Aa+1=RkQk+skI=AkQk;Shep4Ajt+1,其中；Shep5矩阵(A-5iZ)(A-S2I).(ATj)=（八）有QR分解式(4);Shep6结合定理2.5的结论：首先利用正交变换(左变换)将4化为上三角阵，即其中为一系列平面旋转矩阵的乘积.于是有前面的讨论我们知道任何一个方阵都可以正交相似化为一个上Hessenberg矩阵，而有正交过程中矩阵特征值不变性质，故下面我们只考虑HeSSe戾吆矩阵的特质值得计算.设A=A为上Hessenbergg结合(2.1)的具体Pi的构造方法shep6,构造出上“esse戾吆矩阵序列A,在构造的过程中对卜力的选择也是十分重要的，一般选

18、取Sk=4?.具体方法我们看下面这个例题的解决.例2.1用0R方法计算对称三角矩阵的全部特征值解首先选取心结合2.1的方法构造旋转平面重复以上的操作记现在收缩，继续对As的子矩阵进行变换，得到s51故求得A近似特征值为且A的实际特征值是=3.0=结束语以上便是从矩阵的两个常见分解LU,QH分解出发，进而把它们应用到解线性方程组,以及求矩阵的特征值，这种方法在解决阶数比拟高的矩阵时利用这种思想设计出相应的的算法，往往能十分有效的减缓繁重的计算过程.参考文献1王萼芳，石生明.高等代数M.北京：高等教育出版社，1978.162-2032李庆阳，王能超，易大义.数值分析W.武汉：华中科技大学出版社，1982.173-2453周金土.高等代数解题思想和方法M.杭州：浙江大学出版社，2008.96-1304徐仲，陆全，张凯院.高等代数考研教案M.西安：西北工业大学出版社，2005.155-1985郑崇友，樊磊，崔宏斌.Frame与连续格M.北京：首都师范大学出版社，19946GierzG,HoffmannKH,etal.CompendiumofContinuousLatticeM.BerlIniSpringer-Verlag,1980.7吴耀强.关于代数L-domain的一个刻画定理.江西师范大学学报(自然科学版)J.2006,30(6):573-576.