《幂法求解矩阵主特征值的加速方法研究.docx》由会员分享，可在线阅读，更多相关《幂法求解矩阵主特征值的加速方法研究.docx（27页珍藏版）》请在金锄头文库上搜索。
1、幂法求解矩阵主特征值的加速方法摘要：本论文主要研究的是幂法求解矩阵的主特征值和特征向量。物理、 力学和工程技术中有许多需要我们求矩阵的按模最大的特征值（及称为主 特征值）和特征向量。幂法是计算一个矩阵的模最大特征值和对应的特征 向量的一种迭代方法。它最大的优点是方法简单，适合于大型稀疏矩阵的 主特征值，但是收敛速度非常慢。所以我们要用加速的方法来加速收敛， 加速方法包括原点平移加速、Rayleigh商加速和Aitken加速算法。关键词：幕法；原点平移加速；Rayleigh商加速；Aitken加速算法1引言我们来介绍矩阵特征值和特征向量的计算方法，大家知道求一个矩阵 的特征值的问题实质上是求一个
2、多项式的根的问题，而数学上已经证明5 阶以上的多项式的根一般不能用有限次运算求得。因此，矩阵特征值的计 算方法本质上都是迭代，而对于大型的稀疏矩阵就需要用幕法求解最简单。 但是由于收敛速度非常的慢所以我们需要用加速的方法加快收敛速度而本 次论文也是针对加速问题来通过对几种方法的研究讨论。并且通过算法的 实现来说明那种加速算法收敛得快，哪个计算量比较节省。其实本文主要 讨论的问题是一个应用中常见的一类数值计算问题。2加速算法的背景2.1幂法为了说明其基本思想我们先假设A Cnn是可共26页_ 河南理工大学数学与信息科学学院本科毕业论文 第2页 幂法是计算一个矩阵的模最大特征值和对应的特征向量的一
3、种迭代方 法。它适用于大型稀疏矩阵。对角化的，即A有如下分解 其中diag非奇异，再假定现任取一向量u0.由于X的列向量构成。的一组基，故u可表示为0由此可知1 . Aku lim0k1k乂，这里nAku0C.这样，我们有in AkxjjkXjjx11kx.j土这是A的一个很好的近似特 k1征向量。然而，实际计算时，这是行不通的，其原因有二：一是我们事先这表明，当1 0而且k充分大时，向量u并不知道A的特征值1 ；二是对充分大的k计算Ak的工作量太大。所以找出 一种工作量较小的方法，而幂法求解收敛速度很慢所以我们还要找出一种加快速度的算法。迭代格式：y Aukk 1k是y的模最大分量， jk其
4、中U Cn是任意给定的初始向量，通常要求|U1.定理设A Rn n有n个线性无关的特征向量，主特征值满足1 0,按下面构造的向量序，则有|，则对任何非零初始向量v U1 d 1 rno o列u , v：k kvu0,vAu ,kk 1max(v ),k 1,2,k kvu ,kk(1)limuX,kkmax xlimk（注：此定理证明参阅文献5）4 14 0例1.计算矩阵A 5 13 0的主特征值。1 0 22.2幂法的应用物理，力学和工程技术中的很多问题在数学上都归结为求矩阵特征值 问题。例如，振动问题（大型桥梁或建筑物的振动，机械振动，电磁振荡 等），物理学中某些临界值得确定，这些问题都归
5、结为求矩阵的特征值的数 学问题。而幕法求解实际应用矩阵特征值是十分有效方法之一，但是收敛 速度太慢，所以在实际应用中它所需要的时间非常的长，而且计算过程中 所消耗的时间造成了实际问题的完成进度。因而我们需要通过用加速算法 来加快收敛速度，让实际问题提前或者按时完成。为了加快幕法求解矩阵 主特征值的收敛速度，让幕法更有效广泛的运用在实际应用生活中，我们 现在就来认识几种加速方法，如原点平移法、Rayleigh商加速、Aitken加 速算法、一种改进的Aitken加速算法和一种新的改进的Aitken加速算法 并且对他们进行比较，看哪种加速方法收敛得快，哪种计算量比较节省等。 下面我们就来说说这几种
6、加速方法。3常见的几种加速算法3.1原点平移法定理设A Cnn, p个互不相同的特征值满足|，并且模1 12n最大特征值1是半单的（即1的几何重数等于它的代数重数）。如果初始向 量u0在1的特征子空间上的投影不为零，则定理（2.1.2 ）产生的向量序列 uk收敛到1的一个特征向量X1,而且由定理（2.1.2 ）产生的数值序列k 收敛到。（注：此定理证明参阅1）由定理（2.1.1）可知幕法的收敛速度主要取决于l/j的大小。在定理（2.1.1 ）的条件下，这个数总是小于1的，它越小收敛也就越快。当它接近于1时收敛是很慢的。所以为了加快幕法的收敛速度，通常用位移的方法，即应用幕法于入I上。如果适当选
7、取u可使A I之模最大特征值与其他特征值之模的距离更大，就可起到加速的目的。首先我们引进矩阵B A pI其中p为选择参数。设A的特征值为，则B的相应特征值为12n1p, 2 p, , p,而且A, B的特征向量相同。如果需要计算A的主特征值就要适当选择p,使1p仍然是B的主特征值，且使pT T .1 p1对B应用幕法，使得在计算B的主特征值p的过程中得到加速。这种方法通常称为原点平移法。对于A的特征值的某种分布，它是十分有效的。对于参数p的选择依赖于对矩阵A特征值分布的大致了解。通常可以用Gerschgorin （盖尔）圆盘定理得到矩阵A的特征值分布情况。定理3.1.2 （ Gerschgor
8、in圆盘定理）设A为n阶实矩阵，则i 1,2, ,n的并集之中;（1 ） A的每一个特征值必定属于下述n个闭圆盘（称为Gerschgorin圆）a.| a_ r nj 1,j i（2 ）由矩阵a的所有Gerschgorin圆组成的连通部分中任取一个，如果由 k个Gerschgorin圆构成，则在这个连通部分中有且仅有A的k个特征 值（Gerschgorin圆相重时重复计数，特征值相同时也重复计数）。求得矩阵B的主特征值1p后，可得矩阵A的主特征值11p,同时得到对应的特征向量的近似x。1（注：此定理证明参阅文献1）事实上，如果对于矩阵的特征值能够分离得很清楚，就可以利用原点 平移法求得矩阵的所
9、有特征值及其相应的特征向量。但需要说明的是，虽 然常常能够选择有利的p值，使幕法得到加速，但设计一个自动选择适当参 数p的过程是困难的。下面考虑A的特征值是实数时，怎样选择p使幂法计 算得到加速。设A的特征值满足,（3.1.1）12n 1 n则不管p如何，B A ?1的主特征值为p或p.当我们希望计算及气时，首先应选择p使I 1p| lnp|， 且使收敛速度的比值pp|p|.max j , min1 1p I 1p|显然，当E ,即p 一 p时为最小，这时收敛速度的比值为1 p 1 p2pp -2 n .pp 21112 n当A的特征值满足（3.1.1 ）且，能初步估计时，我们就能确定p的近似
10、2 n值。当希望计算时，应选择p 1 n 1 p ,使得应用幂法计算n得到加速。3.2 Rayleigh 商加速定义设A为n阶实对称矩阵，对于任一非零向量x，称Ax, xx, x为对应于向量X的Rayleigh商。定理设a Rn n为对称矩阵（其特征值次序记为1(1)Ax,xx,x（对任何非零x Rn）；1(2)(3)Ax,x max ;x Rn,x 0 X, xAx,x min ;x Rn,x 0 x, x（注：此定理证明参阅文献5）由定理3.2. 1知，对称矩阵A的 及 可用Rayleigh商的极值来表示。 下面我们将把Rayleigh商应用到用幂法计算实对称矩阵a的主特征值的加 速收敛上
11、来。定理设A Rnn为对称矩阵，特征值满足12n 1 n对应的特征向量满足x,x ，应用幂法（公式（2.1.2）计算A的主特征 i j ij值，则规范化向量U的Rayleigh商给出 的Au ,u2k-.uk,uk11（注：此定理证明参阅5）3.3 Aitken加速算法Aitken加速算法在诸多方面得到了广泛的应用，尤其是从对幂法加速 的诸多方法中突颖而出。但是在实际应用中，由于幂法针对的大多是大型 矩阵，而计算速度要求较快，精度要求较高，传统的Aitken方法越来越不能满足需要。3.3.1 Aitken加速算法设序列P线性收敛到极限p,而且对所有n 0,有p p 0.如果存在n n 0n实数
12、A,且|A| 1,满足：limP PniA.则定义为n p p np p 2 q p nnn n p 2 p pn 2 n 1 npYqn0.的序列q 收敛到p,且比p 快，而且1 plim n p算法实现:把上述方法应用于幂法迭代格式中的序列|x|即可做到对 kk 1幂法的加速。具体算法伪代码如下： 输入入a.,初始向量x x,x, ,x ,误差限，最大迭代次数N.（2） 置 k 1,a, 01. 求整数r,使x max lx ,x a . r1 in i r 1计算y ,x Ay置x a .计算aa1 an2 .0 a 2a a210 若I J，输入，x,停机；否则转（7）.若k N.置a
13、 a ,a a ,10210,k 1k转（3）；否则停止.例2.用此加速算法计算矩阵A4 14 05 13 0的主特征值。计算结果如下表Kmax(v ) k17.812526.266666666636.062546.0153846153* * #116.037368126.2335136.0583146.0364156.0145166.91由此A的主特征值 6.91.改进的Aitken加速算法文献6给出一种改进的Aitken算法，具体算法伪代码如下： 输入人a.,初始向量x土，x ,误差限，最大迭代次数N.（2） 置 k 1,a0ai0, 01. 求整数r,使x max |x|,x a. r1
14、 i n 1 r 计算y , x Ay置x a .计算a ，VL. 0 2a 3a a210 若| J，输入，x,停机；否则转（7 ）.若k N.置a a ,a a , ,k 1 k转（3）；否则停止.102104 14 0例3.用此改进的加速算法计算矩阵A5 13 0的主特征值。1 0 2经过比较我发现改进的加速算法还不如不改进的。所以我重新阅读了文献 6发现证明中有一步假设是不合适的，而定理的结论是依赖于这个假设 的，因此，我们认为，这样的算法在实际应用中不具有应用价值。具体的 解释说明请关注附录。新的改进的Aitken加速算法由于改进的加速没有达到我们想要的结果。所以我又参阅文献7了解 到一种解非线性方程的新算法，经过反复与本文对比发现此新算法可以推 及应用到求矩阵的主特征值上，具体计算步骤如下：71）输入入2,初始向量xxx2，,xn ,误差限，最大迭代次数N.（2）置 k 1,1.0（3）求整数r,使 x max |x|,x a .ri r 0 计算y二x Ay置x a0星a a置一02a2.计算y兰 a1
