数值分析(11)QR方法

数值分析数值分析第四节求矩阵全部特征值的QR方法一、矩阵的正交分解,(),,,mnmnnnnnnnARmnrAnAQRQRRRRmnQRRR是列满秩矩阵（），存在分解式其中列法正交矩阵，非奇异上三角阵。若限定阵对角元符号，定理4-4则分解式是唯一的。当时正交阵非奇异上三角阵。数值分析数值分析数值分析数值分析11112112112111221111221,nnnnnTnnTTkkknnAHHHRHHHRQRQHHHRRQAQAHHHHAHHHQQHHHH其中为正交阵1、用Householder变换对A作QR分解有两种情况1221(1,2,,1)1nnknnnnHouseholderHRknHHHHAARR（构造阵则（上三角阵））非奇异数值分析数值分析数值分析数值分析(1)(1)(1)(1)111121(2)(2)(2)11121(2)(2)(2)(2)(2)(2)22212(2)(2)2,,,0,,,0nnnnnnnHAHHHaaaaaAaannARA化矩阵为上三角阵,只须依次将各列对角线下元素化为零(1)(1)(1)(1)12(1)(1)(1)11111,,,(,0,,0)nTAAAHH记对的第一列构造使数值分析数值分析数值分析数值分析(2)(2)(2)(2)2222122,(2)(2)(2)(2)221222(2)(2)(2)(2)1112131(3)(3)(3)22232(3)(3)(3)(3)(3)1233(3)(3)3(,0,,0),,,0,,,000TnnnnnnnAHHaHAHHHaaaaaaaAaaa对的第二列构造使()()()()()12()()()11,,,,,(,,,0,,0)kkkkknkkkTkkkkkkkAAHHaa一般地,设按列分块，构造使)1()1(2)1(1)1()()(2)(1)(,,,,,,knkkkknkkkkkkkAHHHAH数值分析数值分析数值分析数值分析(2)(2)(2)1111()()()()()()12()()(2)(2)(2)(2)1111,11(1)(1),1,(1)1,11,0,,,000000knkkkkkkkkkkknkkknkknknnkknkkkkkknkkkknaaaHAHHHHaaaaaaaaaaaa(1)(1)(1)(1)12(1)(1)(1),1,,,,00kkkknkkknknnAaa数值分析数值分析数值分析数值分析()()1()()22()()()()()1,1()()(())()(0,...,0,,,...,)kkTkknkkkkkikikkkkkkkkkkkkkkkknkHIUUsignaaaUaaa(1)()(1)(1)(1)()()()1212,,,,,,kkkkkkkkknkkknAHAHHH计算，即()(1)()()()()()()()()()()()1(())1()1(())(,1,,)kkkkTkkjjjkkkkTkjjkkkTkkjjkHIUUUUUUjkkn，数值分析数值分析数值分析数值分析(1)(1)(1)?(1,...,).kkkkkkkikaaaikn可以不用上面公式计算，？；思考：()()(1)()(),1,,1(1)()(2),1,,nkkjlljlkkkkkijijjijkkntuaikknaatu()(1)()()()()()()()()()()()1(())1()1(())(,1,,)kkkkTkkjjjkkkkTkjjkkkTkkjjkHIUUUUUUjkkn，数值分析数值分析数值分析数值分析化为上三角阵。矩阵可将阵连乘矩阵用一系列AAHHHHAAHnn1221)1(,1221()()11,2,,1,1,,11(),1,,2nnnkjlljlkkkijijjiHHHHAknjkkntuaikknaatuAA计算。、（）（2）、输出结果。计算值覆盖，输出即为最终计算结果。数值分析数值分析数值分析数值分析121nQHHH计算正交阵(1)(2)(1)1(1)()()121,1,...1...kkknnQIQQHQQHknQHHHTknTkknnknknkkqqqqQ)()(1)()(1)(1)(11)(............记数值分析数值分析数值分析数值分析)1(............)()()()(1)()(1)(1)(11)()1()1()1(1TkkkTknTkkknnknknkkkkTknTkUUIHqqqqHQQ(1)()()()()1()kTkTkTkkTiiikUU)()()1()()(,...,1,)2(1)1(,...,1kjikijkijnklklkilkiutqqnkkjuqtni数值分析数值分析数值分析数值分析用Household方法对矩阵A作正交分解,A=QR。1()()2()2()(())(()1,())1,2,...,1()(()),()(0,...,0,,,...11.(),)nkkkkkkikkkkkkikkkkkTkkkkknkkkTkkknsignaaaUHIUUaaa计算()(1)2.,kkkRHAA计算上三角阵()()(1)()(),1,,1(1)()(2),1,,nkkjlljlkkkkkijijjijkkntuaikknaatu数值分析数值分析数值分析数值分析(1)()(1)3.kkkQIQHQQ计算正交阵()()(1)()()1,,1(1)(2),1,...,nkkiilllkkkkkijijijintqujkknqqtu数值分析数值分析数值分析数值分析nmnnTmmnnnnRAHHHHAQRRHHHHQQRRHHHHA121121121为正交阵其中2,,()mnARmnrAn（）列满秩上三角阵则阵构造nnnmnnmmkRRRORORAHHHHnkRHrHouseholde0),,2,1(121数值分析数值分析数值分析数值分析nmmmnmRRORQAHnnnmnmRQASmnn,法法Matlab调用格式：[q,r]=qr(a)[q,r]=qr(a,0):紧凑格式紧凑格式法结果不一样。法和方法结果一样。正交化方法和HSmnArnmRArHouseholdeSchmidtRAnmnn))(,(,数值分析数值分析数值分析数值分析算法：用Household方法对矩阵A作正交分解,A=QR。1()()2()2()()()(())()1,1,2,...,()(()),()(0,...,0,,11.(),...,)mkkkkkkikkkkkTkkkikkkkkTkkkkkkkmkknsignaaaUaaHIUaU计算()(1)2.,kkkRHAA计算上三角阵()()(1)()(),1,,1(1)()(2),1,,mkkjlljlkkkkkijijjijkkntuaikkmaatu(,,())mnARmnrAn数值分析数值分析数值分析数值分析(1)()(1)3.kkkQIQHQQ计算正交阵()()(1)()()1,,1(1)(2),1,...,nkkiilllkkkkkijijijimtqujkknqqtu数值分析数值分析数值分析数值分析例：用Householder方法求矩阵A的正交分解，即A=QR，其中211010211A(2,1,2),(3,0,0),(5,1,2)125510105101121512514215151102410211331410510110551421115010211TTTTTxyuxyuuHIuuHARQH一：0法数值分析数值分析数值分析数值分析11111111111222(2,1,2),(3,0,0),(1,1,2)11122121121112122331224221331413114(14/11,3/11,4/11),(14/11,5/11,0),TTTTTTTxyuxyuuHIuuHAAxy法二0：02222222212(0,8/11,4/11)10005001121084034551042043105103314115142,0515111021100TTTTuxyuuHIuuQHHRQA数值分析数值分析Householder变换的应用12数值分析数值分析2、用Givens变换对A作QR分解2、用Givens变换对A作QR分解数值分析数值分析数值分析数值分析0:......::...QRAnnnnnmnmQRA0:......::...nmmmnmQRA0...00:......::...数值分析数值分析二、求矩阵全部特征值的QR方法60年代出现的QR算法是目前计算中小型矩阵的全部特征值与特征向量的最有效方法。理论依据：任一非奇异实矩阵都可分解成一个正交矩阵Q和一个上三角矩阵R的乘积，而且当R的对角元符号取定时，分解是唯一的。11QRQR(1,2,).kkkkkkAQRkARQAAA方法的基本思想是利用矩阵的分解通过迭代格式将化成相似的上三角阵（或分块上三角阵），从而求出矩阵的全部特征值与特征向量。数值分析数值分析111111121112,,(2,3,)kkAAQRQARARQQAQAAAAkAA由即。于是即与相似。同理可得，与相似。故与有相同的特征值。可证，在一定条件下，基本QR方法产生的矩阵序列｛Ak｝“基本”收敛于一个上三角阵（或分块上三角阵）。即主对角线（或主对角线子块）及其以下元素均收敛，主对角线（或主对角线子块）以上元素可以不收敛。特别的，如果A是实对称阵，则｛Ak｝“基本”收敛于对角矩阵。数值分析数值分析矩阵的正交相似化简,,1