求矩阵全部特征值的QR方法

1、 8.48.4 求矩阵全部特征值的求矩阵全部特征值的QR方法方法 一、求矩阵全部特征值的一、求矩阵全部特征值的QR方法方法 6060年代出现的年代出现的QRQR算法是目前计算中小型矩阵的算法是目前计算中小型矩阵的 全部特征值与特征向量的最有效方法。全部特征值与特征向量的最有效方法。 理论依据：理论依据： 任一非奇异实矩阵都可分解成一个正交矩阵任一非奇异实矩阵都可分解成一个正交矩阵Q Q和一个和一个 上三角矩阵上三角矩阵R R的乘积，而且当的乘积，而且当R R的对角元符号取定时，的对角元符号取定时， 分解是唯一的。分解是唯一的。 1 1 QRQR (1,2,). kkk kkk AQ R k A

2、R Q AA A 方方法法的的基基本本思思想想是是利利用用矩矩阵阵的的分分解解通通过过 迭迭代代格格式式 将将化化成成相相似似的的上上三三角角阵阵（或或分分块块上上三三角角阵阵）， 从从而而求求出出矩矩阵阵 的的全全部部特特征征值值与与特特征征向向量量。 1 11111 1 21112 , , (2 ,3, ) k AAQ RQAR AR QQAQAA AAk 由由即即。 于于是是即即与与 相相似似。 同同理理可可得得，。 故故它它们们有有相相同同的的特特征征值值。 可证，在一定条件下，基本可证，在一定条件下，基本QRQR方法产生的矩方法产生的矩 阵序列阵序列A Ak k “基本”收敛于一个上

3、三角阵（或“基本”收敛于一个上三角阵（或 分块上三角阵）。即主对角线（或主对角线子块）分块上三角阵）。即主对角线（或主对角线子块） 及其以下元素均收敛，主对角线（或主对角线子及其以下元素均收敛，主对角线（或主对角线子 块）以上元素可以不收敛。特别的，如果块）以上元素可以不收敛。特别的，如果A A是实对是实对 称阵，则称阵，则A Ak k “基本”收敛于对角矩阵。“基本”收敛于对角矩阵。 QR方法的实际计算步骤方法的实际计算步骤 Householder AHessenbergB 用阵用阵 作正交相似变换作正交相似变换 上上 第第 阵阵 一步一步 . *: : : : * 1 kkk Given

4、kkk BQ R B BR Q 用变换产生迭代序列用变换产生迭代序列 第二步第二步 1 2 * * n Householder AB 用阵用阵 作正交相似变换作正交相似变换 （对称阵）三对角阵（对称阵）三对角阵 * * * 二、化一般矩阵为上二、化一般矩阵为上Hessenberg阵阵 1112111 2122212 32333 1 1 (2,3, ), Househ old e r nn nn n nnnn ii hhhh hhhh hhhH hh hin A 称称形形如如 的的矩矩阵阵为为上上海海森森堡堡（Hessenberg) 阵Hessenberg) 阵。如如果果此此对对角角 线线元元全

5、全不不为为零零 则则称称该该矩矩阵阵为为不不可可 约约的的上上Hessenberg矩Hessenberg矩阵阵。 讨讨论论用用变变换换将将一一般般矩矩阵阵 相相似似变变 换换成成HessHessenberg阵enberg阵 11 11 11 1 1 , 100 0 0 1 HouseholderHH H AH HH H HnHouseholder 首首先先，选选取取矩矩阵阵使使得得经经相相似似变变 换换后后的的矩矩阵阵的的第第一一列列中中有有尽尽可可能能多多的的零零元元素素。 为为此此，应应取取为为如如下下形形式式 其其中中为为阶阶矩矩阵阵。 1 112 11 1 11221 12131121

6、2131 (,) ,(,) , T TT nn aa H H AH H aH A H aaaaaaaa 于于是是有有 其其中中 222 22 2 11 11 11 . (, 0) 0, 2 n nnn T aa A aa HH a H AHn 只只要要取取使使得得就就会会使使得得变变换换后后 的的矩矩阵阵的的第第一一列列出出现现个个零零元元。 22112 2 12 2221122 1000* 0100* 00* *00 22, , . nnn Householder HH H AH H H nnHouseholderHH HHH H AH HHH HHessenberg 同同理理，可可构构造造

