矩阵特征值和特征向量PPT课件

1、从理论上讲，可利用代数方程求根求出特征值，再利用线性方程组的解法，求出特征向量。 缺点：工作量大且特征向量对矩阵的依赖很高；当矩阵阶数较高时，高次代数方程求根的计算稳定性较差。另外，实际问题中的具体要求不同，有时只要求A的绝对值最大的特征值（主特征值）及相应的特征向量；有时又要求全部的特征值及特征向量。根据这两种不同要求，求矩阵的特征值与特征向量的方法也大致分为两类：迭代法（幂法反幂法）、变换法。第1页/共89页关于矩阵特征值及特征向量的一些结论： Th1. （i=1,n）为A的特征值，则有 1. 2. det(A)= 11( )nniiiiiatr Ai1nii第2页/共89页Th2、A B

2、(相似相似)，即存在可逆阵，即存在可逆阵T，使，使B=T-1AT,则则 1. A与与B有相同的特征值。有相同的特征值。 2. 设设x是是B的关于的关于 的特征向量的特征向量, 则则Tx是是A的关于的关于 的特征向量。的特征向量。Th3、（Gershgorins定理,园盘定理）：A=(aij),则A的每个特征值必在下述某个园盘中： 1, 1,niiijjj iaainA的每行元素确定一个圆盘，共n个。Th3 表明A的任一特征值必在这n个圆盘中的某一个内。第3页/共89页证明：设 为A的任一特征值，x 0为对应特征向 量，则有( I-A)x=0, 设|xi|=max|xj|,显然xi 0, 第i个

3、方程：1,niiiijjjj iaxa xijij iiiijj iiaxaaxTh3 的证明过程表明A的任一特征值必在其对应特征向量模最大的分量的指标所对应的圆盘中。第4页/共89页 称为A对应于向量x的Rayleigh商。 Def1. Ann 实对称阵，0 xRn,( ),Ax xR xx xTh4. Ann 实对称阵，其特征值依次排序为 , 对应特征向量 组成规范正交系，即 ，则 12n12,nx xx,ijijx x1. 0 xRn, 1,nAx xx x第5页/共89页2.10,max,nx RAx xx x 3.0,min,nnx RAx xx x Proof.1. 0 xRn,

4、forms an orthogonal basis of Rn , so it is possible to write x as where not all could be zero. Thus we have 12,nx xx1niiixxi第6页/共89页n2121nniinii,Ax xx x1111,nniijjijnniijjijAxxxx2121niiinii21121niinii1=第7页/共89页2. From 1 we know so we only need to prove there exists an x 0 such that 1,Ax xx x1,0, ,nA

5、x xxRx x Taking x=x1, we get111 1111111,Ax xx xx xx x3. Proof is similar to 2.第8页/共89页1 幂法与反幂法（按模最大与最小特征值的求法） F幂法：求模最大的特征值主特征值及相应特征 向量的迭代法。 用A的乘幂构造迭代序列，因此称为幂法。 条件：A Rn n具有线性初等因子 A有n个线性无关的特征向量。 优点：简单，适合稀疏矩阵。 缺点：有时收敛速度很慢。第9页/共89页Algorithm 1. suppose A has eigen-values (This implies is a single real ro

6、ot of the characteristic polynomial; else )，and n independent eigen-vectors . 123n11112,nx xxTake an initial vector 0nvRstart the iteration system 102110,()kkkvAvvAvvAvA v第10页/共89页Convergence analysis of Algorithm 1.01 1221,0nnvxxx10112212 1222 nnnnnvAvAxAxAxxxx 1 11222211 12211 kkkknnnkkknnnvxxxxxx

7、 .第11页/共89页11,1,iin10,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-vector第12页/共89页1,1,11,2,211,kkkkknk nvvvvvv1,1,11, 0 ,kikik ik ik ivvvkvv Eigen value 1第13页/

8、共89页Th5. A Rn n有n个线性无关特征向量 主特征值 1满足则做迭代有 12,nx xx123n001 12210,0nnnvRvxxx 10kkkvAvA v1 11,kkvx k 1,1, kik ivkv 第14页/共89页Principal eigen value 1summary10kkkvAvA v1,1,11, 0 ,kikik ik ik ivvvvviteration system1 11,kkvx k eigen-vector corresponding to 1第15页/共89页1. 收敛速度：主要由来收敛速度：主要由来 确定，确定，r 越小，越小，收收敛越快。

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

