理学矩阵的正交分解与求矩阵全部特征值的QR方法课件.pptx

1、2112122122212122221222212nnnnnww ww ww www wHw ww wwnTnTWR Ww wwWHIWWnHouseholder122,(,) ,1,2,.设非零向量设非零向量且满足条件形如且满足条件形如的 阶方阵称为初等反射阵 或称为的 阶方阵称为初等反射阵 或称为定定变换阵变换阵义义1. Householder1. Householder变换与矩阵的正交分解变换与矩阵的正交分解一、初等反射阵一、初等反射阵(Householder(Householder变换阵变换阵) )32110,|122121122002212001010100TTWRWHIWWI 例例

2、：2(2)(2)442TTTTTTTHHHHHIWWIWWIWWWW WWI （ ）对对称称正正交交1det()1H （ ）非非奇奇异异H阵的性质：阵的性质：2112122122212122221222212nnnnnww ww ww www wHw ww ww,()(2)2TTyHyH xkWxk IWWWxkWkWW WxkWy 若若03TW xx 平平面面（ ）镜镜映映射射几几何何方方意意义义程程,(2)2TTxHxIWWxxWW xx 若若kWxykWxyWxH阵的作用：阵的作用：2222 ,2nTnx yRxyxyUUHIUHxyUxy 设设两两个个不不相相等等的的 维维向向量量但但

3、则则存存在在h ho ou us se eh ho ol ld de er r阵阵使使，其其中中定定理理。 yWxxy ,TTTTxxyyxyyx 221UWWU ：若若设设，则则有有证证，因因此此2222TTUUHIWWIU 22()2()TTxyIxyxy 22()2()TTxyHxxxyxxy 22()()2TTxyx xy xxxy 22()()2()TTTTxyxyxyx xy x 因因为为yHx 代代入入上上式式后后即即得得到到niHouseholdereRin1. (1,2, )变变换换可可以以将将给给定定的的向向量量变变为为一一个个与与任任一一个个同同方方向向的的向向量量。 T

4、nnTniiixxxxRxHHxyeR 12(,),0,(0,.,0,0,0)即即：可可构构造造阵阵，使使 niiikkiiisign xxsign xxxsign xx 12221()()() ,10 ()10其中其中 1(,) ,TiiiinUxyxexxx 构造初等反射阵构造初等反射阵2122TTTUUHIWWIIUUU TiiniiiiiiU Uxxxxx2221211 (.()221 (22)()2其中其中iiHxye 有有UUT21433 (2,0,2,1) , ,(0,0,1,0) ,TTxHouseholderHxKeeRKR 已已知知向向量量试试构构造造例例阵阵使使其其中中。

5、3332()40413,20:,sign xxx 因因解解33333 (0,0, 3,0) ,TKyeKe 故故取取于于是是333(2,0,5,1) ,()3(32)15TUxyx 1101020100111510010520514THIUU 11(,0,0)Tkkyxx 12(,)0Tnxxxx推推导导： 12210()() ,()10nkkkikki kxsign xxsign xx TkknHxxxxxnkkn112. (,)(1)构构造造阵阵, ,将将向向量量的的后后面面个个分分量量约约化化为为零零。 12121(,)0, (,0,0)Tn nnkTkkkxx xxHRH xx xx

6、即即：任任给给定定构构造造使使( )1(0,0,)kTkkknUxyxxx ( )( )1()kkTkkHIUU ( )( )1()2k TkkkkkUUx 其其中中 TnnTnniixx xxRxHHxyeRsign xxsign xxxsign xx 121 11122111211111. (,),0,(,0,0) ()()() ,10 ()10特特别别，取取k k可可构构造造 阵阵，使使其其中中 222111112211111111().)221(22)()2TnU Uxxxxx 其其中中1111121122TTTU UHIWWIIU UU 111H xye 有有可构造初等反射阵可构造初

7、等反射阵(1)1 1112(,) ,TnUxexxxkHsign xxx 212222223 2, ()()5解解构构造造 TTTTTUxxxH xxHHIUU (2)2232222212(2)(2)222 (0,)(0,25,1) ()525 (,0)(2,5,0)1 , ()于于是是计计算算 (2,2,1) ,TxyHx 例例：已已知知向向量量试试构构造造初初等等反反射射阵阵使使最最后后一一个个元元素素为为零零。212(, 0 )(2,5 , 0 )TTHxx 252 50010(42 5)(25)52 50(25)(42 5)H , ( ),m nm nn nn nn nARmn r A

