基于QR分解求解线性方程组初探

基于QR分解求解线性方程组初探摘要:本文探讨了基于QR分解求解线性方程组的方法，并通过例题进行了具体的分析。主要介绍了Schmidt正交化方法、Householder变换方法和Givens变换方法。关键词:线性方程组;QR分解；Schmidt正交化方法；Givens变换；Householder变换；线性方程组在实际问题的求解过程中经常遇到,一般情况下没有实用有效的求解方法。与现有的LU分解和一些迭代方法不同,基于实际很少采用的矩阵QR分解方法,利用其对各类矩阵普遍适用的优点提出并探讨了将QR分解运用于求解线性方程组。引理：1.对任意nnCA，若存在n阶正交矩阵Q和n阶上三角矩阵R，使得A=QR，则称QR为A的QR分解。2．若nnCA可逆，则存在正交矩阵Q和正对角元的上三角矩阵R，使得A=QR，且表示式唯一。一、Schmidt正交化方法首先，利用Schmidt正交化方法求可逆矩阵A的QR分解：设A是一个实满秩矩阵,A的n个列向量为，，，，nxxx21由于，，，，nxxx21线性无关，将它们用Schmidt正交化方法得标准正交向量neee，，，21其中0iib，i=1，2，…，n从而有nnnnnnebebebxebebxebx221122211221111nnnnnnbbbbbbeeexxx222112112121nnnnnbbbbbbReeeQ2221121121,令、然后，求解线性方程组Ax=b的解：Ax=bbQRxbQRxbQRx111例1利用Schmidt正交化方法求矩阵QR分解的方法求解线性方程组Ax=b,其中215b解：设,221,143,200321TTTxxx则321,,xxx线性无关首先将它们正交化得：再单位化：于是从而所以20121500540553100210010151020111012111bQRxIQQT则212240130A，Txy200111111222)()(yyyyxxy，，Tyx0432112222231111333)()()()(yyyyxyyyyxxy，，，，Tyyx0565851213，Tye1002111，Tye054535122Tye0535421331112eyx21212521eeyyx32132132251eeeyyyxQRA0015354054530200150212二、Givens变换方法1．定义：设实数c和s满足22sc=1，则称n阶矩阵IcsIscIscTij),(为Givens矩阵（旋转阵）。2．性质性质1i）IscTscTijTij)],([)],([.ii)),()],([)],([1scTscTscTijTijij.iii）1)],(det[scTij性质2Givens变换xTyij只改变x的第i个和第j个分量。性质3设0),,,(21Tnx,则存在有限个Givens矩阵的乘积T，使得1exTx。性质4设nRzx,（n1），且1,0zx，则存在有限个Givens矩阵的乘积T，使得zxTx。定理1设nnRA可逆，则存在有限个Givens矩阵的乘积T,使得TA为可逆上三角矩阵。首先，利用Givens矩阵求矩阵A的QR分解：先将矩阵A按列分块，①对于1存在一组Givens矩阵使得于是②将矩阵)1(1nnCB按列分块nA,,,21nnCAnTTT11312,,,121112131eTTTn2111112131,0*aBaATTTnnB321****又存在一组Givens矩阵使得因此依次进行下去，得到③令则QRA然后，求解线性方程组Ax=b的解：Ax=bbQRxbQRxbQRx111说明：利用Givens矩阵进行QR分解，需要作个初等旋转矩阵的连乘积，当n较大时，计算量较大，因此常用镜像变换来进行QR分解。例2利用Givens变换求矩阵QR分解的方法求解线性方程组Ax=b，其中504430553A25525b解对于A的第1列T4030,构造13T,其中TTsc0055453013于是可得nTTT22423,,,22222232420,,0,*,*bbTTTTn21112123200**0***CbaATTTTnnRcbaATTTTTnnnnn***21121232,1HnnHnHHnHTTTTTQ,122311221nn140430735304050403510130ATTT对于14431A的第1列431,构造12T,其中055453112Tsc于是可得5130516534435111121ATTT最后，令9201212151620015251101TTT则有51300516507359122020150121615251RTQT则QRA所以1312513733251427255252595425122512532516540531350065165103251272535111bQRx三、Househoulder变换方法1.定义：设u是实的单位列向量，称阶n矩阵TuuuIH2为Householder矩阵（初等反射矩阵），Householder变换又称为反射变换或镜像变换。2.性质：性质11det,,,,12HHHIHIHHHHTT。性质2设nRzx,（n1），且1,0zx，则存在Householder矩阵uH，使得zxxHu。性质3对任意的Givens矩阵),(scTij，都存在两个Householder矩阵uH和vH，使得vuijHHscT),(。定理2设nnRA可逆，则存在有限个Householder矩阵的乘积S，使得SA为可逆上三角矩阵。首先，利用Householder矩阵求矩阵A的QR分解如下：①将矩阵A按列分块),,,(21nA，取21121111111,aeaea则TIH111200),,,(11121111BaHHHAHn②将矩阵)1()1(1nnCB按列分块，，取则其中依次进行下去，得到第n-1个n阶的Householder矩阵1nH,使得③因为iH自逆矩阵，令则A=QR然后，求解线性方程组Ax=b的解：Ax=bbQRxbQRxbQRx111例3利用Householder变换求矩阵QR分解的方法求解线性方程组Ax=b，其中nB,,,32122221221222,bebebuTuuIH2222~22~001HHT2211200**0***)(CaaAHH)2()2(2nnCCRaaaAHHHnn***21121121nHHHQ2105112240130bA解：因为T2001,记令则从而记则令记则取则所以50421050535405453100210010151020111012111bQRx以上是为了求解线性方程组而给出的三种不同的矩阵QR分解方法。在进行分解时，所用的主要工具是镜面反射阵（Householder）和旋转阵（Givens）。相对来说，QR分解的计算量较小，但此方法不足之处在于计算精度较低。总的来说，基于QR方法来求解线性方程组是不错的选择。参考文献：[1]王钢林武哲基于QR分解求解带顶点三对角带状线性方程组，北京航空航天大学学报，,2211a21111111eaeaT1,0,121TIH1112,0010101001302402121AH,3,42T,5222b21221222ebeb,3,1101TTIH2222~,433451,5453053540001~00122HHTRAHH200150212120053404305121HHQQRA2003，（4）[2]刘玲葛福生.数值计算方法北京：科学出版社,2005.[3]刘秀梅.矩阵QR分解途径的研究[J].内江师范学院学报,2007,(4).[4]程云鹏.矩阵论[M].西安:西北工业大学出版社,1998.[5]同济大学应用数学系.高等数学(第5版)[M].北京:高等教育出版社,2002.[6]北京大学数学系几何与代数教研室.高等代数.高等教育出版社.[7]冯天祥,李世宏.矩阵的QR分解[J].西南民族学院学报,2001,(4).[8]张凯院,许仲,陆全.矩阵论[M].西安：西北工业大学出版社，2000:50-102.[9]张凯院,许仲,陆全.数值分析教程[M].西安：西北工业大学出版社，2002:142-153.[10]侯自新,郑仲三.线性代数及其应用[M].天津：南开大学出版社，1986:171-192.[11]郝炳新.高等代数[M].北京：高等教育出版社，2000:182-206.[12]杨万利.数值分析教程.北京：国防工业出版社,2002.[13]徐翠薇.计算方法引论[M].北京：高等教育出版社，1985[14]RainerKress.Numericalanalysis1998SpringerVerlagNewYork.Inc[15]MallatS,ZhangZ..MatchingPursuitwithTimefrequencyDictionaries[J]EEETransonSignalProcessing,1993,41(12):3397-3415.InquirybasedonQRdecompositiontosolvethelinearequationsAbstract:ThisarticleisbasedonQRdecompositionmethodsforsolvinglinearequationstodoalittlediscussion,andthroughexamplestoanalyse.MainlyintroducestheSchmidtorthogonalmethod,Householderme