4.4householder

4.4Householder方法Householder方法是计算实对称矩阵A的全部特征值以及特征向量的方法。计算过程是先用反射矩阵做正交相似变换约化一般实矩阵A为hessenberg矩阵，或利用反射矩阵作正交相似变换约化矩阵A为对三角矩阵，使求原矩阵特征值以及相应特征向量问题转化为求hessenberg矩阵或对称矩阵的特征值问题。2222,,,,2nTnxyRxyxyUUHIUHxyUxy设两个不相等的维向量但则存在householder阵使，其中定理。yWxxy复习例2：已知矩阵,112240130A利用Householder变换求A的QR分解因为,2,0,01T记,2211a令21111111eaeaT1,0,121则HIH1112,001010100从而1302402121AH记,3,4T则,5222b令22222221ebeb,3,1101THIH2222~,433451记,430340001~00122HHT则RAHH20015021212取0053404305121HHQ则QRA定义4.4为则称时有，若当一方阵BbjiBij,01.阵阵，对称阵化为上对角交相似变换化为上一般实矩阵都可通过正Hessenberg方法：利用Householder阵，初等反射阵（镜面反射）.1112121222,1...............nnnnnnbbbbbbHessenbergBbb，即4.4.1一般矩实阵约化为hessenberg阵1112112122211121112212nnnnnnaaaaaaaAAAcAaaa设利用Householder阵约化为hessenberg阵设：121311(,....)0Tncaaa，否则就不需要约化了于是选择反射矩阵11111,,RRce使11111TRIuu其中12212112111121111212sgn12niiaauceua其中11112121111111221aARAUAURcRAR1110,0UR令则2211121222122(2)(2)22212112222............0...0nnnnnaaaaaaaAAcA(2)(2)(2)232422(,...)Tncaaa2(2)(2)22nnAR1112111211,11212222,121,1,1,1,11,,1.......................................kkkkkkkkknkkkkknkkkkkkkkknkkkkkkkknkkknknknnAUAUaaaaaaaaaaaaaaaaaa假设前k-1步约化已完成，第k步约化1211220kkkkAAcA10,RkkkkkcRce，可初等反射矩使得1221,1121,21()12nkkkkkikikkkkkkkkkkkTkkkkkksignaauceuaRIuuIOuOR令12(1)11221112111122kkkkkTkkkkkkkkkkkARAAUAUORcRARAAOcA(1)22221112112122(1)323311..........................nTnnnTTnnnnnnnAUAUUUAUUaaAaa重复上述程最后有：为hessenberg阵22112,.....UUUUUTTnnnAH使,,U,U21，则存在初等反射阵如果nnRA定理4.8其中H为hessenberg矩阵12,...,Ukk由于，都是正交的(1)(2)(1)~~...~nAAA故求矩阵A的特征值转化为求H的特征值记221...UUnPU,TTTPAPHAPPH,,TTTTHyyPHyPyAPyPyTPy为对应特征值的特征向量。设y是H对应的特征向量4.4.2是对称矩阵的三对角化反射为对称阵，则存在初等如果nnRA定理4.9(2)111222111..................12n-2n-2112n-2U,U,,U,UUUUUnnnnnnAAcbbcbCbcbbc使4.4.3求三对角矩阵特征值的二分法•设实对称三对角矩阵为111222111.........nnnnnabbabCbabba111211...()......kkkkabbapbba其特征矩阵为记的第k阶主子式为CI()kp设0()1p可得递推式011212()1()....()()()()kkkkkppapapbp定理1｛pi(λ)｝(i=1,2,…，n)的根都是实根.证pi(λ)是i阶实对称矩阵的特征多项式，因此，｛pi(λ)｝(i=1,2,…，n)的根全是实根.定理2设α是pi(λ)的一个根，那么①pi-1(α)pi+1(α)≠0，即相邻的两个多项式无公共根；②pi-1(α)pi+1(α)0，即pi-1(α)与pi+1(α)反号.定理3pi(λ)的根都是单根，并且将pi+1(λ)的根严格隔离.lim()0,iplim()0,lim()0,iipp当i为奇数当i为偶数定理5•定义1设p0(λ)≡1，｛pk(λ)｝(k=1,2,…，n)称相邻的两个数中符号一致的数目为同号数，记为S(λ).若某个pk(λ)=0，规定与pk-1(λ)同号.•定理6设两个实数xy，那么，形如实对称三对角矩阵C的特征多项式在区间(x,y]上根的数目为S(x)-S(y).4.4.4三对角矩阵特征向量的计算求出对称三对角矩阵C的某一特征值后，在用反幂法求矩阵AI的按模最小的特征值0和相应的特征向量y则有0()CIyy即0)Cyy（由此可见，y是矩阵C的相应的于的特征向量并可以得到的更精确的特征值0由于三对角矩阵C是对称矩阵A经过正交相似变换得到的，即存在正交矩阵Q使得T=QAQC故矩阵C与矩阵A有相同的特征值，如果y是矩阵C的相应与的特征向量，则x=Qy便是A的相应于的特征向量AxAQyQCyQyy当用household变换将矩阵A约化C时，由定理4.9有2......n-2112n-2HHHHHTnACAQAQ这里...12n-2Q=HHH为正交矩阵kH具有TIww所以向量x=Qy的计算可以通过()()TTIwwyywyw