计算方法-5.2幂法与反幂法.ppt

适合于计算大型稀疏矩阵的主特征值（按模最大的特征适合于计算大型稀疏矩阵的主特征值（按模最大的特征值）和对应的特征向量，也称乘幂法。值）和对应的特征向量，也称乘幂法。优点优点:方法简单方法简单理论依据：理论依据：迭代法的收敛性迭代法的收敛性 矩阵按模矩阵按模的的最大特征值排列往往表现为阈值。如：矩最大特征值排列往往表现为阈值。如：矩阵的谱半径。幂法就是一种求矩阵按模最大特征值的方法，阵的谱半径。幂法就是一种求矩阵按模最大特征值的方法，它是最经典的方法。它是最经典的方法。2024/5/25 周六1 幂法的基本思想幂法的基本思想:任取一个非零初始向量任取一个非零初始向量 ，由矩阵由矩阵A的乘幂构造一向量序列的乘幂构造一向量序列称称 为为迭代向量迭代向量。问题的提法：问题的提法：设设 ,其特征值为其特征值为 ,对应特征向量为对应特征向量为 即即 ，且且 线性无关。求矩阵线性无关。求矩阵A的的主特主特征值征值及对应的及对应的特征向量特征向量。2024/5/25 周六21.1.A 特征值中特征值中 为强占优为强占优,即即(1)(1)幂法幂法:问题：问题：即即 ，且且 ，线性无，线性无关。特征值满足：关。特征值满足：设设 ,其特征值为其特征值为 ,对应特征向量为对应特征向量为 的的特征向量特征向量。,即即 为强占优。求矩阵的为强占优。求矩阵的主特征值主特征值 及对应及对应2024/5/25 周六3则则（且（且设设 ）线性无关线性无关,即即 为为Rn中一个基，于是中一个基，于是对任意对任意的初始向量的初始向量 有展开式有展开式。(用用 的线性组合表示的线性组合表示)首先讨论首先讨论2024/5/25 周六4其中其中 当当k=2,3,=2,3,时，时，即即从而从而由假设由假设 ,得得2024/5/25 周六5则k足够大时，有可见几乎仅差一个倍数所以：2024/5/25 周六6且收敛速度由比值且收敛速度由比值 确定。确定。所以有所以有其次讨论主特征值其次讨论主特征值 的计算。的计算。表示表示 的第的第i个分量，个分量，则则相相邻邻迭代向量的分量的比迭代向量的分量的比值值为为 2024/5/25 周六7特征向量乘以任意非零常数仍对应于同一特征值的特征向量特征向量乘以任意非零常数仍对应于同一特征值的特征向量因此，幂法是一种迭代方法。因此，幂法是一种迭代方法。则有则有 即相邻迭代向量分量的比值收敛到主特征值即相邻迭代向量分量的比值收敛到主特征值 ,且收敛速度由且收敛速度由敛可能很慢。敛可能很慢。比值比值 来度量来度量,r 越小收敛越快越小收敛越快,当当 而接近于而接近于1 1时时,收收2024/5/25 周六8（1 1）设）设 有有n个线性无关的特征向量；个线性无关的特征向量；（3）幂法：）幂法：（2）设）设A的特征值满足的特征值满足则则 定理定理7：2024/5/25 周六92.A的的主特征值为实的主特征值为实的r重根，即重根，即问题：问题：,求矩阵的求矩阵的主特征值主特征值 及对应及对应即即 ，且且 ，线性无，线性无关。特征值满足：关。特征值满足：设设 ,其特征值为其特征值为 ,对应特征向量为对应特征向量为 的的特征向量特征向量。2024/5/25 周六10对任意的初始向量对任意的初始向量 有有不全为零），则有不全为零），则有（且且设设其中其中 ，且，且从而从而因此，当因此，当k充分大时充分大时,接近于与接近于与 对应的特征向量的某个对应的特征向量的某个线性组合线性组合 (不全为零不全为零)。2024/5/25 周六11解解 取v0=(1,0)T,计算vk=Avk-1,结果如下例：例：求矩阵A的按模最大的特征值k(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 2024/5/25 周六12在幂法中，我们构造的序列在幂法中，我们构造的序列可以看出可以看出因此，若序列收敛慢的话，可能造成计算的溢出或归因此，若序列收敛慢的话，可能造成计算的溢出或归02024/5/25 周六13于于无无穷穷（或或趋趋于于零零），这这样样造造成成计计算算机机中中的的“溢溢出出”。为为了了克克服服这这个个问问题题，利利用用向向量量的的方方向向与与长长度度无无关关这这一一性性质质，将将迭迭代向量的长度代向量的长度规范化（规范化（“规一化规一化”）以以改进幂法改进幂法。用幂法计算用幂法计算A A的主特征值及对应的特征向量时的主特征值及对应的特征向量时,如果如果 ,迭代向量的各个不等于零的分量将随迭代向量的各个不等于零的分量将随 而趋而趋3.3.幂法的改进幂法的改进所所谓谓向向量量长长度度规规范范化化,就就是是将将向向量量的的分分量量同同除除以以一一个个常常数数,使使向量长度为向量长度为1,1,向量长度有多种度量法向量长度有多种度量法,可以采用可以采用 或或 ,2024/5/25 周六14任取初始向量：任取初始向量：迭代迭代规范化规范化则有迭代向量序列则有迭代向量序列 及规范化向量序列及规范化向量序列 。2024/5/25 周六15即即（1）若：2024/5/25 周六16收敛收敛分别收敛反号的两个数（2）若：分别收敛到两个数，且绝对值不同。2024/5/25 周六17（2）设）设A特征值满足特征值满足 定理定理8 （1 1）设）设 有有n个线性无关的特征向量；个线性无关的特征向量；且且（3）及及 由改进幂法得到的规范化向量由改进幂法得到的规范化向量 序列序列及及迭代向量迭代向量序列，则有序列，则有且收敛速度由比值且收敛速度由比值 确定。确定。2024/5/25 周六182024/5/25 周六19应用幂法时,应注意以下两点:(2)(2)加速方法加速方法 (原点平移法原点平移法)应用幂法计算应用幂法计算A主特征值的收敛速度主要由比值主特征值的收敛速度主要由比值来来确确定定，当当r 1 1但但接接近近于于1 1时时,收收敛敛可可能能很很慢慢，一一个个补补救救的办法是采用的办法是采用加速收加速收敛敛的方法。的方法。引进矩阵引进矩阵B=A-pI，其中，其中P是可选择的参数。是可选择的参数。2024/5/25 周六20设设A的特征值为的特征值为 则则B的特征值为的特征值为 且且A,B特征向量相同。特征向量相同。A与与B除了除了对对角角线线元素外，其它元素都相同，元素外，其它元素都相同，原点平移法的思想原点平移法的思想如果需要计算如果需要计算A的主特征值的主特征值 ，适当选择，适当选择p使满足：使满足：（1 1）是是B的主特征值，即的主特征值，即对对B应用幂法应用幂法,使得在计算使得在计算B的主特征值的主特征值 的过程中得到加速。的过程中得到加速。这这种种方方法法通通常常称称为为原原点点平平移移法法。对对于于特特征征值值的的某某种种分分布布，它它是是十分十分有效的。有效的。2024/5/25 周六21原点平移法原点平移法(加速法加速法)显然显然,不管不管B如何选取如何选取,矩阵矩阵B=A-pI 的主特征值为的主特征值为 当要求计算当要求计算 及及x1 1时，时，首先首先考虑应选取考虑应选取p满足满足:其次其次,使使或求极值问题或求极值问题1.1.设设A的特征值是实数且满足：的特征值是实数且满足：求特征值的最大值求特征值的最大值2024/5/25 周六22当当 时时，即，即时时，值值达到最小。达到最小。即当即当 的特征值满足的特征值满足 时时,最佳的最佳的p值为值为 说明说明:当当 能初步估计时，就可选择能初步估计时，就可选择P*的近似值。另外，的近似值。另外，的推导可以理解为的推导可以理解为,因为收敛速度由因为收敛速度由 确定确定,如果能如果能把原点向把原点向 靠拢靠拢,使使 小下去小下去,则可加快收敛速度。但是当原点移则可加快收敛速度。但是当原点移来，收敛速度又慢下去，因此把原点移到来，收敛速度又慢下去，因此把原点移到 与与 的中点最合适，的中点最合适，如图示，取如图示，取 作为新原点。作为新原点。到某点使到某点使 时，时，就代替了就代替了 ，而，而 就成了就成了 ,若若 大起大起2024/5/25 周六23且使且使当当 时时，即，即最佳参数最佳参数说明：说明：1 在实际应用中在实际应用中,A的的特征值并不知道，所以特征值并不知道，所以,p是无法是无法确定的，该方法只是告诉我们，当发现收敛速度慢时，可以适当确定的，该方法只是告诉我们，当发现收敛速度慢时，可以适当移动原点加速收敛。移动原点加速收敛。要求要求 ，选取，选取P P 满足满足2.2.设设A的特征值是实数且满足：的特征值是实数且满足：求特征值的最小值求特征值的最小值 2 由以上讨论知由以上讨论知,用用原点平移法原点平移法可以求可以求最大特征值最大特征值与与最小特征值最小特征值.2024/5/25 周六242024/5/25 周六25例例 设4阶方阵A有特征值首先计算A的比值令作变换则B的特征值为所以对B应用幂法，可使幂法得到加速2024/5/25 周六26原点平移的加速方法,是一种矩阵变换方法。这种变换容易计算,又不破坏A的稀疏性，但参数p的选择依赖于对A的特征值的分布有大致了解。(3)(3)反幂法反幂法(或逆迭代或逆迭代)设设 为非奇异矩阵为非奇异矩阵,A的特征值满足：的特征值满足：,对应特征向量对应特征向量 线性无关，线性无关，则则A-1-1的特征值为的特征值为 ，特征向量，特征向量1 1、反幂法用来计算矩阵、反幂法用来计算矩阵A按模最小的特征值及对应的特征向量按模最小的特征值及对应的特征向量计算计算A的按模最小的特征值的按模最小的特征值 的问题就是计算的问题就是计算A-1-1按模最大的按模最大的特征值特征值 问题。问题。反幂法迭代公式：反幂法迭代公式：任取初始向量，任取初始向量，2024/5/25 周六27若若 有有n个线性无关的特征向量且其特征值满足：个线性无关的特征向量且其特征值满足：则由反幂法构造的向量序列则由反幂法构造的向量序列 满足：满足：且收敛速度由比值且收敛速度由比值 确定。确定。2 2 应用反幂法求一个近似特征值对应的特征向量。应用反幂法求一个近似特征值对应的特征向量。问题：问题：已知已知 的特征值的特征值 的一个近似值的一个近似值 （通常用（通常用其它方法得到），求其它方法得到），求 对应的特征向量对应的特征向量 （近似）（近似）2024/5/25 周六28若若A的特征值为的特征值为 ，则，则A-pI的特征值为的特征值为 取取 ，且设，且设 与其它特征值是分离的，即与其它特征值是分离的，即如果如果(A-pI)-1-1存在存在,则特征值为则特征值为对应对应的特征向量的特征向量即即 ,说明说明对对(A-pI)-1-1应用幂法得到反幂法计算公式：应用幂法得到反幂法计算公式：是是(A-p-pI)-1-1 的主特征根。的主特征根。2024/5/25 周六29即即其中其中线性方程组线性方程组对对(A-pI)-1-1应用幂法得到反幂法计算公式：应用幂法得到反幂法计算公式：取初始向量取初始向量2024/5/25 周六30于是于是312024/5/25 周六定理定理10（1 1）设）设 有有n个线性无关特征向量个线性无关特征向量 ,即即 且收敛速度由比值且收敛速度由比值 确定。确定。（2 2）取）取 （为特征值（为特征值 的一个近似值），设的一个近似值），设(A-pI)-1-1存在存在序列序列 满足：满足：且且 ,则由反幂法迭代公式（则由反幂法迭代公式（2.122.12）构造向量）构造向量2024/5/25 周六32大体位置时，用此法大体位置时，用此法最合适最合适（该方法是一个有效的方法）（该方法是一个有效的方法）(1)(1)定理定理1010可以计算特征向量可以计算特征向量xj。当知道。当知道A的某一个特征的某一个特征值的值的（2 2）取）取 为特征值为特征值 的一个近似值的一个近似值,当当A的特征值分离情的特征值分离情反幂法迭代公式可通过解方程组反幂法迭代公式可通过解方程组(A-pI)vk=uk-1-1来求来求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。说明说明:2024/5/25 周六33 计算计算对称三对角阵对称三对角阵，或计算，或计算HessenbergHessenberg阵阵对应于一个给定的近对应于一个给定的近似特似特征值的特征向量，反幂法是一个有效方法。征值的特征向量，反幂法是一个有效方法。反幂法迭代公式：反幂法迭代公式：1.1.分解计算分解计算P(A-pI)=)=LU ，且保存，且保存L,U及及P信息信息2 2反幂法迭代反幂法迭代2024/5/25 周六342024/5/25 周六35例例 用反幂法求矩阵的对应于特征值的特征向量解解 取解方程组得2024/5/25 周六36再解方程组得若知道某一特征根若知道某一特征根 i 的大致位置的大致位置 p，即对任意，即对任意 j i 有有|i p|j p|，并且如果，并且如果(A pI)1存在，则存在，则可以用反幂法求可以用反幂法求(A pI)1的主特征根的主特征根 1/(i p)，收，收敛将非常快。敛将非常快。思思路路在反幂法中也可用原点平移法来加速收敛。在反幂法中也可用原点平移法来加速收敛。本章作业P115 2、42024/5/25 周六37