特征值问题的计算方法.ppt

《特征值问题的计算方法.ppt》由会员分享，可在线阅读，更多相关《特征值问题的计算方法.ppt（54页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、特征值问题的计算方法现在学习的是第1页，共54页1212det()()()()pnnnpIA 其中其中12;()pijnnnnij 称称 为为 的的代数重数代数重数（简称（简称重数重数）；）；ini()iimnrankIA 为为 的的几何重数几何重数。i iimn 2Def设设 ，n nAC iimn 对于矩阵对于矩阵 的的特征值特征值 ，如果，如果Ai，则称该特征值，则称该特征值 为为 的一个的一个半单半单特征值。特征值。Ai 若若 的所有特征值都是的所有特征值都是半单半单的，则称的，则称 是是非亏损非亏损的。的。AA是是非亏损非亏损的等价条件是的等价条件是 有有n个个线性无关线性无关的特征

2、向量的特征向量AA现在学习的是第2页，共54页3Def设设 ，,n nA BC 若存在矩阵若存在矩阵 ，使得，使得P1BP AP 则称则称 和和 是是相似相似的。的。AB相似相似矩阵有相同的特征值矩阵有相同的特征值1AxxPAP PxPx BPxPx Axx 设设寻求已知矩阵寻求已知矩阵 的的相似相似矩阵矩阵 ，要求：，要求：矩阵矩阵 的的特征值特征值和和特征向量特征向量容易计算容易计算ABB本章本章QR算法的算法的基本思想：基本思想：现在学习的是第3页，共54页8 1 1.Th1(,)iir 设设 ，有，有 r个个互不相同互不相同的特征值的特征值 ，n nAC 其其重数重数分别为分别为 ，则

3、一定存在，则一定存在非奇异非奇异矩阵矩阵11()(),();iiinniikiJdiag JJCir 使得使得（Jordan分解）分解）1(,)in ir n nPC 其中其中112(),(),()rP APdiag JJJJ 11()iijiiJ ()jiJ 且除了且除了 的的排列排列次序次序外，外，是是唯一唯一的。的。J称作称作 的的Jordan标准型标准型AJ现在学习的是第4页，共54页8 1 2.Th设设 ，则存在，则存在酉酉矩阵矩阵 ，使得：，使得：n nAC （Schur分解）分解）其中其中 是是上三角上三角矩阵，且适当选择矩阵，且适当选择 ，可使，可使 的元素的元素HUAUT n

4、 nUC TUT按任意指定的顺序排列。按任意指定的顺序排列。8 1 3.Th设设 ，令，令()n nijAaC （圆盘圆盘定理）定理）/*Disc Theorem*/则则1():;,iiiijj iG AzCzaain 12()()()()nAG AGAGA 现在学习的是第5页，共54页8 1 4.Th设设 为为对称对称矩阵，则存在矩阵，则存在正交正交矩阵矩阵n nAR （谱谱分解定理）分解定理）/*Spectral Decomposition*/其中其中 是是 的的n个特征值。个特征值。n nQR 使得使得1(,)TnQ AQdiag 1,nA8 1 5.Th设设 为为对称对称矩阵，且矩阵，

5、且 的特征值为的特征值为n nAR （极大极小极大极小定理）定理）其中其中 表示表示 中所有中所有k维子空间的全体。维子空间的全体。则有则有12n A0maxminniTiTuu Auu u 10min maxnn iTTuu Auu u nk nR现在学习的是第6页，共54页设设 为为对称对称矩阵，其特征值分别为矩阵，其特征值分别为8 1 6.Th,n nA BR （Weyl定理）定理）则有则有1212;nn 21 2;,iiABin 说明：说明：对称对称矩阵的特征值总是矩阵的特征值总是良态良态的。的。注意注意：实际问题中矩阵一般都是由：实际问题中矩阵一般都是由计算计算或或实验实验得到，得到

6、，本身必然存在本身必然存在误差误差，不妨假设，不妨假设 BAA 21 2;,iiAin 现在学习的是第7页，共54页2 幂法与幂法与反幂法反幂法/*Power Method and Reversed Power Method*/幂法幂法是计算一个矩阵的是计算一个矩阵的模最大模最大的特征值和对应的特征的特征值和对应的特征 向量的一种向量的一种迭代迭代方法（又称为方法（又称为乘幂法乘幂法）。）。一、一、幂法幂法的的基本思想与算法基本思想与算法假设假设 是可是可对角化对角化的，即的，即 存在如下分解：存在如下分解：n nAC A1AXX 其中其中1(,)ndiag 1;,n nnXxxC 不妨假设不

