矩阵的特征值与特征向量

1、第九章第九章 矩阵的特征值与特征向量矩阵的特征值与特征向量 /* Eigen-values and Eigen-vectors of matrix */ 待求解的问题待求解的问题：矩阵的：矩阵的特征值特征值 和和特征向量特征向量x 0，满足满足 :Ax= x or ( I-A)x =0Eigen-valueEigen-vector工程技术中的许多问题例如电磁振荡、桥梁振动、机械振动等，都归结为求矩阵的特征值 和特征向量问题-代数计算中的重要课题。特征向量特征向量: 已知已知A的特征值的特征值 ，求齐次线性方程，求齐次线性方程组组 的非零解的非零解x, （ ,所以有非零解。）为所以有非零解。）为

2、A对应于对应于 的特征向量。的特征向量。 ()0IA x0IA 如何求解如何求解?11( )nnnIAcc 11( )0nnncc 12,n特征值特征值：已知：已知A=(aij)n n，求，求A的的特征多项式特征多项式的根的根有有n个零点（实或复，计重数）：个零点（实或复，计重数）：即求解代数方程即求解代数方程A的特征值从理论上讲，可利用代数方程求根求出特征值，再从理论上讲，可利用代数方程求根求出特征值，再利用线性方程组的解法，求出特征向量。利用线性方程组的解法，求出特征向量。 缺点：工作量大且特征向量对矩阵的依赖很高；缺点：工作量大且特征向量对矩阵的依赖很高；当矩阵阶数较高时，高次代数方程求

3、根的计算稳定当矩阵阶数较高时，高次代数方程求根的计算稳定性较差。性较差。另外，实际问题中的具体要求不同，有时只要求另外，实际问题中的具体要求不同，有时只要求A的绝对值最大的特征值（主特征值）及相应的特征的绝对值最大的特征值（主特征值）及相应的特征向量；有时又要求全部的特征值及特征向量。根据向量；有时又要求全部的特征值及特征向量。根据这两种不同要求，求矩阵的特征值与特征向量的方这两种不同要求，求矩阵的特征值与特征向量的方法也大致分为两类：迭代法（幂法反幂法）、变换法也大致分为两类：迭代法（幂法反幂法）、变换法。法。关于矩阵特征值及特征向量的一些结论：关于矩阵特征值及特征向量的一些结论： Th1.

4、 （i=1,n）为）为A的特征值，则有的特征值，则有 1. 2. det(A)= 11( )nniiiiiatr Ai1niiTh2、A B(相似相似)，即存在可逆阵，即存在可逆阵T，使，使B=T-1AT,则则 1. A与与B有相同的特征值。有相同的特征值。 2. 设设x是是B的关于的关于 的特征向量的特征向量, 则则Tx是是A的关于的关于 的特征向量。的特征向量。Th3、（、（Gershgorins定理定理,园盘定理）：园盘定理）：A=(aij),则则A的每个特征值必在下述某个园盘中：的每个特征值必在下述某个园盘中： 1, 1,niiijjj iaainA的每行元素确定一个圆盘，共的每行元素

5、确定一个圆盘，共n个。个。Th3 表明表明A的任一特征值必在这的任一特征值必在这n个圆盘中的某一个内。个圆盘中的某一个内。证明：设证明：设 为为A的任一特征值，的任一特征值，x 0为对应特征向为对应特征向 量，则有量，则有( I-A)x=0, 设设|xi|=max|xj|,显然显然xi 0, 第第i个方程：个方程：1,niiiijjjj iaxa xijij iiiijj iiaxaaxTh3 的证明过程表明的证明过程表明A的任一特征值必在其对应的任一特征值必在其对应特征向量模最大的分量的指标所对应的圆盘中。特征向量模最大的分量的指标所对应的圆盘中。 称为称为A对应于向量对应于向量x的的Ray

