第8章矩阵特征值与特征向量的计算PPT讲稿.ppt

《第8章矩阵特征值与特征向量的计算PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《第8章矩阵特征值与特征向量的计算PPT讲稿.ppt（64页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第8章矩阵特征值与特征向量的计算研究生学位课程研究生学位课程 数值分析数值分析1第1页，共64页，编辑于2022年，星期一研究生学位课程研究生学位课程 数值分析数值分析2PA()是的高次的多项式，它的求根是很困难的。设法通过数值方法是求它的根。通常对某个特征值，可以用些针对性的方法来求其近似值。若要求所有的特征值，则可以对A做一系列的相似变换，“收敛”到对角阵或上（下）三角阵，从而求得所有特征值的近似。n阶方阵A的特征值是特征方程 PA()=det(A-E)=0 的根.A的特征向量是齐次线性方程组 (A-E)x=0 的非零解.第2页，共64页，编辑于2022年，星期一研究生学位课程研究生学位课

2、程 数值分析数值分析3定理定理1：A R n n，1,n为为A的特征值的特征值，则则（2）A的行列式值等于全体特征值之积，即的行列式值等于全体特征值之积，即（1）A的迹数等于特征值之和，即的迹数等于特征值之和，即特征根和特征向量的基本结论。定理定理2 2 设为A R n n的特征值且Ax=x，其中x不为0,则（1 1）c为为cA的特征值（的特征值（c为常数且不为为常数且不为0);0);（2 2）-p为为A-pI 的特征值，即的特征值，即(A-pI)x=(-p)x;（3 3）k为为Ak的特征值；的特征值；（4 4）设设A A为非奇异阵，那么为非奇异阵，那么 且且 为为 特征值，即特征值，即第3页

3、，共64页，编辑于2022年，星期一研究生学位课程研究生学位课程 数值分析数值分析4定义定义 设矩阵设矩阵A,B R n n，若有可逆阵若有可逆阵P，使使 则称则称A与与B相似相似。定理定理 若矩阵若矩阵A,B R n n且相似且相似，则则（1）A与与B的特征值完全相同的特征值完全相同；（2）若若x是是B的特征向量的特征向量，则则Px便为便为A的特征向量的特征向量。第4页，共64页，编辑于2022年，星期一研究生学位课程研究生学位课程 数值分析数值分析58.1 幂法和反幂法幂法和反幂法 8.1.1 幂法幂法 幂法是用来求矩阵A按模最大的特征值和相应的特征向量的方法.也称为主特征值主特征值和主特

4、征向量主特征向量。设A是单构矩阵,即A有n个线性无关的特征向量.A的n个特征值为|1 2 n 对应的特征向量为1,2,n 线性无关.我们要求1 和1.幂法的基本思想是取初始非零向量x0Rn,作迭代 xk+1=Axk=Ak+1x(0),k=0,1,2,产生迭代序列xk.由于1,2,n 线性无关,从而有 x0 =11+22+nn (8.3)第5页，共64页，编辑于2022年，星期一研究生学位课程研究生学位课程 数值分析数值分析6故有 xk =Akx0=11k1+22k2+nnkn设|12n,这时,上式可写成若10,则对充分大的k有 因而有 从而特征向量1 xk.乘幂法的收敛速度取决于|2/1|的大

5、小.第6页，共64页，编辑于2022年，星期一研究生学位课程研究生学位课程 数值分析数值分析7实际计算时，常把每一步计算的迭代向量xk规范化。对非零向量x,用max(x)表示x的按绝对值最大的分量,称向量y=x/max(x)为向量x的规范化向量.例如,设向量x=(2,1,-5,-1)T,则max(x)=5,y=(0.4,0.2,-1,-0.2)T.可见规范化向量y总满足y=1.幂法的规范化计算公式为:任取初始向量x0=y0 0 0,计算可得第7页，共64页，编辑于2022年，星期一研究生学位课程研究生学位课程 数值分析数值分析8所以其收敛速度由比值|2/1|来确定.又由于所以因此,当k充分大时

6、可取:1 mk,1 xk.第8页，共64页，编辑于2022年，星期一研究生学位课程研究生学位课程 数值分析数值分析9用乘幂法求A的按模最大的特征值和相应特征向量.例例8.1 设 解解 取初值x0=y0=(1,1,1)T,计算得km kxk0123101112107.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(1,0.714316,-0.249895)T 可取 1 6.00