7、妨假设12n 对于对于0nuC 01122;nniuxxxC 现在学习的是第8页，共54页011nnkkkjjjjjjjA uA xx 11121()njkkjjjxx 011211()knjkjjkjA uxx 11()x k 01kkkA uu 说明：当说明：当k充分大时充分大时,的一个的一个近似特征向量近似特征向量为为1 特征向量可以相差一个特征向量可以相差一个倍数倍数现在学习的是第9页，共54页01kkkA uu 因为向量因为向量 中含有中含有未知量未知量 ，实际不能计算，实际不能计算1 ku但我们关心的仅是但我们关心的仅是 的的方向方向，故作如下处理：，故作如下处理：0kkkA uu

8、 令令其中其中 为为 的的模最大分量模最大分量k 0kA u11121011121()()njkkjjkjnkjkkjjjxxA uxx 11()xkx 现在学习的是第10页，共54页 幂法迭代幂法迭代算法算法：1kkkAuu 1limlimlimkkkkkkAuu 1Axx 1k For k=1,2,3,1kkyAu kky if1kkuu 输出输出 和和kuk kkkyu 001,uu 设设 和和 均均收敛收敛，由，由算法算法知知kuk 幂法幂法可以计算矩阵的可以计算矩阵的模最大模最大的特征值和对应的特征向量的特征值和对应的特征向量1ku 现在学习的是第11页，共54页解：解：Step12

9、 1013 1014A 例例1 1：利用利用幂法幂法求下列矩阵求下列矩阵 的模的模最大的特征值及相应的最大的特征值及相应的特征向量特征向量.A01 1 1()Tu (取初始向量为取初始向量为 )10355()TyAu 15 11131 15()Tyu Step2212311555()TyAu 25 222231112525()Tyu 现在学习的是第12页，共54页Step3321 84 24 92(.)TyAu34 92.3330 36590 85371(.)Tyu Step4431 58543 92684 8537(.)TyAu 44 8537.4440 32660 80901(.)Tyu

10、特征值及相应的特征值及相应的特征向量特征向量精确值精确值为为:4 7321.0 26790 73201(.)Tu 现在学习的是第13页，共54页 幂法幂法的收敛性的收敛性：8 2 1.Th12p 设设 有有 p个个互不相同互不相同的特征值满足：的特征值满足：n nAC 且且模最大模最大特征值特征值 是是半单半单的，如果初始向量的，如果初始向量 在在的特征子空间上的的特征子空间上的投影投影不为零，则由不为零，则由幂法幂法算法产生的算法产生的1 ku向量向量序列序列 收敛到收敛到 的一个特征向量的一个特征向量 ，且，且数值数值1 0u1 1x序列序列 收敛到收敛到 。k 1 特征特征子空间：子空间

11、：0Vx Axx 现在学习的是第14页，共54页证明：证明：设设 有如下有如下Jordan分解：分解：A11(,)pAXdiag JJX iinniJC 是属于是属于 的的Jordan块构成的块上三角矩阵块构成的块上三角矩阵i 111nJI 是是半单半单的特征值的特征值1 10yX u 令令将将 和和 如下分块：如下分块：yX12(,)TTTTpyyyy 12pnnn12(,)pXXXX 12pnnn1010(,)kkkpA uXdiag JJXu 111222kkkPppX J yX J yX J y 现在学习的是第15页，共54页111222kkkpppX yX J yX J y 2111

12、2211()()pkkkppJJX yXyXy 0111222kkkkPppA uX J yX J yX J y 021122111()()kpkkppkJA uJX yXyXy1111110()/()kiiiJJ 01110lim()kkkA uX y 现在学习的是第16页，共54页记记11111X yxX y AXXJ 11111AXX JX 11111AX yX y 111Axx 1kkkAuu 011kkkA u 0110kkkkA uA u 1111()kX yukX y 1limkkux 是属于是属于 的一个特征向量的一个特征向量1 1x1kkkAuu 1()kk 现在学习的是第1