6、leigh商商。 Def1. Ann 实对称阵实对称阵，0 xRn,( ),Ax xR xx xTh4. Ann 实对称阵，其特征值依次排序为实对称阵，其特征值依次排序为 , 对应特征向量对应特征向量 组组成规范正交系，即成规范正交系，即 ，则，则 12n12,nx xx,ijijx x1. 0 xRn, 1,nAx xx x2.10,max,nx RAx xx x 3.0,min,nnx RAx xx x Proof.1. 0 xRn, forms an orthogonal basis of Rn , so it is possible to write x as where not al

7、l could be zero. Thus we have 12,nx xx1niiixxin2121nniinii,Ax xx x1111,nniijjijnniijjijAxxxx2121niiinii21121niinii1=2. From 1 we know so we only need to prove there exists an x 0 such that 1,Ax xx x1,0, ,nAx xxRx x Taking x=x1, we get111 1111111,Ax xx xx xx x3. Proof is similar to 2.1 幂法与反幂法幂法与反幂法（按

8、模最大与最小特征值的求法）（按模最大与最小特征值的求法） F幂法幂法：求模最大的特征值求模最大的特征值主特征值及相应特征主特征值及相应特征 向量向量的的迭代法迭代法。 用用A的乘幂构造迭代序列，因此称为幂法。的乘幂构造迭代序列，因此称为幂法。 条件：条件：A Rn n具有具有线性初等因子线性初等因子 A有有n个线性无关的特征向量个线性无关的特征向量。 优点：简单，适合稀疏矩阵。优点：简单，适合稀疏矩阵。 缺点：有时收敛速度很慢。缺点：有时收敛速度很慢。Algorithm 1. suppose A has eigen-values (This implies is a single real r

9、oot of the characteristic polynomial; else )，and n independent eigen-vectors . 123n11112,nx xxTake an initial vector 0nvRstart the iteration system 102110,()kkkvAvvAvvAvA vConvergence analysis of Algorithm 1.01 1221,0nnvxxx10112212 1222 nnnnnvAvAxAxAxxxx 1 11222211 12211 kkkknnnkkknnnvxxxxxx .11,1,i

10、in10,2 kikin 1 11,kkvx k 1x101 1x1 is an eigen-vector of A, and is also an eigen-vector corresponding to of A. The same is 11 1kkxv 111121011 12211kkkknknnvAvxxx11 1kkvx 1111 11kkkvxvk Eigen-vector1,1,11,2,211,kkkkknk nvvvvvv1,1,11, 0 ,kikik ik ik ivvvkvv Eigen value 1Th5. A Rn n有有n个线性无关特征向量个线性无关特征向

11、量 主特征值主特征值 1满足满足则则做迭代做迭代有有 12,nx xx123n001 12210,0nnnvRvxxx 10kkkvAvA v1 11,kkvx k 1,1, kik ivkv Principal eigen value 1summary10kkkvAvA v1,1,11, 0 ,kikik ik ik ivvvvviteration system1 11,kkvx k eigen-vector corresponding to 11. 收敛速度：主要由来收敛速度：主要由来 确定，确定，r 越小，越小，收收敛越快。敛越快。 时收敛可能很慢。时收敛可能很慢。2. 若有若有 ，说明

12、，说明 1 0， 以及以及 都不能作为近似都不能作为近似特征向量，需要重新取初始向量再迭代。特征向量，需要重新取初始向量再迭代。3. 用幂法进行计算时，若用幂法进行计算时，若 在计算机中会产生在计算机中会产生“溢出溢出”或或 “机器零机器零”的情的情况（超过计算机字长所能表示的精度）况（超过计算机字长所能表示的精度） note21r1r 11 10kkvx 1 1x11 1kkxv 11 ( or 1),1,1,if 0,(0)k ikik ivvv Algorithm 2(improvement of A.1). 00011011221221, , ( ), (), ()kkkkkvuvvv

13、Auumax vvvAuumax vvvAuumax vConvergence analysis of A.2.00001100110202002212200202, , ( )()(), ()()max()() =vuvAvvvAuAvumax vmax AvA vA vmax AvvvAuuA vmax Avmax vmax AvA v20002200000100()() maxmax, max()max()kkkkkkmax AvA vmax AvA vA vA vA vvuAvA vMax(x)取出向量取出向量x中模最大的分量中模最大的分量2011 122111kknkkkniiinn

