计算方法-特征值2

1、一、基本一、基本QRQR方法方法 60年代出现的QR算法是目前计算中小型矩阵的全部特征值与特征向量的最有效方法。 实矩阵、非奇异。 理论依据：任一非奇异实矩阵都可分解成一个正交矩阵Q和一个上三角矩阵R的乘积，而且当R的对角元符号取定时，分解是唯一的。()(1)(1)11111(2)1(2)111()(1) QRQR (1,2,). , (2,3,)kkkkkkkAQ RkAR QAAQ RQARAR QQAQAAAAkAA基本方法的基本思想是利用矩阵的分解 通过迭代格式 由 即 。于是 即与 相似。同理可得，。故它们有相同的特征值。 将化成相似A的上三角阵（或分块上三角阵），从而求出矩阵 的全

2、部特征值与特征向量。 可证，在一定条件下，基本QR方法产生的矩阵序列A(k) “基本”收敛于一个Schur型阵。即主对角线及以下元素均收敛，主对角线以上元素可以不收敛。特别的，如果A是实对称阵，则A(k) “基本”收敛于对角矩阵。 基本QR方法每次迭代都需作一次QR分解与矩阵乘法，计算量大，而且收敛速度慢。因此实际使用的QR方法是先用一系列矩阵相似变换将 A 约化成拟上三角矩阵(称为上Hessenberg 矩阵)，然后对此矩阵用基本QR方法。因为拟上三角矩阵具有较多零元素，故可减少运算量。化A为相似的拟上三角阵的方法有多种。1HouseholderAHouseholderA（ ）用变换将矩阵

3、化成上海森柏格矩阵H。(2) 用变换将对称矩阵 化成对称三对角矩阵。为了求矩阵特征值先进行初等变换把矩阵变成较简单形式( )22,nx yRxyHouseholderHHxy定理 : 设为中任意非零向量 且则存在矩阵使得。22222 2, (2)2( ).2 2( ) .TTTTxywHIwwxyxyxyHxIwwxxxxyxyxyxyxxyxyxyHxy证：令于是 由 范数的定义. 代入上式得二、豪斯豪尔德(Householder)方法221122112122122212 (,)1,12222122 22212TnnnTnnnnwwwwwwwwwwww www wHIwww ww wwHou

4、seholder设向量 满足 则称为 矩阵或反射矩阵。豪斯豪尔德(Householder)变换11;(2) det()1;THHHHH 可证其具有以下性质：（ ）是实对称的正交矩阵，即 111211121222123233311(2,3, ),nnnnnnnnniihhhhhhhhHhhhhhhin称形如 的矩阵为拟上三角阵，也称为上海森堡（Hessenberg)阵。如果此对角线元全不为零 则称该矩阵为不可约的上Hessenberg矩阵。 Householder A讨论用 变换将一般矩阵 相似变换 成 Hessenberg阵.11111111,1000 01HouseholderHHH AHH

5、HHHnHouseholder首先，选取 矩阵 使得经 相似变换后的矩阵 的第一列中有尽可能多的零元素。为此，应取 为如下形式其中为阶 矩阵。11121112131111122122221213122211111(,) ,(,) ,.(1,0,0) ,2TTnnTnnnnTaaHH AHaaaaH aH AHaaaaaaAaaHH aH AHn 于 是 有 其 中由 上 节 定 理 ， 只 要 取使 得 就 会使 得 变 换 后 的 矩 阵 的 第 一 列 出 现 个 零 元 。111111211111122221122,() ()1000*0100*00* *00waae sign awHH

6、aae sign aHouseholderHH H AH HH为避免在计算 时会产生较大的误差 取 。同理，可构造如下列形式 矩阵 使得*12222112222, .nnnnnHouseholderH HHHH H AH HHHHHessenbergAH如此进行 次，可以构造 个 矩阵 使得其中 为上 矩阵。特别地，当 为实对称矩阵，则经过上述正交变换后，变为三对角阵。:5222321052 22 2 02100241HouseholderAA例 用 变 换 将 矩 阵 化 成 拟 上 三 角 阵 。1111122(1,0,0) ,(1,00) .21,02TTaH aHIHIHousehol