13、7页，共54页几点说明几点说明：定理定理8.2.1条件不满足时，条件不满足时，幂法幂法产生的产生的向量向量序列序列 ku可能有可能有若干若干个收敛于不同向量的个收敛于不同向量的子序列子序列；幂法幂法的收敛的收敛速度速度取决于取决于 的大小；的大小；21:021122111()()kpkkppkJA uJX yXyXy加速加速方法：适当选取方法：适当选取 ，对，对 应用应用幂法幂法AI 称之为称之为原点平移法原点平移法1Axx 1Axxxx 1()()AI xx 原点平移法原点平移法不改变不改变矩阵矩阵 的特征向量的特征向量A现在学习的是第18页，共54页幂法幂法可以计算第二个可以计算第二个模最

14、大模最大特征值特征值 2 常用常用的方法：的方法：降阶降阶方法（方法（收缩收缩技巧）技巧）设已经计算出设已经计算出模最大模最大特征值特征值 及其特征向量及其特征向量 1 1x111Axx 对向量对向量 ，采用，采用复复的的Household变换计算变换计算酉酉矩阵矩阵1xP11 1Pxe 1111HPAPePAx 1111Px 11e 10HPAPB 其中其中 是是n-1阶方阵阶方阵B2 为为 的的模最大模最大特征值特征值 B现在学习的是第19页，共54页二、二、反幂法的反幂法的基本基本思想与算法思想与算法反幂法反幂法是求一个矩阵的是求一个矩阵的模最小模最小的特征值和对应的特征的特征值和对应的

15、特征 向量的一种向量的一种迭代迭代方法（又称为方法（又称为反迭代法反迭代法）。）。设设 ，则，则Axx 11A xx 1A 对对 应用应用幂法幂法就可以求得矩阵就可以求得矩阵 的的模最小模最小的特征值和相应的特征向量。的特征值和相应的特征向量。A不妨假设不妨假设 的特征值为的特征值为11nn A则则 的特征值为的特征值为11nn 1A 1ii 现在学习的是第20页，共54页 反反幂法幂法算法算法：For k=1,2,3,1kkAyz kky if1kkzz 输出输出 和和kzk kkkyz 001,zz limknkzx nnnAxx 若若 和和 均均收敛收敛，由，由幂法幂法知知kzk 1kz

16、 limknk 收敛收敛速度速度取决于取决于 的大小的大小1:nn 反反幂法幂法每次迭代都需要每次迭代都需要求解方程组求解方程组1kkAyz 现在学习的是第21页，共54页 带位移的带位移的反反幂法幂法：实际应用中，实际应用中，反反幂法幂法主要用于求主要用于求特征向量特征向量。且用某种方法已经得到且用某种方法已经得到 的特征值的特征值 的的近似值近似值A1 1 对矩阵对矩阵 采用采用反反幂法幂法迭代格式为：迭代格式为：AI 1 记记假设假设 的特征值满足的特征值满足120n A1()kkAI vz kkkvzv For k=1,2,3,因为方程组的系数矩阵因为方程组的系数矩阵Doolittle

17、分解化为两个分解化为两个三角三角方方是是固定固定的，通常采用的，通常采用(选主元选主元)AI 程组求解，从而减少工作量。程组求解，从而减少工作量。现在学习的是第22页，共54页AILU 求解方程组求解方程组 化为：化为：1()kkAI vz 1kkkkLyzUvy 带位移的带位移的反反幂法幂法迭代格式：迭代格式：For k=1,2,3,1kkLyz kkUvy kkkvzv 收敛收敛速度速度取决于取决于 的大小的大小12 当当 时，收敛速度会非常快时，收敛速度会非常快1 设矩阵设矩阵 存在存在Doolittle分解：分解：AI 现在学习的是第23页，共54页解：解：2 1013 1014A 例

18、例2 2：用用带位移的带位移的反反幂法幂法求矩阵求矩阵12679.）的近似特征向量。）的近似特征向量。33 对应特征值对应特征值 （精确值精确值为为A1 2679.AILU 其中其中1136591027310 1.L 073211000366210000011.U 01 1 1()Tz 10Lyz 11 00000 63661 9999.y Step1现在学习的是第24页，共54页反反幂法幂法具有一次具有一次“迭代性迭代性”11Uvy 16776 39384960 0001815 8199.v Step221Lyv 21 00001 10796 0073.y 22Uvy 220327 4114