7、0837,1(1,0.714316,-0.249895)T.实际上,A的3个特征值分别为1=6,2=3,3=2.第9页，共64页，编辑于2022年，星期一研究生学位课程研究生学位课程 数值分析数值分析108.1.2 加速技术加速技术由于所以,乘幂法收敛速度取决于比值|2/1|,当|2/1|1时,收敛是很慢的.1 1.Aitken Aitken 加速方法加速方法由上式可知可见,序列mk线性收敛于1.构造Aitken序列会达到加速收敛的目的.第10页，共64页，编辑于2022年，星期一研究生学位课程研究生学位课程 数值分析数值分析11 2 2.原点位移法原点位移法 作矩阵B=A-pE,则B的特征值

8、为qi=i-p(i=1,2,n),而且对应的特征向量相同.如果选取p,使q1仍然是B的按模最大特征值，且满足则对B B 应用乘幂法可达到加速收敛的目的。程序见P170，例8.2第11页，共64页，编辑于2022年，星期一研究生学位课程研究生学位课程 数值分析数值分析12 反幂法是求矩阵按模最小的特征值和相应特征向量的方法.8.1.3 反幂法反幂法 设A是n阶非奇异矩阵,其特征值为|1|2|n-1|n|0对应的特征向量为1,2,n,则有A-1的特征值为对应的特征向量为n,n-1,1.要想求n和n只需对A-1应用乘幂法,任取初始向量x0=y00,作第12页，共64页，编辑于2022年，星期一研究生

9、学位课程研究生学位课程 数值分析数值分析13也可将上式改写成式(8.8)称为反幂法.显然有每一步求xk需要求解线性方程组,可采用LU分解法求解.第13页，共64页，编辑于2022年，星期一研究生学位课程研究生学位课程 数值分析数值分析14(8.9)第14页，共64页，编辑于2022年，星期一研究生学位课程研究生学位课程 数值分析数值分析15 Jacobi方法是求实对称矩阵全部特征值和特征向量的一种矩阵变换方法。8.2 Jacobi 方法方法 实对称矩阵A具有下列性质：(1)A的特征值均为实数;其对应的特征向量线性无关且两两正交。（2）存在正交矩阵Q，使QTAQ=diag(1,2,n),而且 Q

10、的第i个列向量恰为i的特征向量;（3）若记A1=QTAQ,则A1仍为对称矩阵.直接找直接找Q不大可能。我们可以构造一系列特殊形式的正交阵不大可能。我们可以构造一系列特殊形式的正交阵Q1,.,Qn对对A作正交变换，作正交变换，使得使得对角元素比重对角元素比重逐次增加逐次增加，非对角元非对角元变小。变小。当非对角元已经小得无足轻重时，当非对角元已经小得无足轻重时，可以近似认为对角元就是可以近似认为对角元就是A的所有的所有特征值。特征值。Jacobi方法就是这样一类方法。方法就是这样一类方法。第15页，共64页，编辑于2022年，星期一研究生学位课程研究生学位课程 数值分析数值分析16平面解析几何中