8、nAQRQRRRRmnQRRR 是是列列满满秩秩矩矩阵阵（），存存在在分分解解式式其其中中列列正正交交矩矩阵阵，非非奇奇异异上上三三角角阵阵。若若限限1 1、正正交交分分解解的的基基本本定定 阵阵对对角角元元符符号号，则则分分解解式式是是唯唯一一的的。当当时时正正交交阵阵非非奇奇异异上上定定理理定定理理三三角角阵阵。 0:.:.QRAnnnnnmnmQRA 0:.:.nmmmnmQRA 0.00:.:.nnn nnTnnTTkkknnAHHHRH HHRQRQH HHRRQ AQ AHHH H AHHHQQHHH H11112112112111221111221,其中其中为正交阵为正交阵 2、

9、QR分解的实际计算分解的实际计算 用用Householder变换对变换对A作作QR分解分解 n nn nknnHouseholderHRknARHHH H AR 1221(1,2,1)构造阵构造阵则（则（非奇异非奇异上三角阵）上三角阵）(1)(1)(1)(1)111121(2)(2)(2)11121(2)(2)(2)(2)(2)(2)22212(2)(2)2,0,0nnnnnnnH AHHHaaaaaAaa n nARA 化化矩矩阵阵为为上上三三角角阵阵, ,只只须须依依次次将将各各列列对对角角线线下下元元素素化化为为零零(1)(1)(1)(1)12(1)(1)(1)11111,(,0,0)n

10、TAAAHH 记记对的第一列构造使对的第一列构造使TnnnnnnAHHaH AHHHaaaaaaaaaa (2)(2)22(2)(2)22122,(2)(2)(2)(2)221222(2)(2)(2)(2)1112131(3)(3)(3)22232(3)33(3)(3)3(,0,0),0 000 对的第二列构造使对的第二列构造使 nA(3)(3)(3)(3)12 , kkkkknkkkkTkkkkkkAAHHaa( )( )( )( )( )12( )( )( )11,(,0,0)一般地,设按列分块，一般地,设按列分块， 构造使构造使 ()()()()12(1)(1)(1)(1)12, ,kk

11、kkkkkknkkkknH AHHHA knkkkkkkkknkknknnkkkkkknaaaH AHaaaaHHH (2)(2)(2)1111( )( )( )( )( )( )( )( )120000 , kknkkkk kk nkkkkknkkn kn nkkkknaaaaaaaaaaA (2)(2)(2)(2)1111,11(1)(1),1,(1)(1)1,11,(1)(1),1,(1)(1)(1)(1)1200000, ( )( )1( )( )22( )( )( )( )( )1,1()()() )()(0,.,0,.,)kkTkknkkkkkiki kkkkkkkkkkkkkkk

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

13、一的。分解是唯一的。 11 QRQR (1,2,). kkkkkkAQ RkAR QAAA 方方法法的的基基本本思思想想是是利利用用矩矩阵阵的的分分解解通通过过迭迭代代格格式式将将化化成成相相似似的的上上三三角角阵阵（或或分分块块上上三三角角阵阵），从从而而求求出出矩矩阵阵的的全全部部特特征征值值与与特特征征向向量量。111111121112, (2 ,3, ) kAAQ RQARAR QQAQAAAAk 由由即即。于于是是即即与与相相似似。同同理理可可得得，。故故它它们们有有相相同同的的特特征征值值。 可证，在一定条件下，基本可证，在一定条件下，基本QRQR方法产生的矩方法产生的矩阵序列阵序

14、列A Ak k “ “基本基本”收敛于一个上三角阵（或收敛于一个上三角阵（或分块上三角阵）。即主对角线（或主对角线子块）分块上三角阵）。即主对角线（或主对角线子块）及其以下元素均收敛，主对角线（或主对角线子及其以下元素均收敛，主对角线（或主对角线子块）以上元素可以不收敛。特别的，如果块）以上元素可以不收敛。特别的，如果A A是实对是实对称阵，则称阵，则A Ak k “ “基本基本”收敛于对角矩阵。收敛于对角矩阵。,11cossin11sincos11 ()i jiRjjin n阶阶方方阵阵称称为为平平面面旋旋转转阵阵，或或称称为为G Gi iv ve en ns s变变换换阵阵。定定义义 平面

