计算方法幂法与反幂法

计算方法幂法与反幂法第1页，共34页，2023年，2月20日，星期二幂法的基本思想:任取一个非零初始向量，由矩阵A的乘幂构造一向量序列称为迭代向量。问题的提法：设,其特征值为,对应特征向量为即

，且线性无关。求矩阵A的主特征值及对应的特征向量。2023/4/182第2页，共34页，2023年，2月20日，星期二1.A特征值中为强占优,即(1)幂法:问题：即

，且，线性无关。特征值满足：设,其特征值为,对应特征向量为的特征向量。,即为强占优。求矩阵的主特征值及对应2023/4/183第3页，共34页，2023年，2月20日，星期二则（且设）线性无关,即为Rn中一个基，于是对任意的初始向量有展开式。(用的线性组合表示)首先讨论2023/4/184第4页，共34页，2023年，2月20日，星期二其中

当k=2,3,…时，即从而由假设,得2023/4/185第5页，共34页，2023年，2月20日，星期二则k足够大时，有可见几乎仅差一个倍数所以：2023/4/186第6页，共34页，2023年，2月20日，星期二且收敛速度由比值确定。所以有其次讨论主特征值的计算。表示的第i个分量，则相邻迭代向量的分量的比值为

2023/4/187特征向量乘以任意非零常数仍对应于同一特征值的特征向量因此，幂法是一种迭代方法。第7页，共34页，2023年，2月20日，星期二则有

即相邻迭代向量分量的比值收敛到主特征值,且收敛速度由敛可能很慢。比值来度量,r越小收敛越快,当而接近于1时,收2023/4/188第8页，共34页，2023年，2月20日，星期二（1）设有n个线性无关的特征向量；（3）幂法：（2）设A的特征值满足则

定理7：2023/4/189第9页，共34页，2023年，2月20日，星期二2.A的主特征值为实的r重根，即问题：,求矩阵的主特征值及对应即

，且，线性无关。特征值满足：设,其特征值为,对应特征向量为的特征向量。2023/4/1810第10页，共34页，2023年，2月20日，星期二对任意的初始向量有不全为零），则有（且设其中，且从而因此，当k充分大时,接近于与对应的特征向量的某个线性组合(不全为零)。2023/4/1811第11页，共34页，2023年，2月20日，星期二解取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可取10.41263,v1(0.017451,0.014190)T

2023/4/1812第12页，共34页，2023年，2月20日，星期二在幂法中，我们构造的序列可以看出因此，若序列收敛慢的话，可能造成计算的溢出或归02023/4/1813第13页，共34页，2023年，2月20日，星期二于无穷（或趋于零），这样造成计算机中的“溢出”。为了克服这个问题，利用向量的方向与长度无关这一性质，将迭代向量的长度规范化（“规一化”）以改进幂法。用幂法计算A的主特征值及对应的特征向量时,如果,,迭代向量的各个不等于零的分量将随而趋3.幂法的改进所谓向量长度规范化,就是将向量的分量同除以一个常数,使向量长度为1,向量长度有多种度量法,可以采用或,2023/4/1814第14页，共34页，2023年，2月20日，星期二任取初始向量：迭代规范化则有迭代向量序列及规范化向量序列。2023/4/1815第15页，共34页，2023年，2月20日，星期二即（1）若：2023/4/1816收敛分别收敛反号的两个数第16页，共34页，2023年，2月20日，星期二（2）若：分别收敛到两个数，且绝对值不同。2023/4/1817第17页，共34页，2023年，2月20日，星期二（2）设A特征值满足

定理8（1）设有n个线性无关的特征向量；且