14、iA vxxxx 211 1221100211 1221111max()maxmax( )kkknnnkkkkkknnnkxxxA vuA vxxxxx 对应对应 1的特征向量的特征向量x1的规范化向量的规范化向量 211 12211011101211 12211211 122111211 12maxmaxmaxmaxmaxkkknnnkkkkkknnnkkknnnkkxxxAvvA vxxxxxxvx 1121111 11111 1maxmaxkknnnkkkxxxx Th6. A Rn n有有n个线性无关特征向量个线性无关特征向量 主特征值主特征值 1满足满足 则则做迭代做迭代有有 12,

15、nx xx123n0001 12210,0nnnvRuvxxx 001maxkkkkkuvvAuvuv111, maxmax,kkxukxvk 2平面旋转矩平面旋转矩阵阵雅可比法的基本思想雅可比法的基本思想:设法用一系列简单的正角阵设法用一系列简单的正角阵Rk , 逐步地将逐步地将 A 化为近化为近似对角阵似对角阵(非对角元近似化为非对角元近似化为0)。即选择。即选择Rk , 令令 0112, , 1,2, s.t. diag(,), TkkkkknAAAR ARkAk A的全部特征值的全部特征值问题的关键问题的关键：如何构造正交阵：如何构造正交阵Rk ？ 平面旋转变换平面旋转变换雅可比算法雅

16、可比算法:设设Ak-1 (k1, A0 =A)未对角化，即非对角元中有较大的元素，未对角化，即非对角元中有较大的元素，设非对角元中按模最大的元素是设非对角元中按模最大的元素是11cossin1,1sincos11kRp qpq行行(1)(1)(),kkpqqpaapq不妨设引入平面旋转矩阵引入平面旋转矩阵利用利用Rk(p,q)对对Ak-1作旋转变换，使作旋转变换，使 中的非对角元中的非对角元1 TkkkkAR AR( )( )0kkpqqpaa,4 4 (1)(1)(1)22kpqkkppqqatgaa 应满足应满足常将常将 限制在限制在( -1)( -1)( -1) 0, 4 -4kkppq

17、qkpqif aaif aelse，对对Jacobi算法有几点说明：算法有几点说明： 1. 构造旋转矩阵时只需计算构造旋转矩阵时只需计算sin ,cos ,为了防止为了防止舍入误差扩大，舍入误差扩大，sin ,cos 按下面公式计算：按下面公式计算： ( -1)( -1)( -1) sgn4kkkppqqpqif aaa， 否则，否则，(1)2(1)(1)2222tan1tan21tantan2tan101tan1kpqkkppqqaaaCCCC (1)(1)(1)2222( -1)( -1)( -In case of tan too great, we choose21 0sgn( )tan

18、1tan 11 011cos1sincos kkppqqkpqkkkpqppqqaaCaCCtCCCCCCCttifaaa(1)1)(1)(1)1, 2kpqkkppqqawetaket as tCaa 2. 由于由于Ak 是对称阵，因此只要计算上三角（或下三角）是对称阵，因此只要计算上三角（或下三角）元素即可，既节省计算量，有能保证元素即可，既节省计算量，有能保证Ak 严格对称。严格对称。 3. 1 TkkkkAR AR的计算过程如下：的计算过程如下：( )( )( -1)( -1)( )( )( -1)( -1)( )( -1)2( -1)( -1)2( )( -1)2( -1)( -1)

19、2cossin ,sincoscossin2sin sinsin2cos kkkkippiipiqkkkkiqqiipiqkkkkpppppqqqkkkkqqpppqqqaaaaip qaaaaaaaaaaaa ( )( )( )( -1) 0 , , , kkpqqpkkijijaaaai jp q 4. Ak 中经旋转变换化为零的元素，可能在中经旋转变换化为零的元素，可能在Ak+1中又成为中又成为非零元素，因此不能期望通过有限次旋转变换将原矩阵非零元素，因此不能期望通过有限次旋转变换将原矩阵A对角化，但可证对角化，但可证 12 diag(,), knAk ( )( )( )12111( )

