数值分析讲稿11

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

2、值。 可证，在一定条件下，基本QR方法产生的矩阵序列A(k) “基本”收敛于一个上三角阵（或分块上三角阵）。即主对角线（或主对角线子块）及其以下元素均收敛，主对角线（或主对角线子块）以上元素可以不收敛。特别的，如果A是实对称阵，则A(k) “基本”收敛于对角矩阵。 因为上三角阵的主对角元（或分块上三角阵中，主对角线子块的特征值）即为该矩阵的特征值，故当k充分大时， A(k)的主对角元（或主对角线子块的特征值）就可以作为A的特征值的近似。 基本的QR方法的主要运算是对矩阵QR分解，分解的方法有多种。介绍一种Schmit正交化方法。()()0kAu1212211112221121212121211

3、121121111111222212 ,(,) (1,2, )., /. , ,0, /,1nTjjjnjAnAa aaaaaajnaabaabaab baaaaaaaaaa aaab ba aaa aabbbbbbb设 为 阶非奇异实矩阵，记其中取取则1211121111, ,0., /(2,3,),1(1,2,),kkkkiikkkinkkkkkkkkb bbaab bbbbknb bbbknaab babbbb一般地取则向量组正交，且即1111121212112211, ,Q RkkkkkkknnnnnnnnaabbabbbbAaaabbbaababbabQ RbabbSchm it即于

4、 是这 就 是 用正 交 化 方 法 对 矩 阵 进 行 的分 解 。 基本QR方法每次迭代都需作一次QR分解与矩阵乘法，计算量大，而且收敛速度慢。因此实际使用的QR方法是先用一系列相似变换将A化成拟上三角矩阵（称为上Hessenberg矩阵），然后对此矩阵用基本QR方法。因为拟上三角矩阵具有较多零元素，故可减少运算量。化A为相似的拟上三角阵的方法有多种。1231112222112222210 :121.012: (2, 1,0) ,( 1,2, 1) ,(0, 1,2) .21 (,0) ,554213 6,( 1,2, 1)(,0)(, 1) ,5 5555365(,) ,707070TT

5、TTTTTTSchmitAQRaaaababaabbbbbb 例 用正交化方法对进行分解解因而有3331132233322 4 6,(,) 7 7 7123 (,)141414TTaabbabbbbb11, /kkkkiikkkibaa b bbbb121212112211 , , ,253701145451515670214070516700570314002 40 7nnnnnnnnAa aab bbaa ba bba bba bb 所以二、豪斯豪尔德(Householder)变换2211221121221222121 (,)1,1 22221 22 2221 21;(2)det()1;(

6、3)TnnnTnnnnTwwwwwwwwwwww www wHIwww ww wwHouseholderHHHHHH设向量满足则称为矩阵或反射矩阵。可证其具有以下性质：（ ） 是实对称的正交矩阵，即仅11n 1, 1,;w有两个不等的特征值，其中 是重特征值是单重特征值 为其相应的特征向量2212:0,().21()(2)() 22 2TTnTTTwoS w xRH xwxwHIwwwwwH xwIwwxwxwww xww wxwwxw (4)考虑以 为法向量过原点 的超平面为任意的数 有证：且wxo( )2222222222222222 :,1,() 2, (2)2( ) .2 () ()

7、=nTTTTTTTx yRyHouseholderHHxxyxxywHIwwxxyxxyHxIwwxxxxyxxxyxxyxxyxxyx xxy x 定理 设为中任意非零向量 且则存在矩阵使得。证：令于是由 范数的定义.22222222 22() .TTTTTTxx yxy yx xxy xxxxyxHxxy 代入上式得2222222 . ,()() ()iiiiiHxxyxHouseholderxyexHouseholderxxyxxe sign xwwxxyxxe sign x 上式得此定理表明，对任一非零向量都可以构造一个变换，它将 变成事先给定的单位向量的倍数。特别地取则 经过变换后可

8、变成只有一个分量不为零。实际计算时，为避免误差取。三、化一般矩阵为拟上三角阵111211121222123233311 (2,3, ), HouseholdernnnnnnnnniihhhhhhhhHhhhhhhinA称形如 的矩阵为拟上三角阵，也称为上海森堡（Hessenberg)阵。如果次对角线元全不为零 则称该矩阵为不可约的上Hessenberg矩阵。讨论用变换将一般矩阵 相似变换成Hessenberg阵1111111111121112131111122122221213122 ,1000 01(,) ,(,) ,TTnTnHHH AHHHHHnHouseholderaa HH AHaa

9、aaH aH AHaaaaaaA首 先 ， 选 取 矩 阵使 得 经相 似 变 换 后 的 矩 阵的 第 一 列 中 有 尽 可 能 多 的 零 元 素 。 为 此 ， 应 取为 如 下 形 式其 中为阶矩 阵 。 于 是 有 其 中LMLLL211111.(1,0,0) ,2nnnnTaaHH aH AHn 由 上 节 定 理 ， 只 要 取使 得就 会使 得 变 换 后 的 矩 阵的 第 一 列 出 现个 零 元 。MLMLL11121112122212323331nnnnnnnnnhhhhhhhhHhhhhhLLLOOM*11111112111112212222111112 ,() ()

