《幂法和反幂法》PPT课件.ppt

《《幂法和反幂法》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《幂法和反幂法》PPT课件.ppt（54页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第九章 特征值与特征向量的数值求法9.3 幂法和反幂法幂法和反幂法9.3.2反幂法和原点位移反幂法和原点位移9.3.1幂法和加速方法幂法和加速方法第九章 特征值与特征向量的数值求法幂法幂法是一种计算矩阵的按模最大的特征值与相应的特征向量的迭代方法。适合于大型稀疏矩阵反幂法反幂法是计算Hessenberg阵或对角阵的对应一个给定近似特征值的特征向量的有效方法.第九章 特征值与特征向量的数值求法9.3.1 幂法和加速方法幂法和加速方法 在一些工程，物理问题中，通常只需要我们求出矩阵的按模最大的特征值(称为A的主特征值)和相应的特征向量，对于解这种特征值问题，应用幂法是合适的。幂法是一种计算n阶实矩

2、阵A的主特征值的一种迭代法，它最大的优点是方法简单，对稀疏矩阵较合适，但有时收敛速度很慢 第九章 特征值与特征向量的数值求法 幂法的基本思想是任取一个非零的初始向量 ，由矩阵A构造一向量序列vkk=0,1,2,n(3.1)称为迭代向量由此计算按摸最大的特征值和特征向量。第九章 特征值与特征向量的数值求法 例1 设实对称矩阵A为利用幂法求A的按模最大特征值。解：直接求解A的特征方程得第九章 特征值与特征向量的数值求法利用幂法求A的按模最大特征值，任取迭代公式为考虑两个相邻向量相应分量之比第九章 特征值与特征向量的数值求法即两相邻迭代向量的对应非零分量的比值一定收敛到主特征值？即两相邻迭代向量的对

3、应非零分量的比值一定收敛到主特征值？不一定不一定.先讨论以下情况：先讨论以下情况：第九章 特征值与特征向量的数值求法(设 ),(3.2)于是 其中由假设，知从而即两个相邻迭代向量的对应非零分量成比例即两个相邻迭代向量的对应非零分量成比例,且主特征值为且主特征值为第九章 特征值与特征向量的数值求法即两相邻迭代向量的对应非零分量的比值收敛到主特征值.这种由已知非零向量 及矩阵A的乘幂 构造向量序列 计算A的主特征值 及相应特征向量的方法称为幂法。(3.3)(3.4)第九章 特征值与特征向量的数值求法由(3.3)式知，的收敛速度由比值 来确定 越小收敛越快，但当 1时收敛可能就很慢.总结上述讨论，有

4、 定理1设 有 个线性无关的特征向量，主特征值 满足 ，则对任何非零初始向量 ，均成立第九章 特征值与特征向量的数值求法两种特殊情况两种特殊情况第九章 特征值与特征向量的数值求法第九章 特征值与特征向量的数值求法例例1 1属于第一种情况的讨论。属于第一种情况的讨论。一般地，一般地，1.1.若迭代向量的各分量单调变化且有关系式若迭代向量的各分量单调变化且有关系式 则属于第一种情况。则属于第一种情况。2.2.若迭代向量的各分量不是单调变化，且有关系式若迭代向量的各分量不是单调变化，且有关系式 则属于第二种情况。则属于第二种情况。(3.5)第九章 特征值与特征向量的数值求法（或趋于零），这样造成计算

5、机中的（或趋于零），这样造成计算机中的“溢出溢出”。为了克服这个问题，。为了克服这个问题，利用向量的方向与长度无关这一性质利用向量的方向与长度无关这一性质,将迭代向量的长度将迭代向量的长度规范化规范化以以改进幂法改进幂法。用幂法计算用幂法计算A A的主特征值及对应的特征向量时的主特征值及对应的特征向量时,如果如果 ,迭代向量的各个不等于零的分量将随迭代向量的各个不等于零的分量将随 而趋于无穷而趋于无穷所谓向量长度所谓向量长度规范化规范化,就是将向量的分量同除以一个常数就是将向量的分量同除以一个常数,使使向量长度为向量长度为1,1,向量长度有多种度量法向量长度有多种度量法,可以采用可以采用 或或