7、如如下下列列形形式式矩矩阵阵 使使得得 * * 如如此此进进行行次次，可可以以构构造造个个矩矩阵阵 使使得得 其其中中为为上上矩矩阵阵A H 。特特别别地地，当当 为为实实对对称称矩矩阵阵，则则 经经过过上上述述正正交交变变换换后后，变变为为三三对对角角阵阵。 1 22 1 522 23 2 105 2 22 2 0210 0241 2 , 0 2 2, (2,2)2(1,0)(22,2) : TTT HouseholderA A HouseholderHH u 用用变变换换将将矩矩阵阵 化化成成上上HesseHesse例例 解解 nberg阵nberg阵。 求求矩矩阵阵满满：足足 ， 2 2

8、 2 22222 10 4422 2 01 22222 4422 1000 0100 22 00 22 22 00 22 T T uu HI u u H 22 1000 522 23 2 0100 105 2 22 2 22 00 220210 22 0241 00 22 1000 52510100 1032 22 00 0223 22 0012 22 00 22 HH AH 于是有于是有 三、上三、上Hessenberg阵的阵的QR分解分解 对对上上Hessenberg阵阵只需要将其次对角线上的只需要将其次对角线上的 元素约化为零，用元素约化为零，用Given变换比用变换比用Househol

9、der变变 换更节省计算量。为此先介绍换更节省计算量。为此先介绍Given变换。变换。 , 1 1 cossin 1 1 sincos 1 1 () i j i R j ji n n阶方阵阶方阵 称为平面旋转阵，或称为Givens变换阵。称为平面旋转阵，或称为Givens变换阵。 定义定义 、平面旋转阵、平面旋转阵(Givens(Givens变换阵变换阵) ) 1 , 1, TT i ji ji ji j R RIRR R i,ji,j 平平面面旋旋转转阵阵的的 （）平平面面旋旋转转阵阵是是非非对对称称 交交 质质： 阵阵 性性 的的 正正。 , , 2 T i j i j R R （ ）也也

10、是是平平面面旋旋转转阵阵。 (3)det()=1(3)det()=1 1,., R xx xx i,ji,j T T 12n12n 平平面面旋旋转转阵阵的的作作用用： （）将将向向量量 = =的的第第j j个个分分量量约约化化为为零零。 , cossin sincos 1,., ;, i j iij jij kk yR x yxx yxx yxkn ki j , , 若令，有若令，有 11 1,2 22 1 2 12 12 cossin sincos cossin sincos yx R yx x x xx xx j y调调整整 ，可可将将 约约化化为为零零。 0tan j j i x y x

11、 令令，得得 , ,., i j Rxx xxx T T 12n12n 左左乘乘向向量量 = =只只改改变变 的的第第i i个个分分量量和和 第第j j个个分分量量。 j x i x 0tan j j i x y x 令令，得得 22 22 cos sin ii ij jj ij xx C r xx xx S r xx 所所以以，取取 22 ,0 iijijj yCxSxrxxy于于是是 , ,., ,.,0,.,. i j R xxxr xxxx T T 1i-1i+1j-1j+1n1i-1i+1j-1j+1n = = j x i x 2,.,xx xx T T 12n12n （ ）将将向向

12、量量 = =的的第第i+1i+1个个分分量量到到第第n n个个 分分量量约约化化为为零零。 22 ,11 ,., ,0,., i iii Rxxxrxxrxx T T 1i-1i+2n1i-1i+2n = = ,2,1 222 12 ,., ,0,0,., i ii i iii RRxxxrxx rxxx T T 1i-1i+3n1i-1i+3n = = ,2,1 22 ,., ,0,.,0, i ni ii i in RRRxxxr rxx T T 1i-11i-1 = = , , , , (3) i j i j i i ji j j RAA RAA R R ARA A T T T T 左左

13、乘乘 只只改改变变 的的第第i i，j j行行。 右右乘乘 只只改改 用用对对矩矩阵阵 作作变变换换得得 变变 的的第第i i，j j列列。 只只改改变变 的的第第i i，j j行行和和 到到的的结结 第第 论论 i i，j j列列。 2,1,4 ,0,0. xx r T T T T 已已知知向向量量 = =，试试用用GivensGivens变变换换将将 约约 化化为为 例例 (1)(1) 2,1,4x xx T T ：记记 = =，对对计计解解算算C C和和S S。 12 2222 1212 21 , 55 xx CS xxxx 1,2 (1)(2) 1,2 21 0 55 12 0 55

14、001 5,0,4 T R Rxx (2) 4 , 21 xS 5 5 对对计计算算C C和和S,C=S,C= 2121 (1) 1,31,3 4 0 21 010,21,0,0 4 0 21 T RRx 5 5 2121 5 5 2121 (2) 5,0,4 T x 、用、用 GivensGivens变换对变换对上上Hessenberg阵作阵作QR分解分解 (1)(1)(1) 11121 (1)(1)(1) 21222 (1)(1) 1 1 n n nnnn bbb bbb B bb nGivens BQR 对对上上Hessenberg阵Hessenberg阵, , 通通常常用用个个变变换换