（3）及由改进幂法得到的规范化向量序列及迭代向量序列，则有且收敛速度由比值确定。2023/4/1818第18页，共34页，2023年，2月20日，星期二应用幂法时,应注意以下两点:2023/4/1819第19页，共34页，2023年，2月20日，星期二(2)加速方法(原点平移法)应用幂法计算A主特征值的收敛速度主要由比值来确定，当r<1但接近于1时,收敛可能很慢，一个补救的办法是采用加速收敛的方法。引进矩阵B=A-pI，其中P是可选择的参数。2023/4/1820设A的特征值为则B的特征值为且A,B特征向量相同。A与B除了对角线元素外，其它元素都相同，第20页，共34页，2023年，2月20日，星期二原点平移法的思想如果需要计算A的主特征值，适当选择p使满足：（1）是B的主特征值，即对B应用幂法,使得在计算B的主特征值的过程中得到加速。这种方法通常称为原点平移法。对于特征值的某种分布，它是十分有效的。2023/4/1821第21页，共34页，2023年，2月20日，星期二原点平移法(加速法)显然,不管B如何选取,矩阵B=A-pI的主特征值为当要求计算及x1时，首先考虑应选取p满足:其次,使或求极值问题1.设A的特征值是实数且满足：求特征值的最大值2023/4/1822第22页，共34页，2023年，2月20日，星期二当

时，即时，值达到最小。

即当的特征值满足时,最佳的p值为

说明:

当能初步估计时，就可选择P*的近似值。另外，的推导可以理解为,因为收敛速度由确定,如果能把原点向靠拢,使小下去,则可加快收敛速度。但是当原点移来，收敛速度又慢下去，因此把原点移到与的中点最合适，如图示，取作为新原点。到某点使时，就代替了，而就成了,若大起2023/4/1823第23页，共34页，2023年，2月20日，星期二且使当

时，即最佳参数说明：1在实际应用中,A的特征值并不知道，所以,p是无法确定的，该方法只是告诉我们，当发现收敛速度慢时，可以适当移动原点加速收敛。要求，选取P满足2.设A的特征值是实数且满足：求特征值的最小值

2由以上讨论知,用原点平移法可以求最大特征值与最小特征值.2023/4/1824第24页，共34页，2023年，2月20日，星期二例

设4阶方阵A有特征值首先计算A的比值令作变换则B的特征值为所以对B应用幂法，可使幂法得到加速2023/4/1825第25页，共34页，2023年，2月20日，星期二原点平移的加速方法,是一种矩阵变换方法。这种变换容易计算,又不破坏A的稀疏性，但参数p的选择依赖于对A的特征值的分布有大致了解。2023/4/1826第26页，共34页，2023年，2月20日，星期二(3)反幂法(或逆迭代)设为非奇异矩阵,A的特征值满足：,对应特征向量线性无关，则A-1的特征值为，特征向量1、反幂法用来计算矩阵A按模最小的特征值及对应的特征向量计算A的按模最小的特征值的问题就是计算A-1按模最大的特征值问题。反幂法迭代公式：任取初始向量，2023/4/1827第27页，共34页，2023年，2月20日，星期二若有n个线性无关的特征向量且其特征值满足：则由反幂法构造的向量序列满足：且收敛速度由比值确定。2应用反幂法求一个近似特征值对应的特征向量。问题：已知的特征值的一个近似值（通常用其它方法得到），求对应的特征向量（近似）2023/4/1828第28页，共34页，2023年，2月20日，星期二若A的特征值为，则A-pI的特征值为取，且设与其它特征值是分离的，即如果(A-pI)

-1存在,则特征值为对应的特征向量即,说明对(A-pI)-1应用幂法得到反幂法计算公式：是(A-pI)-1的主特征根。2023/4/1829第29页，共34页，2023年，2月20日，星期二即其中线性方程组对(A-pI)-1应用幂法得到反幂法计算公式：取初始向量2023/4/1830第30页，共34页，2023年，2月20日，星期二于是312023/4/18第31页，共34页，2023年，2月20日，星期二定理10（1）设有n个线性无关特征向量,即且收敛速度由比值确定。（2）取（为特征值的一个近似值），设(A-pI)-1存在序列满足：且,则由反幂法迭代公式（2.12）构造向量2023/4/1832第32页，共34页，2023年，2月20日，星期二大体位置时，用此法最合适（该方法是一个有效的方法）(1)定理10可以计算特征向量xj。当知道A的某一个特征值的（2）取为特征值的一个近似值,当A的特征值分离情反幂法迭代公式可通过解方程组(A-pI)vk=uk-1来求vk。为了节况较好时,r

很小,则它本身收敛速度很快。同时改进了特征值。省计算量，可先将(A-pI)进行三角分解P(A-pI)=LU。其中P为置换阵，于是每次迭代求vk相当于求解两个三角形方