15、旋转阵平面旋转阵(Givens(Givens变换阵变换阵) )1,1,TTi ji ji ji jRRIRRRi i, ,j j平平面面旋旋转转阵阵的的（ ）平平面面旋旋转转阵阵是是非非对对称称交交质质：阵阵性性的的正正。,2Ti ji jRR（ ）也也是是平平面面旋旋转转阵阵。( (3 3) )d de et t( () )= =1 11,.,Rxxxxi i, ,j jT T1 12 2n n平平面面旋旋转转阵阵的的作作用用：（ ）将将向向量量 = =的的第第j j个个分分量量约约化化为为零零。,cossinsincos1,., ;,i jiijjijkkyRxyxxyxxyxkn ki

16、j, ,若若令令，有有 111,222121212cossinsincoscossinsincosyxRyxxxxxxx jy调调整整 ，可可将将 约约化化为为零零。0tanjjixyx令令，得得,.,i jRxx xxxT T12n12n左左乘乘向向量量 = =只只改改变变 的的第第i i个个分分量量和和第第j j个个分分量量。jxix 0tanjjixyx令令，得得2222cossiniiijjjijxxCrxxxxSrxx 所所以以，取取22,0iijijjyCxSxrxxy 于于是是 ,., ,.,0,.,.i jRxxxr xxxxT T1 1i i- -1 1i i+ +1 1j

17、j- -1 1j j+ +1 1n n= =jxix 2,.,xxxxT T1 12 2n n（ ）将将向向量量 = =的的第第i i+ +1 1个个分分量量到到第第n n个个分分量量约约化化为为零零。22,11,., ,0,.,i iiiRxxxrxxrxxT T1 1i i- -1 1i i+ +2 2n n= =,2,122212,., ,0,0,.,i ii iiiiRRxxxrxxrxxxT T1 1i i- -1 1i i+ +3 3n n= =,2,122,., ,0,.,0,i ni ii iinRRRxxxrrxxT T1 1i i- -1 1= =,(3)i ji jiij

18、i jjRAARAARRARAAT TT T左左乘乘 只只改改变变 的的第第i i，j j行行。右右乘乘 只只改改用用对对矩矩阵阵 作作变变换换得得变变 的的第第i i，j j列列。只只改改变变 的的第第i i，j j行行和和到到的的结结第第论论i i，j j列列。2,1,4,0,0.xxrT TT T已已知知向向量量 = =，试试用用G Gi iv ve en ns s变变换换将将 约约化化为为例例(1)(1)2,1,4x xxT T：记记 = =，对对计计解解算算C C和和S S。122222121221,55xxCSxxxx1,2(1)(2)1,221055120550015,0,4TR

19、Rxx (2)4,21xS 5 5对对计计算算C C和和S S, ,C C= =2 21 1 (1)1,31,34021010,21,0,04021TRRx 5 52 21 15 52 21 1(2)5,0,4Tx、用、用 GivensGivens变换对变换对上上Hessenberg阵作阵作QR分解分解(1)(1)(1)11121(1)(1)(1)21222(1)(1)1 1 nnnnnnbbbbbbBbbnGivensBQR 对对上上H essenberg阵H essenberg阵, ,通通常常用用个个变变换换阵阵可可将将它它化化成成上上三三角角矩矩阵阵，从从而而得得到到 的的分分解解式式。