10、. 00011011221221, , ( ), (), ()kkkkkvuvvvAuumax vvvAuumax vvvAuumax v第17页/共89页Convergence 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 vMa

11、x(x)取出向量x中模最大的分量第18页/共89页2011 122111kknkkkniiinniA vxxxx 211 1221100211 1221111max()maxmax( )kkknnnkkkkkknnnkxxxA vuA vxxxxx 对应 1的特征向量x1的规范化向量第19页/共89页 211 12211011101211 12211211 122111211 12maxmaxmaxmaxmaxkkknnnkkkkkknnnkkknnnkkxxxAvvA vxxxxxxvx 1121111 11111 1maxmaxkknnnkkkxxxx 第20页/共89页Th6. A Rn

12、 n有n个线性无关特征向量 主特征值 1满足 则做迭代有 12,nx xx123n0001 12210,0nnnvRuvxxx 001maxkkkkkuvvAuvuv111, maxmax,kkxukxvk 第21页/共89页第22页/共89页第23页/共89页第24页/共89页第25页/共89页第26页/共89页第27页/共89页第28页/共89页第29页/共89页第30页/共89页第31页/共89页2第32页/共89页平面旋转矩阵第33页/共89页第34页/共89页雅可比法的基本思想:设法用一系列简单的正角阵Rk , 逐步地将 A 化为近似对角阵(非对角元近似化为0)。即选择Rk , 令

13、0112, , 1,2, s.t. diag(,), TkkkkknAAAR ARkAk A的全部特征值问题的关键：如何构造正交阵Rk ？第35页/共89页 平面旋转变换第36页/共89页第37页/共89页第38页/共89页第39页/共89页第40页/共89页第41页/共89页第42页/共89页第43页/共89页第44页/共89页第45页/共89页第46页/共89页雅可比算法:设Ak-1 (k1, A0 =A)未对角化，即非对角元中有较大的元素，设非对角元中按模最大的元素是11cossin1,1sincos11kRp qpq行行(1)(1)(),kkpqqpaapq不妨设引入平面旋转矩阵第47

14、页/共89页利用Rk(p,q)对Ak-1作旋转变换，使 中的非对角元1 TkkkkAR AR( )( )0kkpqqpaa,4 4 (1)(1)(1)22kpqkkppqqatgaa 应满足常将 限制在( -1)( -1)( -1) 0, 4 -4kkppqqkpqif aaif aelse，第48页/共89页对Jacobi算法有几点说明： 1. 构造旋转矩阵时只需计算sin ,cos ,为了防止舍入误差扩大，sin ,cos 按下面公式计算： ( -1)( -1)( -1) sgn4kkkppqqpqif aaa， 否则，(1)2(1)(1)2222tan1tan21tantan2tan10