19、880 725446 73.v 2221 00000 73200 2679.vzv 所求所求近似近似特征向量为：特征向量为：现在学习的是第25页，共54页3 Jacobi方法方法Jacobi法：计算法：计算实对称实对称矩阵全部特征值和相应特征向量矩阵全部特征值和相应特征向量 基本基本思想思想对对,n nTARAA Q存在存在正交正交矩阵矩阵 ，满足，满足12(,)TnQ AQdiag 记记12(,)nQq qq 则则1 2;,iiiAqq in 寻找寻找正交相似正交相似变换变换 ，将矩阵，将矩阵 约化为约化为对角阵对角阵即可即可QA正交相似正交相似变换求法：通过变换求法：通过Givens变换来

20、实现变换来实现现在学习的是第26页，共54页 经典经典Jacobi方法方法设设,n nijijjiAaRaa 令令1122222111()()()nnniiijFiijj iE AAaa 非对角非对角“范数范数”当当 时，时，趋于一个趋于一个对角阵对角阵0()E A A(,)(,)TGp qAG p q 先来研究一下矩阵先来研究一下矩阵的元素和矩阵的元素和矩阵 的的元素元素之间的之间的关系关系。AGivens变换记为变换记为 ，下面通过，下面通过Givens变换变换(,)G p q 对矩阵对矩阵 进行进行约化约化，使得，使得0()E A A现在学习的是第27页，共54页例如例如取取424;,n

21、pq cos;sincs 记记11a12a24a13a14a13a22a12a23a23a33a34a14a24a34a44a10s000c000100s 0c10s000c000100s 0c11a12a 13a14a13a 23a33a34a10s000c000100s 0c 11a 13a 13a 33a ()ipipiqbcasa;iqipiqbsaca (,)ip q 现在学习的是第28页，共54页11a 13a 13a 33a 222()pppppqqqbc ascas a 222qqpppqqqbs ascac a 22()()pqpqppqqbcsasc aa选取适当的选取适当

22、的 ，由，由Givens变换将矩阵的变换将矩阵的下三角元素下三角元素 尽可能多的化为尽可能多的化为零零：即：即非对角非对角“范数范数”尽可能的尽可能的小小。如果如果 ，则取，则取0pqa 10;cs否则否则，令，令2tan;qqpppqaastca 2210tt 220()()pqpqppqqbcsasc aa首先首先由由 确定确定 现在学习的是第29页，共54页2210tt 21sgn()t 14()t 2211111cossectantc ;stc 其次其次确定旋转平面确定旋转平面(,)p q2222211()nniiiiFFiiEBBbAb由由F-范数的范数的正交不变性正交不变性设设 经

23、过一次经过一次正交相似正交相似变换后变为矩阵变换后变为矩阵AB22222211()nniiiippqqppqqiibaaabb现在学习的是第30页，共54页222222222()()()()ppqqppqqpqEBEAaabbEAa 222222ppqqppqqpqaabba 注意注意到到旋转平面旋转平面 的选取方法：的选取方法：(,)p q1maxpqijij naa 经典经典Jacobi方法的迭代格式：方法的迭代格式：101 2 3();,kTkijkkkAaG AGAA k 8 3 1.Th对于经典对于经典Jacobi方法产生的矩阵序列方法产生的矩阵序列 ，kA存在存在 的特征值的一个排

24、列的特征值的一个排列 满足满足A12,n 12lim(,)knkAdiag 证明见教材证明见教材现在学习的是第31页，共54页 经典经典Jacobi方法的迭代算法方法的迭代算法给定矩阵给定矩阵(),ijijjiAaaa选取选取最佳旋转平面最佳旋转平面 ：(,)p q1maxpqijij naa For k=1,2,3,21sgn();t 2qqpppqaaa 计算计算211;tc ;stc ipipiqacasa ;iqipiqasaca ,ifip q 计算计算222pppppqqqac ascas a222;qqpppqqqas ascac a 220()()pqpqppqqacsasc