20、( )( )21222( )( )( )( )1200, kkknkkknkkkkkknnnnnnaaaaaaEDaaaa证明证明Jacobi法的收敛性法的收敛性222222(1)(1)11(1)(1)22222(1)(1)11222221112202, 2,max1221( -1)2 1( -1)kkkkpqkkpqFFFFkkpqijijkkkpqpqkFFkkkkFFFFkFkEEaDDaaaEnnaaEnnEEEEnnn nEn nE2120 , 2diag(,), Fknas knAk 由前面推论知由前面推论知 5. 实际计算时，当实际计算时，当k充分大或者当充分大或者当 时迭代终止

21、，时迭代终止，( )( ) or maxkkijijijijaa( ),1,2,kiiiainA的全部近似特征值的全部近似特征值 6. 特征向量的计算：设经过特征向量的计算：设经过m次旋转变换迭代结束，则次旋转变换迭代结束，则-111-1112-1 , , ,(, ,) TTTmmmmnmmTTTmmmmmmTmmmAR RR A RRRlet PRRRP orthogonalPA PdiaAAgPP 说明说明Pm的第的第j列就是列就是 j的标准正交特征向量的近似值。的标准正交特征向量的近似值。实际计算时，并不是保留实际计算时，并不是保留 到最后到最后才形成才形成Pm，而是逐步形成的。，而是逐

22、步形成的。令令 (1,2,)TkRkm0-1, , 1,2,TkkkPI PP Rkm每一步的计算公式为每一步的计算公式为( )( -1)( -1)( )( -1)( -1)( )( -1)cossinsincos, , 1,2, kkkipipiqkkkiqipiqkkijijppppppppjp qin 7. 对经典对经典Jacobi法的改进法的改进-避免每次在非对角元中选避免每次在非对角元中选主元素花费太多时间：主元素花费太多时间：循环雅可比法和雅可比过关法循环雅可比法和雅可比过关法。雅可比过关法雅可比过关法：1. 设阈值设阈值T0(一般取为一般取为 )，在，在A的非对角的非对角 元中按

23、行（或列）扫描（只需扫描上（或下）三角元元中按行（或列）扫描（只需扫描上（或下）三角元素），即按如下顺序与阈值素），即按如下顺序与阈值T0作比作比 较：较： 若若 |aij|j+1时，时，bij=0,则称则称B为上为上Hessenberg阵阵(或准上三角阵或准上三角阵)，即，即1112121222 -1,nnn nnnbbbbbbBbbi=j+1i j+1理论基础：理论基础：A是是n阶实矩阵，存在阶实矩阵，存在正交阵正交阵P，s.t.11121222,ssTssAAAAAP APA,1,2,iiA is是是1阶或阶或2阶方阵。若阶方阵。若Aii 是是1阶的，阶的，则它是则它是A的一个实特征值；

24、若的一个实特征值；若Aii 是是2阶的，则它的两阶的，则它的两个特征值是个特征值是A的一对共轭复特征值。的一对共轭复特征值。 定理说明：定理说明：用正交阵相似变换可将一般实矩阵约化为上用正交阵相似变换可将一般实矩阵约化为上Hessenberg阵，将实对称阵约化为对称三对角阵。阵，将实对称阵约化为对称三对角阵。正交相似变换不改变特征值和特征向量，因此求原矩阵正交相似变换不改变特征值和特征向量，因此求原矩阵的特征值问题就转化为求上的特征值问题就转化为求上Hessenberg阵或对称三对角阵或对称三对角阵的特征值问题。阵的特征值问题。问题的关键问题的关键：如何将一般实矩阵正交约化为上：如何将一般实矩

