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

5.2幂法与反幂法,适合于计算大型稀疏矩阵的主特征值（按模最大的特征值）和对应的特征向量，也称乘幂法。,优点:方法简单,理论依据：迭代法的收敛性,矩阵按模的最大特征值排列往往表现为阈值。如：矩阵的谱半径。幂法就是一种求矩阵按模最大特征值的方法，它是最经典的方法。,2020/5/29,1,称为迭代向量。,2020/5/29,2,(1)幂法:,问题：,2020/5/29,3,则,（且设）,首先讨论,2020/5/29,4,其中,当k=2,3,时，,2020/5/29,5,则k足够大时，有,所以：,2020/5/29,6,其次讨论主特征值的计算。,表示的第i个分量，则相邻迭代向量的分量的比值为,2020/5/29,7,特征向量乘以任意非零常数仍对应于同一特征值的特征向量,因此，幂法是一种迭代方法。,则有,2020/5/29,8,则,定理7：,2020/5/29,9,2.A的主特征值为实的r重根，即,问题：,2020/5/29,10,对任意的初始向量有,2020/5/29,11,解取v0=(1,0)T,计算vk=Avk-1,结果如下,例：求矩阵A的按模最大的特征值,可取10.41263,v1(0.017451,0.014190)T,2020/5/29,12,在幂法中，我们构造的序列,可以看出,因此，若序列收敛慢的话，可能造成计算的溢出或归0,2020/5/29,13,3.幂法的改进,所谓向量长度规范化,就是将向量的分量同除以一个常数,使向量长度为1,向量长度有多种度量法,可以采用或,2020/5/29,14,任取初始向量：,迭代,规范化,则有迭代向量序列及规范化向量序列。,2020/5/29,15,即,（1）若：,2020/5/29,16,收敛,分别收敛反号的两个数,（2）若：,分别收敛到两个数，且绝对值不同。,2020/5/29,17,（2）设A特征值满足,定理8（1）设有n个线性无关的特征向量；,且,（3）及由改进幂法得到的规范化向量序列及迭代向量序列，则有,且收敛速度由比值确定。,2020/5/29,18,2020/5/29,19,应用幂法时,应注意以下两点:,(2)加速方法(原点平移法),引进矩阵B=A-pI，其中P是可选择的参数。,2020/5/29,20,原点平移法的思想,如果需要计算A的主特征值，适当选择p使满足：,（1）是B的主特征值，即,对B应用幂法,使得在计算B的主特征值的过程中得到加速。,这种方法通常称为原点平移法。对于特征值的某种分布，它是十分有效的。,2020/5/29,21,原点平移法(加速法),显然,不管B如何选取,矩阵B=A-pI的主特征值为,当要求计算及x1时，首先考虑应选取p满足:,其次,使,或求极值问题,2020/5/29,22,当时，即,时，值达到最小。,即当的特征值满足时,最佳的p值为,2020/5/29,23,且使,当时，即最佳参数,要求，选取P满足,2由以上讨论知,用原点平移法可以求最大特征值与最小特征值.,2020/5/29,24,2020/5/29,25,例设4阶方阵A有特征值,首先计算A的比值,则B的特征值为,所以对B应用幂法，可使幂法得到加速,2020/5/29,26,原点平移的加速方法,是一种矩阵变换方法。这种变换容易计算,又不破坏A的稀疏性，但参数p的选择依赖于对A的特征值的分布有大致了解。,(3)反幂法(或逆迭代),设为非奇异矩阵,A的特征值满足：,对应特征向量线性无关，,则A-1的特征值为，特征向量,1、反幂法用来计算矩阵A按模最小的特征值及对应的特征向量,反幂法迭代公式：,任取初始向量，,2020/5/29,27,若有n个线性无关的特征向量且其特征值满足：,则由反幂法构造的向量序列满足：,且收敛速度由比值确定。,2应用反幂法求一个近似特征值对应的特征向量。,2020/5/29,28,若A的特征值为，则A-pI的特征值为,取，且设与其它特征值是分离的，即,如果(A-pI)-1存在,则特征值为,对应的特征向量,即,说明,对(A-pI)-1应用幂法得到反幂法计算公式：,是(A-pI)-1的主特征根。,2020/5/29,29,即,其中,线性方程组,对(A-pI)-1应用幂法得到反幂法计算公式：,取初始向量,2020/5/29,30,于是,31,2020/5/29,定理10,（1）设有n个线性无关特征向量,即,且收敛速度由比值确定。,（2）取（为特征值的一个近似值），设(A-pI)-1存在,序列满足：,且,则由反幂法迭代公式（2.12）构造向量,2020/5/29,32,大体位置时，用此法最合适（该方法是一个有效的方法）,(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。,说明:,2020/5/29,33,计算对称三对角阵，或计算Hessenberg阵对应于一个给定的近似特征值的特征向量，反幂法是一个有效方法。,反幂法迭代公式：,1.分解计算P(A-pI)=LU，且保存L,U及P信息,2反幂法迭代,2020/5/29,34,2020/5/29,35,例用反幂法求矩阵,解取,解方程组,得,2020/5/29,36,再解方程组,得,若知道某一