Chapter9_1_特征值和乘幂法方法

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第九章 矩阵特征值问题的数值方法 (,Numerical methods for,eigenvalue,problems,),引言,/*Introduction*/,工程实践中有多种,振动问题,，如桥梁或建筑物的,振动，机械机件、飞机机翼的振动，工程实践中,有多种振动问题，如桥梁或建筑物的振动，机械,机件、飞机机翼的振动，及一些,稳定性分析,和相,关分析可转化为求矩阵特征值与特征向量的问题。,G,: Google Matrix,“the worlds largest matrix computation”.,4,300,000,000,x,:,PageRank,（网页级别）,vector,“,The $25,000,000,000 Eigenvector”,搜索引擎,设,A,是,n,阶矩阵,x,是非零列向量,.,如果有数,存在,满足,Ax,=,x,那么,称,x,是矩阵,A,关于特征,值,的特征向量,.,1 特征值与特征向量,/*,E,igenvalue,and eigenvector,*/,如果把右端写为,Ix,，那么又可写为,:,(,I-A,),x,=0,即,|,I,-A,| =0,记,它是关于参数,的,n,次多项式，称为矩阵,A,的特征多项式， 其中,a,0,=(-1),n,|,A,|.,齐次线性,方程组,定义,1,A,的特征值也称为,A,的特征根,.,显然,当,是,A,的一个特征值时,它必然是,f,(,)=0,的根,.,反之,如果,是,f,(,)=0,的根,那么齐次方程组,(,I-A,),x,=0,有非零解向量,x,使,Ax,=,x,成立,.,从而，,是,A,的一个特征值,.,矩阵特征值和特征向量有如下主要性质：,n,阶矩阵,A,是降秩矩阵的充分必要条件是,A,有零,特征值,.,设矩阵,A,与矩阵,B,相似，那么它们有相同的特,征值,.,n,阶矩阵,A,与,A,T,有相同的特征值,.,设,i,j,是,n,阶矩阵,A,的两个互异特征值，,x,、,y,分别是其相应的右特征向量和左特征向,量，那么，,x,T,y,=0 .,定理,1,定理,2,定理,3,定理,4,2,Hermite,矩阵特征值问题,设,A,为,n,阶矩阵，其共轭转置矩阵记为,A,H,.,如果,A,=,A,H,，那么，,A,称为,Hermite,矩阵,一、,Hermite,矩阵的有关性质,设 是,Hermite,矩阵,A,的,n,个特征值,.,有以下性质,:,全是实数,.,有相应的,n,个线性无关的特征向量，它们可以化,为一组标准酉交的特征向量组,即,是酉空间中的一组标准酉交基,.,记,U,=( ),它是一个酉阵，即,U,H,U,=,UU,H,=,I,，那么,即,A,与以 为对角元的对角阵相似,A,为正定矩阵的充分必要条件是 全为,正数,.,设 是,Hermite,矩阵,A,的,n,个特征值， 那么,因此,又由,得,定理,5,证明,如果,A,的,n,个特征值为,其相,应的标准酉交的特征向量为,那么有,设,A,是,Hermite,矩阵 ，那么,设,x,是一个非零向量,A,是,Hermite,矩阵,称,为矩阵,A,关于向量,x,的,Rayleigh,商，记为,R,(,x,).,或,定理,6,定理,7,二、极值定理,(,极值定理,),设,Hermite,矩阵的,n,个特征值为,，其相应的标准酉交特征向量为,用,C,k,表示酉空间,C,n,中任意的,k,维子空间，那么,或,定理,8,矩阵特征值问题的性态是很复杂的，通常分别就,单个特征值或整体特征值给出条件数进行分 析,.,对于,Hermite,矩阵,，由于其特征值问题的特殊性,质，,其特征值都是良态的,.,下面先证明,Hermite,矩,阵特征值的扰动定理,.,三、,Hermite,矩阵特征值问题的性态,矩阵特征值问题与求解线性方程组问题一样，都,存在当矩阵,A,的原始数据有小变化,(,小扰动,),时，,引起特征值问题的变化有大有小的问题，如果引,起的变化小，称 该特征值问题是,良态的,.,反之，,称为,病态的,.,(,扰动定理,),设矩阵,A,E,A,+,E,都是,n,阶,Hermite,矩阵，其特征值分别为, ,那么,设矩阵,A,关于特征值,1,2,n,的标准酉交,特征向量为,u,1,u,2, ,u,n,， 是由,u,i,u,i,+1, ,u,n,生成的,n,-,i,+1,维子空间,.,对 中任意非零向量,x,由极值定理,有,定理,9,证明,由定理,又由定理，对任意,x,0,，有,从而有,另一方面,A,=(,A,+,E,),-,E,.,那么，,重复上面的过程,可得,从而有,为矩阵,-,E,的特征值,记,，,设矩阵,A,和,A,=,A,+,E,都是,n,阶,Hermite,矩 阵，其,特征值分别为 和 ，,那么,这个,定理表明,，扰动矩阵,E,使,A,的特征值的变化,不会超过,E,2,.,一般,E,2,小，因此，,Hermite,矩阵特征值是良态的,.,定理,10,乘幂法是适用于求一般矩阵按模最大特征值及相应特征向量的算法,.,3,乘幂法,设,A,是,n,阶矩阵,其,n,个特征值按模从大到小排序为,又假设关于,1,2, ,n,的特征向量,v,1,v,2, ,v,n,线性无关,一、乘幂法,任意取定初始向量,x,0,建立迭代公式 ：,故当,k,时，,x,k,1,k,a,1,v,1,.,因此，,x,k,可看成是关于特征值,1,的近似特征向量,有一严重缺点，当|,1,|1,（或|,1,|0,时,按模最大特征值,1,及其相应的特征向量,v,1,的乘幂法的计算公式：,当,1,0,时,若,1,为,A,的实重根,幂法仍然有效,.,试用幂法求按模最大的特征值和相应的特征向量,例,1,通过,B,求,1,-,p,的速度快于通过,A,求,1,的速度,二、加速方法,幂法计算,A,的特征值,1,的收敛速度主要由 决定,有特征值,1,-,p,2,-,p, ,n,-,p,选择,p,使,1,-,p,仍为,B,的主特征值,且满足,求按模最小特征值及相应特征向量的,反幂法,又称,为,反迭代法,.,4,反幂法,反幂法可以求一个非奇异矩阵,A,的逆矩阵,A,-1,的按,模最小的特征值及相应的特征向量，又可以求,A,的某个近似特征值相应的特征向量,.,若,A,非奇异,且,Ax,=,x,则,A,-1,x,=,-1,x,因此,求,A,按模最小特征值就是求,A,-,1,按模最大特征值,一、,i,的近似求法,若,A,有特征值,i,i,有近似值,:,先对矩阵 进行,LU,分解,记,“,半迭代法,”的命名也由此而得,.,二、半迭代法,一种选取特殊的初始向量,x,0,的反幂法,选取初始向量,x,0,满足,x,0,=1,，这时,z,0,=,x,0,对照上页中的第二个式子,.,可把,z,0,看成满足,Le,=,z,0,这里，,e,=(1,1,1),T,而,z,0,的各个分量的取值多少,是无关重要的,这样,在第一个迭代步的计算中,只需求解上页中,的上三角方程组,Ux,1,=,e,.,假设,例,2,试用反幂法求矩阵,A,最接近于 的特征值和相应的特征向量,取,作半迭代，计算结果如表,由于,A,是对称矩阵，做一次,Rayleigh,商加速,与精确值,s,=2,相比，这次加速有较好效果,理论上，实对称矩阵,A,正交相似于,以,A,的特征值,为对角元 的 对角阵,.,问题是如何构造这样的正交,矩阵呢,? Jacobi,方法就是通过构造特殊的正交矩,阵 序列，通过相似变换使,A,的非对角线元素逐次,零化来实现对角化的,.,5 Jacobi,方法,一、平面旋转矩阵与相似约化,先看一个简单的例子,.,设 是二阶实对称矩阵,即,a,21,=,a,12,其特,征值为,1,2,.,容易验证,B,T,=,B,且,令,使得,当 时,为使,R,T,AR,为对角阵，要求,b,12,=,b,21,=0,解之得,:,当 时,可选取,一般,的,n,阶平面旋转矩阵,构造一个相似矩阵序列，使,A,k,收敛于一个对,角阵,.,其中,Q,k,为平面旋转矩阵，其旋转角,k,由,使,A,k,的绝对值最大元,a,(,k,),pq,=,a,(,k,),qp,=0,或按列依次,使,A,的非对角元 零化来确定,.,二、经典的,Jacobi,方法,设,A,是实对称矩阵，记,A,1,=,A,.,Jacobi,方法的基本思想是用迭代格式,A,k,+1,=,Q,T,k,A,k,Q,k,k,=1,2,设,A,是,n,阶实对称矩阵，那么由,Jacobi,方法产 生的相似矩阵序列,A,k,的非对角元收敛于,0.,也就 是说，,A,k,收敛,于以,A,的特征值为对角元的对角,记,其中,E,k,是,A,k,除主对角元,外的矩阵,.,由平面旋转矩阵的性质 中,对于,有,因此,定理,11,又由假设,因此,这样,便有,从而,当,循环,Jacobi,方法必须一次又一次扫描,才能使,A,k,收敛于对角阵 ，计算量很大,.,在实际计算中，往,往用一些特殊方法来控制扫描次数,减少计算量,.,减少阈值的方法通常是先固定一个正整数,M,n,，扫描一,次后，让,.,而阈值的下界是根据实际问题的精度,要求选定的,.,三、实用的,Jacobi,方法,下面介 绍一种应用最为广泛的特殊循环,Jacobi,方法,阈,Jacobi,方法,.,阈,Jacobi,方法首先确定一个阈值,，在对非对角元零化的,一次扫描中，只对其中绝对值 超过阈值的非对角元进行,零化,.,当所有非对角元素的绝对值都不超过阈值后，将阈,值减少， 再重复下一轮扫描，直至阈值充分小为止,.,当,A,k,+1,的非对角元素充分小，,Q,k,的第,j,列,q,j,可以看,成是近似特征值,a,(,k,+1),jj,相应的特征向量,了,.,四、用,Jacobi,方法计算特征向量,假定经过,k,次迭代得到,A,k,+1,=,R,T,k,R,T,1,AR,1,R,k,，,这时,A,k,+1,是满足精度要求的一个近似的对角阵,.,记,Q,k,=,R,1,R,2,R,k,=,Q,k,-1,R,k,，,则，,Q,k,是一个正交矩阵，,A,k,+1,=,Q,T,k,AQ,k,.,在实际计算中，把,Q,k,看成,是,Q,k,-1,右乘一个平面旋,转矩阵得到,.,不妨,记,Q,0,=,I,，,Q,k,的元素按下式计算：,理论上，一个实对称矩阵正交相似于一个以其特,征值为对角元的 对角阵,.,但是，经典的结果告诉,我们，一个大于,4,次的多项式方程不可能用有限次,四则运算 求根,.,因此，我们不可能期望只用有限,次相似变换将一个实对称矩阵约化为一个对角阵,.,下面先介绍将一个实对称矩阵相似约化为实对称,三对角矩阵的方法，再讨论求其特征值的对分法,.,6,对分法,一、相似约化为实对称三对角矩阵,将一个实对称矩阵正交相似约化为一个实对称三,对角矩阵的算法，可归纳如下：,记,A,(1),=,A,对,k,=1,2,n,-2,二、,Sturm,序列的性质,设实对称三对角矩阵为,其中,i,0 (,i,=1,2,n,-1),多项式序列,p,i,(,) (,i,=0,1,n,),称为,Sturm,序列,记,T,-,I,的第,i,阶主子式为,:,其特征矩阵为,T,-,I,.,定义,2,令,p,0,(,)1,，,p,1,(,)=,1,-,，,p,i,(,)=(,i,-,),p,i,-1,(,)-,2,i,-1,p,i,-2,(,),，,i,=2,3,n,p,i,(,),是,i,阶实对称矩阵的特征多项式，,因此, ,p,i,(,) (,i,=1,2,n,),的根全是实根,.,设,是,p,i,(,),的一个根，那么,p,i,-1,(,),p,i,+1,()0,即相邻的两个多项式无公,共根；,p,i,-1,(,),p,i,+1,()0,即,p,i,-1,(,),与,p,i,+1,(,),反号,.,p,i,(,),的根都是单根,并且将,p,i,+1,(,),的根严格,隔离,.,p,i,(,) (,i,=1,2,n,),的根都是 实根,.,当,i,为奇数,当,i,为偶数,定理,12,证明,定理,13,定理,14,定理,15,三、同号数和它的应用,设,p,0,(,)1,，,p,i,(,)(,i,=1,2,n,),是一个,Sturm,序列，称相邻的两个数中符号一致的数目为,同号数,，记为,a,i,(,).,若某个,p,i,(,)=0,，,规定与,p,i,-1,(,),反号,.,定义,3,定理,15,设两个实数,x,y,，那么，实对称 三对角矩阵,T,的特征多项式在区间,(,x,y,上根的数目为,a,(,x,)-,a,(,y,).,四、求,Hermite,矩阵特征值的对分法,对分法的计算可归纳为以下,4,个部分,确定矩阵,T,的全部特征值的分布区间,.,在区间,a,b,中,用区间对分的方法找出只含,T,的一个特征值的子区间,.,在只含一个特征值的子区间上的对分法,.,同号数的计算,.,