25、阵正交约化为上Hessenberg阵，将实对称阵约化为对称三对角阵？阵，将实对称阵约化为对称三对角阵？初等反射阵初等反射阵Def122,1Tnwwwww21121221222121 22221 22-2221 2nTnnnnww ww ww www wHIwww ww ww初等反射阵初等反射阵性质性质:221. -2-2;2. -2-2-44;3. TTTTTTTTTTHIwwIwwHH HHIwwIwwIwww w w wIHI对称、正交、对称、正交、对合对合初等反射阵的初等反射阵的几何意义几何意义Swv=x+yyx-yv=x-y: 0, 0TTSw xSx w x, , , ,-22;-2

26、2-nTTTTvRvxy xS ySykwHxIwwxxww xxHyIwwykwww kwkwyHvx y v是是v关于平面关于平面S的镜面反射。的镜面反射。初等反射阵将初等反射阵将 Rn 中任意向量关于以中任意向量关于以w为法向量且过原点的超为法向量且过原点的超平面做镜面反射平面做镜面反射。初等反射阵的作用：对向量作变换初等反射阵的作用：对向量作变换Proposition22,nxyRxyHHxy则 初等反射阵 ，使。证明：令222212()TTxywwxyxyHIxyxy初等反射阵。2222)(2)(2yxxyxxyxxxyxyxyxxHxTTTT)( 2)(22xyxxyyxyyxxx

27、yxyxyxTTTTTTTT2222yxyyxxHx)(Corollary1211222120,2,/2nTTxRxxeuuHIIuuHxeuuxeu 初等反射阵使。1Proof: Taking , we get the result from the proposition immediately.ye111222222222121212211 ( ,) ,(, )111()(2)2221(22)()2TTnnnnxxxu xexxxuxxxxxxxxx 说 明 ： 的 取 法 ：设 11112sgn( )xxxxx若 与 异号，则的有效数字可能损失，所以取 与 同号，即取。结论结论推论说明

28、：通过初等反射阵即可将任何非零向量推论说明：通过初等反射阵即可将任何非零向量约化成只有一个非约化成只有一个非0 0元素的向量。元素的向量。 nxxxx2112111sgn()()TxxxuxeHIuu 10 0Hxe注意：计算注意：计算 时可能上溢或下时可能上溢或下溢，为防止溢出，将溢，为防止溢出，将x 规范化，规范化，1221121sgn( )sgn( )()niixxxx,max1inixxxxx21122,(),TTuuHIu uIHH xH xH xe 用正交相似变换用正交相似变换(初等反射阵初等反射阵)约化矩阵为约化矩阵为Hessenberg阵阵11121(1)2122211121(

29、1)(1)212212nnnnnnaaaaaaaAAAAAaaa0(1)2111121111 .0,:AHH Ae （ ）设否 则 这 一 步 不 需 约 化 。选 择 初 等 反 射 阵， 使1221211211121(1)1211 11111 1sgn()()()niiTaaauAeHIuu (n-1) (n-1)维维1 (1)1(1) 11111121111111110 0101000101010000nnTTTnRHRRHHR RRIH HIHH 令正交、对称、对合令(1)111212111(1)(1)1211221(2)(2)(2)1112132 12 12 (2)(2)(2)222

30、3(2) 1(2) (2)0TnnnnaA HAR ARH AH A HAAAAA111)2(11aA次正交化，即有进行了（设对)1.20kAB(2)( )( )( )111211,11(2)( )1222T( )( )( )k 1111,1( )( )( )1,1,11,( )( )( ),1( )( )11121(1)1kkkkknkkkkkkkkkkkk kknkkkkkkkknkkkn kn knnkkkkkaaaaaaaARA RaaaaaaaaaAAA( )3()( )( )2223() 1() ()0kkn kkkn kn kn kAA( )220kA设，221() 1kkkkn

