计算方法52幂法与反幂法

5.2幂法与反幂法§适合于计算大型稀疏矩阵的主特征值（按模最大的特征值）和对应的特征向量，也称乘幂法。优点:方法简单理论依据：迭代法的收敛性矩阵按模的最大特征值排列往往表现为阈值。如：矩阵的谱半径。幂法就是一种求矩阵按模最大特征值的方法，它是最经典的方法。2020/5/61幂法的基本思想:任取一个非零初始向量，000vRvn且由矩阵A的乘幂构造一向量序列01Avv0212vAAvv011vAAvvkkk),,1,0(nk称为迭代向量。}{kv问题的提法：设,其特征值为,对应特征向量为nnijRaA)(),,,1(nixii即，且线性无关。求矩阵A的主特),,1(ni},,{1nxxiiixAx征值及对应的特征向量。2020/5/62||||||21n1.A特征值中为强占优,即1(1)幂法:问题：即，且，线性无关。特征值满足：),,1(ni},,{1nxxiiixAx设,其特征值为,对应特征向量为nnijRaA)(),,,1(nixii的特征向量。||||||21n,即为强占优。求矩阵的主特征值及对应112020/5/63nnxxxnA，，，相应的特征值为，，，，个线性无关的特征向量有矩阵2121则)(221101nnxxxAvAvnnnxxx222111nnxAxAxA2211niiixv10（且设）01线性无关,即为Rn中一个基，于是对任意},,{1nxx},,{1nxx的初始向量有展开式。000vRvn且(用的线性组合表示)0v}{ix关系与及}{11kvx首先讨论2020/5/64])()([12122111nknnkkxxx)222111nknnkkxxx01vAvAvkkk)(111xkk其中nknnkkxx)()(12122当k=2,3,…时，即,0limkk),,,2(0)(lim1nikik从而),,2(1||1nii由假设,得||||||21nnknnkxx)()(121222020/5/6501则k足够大时，有111xvkkkkkvxv111111可见1,kkvv几乎仅差一个倍数1kkvv/11所以：。特征向量越来越接近，或充分大时，有说明，当111111xvxvkkkkk2020/5/66且收敛速度由比值确定。||12r111limxvkkk所以有其次讨论主特征值的计算。1表示的第i个分量，则相邻迭代向量的分量的比值为ikv)(若kv)(111kkkxv2020/5/67特征向量乘以任意非零常数仍对应于同一特征值的特征向量,2,1,01kvAvAvkkk因此，幂法是一种迭代方法。ikikvv)()(1则有11)()(limikikkvv即相邻迭代向量分量的比值收敛到主特征值,且收敛速度由1敛可能很慢。比值来度量,r越小收敛越快,当而接近于1时,收||12r1||12r])()([])()([11111111ikikikikxx)0)((,)()()()(111111ikikiikivxx2020/5/68为幂法。相应特征向量的方法称的按模最大特征值及其算矩阵，以计的乘幂构造向量序列和矩阵这种由已知的非零向量AvAvk0;lim)(111xvakkk。11)()(lim)(ikikkvvb（1）设有n个线性无关的特征向量；nnRA,1kkvAv);,2,1(k),0(,0110niiixav（3）幂法：（2）设A的特征值满足|;|||||21n则定理7：2020/5/692.A的主特征值为实的r重根，即||||||||||121nrr问题：,求矩阵的主特征值及对应1||||||||||121nrr即，且，线性无关。特征值满足：),,1(ni},,{1nxxiiixAx设,其特征值为,对应特征向量为nnijRaA)(),,,1(nixii的特征向量。2020/5/610,10niiixv对任意的初始向量有,0,00vRvn且01vAvAvkkk])([1111nriikiiriiikxx][11kriiikx不全为零），则有r,（且设,,21其中，且nriikiikx11)(,0limkkriiikkkxv11lim从而因此，当k充分大时,接近于与对应的特征向量的某个kkv11线性组合(不全为零)。riiix1r,,,212020/5/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)T2020/5/612nknnkkkxxxv12122111在幂法中，我们构造的序列可以看出1,1,0,11kvk因此，若序列收敛慢的话，可能造成计算的溢出或归02020/5/613于无穷（或趋于零），这样造成计算机中的“溢出”。为了克服这个问题，利用向量的方向与长度无关这一性质，将迭代向量的长度规范化（“规一化”）以改进幂法。用幂法计算A的主特征值及对应的特征向量时,如果,11)1(1或,迭代向量的各个不等于零的分量将随而趋k3.幂法的改进所谓向量长度规范化,就是将向量的分量同除以一个常数,使向量长度为1,向量长度有多种度量法,可以采用或,||||2||||||||)max(vv|)(|max1iniv)max(vvuv规范化)(2等或vvu2020/5/614,01vAv,022vAv,0vAvkk)max(111vvu)max(00vAvA)max(222vvu)max()max(00vAvAvvukkkkk)0(0100且令vu任取初始向量：迭代规范化则有迭代向量序列及规范化向量序列。}{kv}{ku)max(0202vAvA2020/5/615nknnkknknnkkkxxxxxxu1212211112122111即（1）若：n210,0,111111xxxxuk2020/5/616ku收敛122,kkuu分别收敛反号的两个数（2）若：21321,nnknnkknknnkkkxxxxxxu12211112211111122,kkuu分别收敛到两个数，且绝对值不同。2020/5/617;)max(lim)(11xxuakk.)max(limlim)(1kkkkvb|,|||||21n（2）设A特征值满足定理8（1）设有n个线性无关的特征向量；nnRAiiixAx);,,1(ni且（3）及由改进幂法得到的规范化向量序列及迭代向量序列，则有}{kv}{ku且收敛速度由比值确定。||12r2020/5/6182020/5/619应用幂法时,应注意以下两点:，不过收敛速度较慢。仍然会得到预期的结果，继续求向量序列看作初始向量，用幂法一向量将这的系数可能不等于零。展开时，按照基向量后，影响，经过若干步迭代但是，由于舍入误差的等于零，的系数中选择不当，将导致公式如果初始向量,,,,,,)2(211210110kkknkkxxvxxxxvAvxv向量。特征值及其相应的特征用其它方法来求的近似值；否则，只能征值及其相应特征向量果，就得到主特果。若出现了预期的结查是否出现了预期的结在计算过程中检：先用幂法进行计算，克服上述困难的方法是。个线性无关的特征向量是否有，以及方阵满足事先不知道特征值是否应用幂法时，困难在于nAn21)1((2)加速方法(原点平移法)应用幂法计算A主特征值的收敛速度主要由比值||12r来确定，当r1但接近于1时,收敛可能很慢，一个补救的办法是采用加速收敛的方法。引进矩阵B=A-pI，其中P是可选择的参数。2020/5/620,,,21pp,pn设A的特征值为则B的特征值为,,,,21n且A,B特征向量相同。A与B除了对角线元素外，其它元素都相同，);,,2,1(||||1nippi.||||||max)2(1212ppjnj原点平移法的思想如果需要计算A的主特征值，适当选择p使满足：1（1）是B的主特征值，即p1对B应用幂法,使得在计算B的主特征值的过程中得到加速。p1这种方法通常称为原点平移法。对于特征值的某种分布，它是十分有效的。2020/5/621原点平移法(加速法)显然,不管B如何选取,矩阵B=A-pI的主特征值为p1.pn或min},max{112ppppn},max{min112ppppnp.1ppn当要求计算及x1时，首先考虑应选取p满足:1其次,使或求极值问题1.设A的特征值是实数且满足：n21求特征值的最大值11n20p2020/5/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*p2020/5/623min},max{11ppppnnn且使。211np当时，即最佳参数ppppnnn11说明：1在实际应用中,A的特征值并不知道，所以,p是无法确定的，该方法只是告诉我们，当发现收敛速度慢时，可以适当移动原