6、 ,，其中，其中i0为所有绝对值最大的分量为所有绝对值最大的分量中最小的指标。中最小的指标。3.3.幂法的改进幂法的改进第九章 特征值与特征向量的数值求法任取初始向量：任取初始向量：迭代迭代规范化规范化则有迭代向量序列则有迭代向量序列 及规范化向量序列及规范化向量序列 。第九章 特征值与特征向量的数值求法由由(3.7)及及(3.8)式有式有(1)对规范化向量序列对规范化向量序列:先考虑先考虑 与计算与计算 的关系。的关系。由于由于及及其中其中第九章 特征值与特征向量的数值求法于是，于是，(2)对迭代向量序列对迭代向量序列:即即 绝绝对对值值最最大大的的分分量量当当 时时，趋趋向向于于特特征征根

7、根 。注意：改进的幂法中主特征值 不是两相邻迭代向量 的对应非零分量的比值。第九章 特征值与特征向量的数值求法 （2）设）设A特征值满足特征值满足定理定理2 （1 1）设）设 有有n个线性无关的特征向量；个线性无关的特征向量；且且 （3）及及 由由改进幂法改进幂法得到的规范化向量序列得到的规范化向量序列序列序列(3.7)(3.7)式式),),则有则有且收敛速度由比值且收敛速度由比值 确定。确定。及及迭代向量迭代向量改进的幂法改进的幂法下面我们把改进的幂法简称为幂法。下面我们把改进的幂法简称为幂法。第九章 特征值与特征向量的数值求法用（改进的）用（改进的）幂法幂法求矩阵求矩阵A的主特征值和主特征

8、向量的步骤：的主特征值和主特征向量的步骤：第一步：由第一步：由vu，计算，计算第二步：由第二步：由v1,u1，计计算算第三步：判断第三步：判断第九章 特征值与特征向量的数值求法第九章 特征值与特征向量的数值求法第九章 特征值与特征向量的数值求法解：取初始向量 ,按(3.7)迭代5次得到数据如下 表:k (规范化向量)0 1 1 1 1 1 1 1 0.2143 0.4821 1 12.00 27.00 56.00 2 0.1875 0.4483 1 8.357 19.98 44.57 3 0.1860 0.4463 1 8.168 19.60 43.92 4 0.1895 0.4460 1 8

9、.157 19.57 43.88 5 0.1859 0.4460 1 8.156 19.57 43.88 例2：用幂法计算下面矩阵的主特征值及对应的特征向量。第九章 特征值与特征向量的数值求法对应的特征向量为:故按模特征值为:第九章 特征值与特征向量的数值求法例例3 用幂法求矩阵用幂法求矩阵的主特征值和主特征向量的主特征值和主特征向量.第九章 特征值与特征向量的数值求法 K 0 (1.0000,1.0000,1)1 (0.9091,0.8182,1)2.7500000 5 (0.7651,0.6674,1)2.5887918 10 (0.7494,0.6508,1)2.5380029 15 (

10、0.7483,0.6497,1)2.5366256 20 (0.7482,0.6497,1)2.5365323 表表9-1有效数字。有效数字。第九章 特征值与特征向量的数值求法第九章 特征值与特征向量的数值求法第九章 特征值与特征向量的数值求法第九章 特征值与特征向量的数值求法第九章 特征值与特征向量的数值求法第九章 特征值与特征向量的数值求法第九章 特征值与特征向量的数值求法第九章 特征值与特征向量的数值求法第九章 特征值与特征向量的数值求法第九章 特征值与特征向量的数值求法3.Rayleigh商加速商加速第九章 特征值与特征向量的数值求法第九章 特征值与特征向量的数值求法9.3.2反幂法和

11、原点位移反幂法和原点位移反幂法是计算矩阵按模最小的特征值及特征向量的方反幂法是计算矩阵按模最小的特征值及特征向量的方法，也是修正特征值、求相应特征向量的最有效的方法。法，也是修正特征值、求相应特征向量的最有效的方法。第九章 特征值与特征向量的数值求法计算计算A的按模最小的特征值的按模最小的特征值 的问题就是计算的问题就是计算A-1-1按模最大的按模最大的特征值特征值 问题。问题。反幂法迭代公式：反幂法迭代公式：任取初始向量，任取初始向量，设设 为非奇异矩阵为非奇异矩阵,A的特征值满足：的特征值满足：,对应特征向量对应特征向量 线性无关，线性无关，则则A-1-1的特征值为的特征值为 ，特征向量，