20、(1)211111(2)(2)(2)112131(2)(2)(2)22232(2)(2)(2)1232333(2)(2)1 0(cossin00sincos00(1,2)0011(1,2) nnnnnnnbRrbbbbbbRBBbbbbb 具具体体步步骤骤为为：设设否否则则进进行行下下一一步步），取取旋旋转转矩矩阵阵则则(1)(1)(1)(1)1121111112111 cos, sin, .bbrbbrr 其其中中2322222( 3 )( 3 )( 3 )( 3 )11213111( 3 )( 3 )( 3 )223212( 3 )( 3 )( 3 )333132( 3 )( 3 )434

21、1 0(10cossinsincos (3, 2)11 (3 , 2)nnnnnnnbRrbbbbrbbbbbbRBbb （）设设否否 则则 进进 行行 下下 一一 步步 ） ， 再再 取取 旋旋 转转 矩矩 阵阵 则则3( 3 )4( 3 )( 3 )1( 2 )( 2 )( 2 )2( 2 )23222222223222 cos, sin, ()() .nnnnnBbbbbbrbbrr 其其 中中1( )( )( )( )1111111( )( )( )11111( )( )( )1( )( )( )1111( )( )1 (1, ) kkkkkkkknnkkkkkkknknkkkkkkn

22、knkkkkkknknkknnnnBR kk Brbbbbrbbbbhhbbbbb 1k 假假设设上上述述过过程程已已进进行行了了步步，有有()1()()1()2()21 0,11 (1,)cossinsincos1 cos, sin, ()() .kkkkkkkkkkkkkkkkkkkkkkkkbR kkbbrrrbb 设设取取其其中中(1)(1)(1)11111(1)(1)1(1)(1)(1)111111(1)(1)(1)21212(1)(1)1 (1, )1kkkkknkkkkkknkkkkkkkknknkkkkkknknkknnnnrbbbrbbR kk BBbhbbhhbbn 于于是

23、是因因此此，最最多多做做次次旋旋转转变变换换，即即( )( )( )( )112131( )( )2232( )33 ( ,1) (2,1)(1,2)nnnnnnnnnnnHR n nR nnRBrbbbrbbRrbr 得得213212132123( ,1),(2,3, ) 4,() TTTnnTTTnnR i iinHR RRRQRQR RRnQRO nHRQQRQR 因因为为均均为为正正交交矩矩阵阵，故故其其中中仍仍为为正正交交矩矩阵阵。可可算算出出完完成成这这一一过过程程的的运运算算量量约约为为比比一一般般矩矩阵阵的的分分解解的的运运算算量量少少一一个个数数量量级级。可可证证明明仍仍是是

24、上上H H e es ss se en nb be er rg g阵阵，于于是是可可按按上上述述步步骤骤一一直直迭迭代代下下去去，这这样样得得到到的的方方法法的的运运算算量量比比基基本本QR方方法法大大为为减减少少。需需要要说说明明的的是是，通通常常用用方方法法计计算算特特征征值值，然然后后用用反反幂幂法法求求其其相相应应的的特特征征向向量量。22532644445 (6,4)64 (1,0)(652,4)10 2010.9160250.2773500.8320500.55470020.2773500.08397470.5547000.832050TTTTTQRAAuuuIu u 用用方方法法

25、求求矩矩阵阵的的全全部部特特征征值值。首首先先将将 化化成成上上H H e es ss se en nb be e例例：r rg g：阵阵，取取解解110000.8320500.55470000.5547000.832050H 于于是是 11221111151.3867503.3282007.2111021.2307688.15384000.1538462.230767, 5( 7.21102)8.774964 cos50.56980. sin0.821781 HH AHHAHQRBHrr 即即为为与与 相相似似的的上上H H e es ss se en nb be er rg g阵阵。将将进

26、进行行分分解解，记记取取0.5698030.8217810(2,1)0.8217810.5698030001R 122222228.7749641.8015968.597089(2,1)00.4383101.91103000.1538462.230767 (0.438310)( 0.153846)0.464526, cos0.4383100.943564, sin0.1538460.331189 RBrrr 于于 是是再再 取取11100 (3, 2)00.9435640.33118900.3311890.943564 (3, 2)(2,1)8.7749641.8015968.59708900

27、.4645262.541982001.471953RRRBR 于于 是是12110.5698030.7754030.272165(2,1)(3,2)0.8217810.5376430.18871200.3311890.9435643.5194824.92549110.8401170.3817391.0916272.31065300.4874951.388883,11TTQRRBRQ 第第一一次次迭迭代代得得重重复复上上述述过过程程 迭迭代代次次121232.9920321.000385312.013392 0.0074962.0046951.94197100.0003250.9998952.992032,2.004695,0.999895 3,2,1.0.007496BQR 得得精精确确值值下下三三角角非非对对角角元元的的最最大大模模为为。方方法法“基基本本”收收敛敛较较慢慢。