15、1tan1kpqkkppqqaaaCCCC 第49页/共89页(1)(1)(1)2222( -1)( -1)( -In case of tan too great, we choose21 0sgn( )tan1tan 11 011cos1sincos kkppqqkpqkkkpqppqqaaCaCCtCCCCCCCttifaaa(1)1)(1)(1)1, 2kpqkkppqqawetaket as tCaa第50页/共89页 2. 由于Ak 是对称阵，因此只要计算上三角（或下三角）元素即可，既节省计算量，有能保证Ak 严格对称。 3. 1 TkkkkAR AR的计算过程如下：( )( )(

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

17、nAk ( )( )( )12111( )( )( )21222( )( )( )( )1200, kkknkkknkkkkkknnnnnnaaaaaaEDaaaa证明Jacobi法的收敛性第52页/共89页222222(1)(1)11(1)(1)22222(1)(1)11222221112202, 2,max1221( -1)2 1( -1)kkkkpqkkpqFFFFkkpqijijkkkpqpqkFFkkkkFFFFkFkEEaDDaaaEnnaaEnnEEEEnnn nEn nE2120 , 2diag(,), Fknas knAk 由前面推论知第53页/共89页 5. 实际计算时，当

18、k充分大或者当 时迭代终止，( )( ) or maxkkijijijijaa( ),1,2,kiiiainA的全部近似特征值 6. 特征向量的计算：设经过m次旋转变换迭代结束，则-111-1112-1 , , ,(, ,) TTTmmmmnmmTTTmmmmmmTmmmAR RR A RRRlet PRRRP orthogonalPA PdiaAAgPP 说明Pm的第j列就是 j的标准正交特征向量的近似值。第54页/共89页实际计算时，并不是保留 到最后才形成Pm，而是逐步形成的。令 (1,2,)TkRkm0-1, , 1,2,TkkkPI PP Rkm每一步的计算公式为( )( -1)(

19、-1)( )( -1)( -1)( )( -1)cossinsincos, , 1,2, kkkipipiqkkkiqipiqkkijijppppppppjp qin 第55页/共89页 7. 对经典Jacobi法的改进-避免每次在非对角元中选主元素花费太多时间：循环雅可比法和雅可比过关法。雅可比过关法：1. 设阈值T0(一般取为 )，在A的非对角 元中按行（或列）扫描（只需扫描上（或下）三角元素），即按如下顺序与阈值T0作比 较： 若 |aij|j+1时，bij=0,则称B为上Hessenberg阵(或准上三角阵)，即1112121222 -1,nnn nnnbbbbbbBbbi=j+1i

20、j+1第62页/共89页理论基础：A是n阶实矩阵，存在正交阵P，s.t.11121222,ssTssAAAAAP APA,1,2,iiA is是1阶或2阶方阵。若Aii 是1阶的，则它是A的一个实特征值；若Aii 是2阶的，则它的两个特征值是A的一对共轭复特征值。 第63页/共89页定理说明：用正交阵相似变换可将一般实矩阵约化为上Hessenberg阵，将实对称阵约化为对称三对角阵。正交相似变换不改变特征值和特征向量，因此求原矩阵的特征值问题就转化为求上Hessenberg阵或对称三对角阵的特征值问题。问题的关键：如何将一般实矩阵正交约化为上Hessenberg阵，将实对称阵约化为对称三对角阵

21、？初等反射阵Def122,1Tnwwwww第64页/共89页21121221222121 22221 22-2221 2nTnnnnww ww ww www wHIwww ww ww初等反射阵性质:221. -2-2;2. -2-2-44;3. TTTTTTTTTTHIwwIwwHH HHIwwIwwIwww w w wIHI对称、正交、对合第65页/共89页初等反射阵的几何意义Swv=x+yyx-yv=x-y: 0, 0TTSw xSx w x, , , ,-22;-22-nTTTTvRvxy xS ySykwHxIwwxxww xxHyIwwykwww kwkwyHvx y v是v关于平面

22、S的镜面反射。初等反射阵将 Rn 中任意向量关于以w为法向量且过原点的超平面做镜面反射。初等反射阵的作用：对向量作变换第66页/共89页Proposition22,nxyRxyHHxy则 初等反射阵 ，使。证明：令222212()TTxywwxyxyHIxyxy初等反射阵。2222)(2)(2yxxyxxyxxxyxyxyxxHxTTTT)( 2)(22xyxxyyxyyxxxyxyxyxTTTTTTTT2222yxyyxxHx)(第67页/共89页Corollary1211222120,2,/2nTTxRxxeuuHIIuuHxeuuxeu 初等反射阵使。1Proof: Taking , w

23、e get the result from the proposition immediately.ye第68页/共89页111222222222121212211 ( ,) ,(, )111()(2)2221(22)()2TTnnnnxxxu xexxxuxxxxxxxxx 说 明 ： 的 取 法 ：设 11112sgn( )xxxxx若 与 异号，则的有效数字可能损失，所以取 与 同号，即取。第69页/共89页结论推论说明：通过初等反射阵即可将任何非零向量约化成只有一个非0 0元素的向量。 nxxxx2112111sgn()()TxxxuxeHIuu 10 0Hxe注意：计算 时可能上溢或

24、下溢，为防止溢出，将x 规范化，1221121sgn( )sgn( )()niixxxx,max1inixxxxx21122,(),TTuuHIu uIHH xH xH xe 第70页/共89页用正交相似变换(初等反射阵)约化矩阵为Hessenberg阵11121(1)2122211121(1)(1)212212nnnnnnaaaaaaaAAAAAaaa0(1)2111121111 .0,:AHH Ae （ ）设否 则 这 一 步 不 需 约 化 。选 择 初 等 反 射 阵， 使1221211211121(1)1211 11111 1sgn()()()niiTaaauAeHIuu (n-1)

25、 (n-1)维第71页/共89页1 (1)1(1) 11111121111111110 0101000101010000nnTTTnRHRRHHR RRIH HIHH 令正交、对称、对合令(1)111212111(1)(1)1211221(2)(2)(2)1112132 12 12 (2)(2)(2)2223(2) 1(2) (2)0TnnnnaA HAR ARH AH A HAAAAA111)2(11aA第72页/共89页次正交化，即有进行了（设对)1.20kAB(2)( )( )( )111211,11(2)( )1222T( )( )( )k 1111,1( )( )( )1,1,11,