10、 () ) ( () 1000010 0)xxywxxyH awaae sign awHaae sign aHHouseholderae sn aHig 为避免在计算 时会产生较大的误差 取。 同理，可构造如下列形式矩阵(21122122221122*00*0022, .nnnH H AH HHnnHouseholderHHHHH H AH HHHHHessenbergAH使得*如此进行次，可以构造个矩阵使得其中为上矩阵。特别地，当 为实对称矩阵，则经过上述正交变换后，变为三对角阵。111112222 :5222321052 22 2 02100241(1,0,0) ,(1,0,0) .21,

11、02()(TTiiiHouseholderAAaH aHIHIHouseholderHHxxe sign xwxxe sign 例 用变换将矩阵 化成拟上三角阵。解：因由为使矩阵满足由公式2, (2,2)2(1,0)222(22,2) (,) ,2222TTiTTwxwww ，22 222222104422 2012222244221000010022 0022220022THIwwH22100001000000HH2112 100052223 20100105 2 22 222 000210222202410022100052510100103222 000223220012220022HH

12、 H AH H 于是有四、拟上三角矩阵的QR分解1112111212221232333121 1 0(nnnnnnnnnHnGivensHQRhhhhhhhhHhhhhhh因为拟上三角阵的特殊形状，通常用个旋转变换（又称变换）可将它化成上三角矩阵，从而得到的分解式。具体步骤为：设否则进行下一步），221111121111111211211(2)(2)(2)112131(2)(2)(2)22232(2)(2)(2)2132333(2)(2)1 cos, cossin00sincos00sin.0011 nnnnnnnhrhhrhVrrhhhhhhV Hhhhhh取旋转矩阵，其中， 则(2) H2

13、32222232(2) 2(2) 222232(2)3222222 0(10cossinsincos 11 ()() cos, sinhVrhhhhr（ ）设否则进行下一步），再取旋转矩阵 其中，2)2.r232(3)(3)(3)(3)11213111(3)(3)(3)223212(3)(3)(3)(3)33313(3)(3)(3)43414(3)(3)1 nnnnnnnnnnnnV HrhhhhrhhhhhhHhhhhh（ ）则( )(1)1( )( )( )( )1111111( )( )( )11111( )( )( )1( )( )( )1111( )( )1 1 kkkkkkkkkk

14、nnkkkkkkknknkkkkkknknkkkkkknknkknnnnkHVHrhhhhrhhhhhhhhhhh假设上述过程已进行了步，有()11()()1()2()21 0,11 cossinsincos1 cos, sin, ()() .kkkkkkkkkkkkkkkkkkkkkkkkkkhVhhrrrhh设取其 中( )1(1)(1)(1)11111(1)(1)1(1)(1)(1)11111(1)(1)(1)21212(1)(1)1 kkkkkkkknkkkkkknkkkkkknknkkkkkknknkknnnnVHrhhhrhhhhhhhhhh于是(1) 1kHn因此，最多做次旋转变

15、换，即得( )11221( )( )( )112131( )( )2232( )33 nnnnnnnnnnnnnnnHVVV HrhhhrhhRrhr1213212132123 (2,3, ) 4,() iiTTTnnTTTnnVinHV VVRQRQV VVnQRO nHRQQRQR因为均为正交矩阵，故其中仍为正交矩阵。可算出完成这一过程的运算量约为比一般矩阵的分解的运算量少一个数量级。可证明仍是拟上三角阵，于是可按上述步骤一直迭代下去，这样得到的方法的运算量比基本方法大为减少。需要说明QR的是，通常用方法计算特征值，然后用反幂法求其相应的特征向量。11221nnnnVVV HR222532

16、 644445 (6,4)64 (1,0)(652,4) (0.957092,0.289784) 2100.9160250.2773500.832 2010.2773500.0839747TTTTTQRAAwwwwIww例：用方法求矩阵的全部特征值。解：首先将 化成拟上三角阵，取10500.5547000.5547000.83205010000.8320500.55470000.5547000.832050H于是 222( )( )iiiixxe sign xwxxe sign x11(1)2211112151.3867503.328200 7.2111021.2307688.15384000

17、.1538462.230767, 5( 7.21102)8.774964 cos50.56980. sin0.821781 HH AHHAHQRHHrrV 即为与 相似的拟上三角矩阵。将 进行分解，记取0.5698030.82178100.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)32

18、211100 00.9435640.33118900.3311890.9435648.7749641.8015968.597089 00.4645262.541982001.471953VV V HR于是12132(2)110.5698030.7754030.272165 0.8217810.5376430.18871200.3311890.9435643.5194824.92549110.8401170.3817391.0916272.31065300.4874951.388883,11TTQV 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 理论分析和实际计算均表明，方法产生的矩阵序列的右下角对角元素最先