瑞利商加速定理14课件.ppt

1、1第第8 8章章 矩阵特征值问题计算矩阵特征值问题计算 8.1 8.1 引引 言言 物理、力学和工程技术的很多问题在数学上都归结为求矩阵的特征值问题.例如，振动问题（大型桥梁或建筑物的振动、机械的振动、电磁振荡等），物理学中某些临界值的确定，这些问题都归结为下述数学问题)2()(det)det()(12211212222111211的项次数naaaaaaaaaaaaAInnnnnnnnnn 定义定义1.1.（1）已知 ，则称nnijaA)(为 的特征多项式特征多项式.A2 的特征方程A0)det()(AI（1.1）一般有 个根(实的或复的，重根按重数计算)(当 时，为实系数 次代数方程，其复根

2、共轭成对出现)，称为 的特征值特征值.nnnA R0)(nA 用 表示 的所有特征值的集合.)(AA0)(xAI（1.2）的非零解 称为矩阵 的对应于 的特征向量特征向量.xA （2）设 为 特征值，相应的齐次方程组 A 例例1 1 求 的特征值及特征向量，其中 A3.210131012A 解解 矩阵 的特征方程为 A,08147)det()(23AI求得 特征值为：A.4,2,1321对应于各特征值的特征向量分别为：.121,101,111321xxx4 定理定理1 1 设 为 的特征值且 ，其中 ,则nnA RxAx0 x （1）为 的特征值（为常数 );ccAc0c （2）为 的特征值，

3、即 ppIA;)()(xppIA （3）为 的特征值；kkA （4）设 为非奇异阵，那么 且 为 特征值，即A011A.11xxA 定理定理2 2 设 为 阶矩阵 特征值，则),2,1(niinnnijaA)(5.)det()2();()1(2111nniiiniiAAtra 定理定理3 3 设 ，则 nnA R).()(AAT 定理定理4 4 设 为分块上三角阵，即 A,22211211mmmmAAAAAAA其中每个对角块 均为方阵，则 iiA.)()(1miiiAA6 定理定理5 5 设 与 为相似矩阵（即存在非奇异阵 使 )，则ABPAPPB1 （1）与 有相同的特征值；AB （2）如果

