计算方法52幂法与反幂法ppt课件.ppt

5.2 幂法与反幂法幂法与反幂法适合于计算大型稀疏矩阵的主特征值（按模最大的特征适合于计算大型稀疏矩阵的主特征值（按模最大的特征值）和对应的特征向量，也称乘幂法。值）和对应的特征向量，也称乘幂法。 优点优点: 方法简单方法简单理论依据：理论依据：迭代法的收敛性迭代法的收敛性 矩阵按模矩阵按模的的最大特征值排列往往表现为阈值。如：矩最大特征值排列往往表现为阈值。如：矩阵的谱半径。幂法就是一种求矩阵按模最大特征值的方法，阵的谱半径。幂法就是一种求矩阵按模最大特征值的方法，它是最经典的方法。它是最经典的方法。2022-8-61 幂法的基本思想幂法的基本思想: : 任取一个非零初始向量任取一个非零初始向量 ，000 vRvn且且由矩阵由矩阵A的乘幂构造一向量序列的乘幂构造一向量序列01Avv 0212vAAvv 011vAAvvkkk ), 1 , 0(nk 称称 为为迭代向量迭代向量。kv问题的提法：问题的提法： 设设 , ,其特征值为其特征值为 , ,对应特征向量为对应特征向量为 nnijRaA )(), 1(nixi i 即即 ，且且 线性无关。求矩阵线性无关。求矩阵A的的主特主特), 1(ni ,1nxxiiixAx 征值征值及对应的及对应的特征向量特征向量。2022-8-62|21n 1.1.A 特征值中特征值中 为强占优为强占优, ,即即1 (1)(1)幂法幂法: :问题：问题：即即 ，且且 ，线性无关。特征值满足：，线性无关。特征值满足： ), 1(ni ,1nxxiiixAx 设设 , ,其特征值为其特征值为 , ,对应特征向量为对应特征向量为 nnijRaA )(), 1(nixi i 的的特征向量特征向量。|21n , ,即即 为强占优。求矩阵的为强占优。求矩阵的主特征值主特征值 及对应及对应1 1 2022-8-63nnxxxnA，相应的特征值为，个线性无关的特征向量有矩阵2121则则)(221101nnxxxAvAv nnnxxx 222111nnxAxAxA 2211 niiixv10 （且设（且设 ）01 线性无关线性无关 , ,即即 为为Rn中一个基，于是中一个基，于是对任意对任意,1nxx,1nxx的初始向量的初始向量 有展开式有展开式。000 vRvn且且( ( 用用 的线性组合表示的线性组合表示) )0vix关关系系与与及及11kvx 首先讨论首先讨论2022-8-64)()(12122111nknnkkxxx )222111nknnkkxxx 01vAvAvkkk )(111 xk k 其中其中nknnkkxx)()(12122 当当k =2,3, =2,3, 时，时， 即即, 0lim kk ), 2(0)(lim1nikik 从而从而), 2(1|1nii 由假设由假设 , ,得得|21n nknnkxx)()(12122 2022-8-6501则k足够大时，有111xvkkkkkvxv111111可见1,kkvv几乎仅差一个倍数1kkvv/11所以：。特征向量越来越接近，或充分大时，有说明，当111111xvxvkkkkk2022-8-66且收敛速度由比值且收敛速度由比值 确定。确定。|12 r111limxvkkk 所以有所以有其次讨论主特征值其次讨论主特征值 的计算。的计算。1 表示表示 的第的第i个分量，个分量，则则相邻迭代向量的分量的比值相邻迭代向量的分量的比值为为 ikv )(若若kv)(111kkkxv 2022-8-67特征向量乘以任意非零常数仍对应于同一特征值的特征向量特征向量乘以任意非零常数仍对应于同一特征值的特征向量, 2 , 1,01kvAvAvkkk因此，幂法是一种迭代方法。因此，幂法是一种迭代方法。ikikvv)()(1 则有则有 11)()(lim ikikkvv即相邻迭代向量分量的比值收敛到主特征值即相邻迭代向量分量的比值收敛到主特征值 , ,且收敛速度由且收敛速度由1 敛可能很慢。敛可能很慢。比值比值 来度量来度量, ,r 越小收敛越快越小收敛越快, , 当当 而接近于而接近于1 1时时, ,收收|12 r1|12 r)()()()(11111111ikikikikxx )0)(,)()()()(111111 ikikiikivxx 2022-8-68 为幂法。相应特征向量的方法称的按模最大特征值及其算矩阵，以计的乘幂构造向量序列和矩阵这种由已知的非零向量AvAvk0;lim)(111xvakkk 。11)()(lim)( ikikkvvb（1 1）设）设 有有n个线性无关的特征向量；个线性无关的特征向量；nnRA ,1 kkvAv);, 2 , 1( k),0(, 0110 niiixav（3）幂法：）幂法：（2）设）设A的特征值满足的特征值满足|;|21n 则则 定理定理7：2022-8-692. A的的主特征值为实的主特征值为实的r重根，即重根，即|121nrr 问题：问题：, ,求矩阵的求矩阵的主特征值主特征值 及对应及对应1 |121nrr 即即 ，且且 ，线性无关。特征值满足：，线性无关。特征值满足： ), 1(ni ,1nxxiiixAx 设设 , ,其特征值为其特征值为 , ,对应特征向量为对应特征向量为 nnijRaA )(), 1(nixi i 的的特征向量特征向量。2022-8-610,10 niiixv 对任意的初始向量对任意的初始向量 有有, 0,00 vRvn且且01vAvAvkkk )(1111 nriikiiriiikxx 11kriiikx 不全为零），则有不全为零），则有r ,（且且设设,21 其中其中 ，且，且 nriikiikx11)( , 0lim kk riiikkkxv11lim 从而从而因此，当因此，当k充分大时充分大时, , 接近于与接近于与 对应的特征向量的某个对应的特征向量的某个kkv1 1 线性组合线性组合 ( ( 不全为零不全为零) ) 。 riiix1 r ,212022-8-611解解 取v0=(1,0)T ,计算vk=Avk-1, 结果如下例：例：求矩阵A的按模最大的特征值61515141Ak(vk)1(vk)2(vk)1 / (vk-1)1(vk)2 / (vk-1)201010.250.220.102500.0833330.410.4166530.0422920.0343890.412600.4126740.0174510.0141900.412630.41263可取 1 0.41263 ,v1 (0.017451,0.014190)T 2022-8-612nknnkkkxxxv12122111在幂法中，我们构造的序列在幂法中，我们构造的序列可以看出可以看出1 , 1 , 0,11kvk因此，若序列收敛慢的话，可能造成计算的溢出或归因此，若序列收敛慢的话，可能造成计算的溢出或归02022-8-613于无穷于无穷（或趋于零），这样造成计算机中的（或趋于零），这样造成计算机中的“溢出溢出”。为了。为了克服这个问题，克服这个问题，利用向量的方向与长度无关这一性质，将迭利用向量的方向与长度无关这一性质，将迭代向量的长度代向量的长度规范化（规范化（“规一化规一化”）以以改进幂法改进幂法。用幂法计算用幂法计算A A的主特征值及对应的特征向量时的主特征值及对应的特征向量时, ,如果如果 , ,11 )1(1 或或, ,迭代向量的各个不等于零的分量将随迭代向量的各个不等于零的分量将随 而趋而趋 k3. 3. 幂法的改进幂法的改进所谓向量长度所谓向量长度规范化规范化, ,就是将向量的分量同除以一个常数就是将向量的分量同除以一个常数, ,使使向量长度为向量长度为1,1,向量长度有多种度量法向量长度有多种度量法, ,可以采用可以采用 或或 , , |2| |)max(vv|)( |max1iniv)max(vvuv规范化)(2等或vvu2022-8-614,01vAv,022vAv,0vAvkk)max(111vvu )max(00vAvA )max(222vvu )max()max(00vAvAvvukkkkk )0(0100 且且令令vu任取初始向量：任取初始向量：迭代迭代规范化规范化则有迭代向量序列则有迭代向量序列 及规范化向量序列及规范化向量序列 。kvku)max(0202vAvA 2022-8-615nknnkknknnkkkxxxxxxu1212211112122111即即（1）若：n210 , 0 , 111111xxxxuk2022-8-616ku收敛收敛122,kkuu分别收敛反号的两个数（2）若：21321,nnknnkknknnkkkxxxxxxu12211112211111122,kkuu分别收敛到两个数，且绝对值不同。2022-8-617;)max(lim)(11xxuakk .)max(limlim)(1 kkkkvb|,|21n （2）设）设A特征值满足特征值满足 定理定理8 （1 1）设）设 有有n个线性无关的特征向量；个线性无关的特征向量；nnRA iiixAx );, 1(ni 且且 （3） 及及 由改进幂法得到的规范化向量由改进幂法得到的规范化向量 序列序列及及迭代向量迭代向量序列，则有序列，则有kvku且收敛速度由比值且收敛速度由比值 确定。确定。|12 r2022-8-6182022-8-619应用幂法时,应注意以下两点:，不过收敛速度较慢。仍然会得到预期的结果，继续求向量序列看作初始向量，用幂法一向量将这的系数可能不等于零。展开时，按照基向量后，影响，经过若干步迭代但是，由于舍入误差的等于零，的系数中选择不当，将导致公式如果初始向量,)2(211210110kkknkkxxvxxxxvAvxv向量。特征值及其相应的特征用其它方法来求的近似值；否则，只能征值及其相应特征向量果，就得到主特果。若出现了预期的结查是否出现了预期的结在计算过程中检：先用幂法进行计算，克服上述困难的方法是。个线性无关的特征向量是否有，以及方阵满足事先不知道特征值是否应用幂法时，困难在于nAn21) 1 (2)(2) 加速方法加速方法 (原点平移法原点平移法) )应用幂法计算应用幂法计算A主特征值的收敛速度主要由比值主特征值的收敛速度主要由比值|12 r来确定，来确定，当当r 1 1但接近于但接近于1 1时时, ,收敛可能很慢，一个补救收敛可能很慢，一个补救的办法是采用的办法是采用加速收加速收敛敛的方法。的方法。引进矩阵引进矩阵B = =A- -pI，其中，其中P是可选择的参数。是可选择的参数。 2022-8-620,21pp ,pn 设设A的特征值为的特征值为 则则B的特征值为的特征值为 ,21n 且且A, ,B特征向量相同。特征向量相同。A与与B除了对角线元素外，其它元素都相同，除了对角线元素外，其它元素都相同，);, 2 , 1( |1nippi . |max)2(1212 ppjnj原点平移法的思想原点平移法的思想如果需要计算如果需要计算A的主特征值的主特征值 ，适当选择，适当选择p使满足：使满足：1 （1 1） 是是B的主特征值，即的主特征值，即p 1 对对B应用幂法应用幂法, ,使得在计算使得在计算B的主特征值的主特征值 的过程中得到加速。的过程中得到加速。p 1 这种方法通常称为这种方法通常称为原点平移法原点平移法。对于特征值的某种分布，它是。对于特征值的某种分布，它是十分十分有效的。有效的。2022-8-621原点平移法原点平移法(加速法加速法) )显然显然, ,不管不管B如何选取如何选取, ,矩阵矩阵B= =A- -pI 的主特征值为的主特征值为 p 1 . pn 或或min,max112 ppppn ,maxmin112ppppnp .1ppn 当要求计算当要求计算 及及x1 1时，时，首先首先考虑应选取考虑应选取p满足满足: : 1 其次其次, , 使使或求极值问题或求极值问题1. 1. 设设A的特征值是实数且满足：的特征值是实数且满足： n 21求特征值的最大值求特征值的最大值1 1 n 2 0p2022-8-622 p22n 当当 时，即时，即ppppn 112 ppn22 时，时， 值达到最小。值达到最小。 即当即当 的特征值满足的特征值满足 时时, ,最佳的最佳的p值为值为nnRA n 321 说明说明: : 当当 能初步估计时，就可选择能初步估计时，就可选择P* 的近似值。另外，的近似值。另外，n ,2的推导可以理解为的推导可以理解为, ,因为收敛速度由因为收敛速度由 确定确定, ,如果能如果能 p22n |12 把原点向把原点向 靠拢靠拢, ,使使 小下去小下去, ,则可加快收敛速度。但是当原点移则可加快收敛速度。但是当原点移2 |12 来，收敛速度又慢下去，因此把原点移到来，收敛速度又慢下去，因此把原点移到 与与 的中点最合适，的中点最合适，2 n 如图示，取如图示，取 作为新原点。作为新原点。2*2np 到某点使到某点使 时，时， 就代替了就代替了 ，而，而 就成了就成了 , ,若若 大起大起|2 nn n |n 2 2 1 n 2 0*p2022-8-623min,max11 ppppnnn 且使且使。211 np 当当 时，即时，即最佳参数最佳参数ppppnnn 11说明：说明：1 在实际应用中在实际应用中, ,A的的特征值并不知道，所以特征值并不知道，所以, ,p是无法是无法确定的，该方法只是告诉我们，当发现收敛速度慢时，可以适当确定的，该方法只是告诉我们，当发现收敛速度慢时，可以适当移动原点加速收敛。移动原点加速收敛。要求要求 ，选取，选取P P 满足满足.1ppn n 2. 2. 设设A的特征值是实数且满足：的特征值是实数且满足：nn 121求特征值的最小值求特征值的最小值 n 2 由以上讨论知由以上讨论知, ,用用原点平移法原点平移法可以求可以求最大特征值最大特征值与与最小特征值最小特征值.2022-8-6242022-8-625例例 设4阶方阵A有特征值432115,i, ii首先计算A的比值9012.r令作变换12ppIAB则B的特征值为10124321,确定收敛速度的比值为时，的按模最大的特征值应用幂法计算1B9 . 05 . 0121212pp所以对B应用幂法，可使幂法得到加速2022-8-626原点平移的加速方法,是一种矩阵变换方法。这种变换容易计算,又不破坏A的稀疏性，但参数p的选择依赖于对A的特征值的分布有大致了解。(3)(3)反幂法反幂法(或逆迭代或逆迭代)设设 为非奇异矩阵为非奇异矩阵, ,A的特征值满足：的特征值满足： nnijRaA )(0|21 n , ,对应特征向量对应特征向量 线性无关，线性无关，nxxx,21则则A-1-1的特征值为的特征值为 ，特征向量，特征向量|1|1|1|21n 。nxxx,211 1、反幂法用来计算矩阵、反幂法用来计算矩阵A按模最小的特征值及对应的特征向量按模最小的特征值及对应的特征向量计算计算A的按模最小的特征值的按模最小的特征值 的问题就是计算的问题就是计算A-1-1按模最大的按模最大的n n 1特征值特征值 问题。问题。反幂法迭代公式：反幂法迭代公式：, 2 , 1时时当当 k111 kkkkuAvuAv)0(000 nuv 且且任取初始向量，任取初始向量，（线线性性方方程程组组）)max(kkv kkkvu / 2022-8-627若若 有有n个线性无关的特征向量且其特征值满足：个线性无关的特征向量且其特征值满足： nnijRaA )(0|21 n 则由反幂法构造的向量序列则由反幂法构造的向量序列 满足：满足：,kkvu且收敛速度由比值且收敛速度由比值 确定。确定。 |1 nnr ,)max(lim)(nnkkxxua nkkb 1lim)( 2 2 应用反幂法求一个近似特征值对应的特征向量。应用反幂法求一个近似特征值对应的特征向量。问题：问题：已知已知 的特征值的特征值 的一个近似值的一个近似值 （通常用（通常用nnRA j j 其它方法得到），求其它方法得到），求 对应的特征向量对应的特征向量 （近似）（近似）j jx2022-8-628若若A的特征值为的特征值为 ，则，则A- -pI的特征值为的特征值为 n ,21取取 ，且设，且设 与其它特征值是分离的，即与其它特征值是分离的，即)(jjp j .1,pn ,1,121pp 如果如果( (A- -pI) ) -1-1存在存在, ,则特征值为则特征值为, pn ,1p ,2p 对应的特征向量对应的特征向量。nxxx,21),( |jippij |1pj )( ,|1|1jippij 即即 , ,说明说明对对( (A- -pI) )-1-1应用幂法得到反幂法计算公式：应用幂法得到反幂法计算公式：是是( (A-p-pI) )-1-1 的主特征根。的主特征根。2022-8-629即即,10 niiixv ikiniixp)1(1 )()()1(1111nknjjjkjkjxppxxppp )1(kjjkjxp 其中其中ikijnjiiikxpp)(1 1)( kkuvpIA),0(000 jvu 且且, 2 , 1时时当当 k11)( kkupIAv线性方程组线性方程组对对( (A- -pI) )-1-1应用幂法得到反幂法计算公式：应用幂法得到反幂法计算公式：取初始向量取初始向量)max(kkv kkkvu / 0)(vPIAvkk )(0 k当当|1|1ppij 1| ppij ), 2 , 1(jini 2022-8-630)max(kkkvvu )1max()1(kjjkjkjjkjxpxp )max(kjjkjjxx )max()(0)1(0vPIAvPIAvkkk )1max()1(1kjjkjkjjkjxpxp )max(11 kjjkjjjxxp 于是于是)max(kkv )()max( kxxjj)(1 kpj )max()max(11 kjjkjjjxxp 312022-8-6定理定理10（1 1）设）设 有有n个线性无关特征向量个线性无关特征向量 , ,即即 nnRA ,iiixAx );()max()( kjjkxxua当当且收敛速度由比值且收敛速度由比值 确定。确定。|min|pprijij 。), 1(ni （2 2）取）取 （为特征值（为特征值 的一个近似值），设的一个近似值），设( (A- -pI) )-1-1存在存在jp j ,kkvu序列序列 满足：满足：且且 , ,则由反幂法迭代公式（则由反幂法迭代公式（2.122.12）构造向量）构造向量)( |ijppij ),(1)max()( kpvbjkk当当 )(1 kjkp当当或或 2022-8-632 1kkPuLy大体位置时，用此法大体位置时，用此法最合适最合适（该方法是一个有效的方法）（该方法是一个有效的方法）(1)(1)定理定理1010可以计算特征向量可以计算特征向量xj。当知道。当知道A的某一个特征的某一个特征值的值的（2 2）取）取 为特征值为特征值 的一个近似值的一个近似值, ,当当A的特征值分离情的特征值分离情jp j 反幂法迭代公式可通过解方程组反幂法迭代公式可通过解方程组( (A- -pI) )vk= =uk-1-1来求来求vk。为了节。为了节况较好时况较好时, , r 很小很小, ,则它本身则它本身收敛速度很快收敛速度很快。同时。同时改进改进了特征值。了特征值。省计算量，可先将省计算量，可先将( (A- -pI) )进行三角分解进行三角分解P( (A- -pI)=)=LU。其中。其中P为置为置换阵，于是每次迭代求换阵，于是每次迭代求vk相当于求解两个三角形方程组。相当于求解两个三角形方程组。kkyUv 取取v0= =u0, ,即选即选u0 0使使Uv1 1= =L-1-1Pu0 0=(1,1)=(1,1)T, ,回代求解即求得回代求解即求得v1 1。说明说明: :2022-8-633 ,)1 , 1()1(11vUvT求求 );max(,/11111vvu , 3 , 2)2( k,)11kkkyPuLy求求 ;,kkkvyUv求求 );max()2kkv ./)3kkkvu 计算计算对称三对角阵对称三对角阵，或计算，或计算HessenbergHessenberg阵阵对应于一个给定的近对应于一个给定的近似特似特征值的特征向量，反幂法是一个有效方法。征值的特征向量，反幂法是一个有效方法。反幂法迭代公式：反幂法迭代公式：1 .1 .分解计算分解计算P( (A- -pI)=)=LU ，且保存，且保存L,U及及P信息信息2 2反幂法迭代反幂法迭代2022-8-6342022-8-635例例 用反幂法求矩阵2100121001210012A的对应于特征值40.的特征向量解解 取T, , ,x11110解方程组0140 xyI.A得,yT406565401 ,ymaxm6511., ,ymxT138111381111