15、阵阵可可将将它它化化成成上上三三角角矩矩阵阵， 从从而而得得到到 的的分分解解式式。 (1) 21 11 11 (2)(2)(2) 112131 (2)(2)(2) 22232 (2)(2)(2) 1232333 (2)(2) 1 0( cossin00 sincos00 (1,2)001 1 (1,2) n n n nnnn b R rbbb bbb RBBbbb bb 具具体体步步骤骤为为： 设设否否则则进进行行下下一一步步）， 取取旋旋转转矩矩阵阵 则则 (1)(1) (1)(1)1121 1111121 11 cos, sin, . bb rbb rr 其其中中 2 32 22 22

16、(3)(3)(3)(3) 11213111 (3)(3)(3) 223212 (3)(3)(3) 33313 2 (3)(3) 4341 0( 10 cossin sincos (3,2) 1 1 (3 ,2) nn nn nn n b R rbbbb rbbb bbb RB bb （ ） 设设否否则则进进行行下下一一步步），再再取取旋旋转转矩矩阵阵 则则 3 (3) 4 (3)(3) 1 (2)(2) (2)2(2)23222 2222232 22 cos, sin, ()() . n nnnn B b bb bb rbb rr 其其中中 1 ( )( )( )( ) 1111111 ( )

17、( )( ) 11111 ( )( )( ) 1 ( )( )( ) 1111 ( )( ) 1 (1, ) kk kkkk kknn kkk kkkknkn kkk kkknkn kkk kkknkn kk nnnn BR kk B rbbbb rbbb bhh bbb bb 1k 假假设设上上述述过过程程已已进进行行了了步步，有有 ( ) 1 ( )( ) 1 ( )2( )2 1 0, 1 1 (1, )cossin sincos 1 cos, sin, ()() . k kk kk kk kk kkkk kk kk kk kkkkk b R kk bb rr rbb 设设取取 其其中中

18、 (1)(1)(1) 11111 (1)(1) 1 (1)(1)(1) 111111 (1)(1)(1) 21212 (1)(1) 1 (1, ) 1 kkk kkn kk kkkkn kkk kkkkknkn kkk kkknkn kk nnnn rbbb rbb R kk BBbhb bhh bb n 于于是是 因因此此，最最多多做做次次旋旋转转变变换换，即即 ( ) ( )( )( ) 112131 ( )( ) 2232 ( ) 33 ( ,1) (2,1)(1,2) n nnn n nn n n n n HR n nR nnRB rbbb rbb Rrb r 得得 21321 213

19、21 2 3 ( ,1),(2,3, ) 4, () TTT nn TTT nn R i iin HR RRRQR QR RR nQR O n HRQ QR QR 因因为为均均为为正正交交矩矩阵阵，故故 其其中中仍仍为为正正交交矩矩阵阵。可可算算出出完完成成这这 一一过过程程的的运运算算量量约约为为比比一一般般矩矩阵阵的的分分解解的的运运 算算量量少少一一个个数数量量级级。 可可证证明明仍仍是是上上Hessenberg阵Hessenberg阵，于于是是可可按按 上上述述步步骤骤一一直直迭迭代代下下去去，这这样样得得到到的的方方法法的的运运算算 量量比比基基本本 QR 方方法法大大为为减减少少。

20、需需要要说说明明的的是是，通通常常用用 方方法法计计算算特特征征值值，然然后后用用反反幂幂法法求求其其相相应应的的特特征征 向向量量。 22 532 644 445 (6,4)64 (1,0)(652,4) 10 2 01 0.9160250.2773500.8320500.554700 2 0.2773500.08397470.5547000.832050 TTT T T QRA A u uu I u u 用用方方法法求求矩矩阵阵的的全全部部特特征征值值。 首首先先将将 化化成成上上HessenbeHessenbe 例例： rgrg：阵阵，取取解解 1 100 00.8320500.554700 00.5547000.832050 H 于于是是 11 22 11 111 51.3867503.328200 7.2111021.2307688.153840 00.1538462.230767 , 5( 7.21102)8.774964 cos50.56980. sin0.821781 HH AH HAHQR BHr r 即即为为与与 相相似似的的上上Hessenberg阵Hessenberg阵。将将进进行行分分解解， 记记 取取 0.5698030.8217810 (2,1)0.8217810