25、aa ()E A 直到直到需比较需比较 个元素个元素12()n n 现在学习的是第32页，共54页习惯上称习惯上称 次次Jacobi迭代为一次迭代为一次“扫描扫描”12()n n 循环循环Jacobi方法方法每一次每一次Jacobi迭代不是去选择迭代不是去选择最佳旋转平面最佳旋转平面，而是而是直接按照某种直接按照某种预先指定预先指定的顺序来的顺序来“扫描扫描”自然自然顺序：顺序：1 21 312 32 42(,)(,),(,),(,);(,),(,),(,);p qnn 3 43 531(,),(,),(,);(,);nnn 按照按照自然自然顺序的循环顺序的循环Jacobi方法是方法是渐进平方

26、渐进平方收敛的收敛的现在学习的是第33页，共54页4 QR 方方 法法 基本基本思想思想利用利用正交相似正交相似变换将一个给定的矩阵逐步约化变换将一个给定的矩阵逐步约化为为上三角上三角矩阵或矩阵或拟上三角拟上三角矩阵的一种矩阵的一种迭代迭代方法方法 QR方法的方法的迭代迭代格式格式设设0n nAAC 令令111ARQ 011AQ R 对矩阵对矩阵 进行进行QR分解分解0A122AQ R 再对矩阵再对矩阵 进行进行QR分解分解1A一、一、QR基本迭代基本迭代方法方法QR方法是目前计算矩阵方法是目前计算矩阵全部全部特征值的特征值的最最有效有效的方的方法之一；具有法之一；具有收敛快收敛快、算法、算法

27、稳定稳定等特点。等特点。现在学习的是第34页，共54页一般地有：一般地有：1mmmAQ R 1 2;,mmmAR Qm 1HmmmmAQ AQ 矩阵序列矩阵序列 中每一个矩阵都与原矩阵中每一个矩阵都与原矩阵 相似相似 mAAQR方法的迭代算法：方法的迭代算法：1mmmAQ R mmmAR Q For m=1,2,3,直到直到 近似近似为为上三角上三角阵阵mA由由迭代格式迭代格式同时还得到：同时还得到：2112HHHmmmAQQ Q AQQQ HmmmAQ AQ 记记12mmQQQQ 11mmmAQR 代入代入11mmmmQ QRAQ 现在学习的是第35页，共54页11mmmmQ QRAQ 等式

28、两端同时右乘等式两端同时右乘21mRR R112121mmmmmmQ QRRR RAQ RR R 记记21kkRRR R 11mmmmQRAQ R 21111111mmmmmmQRA QRA Q RA mmmAQ R 即即111 1()mmA er q 其中其中 是是 的的第一列第一列，是是 的相应元素的相应元素1()mq11rmQmR可以看作是对矩阵可以看作是对矩阵 用用 为为1()mqA初始向量的初始向量的幂法幂法所得到的向量。所得到的向量。1eQR方法与方法与幂法幂法的关系：的关系：现在学习的是第36页，共54页 QR方法的方法的收敛收敛性性8 4 1.Th设设 的特征值满足的特征值满足

29、 ，且，且 的的LU则由则由QR迭代算法产生的矩阵迭代算法产生的矩阵 的对角线以的对角线以120n Ai()mmijAa()miiaY第第i行是行是 对应于对应于 的的左特征左特征向量；若向量；若 有有 分解，分解，AY下的元素趋于下的元素趋于0，同时对角元素，同时对角元素 趋于趋于1(,)iin （QR方法的方法的收敛收敛性质）性质）证明：证明：令令1;XY 1(,)ndiag 则有则有AXY mmmAXYXLU ()mmmXLU ()mmX IEU 其中其中mmmIEL 0limmmE 现在学习的是第37页，共54页01(,)iirin且且()mmmAX IEU ()mmQR IEU 1(

30、)mmmAQ IRE RRU 1mIRE R 当当m充分大时，充分大时，存在唯一存在唯一QR分解：分解：1mmmIRE RQ R 01()(,)miirin 且且mmQ RI 当当m充分大时充分大时limlimmmmmQRI()()mmmmAQQR RU QR （QR分解）分解）记记 的的QR分解为：分解为：XQR X现在学习的是第38页，共54页为保证上述为保证上述QR分解中上三角矩阵的对角元为分解中上三角矩阵的对角元为正正，令，令111(,)nnDdiag 11211;(,)nnnnuuDdiaguu 11221()()mmmmmmAQQ D DD DR RU mmQ R 由由QR分解唯一

