CH矩阵特征值问题计算PPT课件

1、Ch8 矩阵特征值问题计算第1页/共42页引言1110102()()31140 .定理设 为的特征值且，其中，则定理设 为的特征值且，其中，则（）为的特征值（ 为常数）；（）为的特征值（ 为常数）；（）为的特征值，即；（）为的特征值，即；（）为的特征值；（）为的特征值；（）设 为非奇异矩阵，那么且为的特征值，即（）设 为非奇异矩阵，那么且为的特征值，即n nkkARAxxxccAccpApIApI xp xAAAA xx 111(1,2, )()(1)( );(2)det( ).定理设为 阶矩阵的特征值，则定理设为 阶矩阵的特征值，则iijn nnniiiiiniiinnAaatr AA 第2

2、页/共42页定义设，如果 有一个重数为 的特征值 且对应定义设，如果 有一个重数为 的特征值 且对应矩阵 的线性无关的特征向量个数少于 ，则称 为亏损矩阵.矩阵 的线性无关的特征向量个数少于 ，则称 为亏损矩阵.n nARAkAkA 1()|(1,2, )2 |,.定义设，（1）令；定义设，（1）令；（）称复平面上以为圆心，（）称复平面上以为圆心，以 为半径的圆为 的圆盘以 为半径的圆为 的圆盘nijn niijjj iiiiiiiiAarainDzzar zCarAGerschgorin 1(), |1,2, ).(2).定理（G erschgori n定理）定理（G erschgori n

3、定理）（）设则 的每个特征值必属于下述某个圆盘中（）设则 的每个特征值必属于下述某个圆盘中（如果 有个圆盘组成一个连通的并集 ，且 与余下个如果 有个圆盘组成一个连通的并集 ，且 与余下个圆盘是分离的，则 内恰包含 的个特征值圆盘是分离的，则 内恰包含 的个特征值ijn niiiAaAarinAmSSnmSAm 第3页/共42页11121222 (1,2, ).定理（Schur定理）设，则存在酉矩阵使定理（Schur定理）设，则存在酉矩阵使其中为 的特征值其中为 的特征值n nnnHnniiARUrrrrrUAURrr inA 11121222, .定理（是Schur定理）设，则存在正交矩阵使

4、得定理（是Schur定理）设，则存在正交矩阵使得其中对角块为一阶或二阶方阵，每个一阶是 的是特征值，其中对角块为一阶或二阶方阵，每个一阶是 的是特征值，每个二阶对角块的两个特征值是 的两个共轭复特征值每个二阶对角块的两个特征值是 的两个共轭复特征值n nmmTmmiiiijjARQRRRRRQ AQRRRARA 第4页/共42页(, ) ( )( , )定义设 为 阶实对称矩阵，对于任一非零向量 ，称定义设 为 阶实对称矩阵，对于任一非零向量 ，称为对应向量 的瑞利商（R ayl ei gh）.为对应向量 的瑞利商（R ayl ei gh）.AnxAx xR xx xx 12111,0,0(,

5、 )(1),0;( , )(, )(2)max;( , )(, )(3)min.( , )定理设为对称矩阵，记为定理设为对称矩阵，记为的特征值，则的特征值，则nnn nnnx Rxnx RxARAAx xxx xAx xx xAx xx x 第5页/共42页计算矩阵的主特征根及对应的特征向量计算矩阵的主特征根及对应的特征向量Wait a second, what does that dominant eigenvalue mean?That is the eigenvalue with the largest magnitude.Why in the earth do I want to kn

6、ow that?Dont you have to compute the spectral radius from time to time? 原始幂法原始幂法条件：条件：A 有特征根有特征根 | 1| | 2| | n| 0，对应对应n个线性无关的特征向量个线性无关的特征向量nxx,.,1思路：思路：从任意从任意 出发出发0)0( 0,11)0( niiix )0()1( A niiiix1 )1()2( A niiiix12 niikiikniikiikkxxA1111)1()( | i / 1 | 2n , 这时,(8.1)式可写成若a10, 则对充分大的k有 )()(11222111)

