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