31、性知：分解唯一性知：2112()HHHmHHmmmmmmAQ AQDDQ Q AQQ D D代入代入11HAXYXXQR R Q 12112()HHmHmmmmADDQ R R Q D D 趋于趋于上三角上三角阵阵现在学习的是第39页，共54页实际应用中遇到的多数特征值问题都是关于实际应用中遇到的多数特征值问题都是关于实矩阵实矩阵的，所以自然希望设计只涉及实数运算的的，所以自然希望设计只涉及实数运算的QR迭代。迭代。实实QR迭代迭代格式格式设设1n nAAR 二、实二、实Schur标准形标准形kkkAQ R 1kkkAR Q For k=1,2,3,为为正交正交矩阵矩阵为为上三角上三角阵阵kQ

32、kR8 4 2.Th（实（实Schur分解）分解）设设n nAR ，则存在，则存在正交正交矩阵矩阵n nQR ，满足：，满足：11121222mmTmmRRRRRQ AQR 其中其中 为为实数实数或具有或具有一对复共轭一对复共轭特征值的特征值的2阶方阵阶方阵iiR现在学习的是第40页，共54页iiiiiiR 220()iiiiIR 特征值为特征值为iij，其中，其中 为为虚单位虚单位j见文献见文献1311121222mmmmRRRRRR矩阵矩阵称为称为 的的Schur标准形标准形A定理定理8.4.2说明：只要求得矩阵的说明：只要求得矩阵的Schur标准形，标准形，就很容易求得矩阵的就很容易求得

33、矩阵的全部全部特征值。特征值。缺陷缺陷：很难得到很难得到Q现在学习的是第41页，共54页H 011h21h0022h32h12h0023h33h13h043h21,nh 31,nh 11,nh 41,nh 11,nnh 2,nh3,nh1,nh4,nh1,nnh 22,nh 32,nh 12,nh 0001,n nh,n nh042,nh 12,nnh 称下述形状的矩阵为称下述形状的矩阵为上上Hessenberg矩阵矩阵三、上三、上Hessenberg化化现在学习的是第42页，共54页设设 ，n nAR 寻求非奇异矩阵寻求非奇异矩阵 ，使得，使得 为上为上Hessenberg 矩阵矩阵，然后再

34、对，然后再对 进行进行 迭代。迭代。1QAQ Q1QAQ QR 基本基本思想思想和和约化约化过程：过程：ijAa 记矩阵记矩阵Q下面采用下面采用Householde变换寻找变换寻找Step1 选取选取Householde变换变换 ，使得，使得1H111Hpe 其中其中1111aAA 令令11100HH 11111111101000aH AHHAH 现在学习的是第43页，共54页1111 1111aHHH AH 11a p2A0 2111AH A H 其中其中Step2 选取选取Householde变换变换 ，使得，使得2H221Hqe 下面对作下面对作 同样的处理，以此类推同样的处理，以此类推

35、2A其中其中223AA 令令22100HH 2222322101000H A HAHH 22232HH A H 现在学习的是第44页，共54页令令22100HH 1121122122101000aH H AH HHpeAH 111222apeH AH 3232AH A H 其中其中 11a p3A0 0 q0 22222232H A HHH A H 记记2112H H AH H 0 11h21h0 0 22h32h12h 12H H为为正交正交阵阵现在学习的是第45页，共54页按照前述方法，经过按照前述方法，经过n-2步后，可以得到：步后，可以得到：221122nnHH H AH HHH 其中

36、其中H 011h21h0022h32h12h0023h33h13h043h21,nh 31,nh 11,nh 41,nh 11,nnh 2,nh3,nh1,nh4,nh1,nnh 22,nh 32,nh 12,nh 0001,n nh,n nh042,nh 12,nnh 现在学习的是第46页，共54页122nPH HH 记记 ，则，则TAPHP 称分解式称分解式 为矩阵为矩阵 的上的上Hessenberg分解分解TAPHP A 上上Hessenberg分解分解算法算法（8.4.1）1,(:,)vhouse A kn k For k=1:n-211(:,:)()(:,:)TA kn k nIvv