7、(nknkkknaaaxxxv111)(xvakk)(11111)1(,kkkavxv因而有 nivvkiki, 2 , 1/)()1(1或取 )(1)()1()(2)1(2)(1)1(11knknkkkkvvvvvvn而特征向量 x1 v(k).乘幂法的收敛速度取决于|2/1|的大小. 第9页/共42页 求矩阵A的按模最大的特征值 解 取v(0)=(1,0)T ,计算v(k)=Av(k-1), 结果如下例2kv1(k)v2(k)v1(k)/v1(k-1)v2(k)/v2(k-1)01010.250.220.102500.0833330.410.4166530.0422920.0343890.

8、412600.4126740.0174510.0141900.412630.41263 可取0.41263 ,x1(0.017451,0.014190)T .第10页/共42页 对非零向量v,用max(v)表示v的按绝对值最大的分量,称向量u=v/max(v)为向量v的规范化向量. 例如, 设向量v=(2,1,-5,-1)T,则max(v)=-5,u=(-0.4,-0.2,1,0.2)T.可见规范化向量u总满足u=1. 乘幂法的规范化计算公式为:)1()(kkAuv 任取初始向量u(0)=v(0) 0,计算)max()(kkv, 3 , 2 , 1,)()(kkkkvu由于1)0()1(Avu

9、21)0(22)1()2(vAAuu，第11页/共42页)(max()(21121111niikiniikiiiaaaaxxxxkkkkkkkk.21)0(1)2(2)1()(vAuAAuu)max()0()0(vAvAkk所以)max()max(lim111111)(xxxxuaakk又由)(max()(2111211111niikiniikiiiaaaaxxxx)max()0(1)0(1vAvAAuvkkkk）（）（第12页/共42页其收敛速度由比值|2/1|来确定,其值越小收敛越快.)(max)(max2111211111niikiniikiiiaaaaxxxx)max()(kkv所以1

10、limkk因此,当|k-k-1|r+1n ,这时,(8.1)式可写成)()(1111122111)(nknrkrrrkknraaaaaxxxxxv若a1,a2,ar不全为零, 则对充分大的k有 22111)(rrkkaaaxxxv由于a1x1+a2x2+arxr 是对应1的特征向量, 若仍记为x1 ,则有: v(k) 1kx1 ,故前面的结论仍然成立. 3. 设1=-2,且 |1=|2|3 n ,这时,(8.1)式可写成)()() 1(1133122111)(nknkrkkknaaaaxxxxv则对充分大的k有 第16页/共42页 v(2i)12i(a1x1+a2x2) , v(2i+1)12

11、i+1(a1x1-a2x2) 1(22111)(xxvaakkk于是有nivvkiki, 2 , 1,/)()2(1 x1v(k+1)+1v(k) , x2v(k+1)-1v(k) 对于规范化的幂法，由于 u(k+2)=v(k+2)/k+2=Au(k+1)/k+2 =Av(k+1)/k+1k+2=A2u(k)/k+1k+2于是有，211kk12第17页/共42页 x1k+1u(k+1)+1u(k) , x2k+1u(k+1)-1u(k)的按模最大特征值和相应的特征向量。例4 用乘幂法求矩阵 解 取初始向量u(0)=v(0)=(1,1,2)T ,计算可得第18页/共42页K ku(k)01234

12、5678910111213113.5536284.6792043.4611244.6354653.4526554.6321163.4543154.6319293.4542914.6319203.4542884.631924(1,1,2)T(0.454545, 0.909091, 1)T(0.537222, 0.972116, 1)T(0.465201, 0.994041, 1)T(0.539392, 0.998269, 1)T(0.465721, 0.999627, 1)T(0.539487, 0.999892, 1)T(0.465890, 0.999975, 1)T(0.539495, 0.

13、999993, 1)T(0.465893, 0.999999, 1)T(0.539495, 1, 1)T(0.465893, 1, 1)T(0.539495, 1, 1)T(0.465893, 1, 1)T第19页/共42页1.2 加速技术由于21( )1max()()(8.2)kkkvo所以,乘幂法收敛速度取决于比值|2/1|,当|2/1|1时,收敛是很慢的. 1.Aitken 加速方法由(8.2)式可知 x2=13u(13)-1u(12)=(0 , 0.631924 , 0.631924)T.4, 4631924. 4454288. 3213121 x1=13u(13)+1u(12)=(4

14、.315961, 8.631924, 8.631924)T, 实际上, A的特征值为1=4,2=-4,3=1.第20页/共42页可见,序列k线性收敛于1 .会达到加速收敛的目的.0lim12111kkk 构造Aitken序列kkkkkkk12212)( 如把Aitken加速方法用于例3,则有第21页/共42页 ku(k)107.26.56.0033526.0016756.000837(1,1,1)T(1,0.8,0.1)T(1,0.75,-0.111)T(1,0.730769,-0.188034)T.(1,0.714405,-0.249579)T(1,0.714346,-0.249790)T(

15、1,0.714316,-0.249895)Tk01231011126.2666676.0000176.0000036.000000k 2.原点位移法 作矩阵B=A-pI, 则B的特征值为mi=i-p(i=1,2,n),而且对应的特征向量相同.第22页/共42页则对B应用乘幂法可达到加速收敛的目的。 解 由于A的特征值为1=6,2=3,3=2,故取p=2.5,则B的特征值为m1=3.5,m2=0.5,m3=-0.5,则如果选取p,使m1仍然是B的按模最大特征值，且满足取初始向量u(0)=v(0)=(1,1,1)T,由规范化计算公式:121212ppmm例5 用原点位移法求例3中矩阵A的按模最大的

16、特征值和特征向量.5 . 00105 .1050145 . 65 . 2 EAB第23页/共42页计算可得, 3 , 2 , 1,)()(kkkkvu)max()(kkv)1()(kkBuvkkU(k)01234567.53.7666623.5353963.5050023.5007183.500102(1,1,1,)T(1,0.733333,-0.2)T(1,0.716814,-0.238938)T(1,0.714643,-0.249061)T(1,0.714337,-0.249777)T(1,0.714293,-0.249981)T(1,0.714287,-0.249995)T第24页/共4

17、2页这是因为|2/1|=1/2,而|m2/m1|=1/7,故对B应用乘幂法远比对A应用乘幂法收敛的快. 反幂法是求矩阵按模最小的特征值和相应特征向量的方法.取,16+2.5=6.000102,x1u(6)=(1,0.714287,0.249995)T1.3 反幂法 设A是n阶非奇异矩阵, 其特征值为 |1| |2| |n-1| |n| 0对应的特征向量为x1,x2,xn, 则有A-1的特征值为1211111nnn对应的特征向量为xn,xn-1,x1. 要想求n和xn只需对A-1应用乘幂法,任取初始向量u(0)=v(0)0, 作第25页/共42页也可将上式改写成, 3 , 2 , 1,)()(k

18、kkkvu)max()(kkv)1(1)(kkuAv)1()(kkuAv)max()(kkv( )( )(8.3),1,2,3,kkkkuv式(8.3)称为反幂法. 显然有)max(/lim,1lim)(nnkknkkxxu每一步求v(k)需要求解线性方程组, 可采用LU分解法求解.第26页/共42页 反幂法还可结合原点位移法应用.设已求得矩阵A的特征值i的某个近似值对B应用反幂法可求出精度更高的i和xi. 设已求得例3中矩阵A的特征值的近似值16.003,和相应的特征向量x1(1,0.714405,-0.249579)T, 试用带原点位移的反幂法求1和x1的更精确的值.iip,取 作原点位移

19、,令B=A- E, i 则B的特征值为 )( ,221ijijiiiniii且必有例6 解 取p=6.003, 作矩阵B=A-6.003I,则003. 4010997. 65014003.10B第27页/共42页取初始向量u(0)=(1,0.714405,-0.249579)T,对B用反幂法计算可得:可见收敛速度非常快,这是因为B的3个特征值为1=-4.003, 2=-3.003,3=-0.003,|3/2很小.T)250000. 0,714286. 0 , 1 (,00000167. 6003. 61)1(1uT)250000. 0,714286. 0 , 1 (,000000007. 60

20、03. 61)2(2u第28页/共42页 反幂法反幂法 /* Inverse Power Method */Ch.5 Power Method Inverse Power Method若若 A 有有| 1 | | 2 | | n |，则，则 A 1 有有对应同样一组特征向量。对应同样一组特征向量。11111 nnA 1 的主特征根的主特征根 A的绝对值最小的特征根的绝对值最小的特征根Q: How must we compute in every step?)(1)1(kkA A: Solve a linear system with A factorized.)()1(kkA 若知道某一特征根

21、若知道某一特征根 i 的大致位置的大致位置 p ，即对任意，即对任意 j i 有有| i p | | j p | ，并且如果，并且如果 (A pI) 1存在，则可以用反幂法求存在，则可以用反幂法求(A pI) 1的主特的主特征根征根 1/( i p ) ，收敛将非常快。，收敛将非常快。思思路路第29页/共42页 Jacobi方法是求实对称矩阵全部特征值和特征向量的一种矩阵变换方法。2 Jacobi 方法-正交变换法-QR分解 实对称矩阵A具有下列性质： （1）A的特征值均为实数； （2）存在正交矩阵R，使RTAR=diag(1,2,n),而 第30页/共42页R的第i个列向量恰为i的特征向量;

22、 直接求正交矩阵R是困难的 . Jacobi提出用一系列所谓平面旋转矩阵逐次将A约化为对角矩阵.平面解析几何中的平面坐标旋转变换表示平面上坐标轴旋转角的变换. （3）若记A1=RTAR,则A1仍为对称矩阵. 2.1 平面旋转矩阵 1122cossinsincosyxyx 在三维空间直角坐标系中,ox1y1平面绕着oz1轴旋转角的坐标变换为1112221000cossin0sincoszyxzyx第31页/共42页 Rpq()具有下列性质: 一般地, 在n维向量空间Rn中, 沿着xpyq平面旋转角的变换矩阵为行第行第qppq11cossin11sincos11)(R称Rpq()为平面旋转矩阵.

23、第32页/共42页 设实对称矩阵A=(aij)nn ,记B=RpqT()ARpq()=(bij)nn则它们元素之间有如下关系: （1）Rpq()为正交矩阵,即Rpq-1()=RpqT(); （2）如果A为对称矩阵, 则RpqT()ARpq()也为对称矩阵, 且与A有相同的特征值. （3）RpqT()A仅改变A的第p行与第q行元素,ARpq()仅改变A的第p列与第q列元素.222212cossinsin2sincossin2()sin2cos2(8.4)cossinsincos( , )ppppqqpqqqppqqpqpqqpqqpppqjppjjpjqjqqjjpjqijijbaaabaaab

24、baaabbaabbaabai jp q 第33页/共42页222222(8.5)22ppqqpqppqqpqbbbaaa所以有从而2222qipiqipiaabb),(2222qpiaabbiqipiqip22FFAB2211,(8.6)nnijijijijba，即有(8.5)、(8.6)式可得222222pqjiijpqjiijaabb21221222pqniiipqniiiaabb 如果apq0, 适当选取角, 使02cos2sin)(21pqppqqqppqaaabb第34页/共42页只需角满足从而 如果取|apq|=若记cot2,|(8.7)24ppqqpqaaajiijpqjiij

25、jiijaaab22222niiipqniiiniiiaaab12212122|maxijjia于是jiijpqanna2211）（，则jiijjiijannb22) 1(21 (,)(2jiijaA 则上式可记为2( )(1) ( )(8.8)(1)n nBA第35页/共42页 由式(8.7),令t=tan,则t满足方程 t2+2t-1=0 经典Jacobi算法是对A(0)=A施行一系列平面旋转变换:为保证|/4,取绝对值较小的根,有于是2sgn( )/(|1),0(8.9)1,0t,)1 (cos212tsincos(8.10)t2.2 Jacobi 方法 A(1)=R1TA(0)R1 ,

26、A(2)=R2TA(1)R2 , A(k)=RkTA(k-1)Rk ,每一步变换选择A(k-1)=(aij(k-1)nn 的非对角线元素中绝对值最大者apq(k-1)(称为主元素)作为歼灭对象, 构造平面旋第36页/共42页 是给定的精度要求,则A的特征值可取为iaii(k),i=1,2,n.转矩阵Rk=Rpq(), 经变换得到A(k)=(aij(k)nn ,且apq(k)=0,这时由(8.8)式有从而由此递推得到 当k充分大时,或者(A(k),或者)() 1(21 ()()1()(kknnAA)() 1(21 ()()(AAkknn)( , 0k),(lim21)(nkkdiagDA 另外,由于 A(k)=RkTA(k-1)Rk=RkTRk-1TR1TAR1R2Rk=RTAR ,|max)(kijjia第37页/共42页的全部特征值. 解 记 A(0)=A,取p=1,q=2,apq(0)=a12(0)=2,于是有因此,R=R1R2Rk 的列向量xj (j=1,2,n)为A的近似特征向量.例7 用Jacobi 方法计算对称矩阵25. 02)0(12)0(22)0(11aaa780776. 0)1|/(|)sgn(,2t788206. 0)1 (cos212t615412. 0cossin,t从而有第38页/共42页所以 再取p=2,q=3