11、的平面坐标旋转变换表示平面上坐标轴旋转角的变换.8.2.1 平面旋转矩阵平面旋转矩阵(旋转正交相似变换）旋转正交相似变换）在三维空间直角坐标系中,ox1y1平面绕着oz1轴旋转角的坐标变换为 一般地,在n维向量空间Rn中,沿着xi yj平面旋转角的变换矩阵为第16页，共64页，编辑于2022年，星期一研究生学位课程研究生学位课程 数值分析数值分析17称Rij()为平面旋转矩阵或平面旋转矩阵或Givens变换矩阵变换矩阵.Rij()具有下列性质:i j 第17页，共64页，编辑于2022年，星期一研究生学位课程研究生学位课程 数值分析数值分析18第18页，共64页，编辑于2022年，星期一研究生

12、学位课程研究生学位课程 数值分析数值分析19第19页，共64页，编辑于2022年，星期一研究生学位课程研究生学位课程 数值分析数值分析20 设实对称矩阵A=(apq)nn,记B=RijT()ARij()=(bpq)nn则它们元素之间有如下关系:（2）Rij()为正交矩阵,即Rij-1()=RijT();（3）如果A为对称矩阵,则RijT()ARij()也为对称矩阵,且与A有相同的特征值.（4）RijT()A仅改变A的第i行与第j行元素,ARij()仅改变A的第i列与第j列元素.第20页，共64页，编辑于2022年，星期一研究生学位课程研究生学位课程 数值分析数值分析21所以有从而由上面两式可得

13、 如果aij0,适当选取角,使第21页，共64页，编辑于2022年，星期一研究生学位课程研究生学位课程 数值分析数值分析22只需角满足 由式(8.15),令t=tan,则t满足方程t2+2dt-1=0为保证|/4,取绝对值较小的根,有于是且且第22页，共64页，编辑于2022年，星期一研究生学位课程研究生学位课程 数值分析数值分析23非对角线元素的平方和，非对角线元素的平方和，由由 可知可知第23页，共64页，编辑于2022年，星期一研究生学位课程研究生学位课程 数值分析数值分析24 我们有以下的收敛性定理保证上述计算过程。我们有以下的收敛性定理保证上述计算过程。8.2.2 Jacobi方法方

14、法 第24页，共64页，编辑于2022年，星期一研究生学位课程研究生学位课程 数值分析数值分析25 收敛性定理收敛性定理证证则有反复利用上式，即得反复利用上式，即得第25页，共64页，编辑于2022年，星期一研究生学位课程研究生学位课程 数值分析数值分析26 设设k充分大时，有充分大时，有的近似特征值.的对角线元素就是为对角阵,则kAAD 这里需要说明一点这里需要说明一点:并不是对矩阵并不是对矩阵A的每一对非的每一对非对角线非零元素进行一次这样的变换就能得到对对角线非零元素进行一次这样的变换就能得到对角阵角阵.因为在用变换消去因为在用变换消去 的时候的时候,只有第只有第 i 行行,第第 j 行

15、行,第第 i 列列,第第 j 列元素在变化列元素在变化,如果如果 或或 为零为零,经变换后又往往不是零了经变换后又往往不是零了.因此,Qk=RT1RT2RTk 的列向量xj(j=1,2,n)为A的近似特征向量.第26页，共64页，编辑于2022年，星期一研究生学位课程研究生学位课程 数值分析数值分析27的全部特征值.解解 记 A0=A,取i=1,j=2,aij(0)=a12(0)=2,于是有例例 用Jacobi 方法计算对称矩阵从而有第27页，共64页，编辑于2022年，星期一研究生学位课程研究生学位课程 数值分析数值分析28所以 再取i=2,j=3,aij(1)=a23(1)=2.02019

16、0,类似地可得以下依次有第28页，共64页，编辑于2022年，星期一研究生学位课程研究生学位课程 数值分析数值分析29从而A的特征值可取为 12.125825,28.388761,34.485401 特征向量为R1TR2TRkT第29页，共64页，编辑于2022年，星期一研究生学位课程研究生学位课程 数值分析数值分析30 为了减少搜索非对角线绝对值最大元素时间,对经典的Jacobi方法可作进一步改进.1.循环循环Jacobi方法方法:按(1,2),(1,3),(1,n),(2,3),(2,4),(2,n),(n-1,n)的顺序,对每个(i,j)的非零元素aij作Jacobi变换,使其零化,逐次

17、重复扫描下去,直至S(A)|n|0，其相应的n个线性无关特征向量为x1,x2,xn.记X(x1,x2,xn),Y=X.如果Y存在LU分解，那么，矩阵序列Ak基本收敛于上三角矩阵R.这里，基本收敛的含义指Ak的对角元均收敛，且严格下三角部分的元素均收敛于零，但严格上三角部分的元素没有收敛的要求。定理 设n阶矩阵A非奇异实对称矩阵，则矩阵序列Ak收敛于对角阵。第33页，共64页，编辑于2022年，星期一研究生学位课程研究生学位课程 数值分析数值分析34QRQR方法方法收敛性收敛性 第34页，共64页，编辑于2022年，星期一研究生学位课程研究生学位课程 数值分析数值分析35QRQR方法方法收敛性收

18、敛性第35页，共64页，编辑于2022年，星期一研究生学位课程研究生学位课程 数值分析数值分析36 QR方法运算量很大，为了减少运算量，常在使用QR方法之前把矩阵A简化为拟上三角矩阵。或称之为海森伯格矩阵(次对角元以下的元素全为零)。8.3.2 化一般矩阵为拟上三角矩阵化一般矩阵为拟上三角矩阵 形状为形状为可以用镜面反射矩阵将可以用镜面反射矩阵将A化为化为Hessenberg形形,下面介绍。下面介绍。第36页，共64页，编辑于2022年，星期一研究生学位课程研究生学位课程 数值分析数值分析37定义定义8.2为为镜面反射矩阵镜面反射矩阵，或，或Householder变换矩阵变换矩阵。Houhol

19、der矩阵矩阵H=H(v)有如下性质：有如下性质：(1)(2)(3)记记S为以为以v为法向量的平面为法向量的平面,则几何上则几何上x与与y=Hx关于平面关于平面S对称对称。因为因为上式表明向量上式表明向量x-y与与v平行，注意到平行，注意到y与与x的长度相等，于是的长度相等，于是x经变换后的象经变换后的象y=Hx是是x关于关于s对称的向量，如下图所示。对称的向量，如下图所示。第37页，共64页，编辑于2022年，星期一研究生学位课程研究生学位课程 数值分析数值分析38xvyx-y据前面定义和性质，据前面定义和性质，有下面的定理。有下面的定理。定理定理8.4得得Hx=y。证证第38页，共64页，

20、编辑于2022年，星期一研究生学位课程研究生学位课程 数值分析数值分析39由此可得由此可得定理得证。定理得证。第39页，共64页，编辑于2022年，星期一研究生学位课程研究生学位课程 数值分析数值分析40与平面旋转不同的是，镜面反射变换可成批的消去向量的非零元。程序见P187第40页，共64页，编辑于2022年，星期一研究生学位课程研究生学位课程 数值分析数值分析41与平面旋转变换不同的是，镜面反变换可成批的消去向量的非零元与平面旋转变换不同的是，镜面反变换可成批的消去向量的非零元将任意矩阵将任意矩阵A简化为海森伯格矩阵的步骤如下：简化为海森伯格矩阵的步骤如下：第41页，共64页，编辑于202

21、2年，星期一研究生学位课程研究生学位课程 数值分析数值分析42第42页，共64页，编辑于2022年，星期一研究生学位课程研究生学位课程 数值分析数值分析43第43页，共64页，编辑于2022年，星期一研究生学位课程研究生学位课程 数值分析数值分析44第44页，共64页，编辑于2022年，星期一研究生学位课程研究生学位课程 数值分析数值分析45第45页，共64页，编辑于2022年，星期一研究生学位课程研究生学位课程 数值分析数值分析46第46页，共64页，编辑于2022年，星期一研究生学位课程研究生学位课程 数值分析数值分析47第47页，共64页，编辑于2022年，星期一研究生学位课程研究生学位

22、课程 数值分析数值分析48第48页，共64页，编辑于2022年，星期一研究生学位课程研究生学位课程 数值分析数值分析49用用Household方法对矩阵方法对矩阵A作正交相似变换作正交相似变换,使使A相相似与上似与上Hessenberg阵，算法如下：阵，算法如下：第49页，共64页，编辑于2022年，星期一研究生学位课程研究生学位课程 数值分析数值分析50第50页，共64页，编辑于2022年，星期一研究生学位课程研究生学位课程 数值分析数值分析51、用、用 GivensGivens变换对变换对上上Hessenberg阵作阵作QR分解分解第51页，共64页，编辑于2022年，星期一研究生学位课程

23、研究生学位课程 数值分析数值分析52第52页，共64页，编辑于2022年，星期一研究生学位课程研究生学位课程 数值分析数值分析53第53页，共64页，编辑于2022年，星期一研究生学位课程研究生学位课程 数值分析数值分析54第54页，共64页，编辑于2022年，星期一研究生学位课程研究生学位课程 数值分析数值分析55第55页，共64页，编辑于2022年，星期一研究生学位课程研究生学位课程 数值分析数值分析56第56页，共64页，编辑于2022年，星期一研究生学位课程研究生学位课程 数值分析数值分析57第57页，共64页，编辑于2022年，星期一研究生学位课程研究生学位课程 数值分析数值分析58

24、第58页，共64页，编辑于2022年，星期一研究生学位课程研究生学位课程 数值分析数值分析59第59页，共64页，编辑于2022年，星期一研究生学位课程研究生学位课程 数值分析数值分析60第60页，共64页，编辑于2022年，星期一研究生学位课程研究生学位课程 数值分析数值分析61第61页，共64页，编辑于2022年，星期一研究生学位课程研究生学位课程 数值分析数值分析62算法：用算法：用Givens方法对上方法对上Hessenberg阵阵A作作 正交分解正交分解,A=QR。第62页，共64页，编辑于2022年，星期一研究生学位课程研究生学位课程 数值分析数值分析63算法：用算法：用Givens方法对上方法对上Hessenberg阵阵A作作 正交分解正交分解A=QR，求，求A 的全部特征值。的全部特征值。第63页，共64页，编辑于2022年，星期一研究生学位课程研究生学位课程 数值分析数值分析64练习题练习题第第194页页 习题习题88-2,8-3-8 第64页，共64页，编辑于2022年，星期一