4、 是 特征向量，则 是 特征向量.yBPyA 定理5说明，一个矩阵经过相似变换后特征值不变.定义定义2 2 设 ，如果 有一个重数为 的特征值 且对应于 的矩阵 的线性无关的特征向量个数少于 (一般 )，称 为亏损矩阵亏损矩阵.nnA RAkAkkA 定理定理6 6 （1）可对角化，即存在非奇异矩阵 使 nnA RPnAPP2117的充要条件是 具有 个线性无关的特征向量.An （2）如果 有 个 不同的特征值 则对应的特征向量 线性无关.nnA Rm)(nm,21mmxxx,21 定理定理7 7（对称矩阵的正交约化）设 为对称矩阵，则：nnA R （1）的特征值均为实数；A （2）有 个线性

5、无关的特征向量；An （3）存在一个正交矩阵 使得 P,211nAPP8且 为 特征值，而 的列向量 为 的对应于 的特征向量.A),1(nii),(21nuuuPjuAj 定义定义3 3 设 .令：nnijaA)(1);,2,1(1niarnijjiji (2)集合 .称复平面上以 为圆心，以 为半径的所有圆盘为 的Gerschgorin圆盘.C,zrazzDiiiiiiairA 定理定理8 8 （Gerschgorin圆盘定理）（1）设 ，则 的每一个特征值必属于下述某个圆盘之中 nnijaA)(A).,2,1(1niaranijjijiii9或者说，的特征值都在复平面上 个圆盘的并集中.

6、An （2）如果 有 个圆盘组成一个连通的并集 ，且 与余下 个圆盘是分离的，则 内恰包含 的 个特征值.AmSSmn SAm 特别地，如果 的一个圆盘 是与其他圆盘分离的(即孤立圆盘)，则 中精确地包含 的一个特征值.AiDiDA 证明证明 只就(1)给出证明.设 为 的特征值，即 A.0),(,21TnxxxxxAx其中记 考虑 的第 个方程，即 0max1xxxinikxAxk,1knjjkjxxa10或,)(nkjjkjkkkxaxa于是,nkjkjknkjjkjkkkaxxaxa即.knkjkjkkraa 这说明，的每一个特征值必位于 的一个圆盘中，并且相应的特征值 一定位于第 个圆

7、盘中（其中 是对应特征向量 绝对值最大的分量的下标）.AAkkx11 利用相似矩阵性质，有时可以获得 的特征值进一步的估计，即适当选取非奇异对角阵 A112111nD并做相似变换 .适当选取 可使某些圆盘半径及连通性发生变化.nnijijaADD1,2,1(ii),n12 例例2 2 估计矩阵 411101014A特征值的范围.解解 的3个圆盘为 A,24:,2:,14:321DDD 由定理8，可知 的3个特征值位于3个圆盘的并集中，由于 是孤立圆盘，所以 内恰好包含 的一个特征值 （为实特征值），即A1D1DA113531 的其他两个特征值 包含在 的并集中.A32,32,DD 现选取对角阵

8、 9.0111D做相似变换.49.09.09100101411ADDAA14 的3个圆盘为 1A.8.14:,910:,14:321EEE 显然，3个圆盘都是孤立圆盘，所以，每一个圆盘都包含 的一个特征值（为实特征值）且有估计 A.2.28.5,919919,5332115 定理定理9 9 (Schur定理）设 ，则存在酉阵 使 nnA RU),(22211211上三角阵RrrrrrrAUUnnnnH其中 为 的特征值.A),2,1(nirii 当 时，如果限制用正交相似变换，由于 有复的特征值，不能用正交相似变换约化为上三角阵.nnA RAA16 定理定理10 10 （实Schur分解）设

9、，则存在正交矩阵 使 nnA RQ,22211211mmmmTRRRRRRAQQ其中对角块 为一阶或二阶方阵，且每个一阶 是 的实特征值，每个二阶对角块 的两个特征值是 的两个共轭复特征值.),2,1(miRiiiiRAjjRA 定义定义4 4 设 为 阶实对称矩阵，对于任一非零向量 ，称 Anx),(),()(xxxAxxR17为对应于向量 的瑞利（Rayleigh）商.x 定理定理11 11 设 为对称矩阵（其特征值次序记为 ，则nnA R)21n.),(),(min.2;),(),(max.2);R(),(),(.10R0R11xxxAxxxxAxxxxxAxxxnxxnnnn对任何 证

10、明证明 只证 1.由于 为实对称矩阵，可将 对应的特征向量 正交规范化，则有 n,21Anxxx,21.),(ijjixx18 设 为 中任一向量，则有展开式 0 xnR,0,211221niiniiixxx于是.),(),(1212niiniiixxxAx从而1成立.结论1说明瑞利商必位于 和 之间.n119 8.2 8.2 幂法及反幂法幂法及反幂法 8.2.1 8.2.1 幂法幂法 幂法是一种计算矩阵主特征值（矩阵按模最大的特征值）及对应特征向量的迭代方法，特别适用于大型稀疏矩阵.反幂法是计算海森伯格阵或三对角阵的对应一个给定近似特征值的特征向量的有效方法之一.设实矩阵 有一个完全的特征向

11、量组，其特征值为 ，相应的特征向量为 .已知 的主特征值是实根，且满足条件 nnijaA)(n,21nxxx,21A,321n（2.1）现讨论求 及 的方法.11x20 幂法的基本思想是任取一个非零的初始向量 ，由矩阵 构造一向量序列 0vA,011021201vAAvvvAAvvAvvkkk（2.2）称为迭代向量.由假设，可表示为 0v),0(122110设nnxxxv（2.3）于是 21),()/(1112111122211101kkniikiiknknnkkkkkxxxxxxvAAvv其中.)/(21niikiikx由假设),3,2(1/1nii故,0limkk（2.4）.lim111x

12、vkkk从而 22 这说明序列 越来越接近 的对应于 的特征向量，或者说当 充分大时 kkv1A1k,111xvkk（2.5）即迭代向量 为 的特征向量的近似向量（除一个因子外）.kv1 再考虑主特征值 的计算，用 表示 的第 个分量，则 1ikv)(kvi,)()()()()()(1111111ikiikiikikxxvv（2.6）故,)()(lim11ikikkvv（2.7）23也就是说两相邻迭代向量分量的比值收敛到主特征值.这种由已知非零向量 及矩阵 的乘幂 构造向量序列 以计算 的主特征值 （利用（2.7）式）及相应特征向量（利用（2.5）式）的方法称为幂法幂法.0vAkAkvA1 由

13、（2.6）式知，的收敛速度由比值 来确定，越小收敛越快，但当 时收敛可能就很慢.11)()(ikikvv12rr112r 定理定理12 12 设 有 个线性无关的特征向量，主特征值 满足 nnA Rn1,321n则对任何非零初始向量 ,(2.4),(2.7)式成立.)0(1v24 如果 的主特征值为实的重根，即 ，且 Ar21,1nrr又设 有 个线性无关的特征向量，对应的 个线性无关特征向量为 ，则由（2.2）式 An1rrxxx,21,)/(11110nriikiiriiikkkxxvAv).0(lim111riiiriiikkkxxv设 这说明当 的主特征值是实的重根时，定理5的结论还是

14、正确的.A 应用幂法计算 的主特征值 及对应的特征向量时，如果 （或 ），迭代向量 的各个不等于零A11111kv25的分量将随 而趋向于无穷（或趋于零），这样在计算机实现时就可能“溢出”.k 为了克服这个缺点，就需要将迭代向量加以规范化.设有一向量 ，将其规范化得到向量 0v,)max(vvu 其中 表示向量 的绝对值最大的分量，即如果有)max(vv,max10iniivv则 ，且 为所有绝对值最大的分量中的最小下标.oivv)max(0i 主特征值为单特征值的条件下幂法可这样进行：26 任取一初始向量 ，构造向量序列)0(010v)max(v,)max(,)max(,)max()max(

15、,)max(,)max()max(,0001002022220021200111001vAvAuvAvAvvAvAvvuAvvAAuvAvAvvvuAvAuvkkkkkk由（2.3）式,2111110niikiikniikiikxxxvA（2.8）27).()(maxmaxmax)(max1121112111211112111100kxxxxxxxxxxvAvAuniikiiniikiiniikiikniikiikkkk这说明规范化向量序列收敛到主特征值对应的特征向量.同理，可得到 28),(,maxmax)max(,max12111121111211111121111kxxxxvxxxxvn

16、iikiiniikiikniikiikniikiikk收敛速度由比值 确定.12r29 定理定理13 13 设 有 个线性无关的特征向量，主特征值 满足 ,则对任意非零初始向量 ，按下述方法构造的向量序列 nnA Rn1n321)0(100uv:,kkvu),2,1(./),max(,0100kvuvAuvuvkkkkkkk（2.9）则有.lim)2(,)(maxlim)1(111kkkkxxu30 例例3 3 用幂法计算 0.225.05.025.00.10.15.00.10.1A的主特征值和相应的特征向量.计算过程如表8-1.表8-1的结果是用8位浮点数字进行运算得到的，的分量值是舍入值.

17、于是得到 ku5365323.21及相应的特征向量 和相应的特征向量的真值（8位数字）为 1.)16497.0,74822116.0(T.)164966116.074822116.0(,5365258.211Tx 315365323.2)16497.07482.0(205365374.2)16497.07482.0(195365456.2)16497.07482.0(185365598.2)16497.07482.0(175365840.2)16497.07483.0(165366256.2)16497.07483.0(155380029.2)16508.07494.0(105587918.2

18、)16674.07651.0(57500000.2)18182.09091.0(1)111(0)max(18kTkvuk（规范化向量）表32 8.2.2 8.2.2 加速方法加速方法 原点平移法原点平移法 由前面讨论知道，应用幂法计算 的主特征值的收敛速度主要由比值 来决定，但当 接近于1时，收敛可能很慢.A12rr 一个补救的办法是采用加速收敛的方法.引进矩阵,pIAB其中 为选择参数.设 的特征值为 ，则 的相应特征值为 ，而且 的特征向量相同.pAn,21Bpppn,21BA,33 如果要计算 的主特征值 ，就要适当选择 使 仍然是 的主特征值，且使 A1pp1B.1212pp对 应用幂

19、法，使得在计算 的主特征值 的过程中得到加速.这种方法通常称为原点平移法.BBp1 例例4 4 设 有特征值 44RA),4,3,2,1(15jjj比值 .作变换 9.0/12r),12(ppIAB则 的特征值为 B34.1,0,1,24321应用幂法计算 的主特征值 的收敛速度的比值为 B1.9.021121212pp 选择有利的 值，虽然能够使幂法得到加速，但问题在于如何选择适当的参数 .pp 设 的特征值满足 A,121nn（2.10）则不管 如何，的主特征值为 或 .当希望计算 及 时，首先应选择 使 ppIABp1pn11xp,1ppn35且使收敛速度的比值.min,max112pp

20、ppn显然，当 ,即 时 为最小，这时收敛速度的比值为 ppppn112*22ppn.2*212112nnnpppp 当 的特征值满足（2.10）且 能初步估计时，就能确定 的近似值.An,2*p 当希望计算 时，应选择n36*,211ppn 例例5 5 计算矩阵0.225.05.025.00.10.15.00.10.1A的主特征值.使得应用幂法计算 得到加速.n 作变换 取 ，则,pIAB75.0p.25.125.05.025.025.00.15.00.125.0B37对 应用幂法，计算结果如表8-2.B7865914.1)16497.07482.0(107866587.1)16497.07

21、483.0(97869152.1)16499.07484.0(87873300.1)16501.07488.0(77888443.1)16511.07491.0(67914011.1)16522.07516.0(5)1 1 1(0)max(28kTkvuk（规范化向量）表由此得 的主特征值为 的主特征值 为 BA,7865914.11138,5365914.275.011与例3结果比较，上述结果比例3迭代15次还好.若迭代15次，（相应的 ).7865258.115365258.21 原点位移的加速方法，是一个矩阵变换方法.这种变换容易计算，又不破坏矩阵 的稀疏性，但 的选择依赖于对 的特征值分布的大致了解.ApA 瑞利商加速瑞利商加速 定理定理14 14 设 为对称矩阵，特征值满足 nnA R,321n对应的特征向量满足 ，应用幂法计算 的主特征值 ，则规范化向量 的瑞利商给出 的较好的近似 ijjixx),(A1ku139.),(),(2121kkkkkOuuuAu 证明证明 由（2.8）式及,)max(,)max(001100uAuAAuvuAuAukkkkkkk得.),(),(),(),(2121122112200001knjkjjnjkjjkkkkkkkkOuAuAuAuAuuuAu（2.11）