31、 kHH Ae （ ）选择初等反射阵，使122( )( )1,1( )1,( )2211sgn()()nkkkkki ki kkkkkkkkkkTkkkkaaauAeHIu u ()()( )( )( )1112131( )( )2223( )( )( )111213( )1230,000k kkknknkkkkkkkkkkkkkkkkkkkkkkIRHAAAHAR A RH AH AHAAAHeH AH令重复这一过程直到 122112211(2)122(3)233(1)1HnnnnnnnARR R AR RRaxxxxaxxaxessenberga上阵结论结论122221122,10,12,

32、0Hn nniinnARH HHRinHRR R AR RRCessenberg则 初等反射阵也是初等反射阵，使上阵122,( )( )TnTiiPR RRP PI PP APCAC令 正交设x是c 的对应于的特征向量，则有 ()()TCxP APxxA PxPx说明说明 P x 是是 A 对应于对应于 的特征向量。的特征向量。A的特征值和特征向量的特征值和特征向量若若A是实对称阵，则是实对称阵，则C也是实对称阵也是实对称阵(CT=PTATP=PTAP=C),故故C为对称三对角阵，即为对称三对角阵，即关于实对称阵关于实对称阵1112211nnncbbcbCbbc4 QR方法方法是一种变换方法，

33、计算一般中小型矩阵全部特征值的是一种变换方法，计算一般中小型矩阵全部特征值的最有效方法之一。最有效方法之一。主要用于计算：主要用于计算：1.1.上上Hessenberg阵的全部特征值阵的全部特征值; ; 2.2.对称三对角矩阵的全部特征值。对称三对角矩阵的全部特征值。对于一般矩阵或对称阵，先用对于一般矩阵或对称阵，先用Householder方法将其方法将其约化为上约化为上Hessenberg阵或对称三对角阵，再用阵或对称三对角阵，再用QR法法计算全部特征值。计算全部特征值。优点：算法稳定，收敛快。优点：算法稳定，收敛快。 矩阵的矩阵的QR分解分解12(,) ,0Tijnijijxx xxxxx

34、 xP不全为 ，则可选旋转阵使Lemma1 （旋转对向量的作用）（旋转对向量的作用）2212( ,) , , 0,111111TijniijjijPxx xxxxxxxxcsPsc其中i行j行i列j列证：证：P左乘左乘x只对的第只对的第i,j个元素有影响，其它元素不变。个元素有影响，其它元素不变。 22, 0iijijjijxcxsxxxxsxcx （旋转对矩阵的作用）（旋转对矩阵的作用）A A非奇异，则存在旋转阵非奇异，则存在旋转阵P1, , P2, , , Pn, ,s.t.1112122212213nnnnnrrrrrP PP PARr为上三角阵，且对角线元素为上三角阵，且对角线元素 0

35、1,2,iirin，,Theorem2证明：证明：A=A1非奇异，非奇异，A1的第一列一定存在的第一列一定存在ai1 0, 1. 若若ai1 0, 由引理由引理1，存在旋转阵，存在旋转阵 , s.t. 21311,nPPP(2)(2)(2)(2)(2)(2)1112122211,1312111122nnnnnnnraaaaP PP P APAAaa2. 同理，同理， 若若 ,由引理由引理1, 存在旋转阵存在旋转阵 , s.t.32422,nPPP(2)20ia(2)(2)(2)(3)(3)(3)(3)(3)(3)111213122232n2423222 1133333AAnnnnnnraaaraaPP PPPAaaaa3. 重复上述过程，得到重复上述过程，得到 , s.t.121,nP PP1112122211nnnnnrrrrrPPARr111111, TTTnTTTnAP PP RQAQRP PP由定理知，令正交阵，则 矩阵的矩阵的QR分解分解(,ORAAQRAQRR矩阵的分解） 非奇异可分解为正交阵 与上三角阵 之乘积，即且当 的对角元素都为正时分解唯一。Theorem3下三下三角角正交阵正交阵上三角阵上三角阵证证( (仅证唯一性，反正仅证唯一性，反正) )：设：设1111,AQRQ RR RQ Q，为 非 奇 异 上 角 阵 ，且 对 角 元 素 都