带原点位移的QR方法ppt课件

《带原点位移的QR方法ppt课件》由会员分享，可在线阅读，更多相关《带原点位移的QR方法ppt课件（28页珍藏版）》请在装配图网上搜索。

1、 8.4.2 8.4.2 带原点位移的带原点位移的QRQR方法方法 定理20中 的速度依赖于比值 ，nknnka)(lim1/nnnr当 很小时，收敛较快，假设 为 的一个估计，且对 运用QR算法，那么 元素将以收敛因子 线性收敛于零，元素将比在根本算法中收敛更快.nrsnsIA)1,(nn)/()(1ssnn),(nn 为了加速收敛，选择数列 ，按下述方法构造矩阵序列 ，称为带原点位移的QR算法.kskA 设 nnAAR1 对 进展QR分解 IsA111111RQIsA 构成矩阵 111111111112)(QAQIsQIsAQIsQRATT求得 后，将 进展QR分解 kAIsAkk,4,3

2、,kRQIsAkkkk4.4构成矩阵 kkTkkkkkQAQIsQRA14.5假设令 ，那么有 ，并且矩阵 有QR分解式 1221,RRRRQQQQkkkkkTkkQAQA1)()()(21AIsAIsAIsAn.)(kkRQA 在带位移QR方法中，每步并不需求构成 和 ，可按下面的方法计算：QR 首先用正交变换左变换将 化为上三角阵，即 IsAkkkkknRIsAPPP)(121(当 为上海森伯格阵或对称三对角阵时，可为平面旋转阵)，那么 AiP.)(1211211IsPPPIsAPPPAkTnTTkknk 下面思索用QR方法计算上海森伯格阵的特征值.设 为上海森伯格阵，即 B.1,2222

3、111211nnnnnnbbbbbbbbB假设 ，那么称 为不可约上海森伯格阵.)1,2,1(0,1nibiiB 设 ，由定理17可选正交阵 使 为上海森伯格阵，对 运用QR算法.nnA R0U00AUUHTH QR算法：1HH 对于,2,1kkkkkkkQRHQRRQH1)(分解4.6假设由4.6迭代产生的每一个上海森伯格阵 都是不可约的，否那么，假设在某步有 kH.02212111pnpHHHHpnpk于是，这个问题就分别为 与 两个较小的问题.当 或 时，有11H22H1 np2n11011)1(12111nhHHHnknnk或,22*02212111nHHHnk即可求出 的特征值 或

4、由 右下角二阶阵的特征值求得，且求 的其他特征值时，转化为降阶求 的特征值.H)1(knnnh1kHH11Hnn,1 实践上，每当 的次对角元适当小时，就可进展分别.例如，假设1kH),(1,1,1pppppphhh就把 视为零.pph,1 普通取 ，其中 是计算中有效数字的位数.t 10t 8.4.3 8.4.3 用单步用单步QRQR方法计算上海森伯格阵特征方法计算上海森伯格阵特征值值 上海森伯格阵的单步QR方法：选取 并设 ks).(11,2222111211为不可约阵设HHhhhhhhhhHnnnnnn 对于 用位移来加速收敛,2,1kIsQRHRQIsHkkkkkkkk1由 实践计算为

5、 1kkHH 1 左变换：).()(1111223,1上三角阵RIsHPPPnn 2 右变换：.1,1231212IsPPPRHTnnTT其中 为平面旋转阵.)1,(1,kkPPkk 1 左变换计算),2,1(1nkshhkkkk确定平面旋转阵 使)2,1(12PP.00)(1,33332)2(2)2(23)2(22)2(1)2(13)2(12111112nnnnnnnhhhhhhhhhhhrIsHP设已完成第1次，第 次左变换，即有 1k.)(1,1,1)()()(,1)(,11,1)2(1)2(1)2(1,111111223,1nnnnnkkkkknkkkknkkkkkknkkkkhhhh

6、hhhhrhhhrIsHPPP4.7确定平面旋转阵 ，使 变为0，且完成第 次左变换 计算只)1,(1,kkPPkkkkh,1k)(1112,11,IsHPPPkkkk需计算4.7阵第 行及第 行元素.k1k 继续这一过程，最后有).()(1111223,1上三角阵RIsHPPPnn 2 右变换计算,1,1231212IsPPPRHTnnTT在第 次右变换 中，只需计算 第 列及第 列元素.kTkkTPPR1,121)(TkkTPPR,1121k1k).,2,1(1,nkshhkkkk最后).(*1,11212为上海森伯格阵IsPPRHTnnT 由上述讨论指出，假设 为上海森伯格阵，那么用QR

7、算法产生的 亦是上海森伯格阵.即上海森伯格阵在QR变换下方式不变.nnH R,32kHHH 讨论一个极端的情况 定理22 设：1 为不可约上海森伯格阵；2 为 一个特征值.那么QR方法 nnH R1HH IRQHQRQRIH21)(分解中.,0)2()2(1,nnnnhh 证明 记).(111上三角阵nnnrrrR由设 为不可约阵，那么上海森伯格阵 亦为不可约.1HIH1由将上海森伯格阵 约化为上三角阵 的平面旋转变换的取法可知 IH1R),1,2,1(0,1nihriiii又由于 为奇特矩阵，从而得到 .因此，的最后一行为 ，即RIHQT)(10nnr2H),0,0,0(.,0)2()2(1

8、,nnnnhh这样在QR方法迭代中，参数 可选为 ，即 的 元素.通常可以作为特征值的最好近似.ks)(knnhkH),(nn 算法3上海森伯格阵的QR算法给定 为上海森伯格阵，本算法计算 nnH RsIQRHhsQRRQsIHnn112111)()(取分解且 覆盖 2H)(1HHHshh1111.11,2,1)1(1,2,1.3,)3(0)1,()2()1(1,2,1.2,1,1,11,11,1kinkhhcsschhnkjrhhcssckkPshhnkjkkjkkkkjkkjkkkkkkkkkkkkkk对于右变换对于对于左变换使确定对于shhshhcsschhhhnnnnkkkkkkkkk

9、iikkiik.4)2(),),1,1,（假设用不同的位移 ，反复运用算法3就产生正交类似的上海森伯格阵序列 .当 充分小时，可将它置为零就得到 的近似特征值 .再将矩阵降阶，对较小矩阵延续运用算法.)(knnkhs,21kHHH)(1,knnh)(knnnhH 例8 用QR方法计算对称三对角矩阵.4101310121 AA的全部特征值.解 选取 ，那么)(knnkas.41s,81650.03651.00954.14472.0342.12361.2)(111223RIsAPP.3333.47454.007454.02667.34899.004899.04000.1123122IsPRPATT

10、,6884.42724.002724.00202.32017.002017.02915.13A,7320.40072.000072.09943.20993.000993.02737.14A,7321.40009986.20498.000498.02694.15A.9986.20498.00498.02694.15A如今收缩，继续对 的子矩阵 进展变换，得到 5A225RA,0000.31041042680.1)(5551255125IsPIsAPAT故求得 近似特征值为 A.2680.1,0000.3,7321.4123而 的特征值是 A.2679.133,0.3,7321.433123 算法

11、3是在实数中进展选择位移 ,不能逼近一个复特征值，所以算法3不能用来计算 的复特征值.)(knnkhsH 8.4.4 8.4.4*双步双步QRQR方法隐式方法隐式QRQR方法方法 第3节中将 经过正交类似变换化为上海森伯格矩阵 ，即 ，其中 不是独一的.但是，假设规定了正交矩阵 的第一列，那么 和 除差1因子外独一.nnA RHHAUUT00H0U0UH 定理23隐式Q定理设 ,且：nnA R 1 及 都是正交阵，且有 都是上海森伯格阵.),(21nqqqQ),(21nvvvVGAVVHAQQTT,2 为不可约上海森伯格阵，且 即 与 第1列一样.那么：H11vq QV 1 ,且 ;2 ,其中

12、 ，iiqv),2(1,1,nighiiiiHDDG1)1,1,1(diagD即 和 在 意义上“本质上相等.HGHDDG1 算法3不能用来求 的一个复特征值，当 上海森伯格阵的依模最小特征值是复数时，位移参数 可取为某步 右下角的二阶矩阵HH1,kksskHnnnnnnnnhhhhG1,11,14.8的特征值.当 的特征值 与 为复数时，假设运用算法3就要引进复数运算，这对于实矩阵 是不用要的，在某些条件下，可以用正交类似变换将 约化为实Schur型.G1s2sHH 隐式位移的QR方法，即用 与 作位移延续进展二次1s2s单步的QR迭代，运用复位移，又防止复数运算.1 设 为上海森伯格阵，取

13、共轭复数 作两步位移的QR方法，即 nnHHR121,ss.,12211211123333222211111121111RRRQQQQHQQQHQQIsQRHRQIsHQHQIsQRHRQIsHTTTT其中4.9显然 有QR分解)(2111IsHIsHM.QRM 4.10现实上，由(4.9)式并利用22121122)()(RQQIsHQIsHT有.)()(12211112211121QRRRQQRQQRQQRQIsHMT且 阵为实矩阵，这是由于即使 特征值为复数 MGIssHssHM2112121)(4.11其中 为实数.thhhhssshhssnnnnnnnnnnnn,11,1,1211,1

14、21,于是，4.10式为实矩阵 的QR分解，并且可以选取 和 使 为实的正交阵.M1Q2Q21QQQ 由此得出QHQQQHQQHTT1211213)()(是实矩阵.假设用下述算法就能保证 是实矩阵 3H (a)直接构成实矩阵 tIsHHM121 (b)计算 阵的实QR分解 MQRM (c)令 QHQHT13 但是(a)需求 次乘法运算，不适用.)(3nO 2 根据隐式Q定理，假设按下述算法进展，就有可能用 次运算来实现从 到 的转换.)(2nO1H3H (a)求与 有一样第一列的正交阵 Q0P (b)运用豪斯霍尔德方法将 化为一个上海010PHPT森伯格阵，即.)(221010122HPPPP

15、HPPPPnTn记 ,上式为 210nPPPQ.1HQHQT显然，的第一列与 的第一列一样，即 与 第一列一样 .Q 0PQ Q1101QeePeQ 假设 与 两者都是不可约上海森伯格阵，那么由隐式Q定理 与 本质上相等.QHQT1QHQT1H 3H 3 如何寻求正交阵 .0P 由于 (为 的QR分解，那么 QRM M.11111QereRQMe 阐明 第一列即是 第一列的一个倍数，于是，对 阵的第一列非零寻求初等反射阵 使 QM0PM)()(1111110rerMeP其中即.10111ePrMe这阐明 与 具有一样的第一列.0PQ 由于 ,那么)(21IsHIsHMTzyxMe)0,0,(1

16、其中.),()()(,)(32212211212112221211112112212112112211111hhzshhhhshhshytshhhhhhhshshx4.12 双步QR方法：设 为不可约上海森伯格阵.nnHHR1 (a)计算 阵的第一列.即按4.12式计算 M;)0,0,(1TzyxMe (b)确定初等反射阵 使 0P,)(110eMeP即确定初等反射阵 使 330RR;10ezyxR;3300nIRP (c)计算初等反射阵 使 221,nPPPHPPPPHPPPPnn221010122)(为上海森伯格阵，那么 与 第一列一样且 .21QQQ 210nPPPQ3HH 这样上面的算法就完成了从 到 的变换，但没有明显的运用到位移 和 .1H3H1s2s