幂法和反幂法.ppt

9.3幂法和反幂法,9.3.2反幂法和原点位移,9.3.1幂法和加速方法,幂法是一种计算矩阵的按模最大的特征值与相应的特征向量的迭代方法。,适合于大型稀疏矩阵,反幂法是计算Hessenberg阵或对角阵的对应一个给定近似特征值的特征向量的有效方法.,9.3.1幂法和加速方法,在一些工程，物理问题中，通常只需要我们求出矩阵的按模最大的特征值(称为A的主特征值)和相应的特征向量，对于解这种特征值问题，应用幂法是合适的。,幂法是一种计算n阶实矩阵A的主特征值的一种迭代法，它最大的优点是方法简单，对稀疏矩阵较合适，但有时收敛速度很慢,幂法的基本思想是任取一个非零的初始向量，由矩阵A构造一向量序列vkk=0,1,2,n,(3.1),称为迭代向量由此计算按摸最大的特征值和特征向量。,例1设实对称矩阵A为,利用幂法求A的按模最大特征值。,解：直接求解A的特征方程,得,利用幂法求A的按模最大特征值，任取,迭代公式为,考虑两个相邻向量相应分量之比,即两相邻迭代向量的对应非零分量的比值一定收敛到主特征值？,不一定.先讨论以下情况：,(设),(3.2),于是,其中,由假设，知,从而,即两个相邻迭代向量的对应非零分量成比例,且主特征值为,即两相邻迭代向量的对应非零分量的比值收敛到主特征值.,这种由已知非零向量及矩阵A的乘幂构造向量序列计算A的主特征值及相应特征向量的方法称为幂法。,(3.3),(3.4),由(3.3)式知，的收敛速度由比值来确定越小收敛越快，但当1时收敛可能就很慢.,总结上述讨论，有,定理1设有个线性无关的特征向量，主特征值满足,，,则对任何非零初始向量，,均成立,两种特殊情况,例1属于第一种情况的讨论。,一般地，1.若迭代向量的各分量单调变化且有关系式则属于第一种情况。,2.若迭代向量的各分量不是单调变化，且有关系式则属于第二种情况。,(3.5),（或趋于零），这样造成计算机中的“溢出”。为了克服这个问题，,利用向量的方向与长度无关这一性质,将迭代向量的长度规范化,以改进幂法。,用幂法计算A的主特征值及对应的特征向量时,如果,迭代向量的各个不等于零的分量将随而趋于无穷,所谓向量长度规范化,就是将向量的分量同除以一个常数,使,向量长度为1,向量长度有多种度量法,可以采用或,，其中i0为所有绝对值最大的分量,中最小的指标。,3.幂法的改进,任取初始向量：,迭代,规范化,则有迭代向量序列及规范化向量序列。,由(3.7)及(3.8)式有,(1)对规范化向量序列:,先考虑与计算的关系。,由于,及,其中,于是，,(2)对迭代向量序列:,即绝对值最大的分量当时，趋向于特征根。,注意：改进的幂法中主特征值不是两相邻迭代向量的对应非零分量的比值。,（2）设A特征值满足,定理2（1）设有n个线性无关的特征向量；,且,（3）及由改进幂法得到的规范化向量序列,序列(3.7)式),则有,且收敛速度由比值确定。,及迭代向量,改进的幂法,下面我们把改进的幂法简称为幂法。,用（改进的）幂法求矩阵A的主特征值和主特征向量的步骤：,第一步：由vu，计算,第二步：由v1,u1，计算,第三步：判断,解：取初始向量,按(3.7)迭代5次得到数据如下表:k(规范化向量)011111110.21430.4821112.0027.0056.0020.18750.448318.35719.9844.5730.18600.446318.16819.6043.9240.18950.446018.15719.5743.8850.18590.446018.15619.5743.88,例2：用幂法计算下面矩阵的主特征值及对应的特征向量。,表9-1,有效数字。,3.Rayleigh商加速,9.3.2反幂法和原点位移,反幂法是计算矩阵按模最小的特征值及特征向量的方法，也是修正特征值、求相应特征向量的最有效的方法。,计算A的按模最小的特征值的问题就是计算A-1按模最大的,特征值问题。,反幂法迭代公式：,任取初始向量，,设为非奇异矩阵,A的特征值满足：,对应特征向量线性无关，,则A-1的特征值为，特征向量,1、反幂法用来计算矩阵A按模最小的特征值及对应的特征向量,若有n个线性无关的特征向量且其特征值满足：,则由反幂法(3.11)构造的向量序列满足：,且收敛速度由比值确定。,若A的特征值为，则A-pI的特征值为,问题：已知的特征值的一个近似值（通常用,其它方法得到），求对应的特征向量（近似）。,如果(A-pI)-1存在,则特征值为,对应的特征向量,2反幂法的一个应用,取，且设是离p最近的特征值，即,即,说明,是(A-pI)-1的主特征根,对(A-pI)-1应用幂法得到反幂法计算公式：,即,其中,线性方程组,取初始向量,于是,结论,定理4（1)设有n个线性无关特征向量,即,且收敛速度由比值确定。,（2）取（为特征值的一个近似值），设(A-pI)-1存在,序列满足：,且,则由反幂法迭代公式（3.12）构造向量,值的大体位置时，用此法最合适（该方法是一个有效的方法）。,说明:(1)定理4可以计算特征向量xj。当知道A的某一个特征,（2）取为特征值的一个近似值,当A的特征值分离情,反幂法迭代公式可通过解方程组(A-pI)vk=uk-1来求vk。为了节,况较好时,r很小,则它本身收敛速度很快。同时改进了特征值。,省计算量，可先将(A-pI)进行三角分解P(A-pI)=LU。其中P为置,换阵，于是每次迭代求vk相当于求解两个三角形方程组。,取v0=u0,即选u0使Uv1=L-1Pu0=(1,1)T,回代求解即求得v1。,小结：给定的特征值的一个近似值p，求p对应的特征向量(近似)的步骤：,第一步：将(A-pI)进行三角分解(A-pI)=LU，(或P(A-pI)=LU，其中P为排列阵）,第二步：由Uv1=(1,1,1)T，解方程组求得v1,u1，其中,第三步：由LU