12、特征向量1 1、反幂法用来计算矩阵、反幂法用来计算矩阵A按模最小的特征值及对应的特征向量按模最小的特征值及对应的特征向量第九章 特征值与特征向量的数值求法若若 有有n个线性无关的特征向量且其特征值满足：个线性无关的特征向量且其特征值满足：则由反幂法则由反幂法(3.11)(3.11)构造的向量序列构造的向量序列 满足：满足：且收敛速度由比值且收敛速度由比值 确定。确定。第九章 特征值与特征向量的数值求法第九章 特征值与特征向量的数值求法第九章 特征值与特征向量的数值求法第九章 特征值与特征向量的数值求法111/45/85/819/1619/1667/3205/8121/167/475/32301

13、/37/67/87/421/1623/869/32由于 的平均值之倒数为而A的按模最小特征值精确值为可见已获得了较好的特征值。第九章 特征值与特征向量的数值求法若若A的特征值为的特征值为 ，则，则A-pI的特征值为的特征值为 问题：问题：已知已知 的特征值的特征值 的一个近似值的一个近似值 （通常用（通常用其它方法得到），求其它方法得到），求 对应的特征向量对应的特征向量 （近似）。（近似）。如果如果(A-pI)-1-1存在存在,则特征值为则特征值为对应对应的特征向量的特征向量2 2反幂法的一个应用反幂法的一个应用取取 ，且设，且设 是离是离p最近的特征值，即最近的特征值，即即即 ,说明说明是

14、是(A-p-pI)-1-1 的主特的主特征根征根第九章 特征值与特征向量的数值求法对对(A-pI)-1-1应用幂法得到反幂法计算公式：应用幂法得到反幂法计算公式：即即其中其中线性方程组线性方程组取初始向量取初始向量第九章 特征值与特征向量的数值求法于是于是第九章 特征值与特征向量的数值求法结论结论定理定理4 4（1)1)设设 有有n个线性无关特征向量个线性无关特征向量,即即 且收敛速度由比值且收敛速度由比值 确定。确定。（2 2）取）取 （为特征值（为特征值 的一个近似值），设的一个近似值），设(A-pI)-1-1存在存在序列序列 满足：满足：且且 ,则由反幂法迭代公式（则由反幂法迭代公式（3

15、.123.12）构造向量）构造向量第九章 特征值与特征向量的数值求法值的大体位置时，用此法值的大体位置时，用此法最合适最合适（该方法是一个有效的方法）。（该方法是一个有效的方法）。说明说明:(1)(1)定理定理4 4可以计算特征向量可以计算特征向量xj。当知道。当知道A的某一个特征的某一个特征（2 2）取）取 为特征值为特征值 的一个近似值的一个近似值,当当A的特征值分离情的特征值分离情反幂法迭代公式可通过解方程组反幂法迭代公式可通过解方程组(A-pI)vk=uk-1-1来求来求vk。为了节。为了节况较好时况较好时,r 很小很小,则它本身则它本身收敛速度很快收敛速度很快。同时。同时改进改进了特

16、征值。了特征值。省计算量，可省计算量，可先先将将(A-pI)进行进行三角分解三角分解P(A-pI)=)=LU。其中。其中P为置为置换阵，于是每次迭代求换阵，于是每次迭代求vk相当于求解两个三角形方程组。相当于求解两个三角形方程组。取取v0=u0,即选即选u0 0使使Uv1 1=L-1-1Pu0 0=(1,1)=(1,1)T,回代求解即求得回代求解即求得v1 1。第九章 特征值与特征向量的数值求法小结：给定的特征值小结：给定的特征值 的一个近似值的一个近似值p，求求p对应的特征向量对应的特征向量 (近似近似)的步骤：的步骤：第一步：将第一步：将(A-pI)进行进行三角分解三角分解(A-pI)=)

17、=LU，(或或P(A-pI)=)=LU，其其中中P为为排列排列阵阵）第二步：由第二步：由Uv1=(1,1,1)=(1,1,1)T T，解方程解方程组组求得求得v1,u1，其中其中第三步：由第三步：由LUv2=Pu1（或（或LUv2=Pu1）,解方程解方程组组求得求得v2,u2，其中其中第九章 特征值与特征向量的数值求法例例7.2 用反幂法求下列矩阵的接近于用反幂法求下列矩阵的接近于p=1.2679的特征值的特征值(精确特征值精确特征值其中其中第九章 特征值与特征向量的数值求法第九章 特征值与特征向量的数值求法例例7.3 下列矩阵下列矩阵A的主特征值接近于的主特征值接近于p=-6.42，用反幂法求更精确的主，用反幂法求更精确的主特征值及其特征向量（计算两步即可）特征值及其特征向量（计算两步即可）其中其中第九章 特征值与特征向量的数值求法第九章 特征值与特征向量的数值求法