7、derHH 解：因 由 为使 矩阵 满足 222(), () (2,2)2(1,0)(22,2) 222 ,22 22iiiiTTTTxxe sign xwxxe sign xwwww 由 公式 ，。22 222222104422 2012222244221000010022 0022220022THIwwH2112 100052223 201001052 22 222 000210222202410022100052510100103222 000223220012220022HH H AH H 于是有四、拟上三角矩阵的QR分解2121(2)(2)(2)11112131(2)(2)(1122

8、23221 1 0(cossin00sincos000011nnHnGivensHQRhVrhhhhhhV H因为拟上三角阵 的特殊形状，通常用个旋转变换（又称变换）可将它化成上三角矩阵，从而得到 的分解式。具体步骤为：设否则进行下一步），取旋转矩阵 则2)(2)(2)(2)32333(2)(2)1(2)221121111112111 cos, sin, .nnnnnhhhhhhhHrhhrr其中232222232(3 )(3 )(3 )(3 )11213111(3 )(3 )(3 )223212(3 )(3 )(3 )23331332(3 )(3 )(43414 0(10cossinsinc

9、os 11 nnnnnnnnhVrhhhhrhhhhhhVHhhh（）（）设否 则 进 行 下 一 步 ） ， 再 取 旋 转 矩 阵 则(3 )3 )(3 )(3 )1( 2 )( 2 )( 2 )2( 2 )23222222223222 cos, sin, ()() .nnnnHhhhhrhhrr其 中( )(1)1( )( )( )( )1111111( )( )( )11111( )( )( )1( )( )( )1111( )( )1 1 kkkkkkkkkknnkkkkkkknknkkkkkknknkkkkkknknkknnnnkHVHrhhhhrhhhhhhhhhhh假设上述过程

10、已进行了步，有()11()()1()2()21 0,11 cossinsincos1 cos, sin, ()() . kkkkkkkkkkkkkkkkkkkkkkkkkkhVhhrrrhh设取其中(1)(1)(1)11111(1)(1)1( )(1)(1)(1)(1)111111(1)(1)(1)21212(1)(1)1 1kkkkknkkkkkknkkkkkkkkkknknkkkkkknknkknnnnrhhhrhhVHHhhhhhhhhn于是因此，最多做次旋转变( )( )( )112131( )( )2232( )( )1122133 nnnnnnnnnnnnnnnrhhhrhhHVV

11、V HRrhr换，即得121 32121 32123 (2,3, ) 4 ,( ) iiTTTnnTTTnnVinHV VVRQRQ V VVnQRO nHRQQRQR因为均为正交矩阵，故其中仍为正交矩阵。可算出完成这一过程的运算量约为比一般矩阵的分解的运算量少一个数量级。可证明仍是拟上三角阵，于是可按上述步骤一直迭代下去，这样得到的方法的运算量比基本方法大为减少。需要说明QR的是，通常用方法计算特征值，然后用反幂法求其相应的特征向量。222532644445 (6,4)64 (1,0)(652,4) (0.957092,0.289784) 2100.9160250.27 73500.8320

12、500.55 2010.2773500.0839747TTTTTQRAAwwwwIww用方法求矩阵的全部特征值。首先将 化成拟上三角阵解：，取例：147000.5547000.83205010000.8320500.55470000.5547000.832050H于是 11(1)2211112151.3867503.328200 7.2111021.2307688.15384000.1538462.230767, 5( 7.21102)8.774964 cos50.56980. sin0.821781 HH AHHAHQRHHrrV 即为与 相似的拟上三角矩阵。将 进行分解，记取0.56980

13、30.821781 00.8217810.5698030001(1)2122222228.7749641.8015968.597089 00.4383101.91103000.1538462.230767 (0.438310)( 0.153846)0.464526, cos0.4383100.943564, sin0.1538460.331189 V Hrrr 于是再取32(1)32211100 00.9435640.33118900.3311890.9435648.7749641.8015968.597089 00.4645262.541982001.471953VV V HR于是12132

14、(2)110.5698030.7754030.272165 0.8217810.5376430.18871200.3311890.9435643.5194824.92549110.8401170.3817391.0916272.31065300.4874951.38888,11 3TTQV VHRQ 第一次迭代得重复上述过程迭代 次(12)1232.9920321.0003853 12.013392 0.0074962.0046951.94197100.0003250.9998952.992032,2.004695,0.999895 3,2,1.0.007496HQR 得精确值下三角非对角元的最大模为。方法“基本”收敛较慢。五、带原点移位的QR方法( )( )121( )( )1121 QR,(), , kknnnnkknnnnnnnHhAAHhkuuuuu 理论分析和实际计算均表明，方法产生的矩阵序列的右下角对角元素最先与 的特征值接近。可以证明，若矩阵 的特征值满足则的右下角对角元且收敛速度是线性的，速率为。于是考虑原点移位的技巧来加快收敛速度