26、( )( )( ),1( )( )11121(1)1kkkkknkkkkkkkkkkkk kknkkkkkkkknkkkn kn knnkkkkkaaaaaaaARA RaaaaaaaaaAAA( )3()( )( )2223() 1() ()0kkn kkkn kn kn kAA第73页/共89页( )220kA设，221() 1kkkkn kHH Ae （ ）选择初等反射阵，使122( )( )1,1( )1,( )2211sgn()()nkkkkki ki kkkkkkkkkkTkkkkaaauAeHIu u 第74页/共89页()()( )( )( )1112131( )( )2223

27、( )( )( )111213( )1230,000k kkknknkkkkkkkkkkkkkkkkkkkkkkIRHAAAHAR A RH AH AHAAAHeH AH令重复这一过程直到 第75页/共89页122112211(2)122(3)233(1)1HnnnnnnnARR R AR RRaxxxxaxxaxessenberga上阵结论122221122,10,12,0Hn nniinnARH HHRinHRR R AR RRCessenberg则 初等反射阵也是初等反射阵，使上阵第76页/共89页122,( )( )TnTiiPR RRP PI PP APCAC令 正交设x是c 的对应

28、于的特征向量，则有 ()()TCxP APxxA PxPx说明 P x 是 A 对应于 的特征向量。A的特征值和特征向量第77页/共89页若A是实对称阵，则C也是实对称阵(CT=PTATP=PTAP=C),故C为对称三对角阵，即关于实对称阵1112211nnncbbcbCbbc第78页/共89页4 QR方法是一种变换方法，计算一般中小型矩阵全部特征值的最有效方法之一。主要用于计算：1.1.上Hessenberg阵的全部特征值; ; 2.2.对称三对角矩阵的全部特征值。对于一般矩阵或对称阵，先用Householder方法将其约化为上Hessenberg阵或对称三对角阵，再用QR法计算全部特征值。

29、优点：算法稳定，收敛快。 矩阵的QR分解12(,) ,0Tijnijijxx xxxxx xP不全为 ，则可选旋转阵使Lemma1 （旋转对向量的作用）第79页/共89页2212( ,) , , 0,111111TijniijjijPxx xxxxxxxxcsPsc其中i行j行i列j列第80页/共89页证：P左乘x只对的第i,j个元素有影响，其它元素不变。 22, 0iijijjijxcxsxxxxsxcx （旋转对矩阵的作用）A A非奇异，则存在旋转阵P1, , P2, , , Pn, ,s.t.1112122212213nnnnnrrrrrP PP PARr为上三角阵，且对角线元素 01,

30、2,iirin，,Theorem2第81页/共89页证明：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 PPPAaaaa第82页/共89页3. 重复上述过

31、程，得到 , s.t.121,nP PP1112122211nnnnnrrrrrPPARr111111, TTTnTTTnAP PP RQAQRP PP由定理知，令正交阵，则 矩阵的QR分解(,ORAAQRAQRR矩阵的分解） 非奇异可分解为正交阵 与上三角阵 之乘积，即且当 的对角元素都为正时分解唯一。Theorem3第83页/共89页下三角正交阵上三角阵证( (仅证唯一性，反正) )：设1111,AQRQ RR RQ Q，为 非 奇 异 上 角 阵 ，且 对 角 元 素 都 为 正 ，正 交 ，11111111-111111TTQ QR RR RR RR RRRR R正交阵，即对角阵。-1112-121111(,),0,1niRRdiag d ddDRRDIRRdinDIRRQQ设正交由于 ， 对角元素都为正,n nA RQRA QRAR 说明：都可作分解：，但若 奇异，则 奇异