《北航数值分析B第三章课件Ch3.2》由会员分享，可在线阅读，更多相关《北航数值分析B第三章课件Ch3.2（25页珍藏版）》请在金锄头文库上搜索。
1、2 2 幂法及反幂法幂法及反幂法2.1 2.1 幂法幂法适合于计算大型稀疏矩阵的主特征值（按模最大的特征值）适合于计算大型稀疏矩阵的主特征值（按模最大的特征值）问题的提法：问题的提法：称称 为为迭代向量迭代向量。 (2.2) 幂法的基本思想幂法的基本思想: : 任取一个非零初始向量任取一个非零初始向量 ，和对应的特征向量。和对应的特征向量。即即，且且 线性无关。求矩阵线性无关。求矩阵A的的主特主特征值征值及对应的及对应的特征向量特征向量。由矩阵由矩阵A的乘幂构造一向量序列的乘幂构造一向量序列 设设 , ,其特征值为其特征值为 , ,对应特征向量为对应特征向量为 首先讨论首先讨论则则幂法幂法:
2、:问题：问题：即即 ，且且 ，线性无，线性无关。特征值满足：关。特征值满足： （且（且设） 设设 , ,其特征值为其特征值为 , ,对应特征向量为对应特征向量为 的的特征向量特征向量。1.1.A特征值中特征值中 为强占优为强占优, ,即即线性无关线性无关 , ,即即 为Rn中一个基，于是中一个基，于是对任意对任意的初始向量的初始向量 有展开式有展开式。 ( ( 用用 的线性组合表示的线性组合表示) ) , ,即即 为强占优。求矩阵的为强占优。求矩阵的主特征值主特征值 及对应及对应即即且收敛速度由比值且收敛速度由比值 确定。确定。说明，当说明，当k充分大时，有充分大时，有 ，或，或 越来越接近特
3、征向量越来越接近特征向量所以有所以有其中其中 当当k =2,3, =2,3, 时，时， 从而从而由假设（由假设（2.12.1）式）式 , ,得得其次讨论主特征值其次讨论主特征值 的计算。的计算。表示表示的第的第i个分量，个分量，则则相相邻迭代向量的分量的比迭代向量的分量的比值为为 即相邻迭代向量分量的比值收敛到主特征值即相邻迭代向量分量的比值收敛到主特征值 , ,且收敛速度由且收敛速度由则有则有 敛可能很慢。敛可能很慢。比值比值 来度量来度量, ,r 越小收敛越快越小收敛越快, , 当当 而接近于而接近于1 1时时, ,收收结论：结论： 定理定理7（1 1）设）设 有有n个线性无关的特征向量；
4、个线性无关的特征向量； （2）设）设A的特征值满足的特征值满足 （3）幂法：）幂法：则则 2.A的的主特征值为实的主特征值为实的r重根，即重根，即问题：问题：即即 ，且且 ，线性无，线性无关。特征值满足：关。特征值满足： 设设 , ,其特征值为其特征值为 , ,对应特征向量为对应特征向量为 , ,求矩阵的求矩阵的主特征值主特征值 及对应及对应的的特征向量特征向量。幂法幂法: :对任意的初始向量对任意的初始向量 有有不全为零），则有不全为零），则有从而从而其中其中 ，且，且因此，当因此，当k充分大时充分大时, , 接近于与接近于与 对应的特征向量的某个对应的特征向量的某个线性组合线性组合 ( (
5、 不全为零不全为零) ) 。（且且设（或趋于零），这样造成计算机中的（或趋于零），这样造成计算机中的“溢出溢出”。为了克服这个问题，。为了克服这个问题，利用向量的方向与长度无关这一性质利用向量的方向与长度无关这一性质, , 将迭代向量的长度将迭代向量的长度规范化规范化以以改进幂法改进幂法。用幂法计算用幂法计算A A的主特征值及对应的特征向量时的主特征值及对应的特征向量时, ,如果如果 , , ,迭代向量的各个不等于零的分量将随迭代向量的各个不等于零的分量将随 而趋于无穷而趋于无穷所谓向量长度所谓向量长度规范化规范化, ,就是将向量的分量同除以一个常数就是将向量的分量同除以一个常数, ,使使向量
6、长度为向量长度为1,1,向量长度有多种度量法向量长度有多种度量法, ,可以采用可以采用 或或 , ,，其中，其中i0为所有绝对值最大的分量为所有绝对值最大的分量中最小的指标。中最小的指标。性质：性质：设设t 为实数，为实数，3. 3. 幂法的改进幂法的改进2.1 2.1 幂法总结幂法总结称称 为为迭代向量迭代向量。 (2.2) 幂法的基本思想幂法的基本思想: : 任取一个非零初始向量任取一个非零初始向量 ，由矩阵由矩阵A的乘幂构造一向量序列的乘幂构造一向量序列1.1.A特征值中特征值中 为强占优为强占优, ,即即结论结论: :2.2.A的主特征值为实的的主特征值为实的r重根重根, ,即即结论结
7、论: :任取初始向量：任取初始向量：迭代迭代规范化规范化则有迭代向量序列则有迭代向量序列 及规范化向量序列及规范化向量序列 。3. 3. 幂法的改进幂法的改进由由(2.7)及及(2.8)式有式有(1)对规范化向量序列对规范化向量序列:改进幂法计算公式：改进幂法计算公式：先考虑先考虑 与计算与计算 的关系。的关系。由于由于及及其中其中于是，于是， (2)对迭代向量序列对迭代向量序列:结论：结论： 即即 绝对值最大的分量当绝对值最大的分量当 时，趋向于特征根时，趋向于特征根 。 （2）设）设A特征值满足特征值满足定理定理8 （1 1）设）设 有有n个线性无关的特征向量；个线性无关的特征向量；且且
8、（3） 及及 由改进幂法得到的规范化向量序列由改进幂法得到的规范化向量序列及及迭代向量迭代向量序列序列(2.7)(2.7)式式),),则有则有且收敛速度由比值且收敛速度由比值 确定。确定。2.2 2.2 加速方法加速方法(原点平移法原点平移法) )应用幂法计算应用幂法计算A主特征值的收敛速度主要由比值主特征值的收敛速度主要由比值 来确定来确定, ,当当r 1 1但接近于但接近于1 1时时, ,收敛可能很慢，一个补救的办法是采用收敛可能很慢，一个补救的办法是采用加速收加速收敛敛的方法。的方法。引进矩阵引进矩阵B = =A- -pI，其中，其中P是可选择的参数。是可选择的参数。 设设A的特征值为的
9、特征值为 则则B的特征值为的特征值为 且且A, ,B特征向量相同。特征向量相同。原点平移法的思想原点平移法的思想如果需要计算如果需要计算A的主特征值的主特征值 ，适当选择，适当选择p使满足：使满足：（1 1） 是是B的主特征值，即的主特征值，即对对B应用幂法应用幂法, ,使得在计算使得在计算B的主特征值的主特征值 的过程中得到加速。的过程中得到加速。原点平移法原点平移法(加速法加速法) )显然显然, ,不管不管B如何选取如何选取, ,矩阵矩阵B= =A- -pI 的主特征值为的主特征值为 1. 1. 设设A的特征值是实数且满足：的特征值是实数且满足： 这种方法通常称为这种方法通常称为原点平移法
10、原点平移法。对于特征值的某种分布，它是十分。对于特征值的某种分布，它是十分有效的。有效的。求特征值的最大值求特征值的最大值当要求计算当要求计算 及及x1 1时，时，首先首先考虑应选取考虑应选取p满足满足: : 其次其次, , 使使或求极值问题或求极值问题当当 时，即，即时，值达到最小。达到最小。即当即当 的特征值满足的特征值满足 时时, ,最佳的最佳的p值为值为 说明说明: : 当当 能初步估计时，就可选择能初步估计时，就可选择P* 的近似值。另外，的近似值。另外，的推导可以理解为的推导可以理解为, ,因为收敛速度由因为收敛速度由 确定确定, ,如果能如果能把原点向把原点向 靠拢靠拢, ,使使
11、 小下去小下去, ,则可加快收敛速度。但是当原点移则可加快收敛速度。但是当原点移来，收敛速度又慢下去，因此把原点移到来，收敛速度又慢下去，因此把原点移到 与与 的中点最合适，的中点最合适，如图示，取如图示，取 作为新原点。作为新原点。到某点使到某点使 时，时， 就代替了就代替了 ，而，而 就成了就成了 , ,若若 大起大起说明：说明：1在实际应用中在实际应用中, ,A的的特征值并不知道，所以特征值并不知道，所以, ,p是无法是无法2. 2. 设设A的特征值是实数且满足：的特征值是实数且满足：且使且使当当 时，即，即最佳参数最佳参数确定的，该方法只是告诉我们，当发现收敛速度慢时，可以适当确定的，
12、该方法只是告诉我们，当发现收敛速度慢时，可以适当移动原点加速收敛。移动原点加速收敛。要求要求 ，选取，选取P P 满足满足求特征值的最小值求特征值的最小值 2由以上讨论知由以上讨论知, ,用用原点平移法原点平移法可以求可以求最大特征值最大特征值与与最小特征值最小特征值.2.3 2.3 反幂法反幂法 ( (或逆迭代或逆迭代) )设设 为非奇异矩阵为非奇异矩阵, ,A的特征值满足：的特征值满足： , ,对应特征向量对应特征向量 线性无关，线性无关，则则A-1-1的特征值为的特征值为 ，特征向量，特征向量1 1、反幂法用来计算矩阵、反幂法用来计算矩阵A按模最小的特征值及对应的特征向量按模最小的特征值
13、及对应的特征向量计算计算A的按模最小的特征值的按模最小的特征值 的问题就是计算的问题就是计算A-1-1按模最大的按模最大的特征值特征值 问题。问题。反幂法迭代公式：反幂法迭代公式：任取初始向量，任取初始向量，若若 有有n个线性无关的特征向量且其特征值满足：个线性无关的特征向量且其特征值满足： 则由反幂法则由反幂法(2.11)(2.11)构造的向量序列构造的向量序列 满足：满足：且收敛速度由比值且收敛速度由比值 确定。确定。 2 2 应用反幂法求一个近似特征值对应的特征向量。应用反幂法求一个近似特征值对应的特征向量。在反幂法中也可用原点平移法来加速收敛。在反幂法中也可用原点平移法来加速收敛。问题
14、：问题：已知已知 的特征值的特征值 的一个近似值的一个近似值 （通常用（通常用其它方法得到），求其它方法得到），求 对应的特征向量对应的特征向量 （近似）。（近似）。若若A的特征值为的特征值为 ，则，则A- -pI的特征值为的特征值为 取取 ，且设，且设 与其它特征值是分离的，即与其它特征值是分离的，即2 2 应用反幂法求一个近似特征值对应的特征向量。应用反幂法求一个近似特征值对应的特征向量。问题：问题：已知已知 的特征值的特征值 的一个近似值的一个近似值 （通常用（通常用其它方法得到），求其它方法得到），求 对应的特征向量对应的特征向量 （近似）。（近似）。如果如果( (A- -pI) )
15、-1-1存在存在, ,则特征值为则特征值为对应的特征向量的特征向量即即 , ,说明说明对对( (A- -pI) )-1-1应用幂法得到反幂法计算公式：应用幂法得到反幂法计算公式：是是( (A-p-pI) )-1-1 的主特征根。的主特征根。即即其中其中线性方程组线性方程组对对( (A- -pI) )-1-1应用幂法得到反幂法计算公式：应用幂法得到反幂法计算公式：取初始向量取初始向量于是于是结论结论定理定理1010（1 1）设）设 有有n个线性无关特征向量个线性无关特征向量 , ,即即 且收敛速度由比值且收敛速度由比值 确定。确定。 （2 2）取）取 （为特征值（为特征值 的一个近似值），设的一
16、个近似值），设( (A- -pI) )-1-1存在存在序列序列 满足：满足：且且 , ,则由反幂法迭代公式（则由反幂法迭代公式（2.122.12）构造向量）构造向量值的大体位置时，用此法值的大体位置时，用此法最合适最合适（该方法是一个有效的方法）。（该方法是一个有效的方法）。说明说明: : (1)(1)定理定理1010可以计算特征向量可以计算特征向量xj。当知道。当知道A的某一个特征的某一个特征（2 2）取）取 为特征值为特征值 的一个近似值的一个近似值, ,当当A的特征值分离情的特征值分离情反幂法迭代公式可通过解方程组反幂法迭代公式可通过解方程组( (A- -pI) )vk= =uk-1-1
17、来求来求vk。为了节。为了节况较好时况较好时, , r 很小很小, ,则它本身则它本身收敛速度很快收敛速度很快。同时。同时改进改进了特征值。了特征值。省计算量，可先将省计算量，可先将( (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。 计算计算对称三对角阵对称三对角阵，或计算，或计算HessenbergHessenberg阵阵对应于一个给定的近似特对应于一个给定的近似特反幂法迭代公式：反幂法迭代公式：1 .1 .分解计算分解计算P( (A- -pI)=)=LU ，且保存，且保存L,U及及P信息信息2 2反幂法迭代反幂法迭代征值的特征向量，反幂法是一个有效方法。征值的特征向量，反幂法是一个有效方法。u 反反幂法迭代过程中主要步骤：幂法迭代过程中主要步骤：若若p近似特征值好，则矩阵越奇异，方程组条件数越大？近似特征值好，则矩阵越奇异，方程组条件数越大？