37、A kn k n 1111(:,:)(:,:)()TAn knAn kn Ivv 然后对上然后对上Hessenberg矩阵进行矩阵进行QR迭代迭代设设Hyy TP APyy APyPy 现在学习的是第47页，共54页上上Hessenberg矩阵的矩阵的QR迭代算法：迭代算法：1mmmHQ R mmmHR Q For m=1,2,3,直到直到 的的次对角次对角元素趋于元素趋于零零mH注意注意：此时的此时的QR分解可采分解可采用用Givens变换来实现；变换来实现；用用Givens变换得到的变换得到的RQ仍仍然为上然为上Hessenberg矩阵；矩阵；上上Hessenberg分解不唯一。分解不唯一

38、。若上若上Hessenberg矩阵的次对角元素均不为矩阵的次对角元素均不为零零，则称则称之为之为不可约不可约的上的上Hessenberg矩阵。矩阵。7Def定理定理8.4.3说明：在说明：在不可约不可约的条件下，的条件下，上上Hessenberg分解在相差一个分解在相差一个正负号正负号的意义下的意义下唯一唯一。见文献。见文献6现在学习的是第48页，共54页 实用的实用的QR迭代算法（仅计算迭代算法（仅计算特征值特征值）Step1 由算法由算法8.4.1计算计算上上Hessenberg矩阵矩阵：()TAHP AP Step2（QR分解分解）For k=1:n-11(),()(,),(,)c k

39、s kGivens H k k H kk 1111()()(:,:)(:,:)()()c ks kH k knH k kns kc k Step3（计算（计算RQ）Step4 重复步骤重复步骤Step23，直到，直到下次对角下次对角元素趋于元素趋于零零1111()()(:,:)(:,:)()()c ks kHn k kHn k ks kc k 现在学习的是第49页，共54页四、四、三对角三对角化（化（对称对称矩阵的矩阵的上上Hessenberg化）化）TP APH 设设 为为对称对称矩阵，矩阵，的的上上Hessenberg分解为分解为n nAR A其中其中 为为对称三对角对称三对角矩阵。矩阵。

40、HStep1 选取选取Householde变换变换 ，使得，使得1H111Hpe 其中其中11111TaAA 令令11100HH 111111111101000TaH AHHHA 11111 1111TaHHH AH 2111AH A H 其中其中 11ap2A0p0现在学习的是第50页，共54页111H A H主要主要工作量工作量在于计算在于计算1THIvv 1111()()TTH AHIvvA Ivv 21111TTTTAAvvvv Avv Avv21111()()TTTTAAv vv Avvv Avv 令令112;()TuAvuv u v 1111()TTTTH A HAuvvuv v

41、u v 1TTAvv 11122()()TTTTAuv uv vv uv uv减少减少运算量运算量现在学习的是第51页，共54页 三对角三对角分解分解算法算法（8.4.2）1,(:,)vhouse A kn k For k=1:n-211(:,:)uA kn kn v 1111(:,:)(:,:)TTA kn knA kn knvv 12()TTuu v v 211(,)(:,)A kkA kn k 11(,)(,)A k kA kk 2020(:,)(,:)A kn kA k kn现在学习的是第52页，共54页五、五、隐式隐式对称对称的的QR迭代方法（仅适用于迭代方法（仅适用于对称对称矩阵）

42、矩阵）带原点带原点位移位移的的QR迭代格式：迭代格式：假设已经对矩阵假设已经对矩阵 完成完成三对角三对角分解，得到三对角矩阵分解，得到三对角矩阵A为了为了加速加速收敛，下面选取适当的收敛，下面选取适当的位移位移进行进行QR迭代。迭代。HkkkkHIQ R 10 1;,kkkkHR QI k 迭代过程中产生的矩阵序列迭代过程中产生的矩阵序列 均为均为三对角三对角矩阵矩阵kH的选取方法：的选取方法：k 著名的著名的Wilkinson位移位移一种简单的取法一种简单的取法-(,)kkHn n 现在学习的是第53页，共54页11111(:,:)nnknnHnn nn 记矩阵记矩阵令令12nn 221sgn()knn 取取11(:,:)kIHnn nn 1110nnnn 221 21,nn k 的的含义含义：是取上述矩阵两个：是取上述矩阵两个特征值中靠近特征值中靠近 的那个特征值的那个特征值n 收敛性见文献收敛性见文献4现在学习的是第54页，共54页