（计算数学专业论文）解大规模反对称矩阵特征问题的广义lanczos方法.pdf

摘要 本文研究求解大规模反对称矩阵特征问题的广义l a n c z o s 方法本学位论文 共分四章 第一章介绍大规模反对称矩阵特征问题的来源，解决这类问题的基本方法以 及与论文有关的研究方向及发展动态，并概述了本文的主要工作 第二章是本文的一些预备知识，包括l 趾c z o s 算法，反对称矩阵的性质，以 及求解反对称矩阵特征问题的j a c o b i 迭代 第三章研究了求解大规模反对称矩阵特征问题的广义l a i i c 乃o s 方法及精化广 义l a n c z o s 方法 第四章研究了求解大规模反对称矩阵内部特征问题的广义调和l a n c z o s 方 法 关键词：反对称矩阵，广义l a n c z o s 方法，内特征值，精化方法，精化向量，调 和方法，调和r j t z 值，调和r i t z 向量 a b s t r a c t t h i sp a p e ri n v e s t i g a t e st h es o l u t i o no fl a r g es c a l es k e ws y m m e t r i ce i g e n v a l u e p r o b l e m su s i n gg e n e r a l i z e dl a n e z o s m e t h o d s i tc o n s i s t so f f o u rc h a p t e r s c h a p t e ro n eg i v e sab a c k g r o u n do fl a r g ee i g e n v a l u ep r o b l e m s ，t h em a i nm e t h o d s f o rs o l v i n gt h e m t h es t a t eo f t h ea r to f t h ea r e ai sr e v i e w e db r i e f l y t h ew o r ko f t h e t h e s i si so u t l i n e d i nc h a p t e rt w o ，w er e c a l lt h el a n c z o sa l g o r i t h m ，t h ep r o p e r t i e so ft h es k e w s y m m e t r i cm a t r i x a n dt h ej a c o b ii t e r a t i o nm e t h o df o rs o l v i n gs k e wh a a t r i xe i g e n v a l u e p r o b l e m s i nc h a p t e rt h r e e ，w ep r e s e n tt h eg e n e r a l i z e dl a n c z o sm e t h o da n di t sr e f i n e d v a r i a n tf o rs o l v i n gl a r g es c a l es k e ws y m m e t r i ce i g e n v a l u ep r o b l e m s i nc h a p t e rf o u r , t h eh a r m o n i cg e n e r a l i z e dl a n c z o sm e t h o di si n v e s t i g a t e d ，w h i c h i sm o r es u i t a b l ef o rc o m p u t i n ge i g e n v a l u e si nt h ei n t e r i o ro f t h es p e c t r u m k e yw o r d s ：s k e w - s y m m e t r i cm a t r i c e s ，t h eg e n e r a l i z e dl a n c z o sp r o c e s s ，i n t e r i o re i g e n v a h e ， r e f i n ep r o j e c t i o n ，r e f i n ev e c t o r ，h a r m o n i cp r o j e e t i o n ，h a r m o i cr i t zv a l u e ，h a r m o i er i t zv e c t o l 第一章前言 1 1 问题的来源 大规模矩阵特征问题产生于许多科学计算和工程应用领域，例如计算流体力 学的稳定性分析，量子力学，化学工程和网络排队的马尔科夫链模拟等许多实际 问题最终都转化为矩阵的特征问题 仍= 五够 ( 1 1 ) 的求解，其中一为玎阶实( 或复) 方阵，( 丑，仍) 是a 的特征对且恼i | - 1 ，i = l ，玎 这类实际问题的求解的主要困难是求解矩阵都比较稀疏，而且阶数都非常高在 求解大规模矩阵特征问题时，我们往往需要的是矩阵的部分特征对，如按实部最 大或最小，按模最大或最小，或者在某个区域的特征值以及相应的特征向量 由于这些大型矩阵特征问题产生于科学工程应用领域，他们的求解已经成为 许多项目的核心问题，往往需要花费大量的运算时间，国际上大规模矩阵特征问 题的研究非常活跃因此，9 0 年代以来学者开始收集产生于不同应用领域的典型 矩阵，形成了不同的矩阵测试集，如f 1 】中的h a r w e l l - b o e i n g 矩阵集以及最近还在 不断更新的b a i 等人提供的矩阵市场 2 】等等 1 2 历史与主要方法 特征值问题是一个古老而新鲜的问题，早期的方法有幂法( 反幂法) 、子空 间迭代法、分而治之法和逐步对角化的j a e o b i 方法等等幂法的特点是只需要用 到矩阵向量运算，这种方法在求解矩阵按模最大的特征对方面起到了很好的作 用，目前著名的搜索软件g o o g l e 在其核心技术p a g e r a n k 中求解网络排名时用的 就是幂法当已知矩阵的近似特征值，要求解其对应的特征向量时，可以用反幂 法分而治之法是求解对称三对角矩阵全部特征值和相应特征向量的数值方法， 它由d o n g a r r a 和s o r e n s e n 于1 9 8 7 年首先提出的，其基本思想是先把给定对称矩 l 阵“分割”成2 个低阶的对称三对角矩阵，然后分别求出每个低阶的对称三对 角矩阵的谱分解，最后将这些低阶的谱分解“胶合”在一起而得到原来矩阵的准 确特征值，这种方法非常适合于并行计算j a c o b i 方法是求解对称矩阵全部特征值 和特征向量的最古老的方法之一，它由j a c o b i 于1 8 4 6 年首先提出，由于这种方 法编程简单，并行的效率很高，近年来又重新引起了人们的重视q r 方法的出现 是特征问题求解的大突破，它被列为十大算法之一这种方法也是求解矩阵的 全部特征对，它通过正交相似变换逐步地将一个给定矩阵约化为上三角矩阵或者 拟上三角矩阵，它的收敛速度是二阶的，当求解矩阵为对称时收敛速度可以达到 三阶，该方法在收敛性分析、数值稳定性等许多方面已经取得了非常令人满意的 结果，有的软件包中的子程序就是根据q r 算法编写的对于不同的问题，由于 矩阵的结构不同，采用的方法也不同，因此，不同的方法往往有其各自的优点， 但是对于中小规模的特征问题现在已经基本上得到了满意的解决 对于大规模矩阵特征问题，传统的求解方法还存在着很多困难，第一，由于 矩阵的阶数很高，计算机的内存往往不足，另外我们需要的往往是部分特征对， 传统方法往往是求解全部特征对第二，实际应用领域产生的矩阵往往是非常的 稀疏，在实际求解过程中一般要求不对矩阵做任何改变，所用到的就是矩阵乘向 量的一个子程序 对于大规模矩阵特征问题，主要的方法是子空间投影方法，其基本思想是通 过将大规模矩阵向一个低维的子空间进行投影，可以极大的降低原问题矩阵的阶 数，将其转化为中小规模矩阵特征问题，再用成熟的方法进行求解，用得到的达 到满意精度的解作为原来问题的近似解目前研究的比较多的主要有以下三种方 法 1 2 1 正交投影( r a y i e i g h - r i t z ) 方法 给定m 维求解子空间u ，正交投影方法用满足下列条件 2 再甜，钆 ( 1 2 ) 【一萌一丑菇上u 的瓴，磊) 作为矩阵a 的近似特征对，互，磊分别称为a 在子空间u 上的r i t z 值和 r i t z 向量 通常我们选择子空间u 的一组标准正交基那么r i t z 对瞩，羁) 满足 j 磊= g y , ，y i 刘( 1 1 3 ) 、h 。y 。= a j y 。 其中h ，= v 7 a v 是a 在子空间u 上标准正交基v 下的限制矩阵通常( 1 3 ) 可 以由标准的方法e i s p a c k 中的子程序来求解，根据标准正交基的不同生成方法 产生很多不同的方法，例如a m o l d i 方法、j a c o b i d a v i d s o n 方法、子空间迭代法 等等上述过程的计算次序为： 1 计算子空间u 的一组标准正交基v ： 2 形成a 在子空间u 上的限制矩阵乩； 3 计算巩的特征对( 互，只) ； 4 将瓯，菇) = 瞩，g y ，) 作为a 的近似特征对 1 2 2 斜投影方法 绘定两个m 维子空间k 和l ，斜投影方法寻找( 互，西) 满足下列条件 荡， 【一萌一互话上厶 ”1 7 并将( 互，谚) 作为a 的某些特征对的近似值，子空间k 和l 分别称为右子空间和 左子空间假定畋和均为一坍矩阵，他们的列向量分别是子空间和k 的一 组基，则上述关系可以写成 像巍嘞 s ， 这里l = 孵一吃根据上和k 的不同选取我们可以导出很多不同的斜投影方法， 目前研究比较多的是调和投影方法和非对称的i a i n c z o s 算法 1 2 3 精化投影方法 精化投影方法的基本思想是对于任意的求解子空问e ，以及每一个近似特征 值互，精化投影类方法用满足极小残量条件 i i ( a 一五j ) “，i i = 。m f i i 。n f 。1l l ( 4 一 ，) “l i ( 1 6 ) 的坼作为与近似特征值互相对应的近似特征向量，称毡为a 在子空间e 上与互相 对应的精化向量对于指定的求解子空间e ，精化向量”。可以通过计算一个小型的 矩阵奇异值问题来计算贾的一系列收敛性分析表明精化方法彻底克服了传统投 影方法可能出现的近似特征值收敛而近似特征向量却可能收敛很慢甚至不收敛 的潜在隐患，从理论上证明了在近似特征值收敛的情况下，相应的精化向量必收 敛，大量的数值实验已经证明了精化方法的显著有效性贾在提出精化方法的同 时，也指出这种思想对于任意的投影方法都是适用的 精化方法开辟了求解大规模矩阵特征问题的一个全新的研究领域，如何将精 化投影思想应用到传统的投影方法中去，从而开发出更为实用有效的算法将是一 个十分有意义的课题 1 3 选题与本文工作 当大规模矩阵为对称矩阵时，由于其良好的性态，传统的投影方法包括子空 间迭代法以及l a n c z o s 方法，块的l a n c z o s 方法等已经进行了近3 0 年的研究， 在理论研究、数值性态的分析以及软件开发等方面进行了深入全面的研究，目前 已经形成了臻于完善的系统体系反对称矩阵与对称矩阵都属于正规矩阵，两种 矩阵都可以正交对角化，不同的是对称矩阵的特征值都在实轴上，而反对称矩阵 的特征值都落在虚轴上，因此，反对称矩阵跟对称矩阵一样也有很多很好的性质 我们希望将求解对称矩阵特征问题成熟的思想方法用到求解反对称矩阵中，从而 开发出求解大规模反对称矩阵特征问题的有效算法 当大规模矩阵为反对称矩阵时，非常幸运的是h a v a i l d e r v o r s t 在1 9 8 1 年 给出了类似于l a n c z o s 算法的三项递推关系式，可以用来生成反对称矩阵求解空 间的标准正交基根据现行的求解大规模矩阵特征问题的主要方法本文分别作了 以下工作： 求解大规模反对称矩阵特征问题的广义l a n c z o s 方法及其精化变形 首先由广义l a r l c z o s 算法生成m 维k r y l o v 子空间j 0 ( 4 ，v 1 ) 的标准正交基， 然后通过r a y l e i g h - r i t z 的基本思想将大规模矩阵特征问题转化为一个低阶的反 对称三对角矩阵特征问题来近似，根据r i t z 向量收敛不规则的特点我们又给出 了广义l a n c z o s 方法的精化变形，数值试验表明精化方法更为有效 求解大规模反对称矩阵特征问题的广义调和l a n c z o s 方法 首先由广义l a n c z o s 算法生成1 3 3 维k r y l o v 子空间k ( 爿，v 1 ) 的标准正交基， 然后通过调和r a y l e i g h - r i t z 的基本思想将大规模矩阵特征问题转化为一个低阶 的广义特征问题来近似 第二章预备知识 2 1l a n c z o s 算法 l a n e z o s 算法于1 9 5 0 年提出，此方法可以求解大规模稀疏对称矩阵少数最大 或者最小的特征值，此方法可以产生一列对角阵瓦，其最大与最小的特征值越来 越好的近似a 的最大与最小特征值，其迭代格式为： r o = v l ；屁= 1 ；v o = 0 ；k = 0 w h i l e ( i l k o ) ， v 七+ 1 3 瓦r k ；七= m 2 k 7 彳喙； r k = ( a 一“t i ) v t 一羼一1 v t - l ： 展= ir k | | 2 ； e 玎d 上述过程的矩阵表达式为 一k = k 瓦+ r k e k 7 ( 2 1 ) 其中瓦= v ；a v i = t r i g ( p , ，q ，层) 定理2 1 。”r i t z 向量话= v , y ，满足如下关系式 4 谚一五磊= 屏k “ ( 2 _ 2 ) 其中是的第七个分量 定理2 2 ”k a n i e l p a i g e 设a 为1 1 阶对称矩阵，且特征值为 五2 以，相应的特征向量为 讫仍纯，五为用l a n c z o s 算法得到的三对角矩阵，其相应的特征值为 q 岛- b 则 五q 一( 4 ：- 石l 研) t a a o , ( 2 _ 3 ) 其中q l 为k 1 次c h e b y s h e v 多项式，p l = 孚二争，c o s o i = 爿群萌i 如一 6 2 2 反对称矩阵的性质 设爿为n 阶反对称矩阵，那么 a 的对角元为零： d e t ( a ) = d e t ( a 7 ) = ( 一1 ) “d e t ( a ) ； 如果n 为奇数，那么d e t ( a ) = 0 ； 如果4 _ 1 存在，那么爿“也是反对称矩阵； a 的特征值为零或者纯虚数 2 3 求解反对称矩阵矩阵特征问题的j a c o bi 迭代 求解反对称矩阵矩阵特征问题的j a c o b i 迭代是由m h c p a a r d e k o o p e r 于 1 9 7 0 年提出的它的基本思想是通过正交相似变换将彳转化成一阶零矩阵和2 阶 矩阵匕加直和，其中加为4 的一对共轭特征值，这种直和称为爿的 m u r n a g h a n s 标准形 设a 是刀开反对称矩阵，且a 7 = 一a ，矩阵以下面形式分块 a = 4 l4 2 a l i a 2 1a 2 2 一a 2 t a i la 1 2 如 a 的每一个子矩阵爿。是2 维方阵，如果n 是奇数，那么a 。= ( 口。) 是1 维的， 黼= 孚 ，批# ( 渺8 ：) i 其+ 1 1 - 1 1 。是欧几里德矩阵范数，称f ( 4 ) 为a 的m u r n a g h a n s 形式的偏差，此算法 是建立在平面旋转的基础上，在o ，m ) 位置上平面旋转的矩阵称为正交旋转变换 矩阵，记为巩，瓦的非平凡元( c o s 仍s i n p ，一s i n 弘c o s 缈) 称为毛的雅可比参数， 它们构成2 2 矩阵 允= = ( 三s i n ：c 血o s ；)l 一 伊 尹 称丸为正交旋转变换矩阵的( ，m ) 限制在求解反对称矩阵特征问题的j a c o b i 迭代算法中初始矩阵厶= a 逐次变换为矩阵a l ，一：，这些矩阵收敛于a 的 m u r n a g h a n s 标准形式 矩阵序列a j 定义为如下关系： a j ；t i | m | a j | j m i j = l ，2 ， 其中i ，q 是在主元对n ，m ，) 上的正交旋转变换矩阵，在这种正交旋转变换下 f ( 一) 渐小 甄l i m r ( a ，) 三0 如4 4 反对称矩阵a 经若干次的正交旋转变换为a 的m u r n a g h a n s 标准形 式 0 v i v 1 0 00 oo 00 00 0 ”2 一v 2 0 其中i v l ，+ i v 2 是a 的特征值 第三章 求解大规模反对称矩阵特征问题的广义l a n c z o s 方法 及精化广义l a n c z o s 方法 3 1 引言 考察大规模反对称矩阵特征问题 舷= 五记 ( 3 ，1 ) 其中a 是疗疗实反对称矩阵，( ，纯) 是a 的特征对且慨j = 1 ，i = 1 ，聆我们要求 矩阵a 端部的部分近似特征值以及相应的特征向量。 反对称问题产生于许多工程领域和线性系统的分裂预条件方法中对于特征 问题( 3 1 ) ，r a y l e i g h r i t z 方法是最为有效的，收敛性分析表明当特征向量和求 解子空间的夹角趋于零时，r i t z 值能够收敛到准确特征值，而r i t z 向量的收敛性 则可能很慢，甚至不收敛本章在第二部分我们首先给出了广义l a n c z o s 算法，然 后在第三部分给出收敛性分析，并根据精化策略给出了求解反对称矩阵部分特征 对的精化广义l a l l c z o s 算法 3 2 广义l a n c z o s 算法 广义l a n e z o s 算法的基本思想是给定一初始向量v 1 ，通过简单的三项递推公 式生成k r y l o v 子空间如( 彳，v 1 ) 的标准正交基，这种方法只需要很少的运算量和存储 量，因此十分简单 r n 步的广义l a n c z o s 算法，计算反对称阵a 的1 1 1 维k r y l o v 子空间x 。( 彳，v i ) 的一组标准正交基 v j 二。 算法3 1m 步的广义l a n c z o s 过程 1 、开始：给定初始向量v l ，使“，) = l 。= a v 9 2 、迭代：f o r j = l ，2 ，m d o ! 岛+ t = _ 1 ) 是标准正交的，那么由 屈“v k “= a v , 一反v “， 当j 0 s m 么( x ，i ) ( 1 + ：写2 ；丽1 1 a i i j , s ( 3 1 2 ) 3 4 显式重新启动广义l a n c z o s 算法 将s a a d t ”1 的重新启动策略应用到广义l a n c z o s 方法上便得到显示重新启动 的广义l a n c z o s 算法 算法3 。2 显式重新启动的广义l a r l c z o s 算法 ( 1 ) 开始：给定k r y l o v 子空间维数m ，所求的内特征对个数k 茎册，控制 精度t o l 和单位长初始向量m ( 2 ) 广义l a n z o s 过程：完成m 步广义l a n c o s 过程( 算法3 i ) ，形成三对 角反对称阵l ，曩和列正交阵 ( 3 ) 计算近似特征对：计算r i t z 对( 五，谚) ，i = 1 , 2 ，脚，选取其中i n 个作 为a 的特征对( 五，识) 的近似 ( 4 ) 检验收敛：如果r i t zx 于 i ，磊) ，i = l ，2 ，m 的残量范数l 均小于t o ， 则算法停止，否则继续进行 ( 5 ) 重新开始：利用s a a d 0 1 构造新的初始单位长初始向量v l ，转( 2 ) 类似于s a a d 的重新启动动策略，该算法重新启动时新的v l 可按如下方式选 取 口v 1 ；圭一互，) 羁l 啊口g ( 玩) ， ( 3 1 3 ) 其中口是规范化因子关系式( 3 ，1 3 ) 中的v l 是一个实向量，因此可以保证算法过 程对实矩阵仅做实运算 3 5 精化广义l a n c z o s 算法 设( 五，谚) 是广义l a n c z o s 算法求得的r i t z 对，我们保留互作为近似特征值， 舍弃彝，从子空间s p a n v ) 中寻找单位长度的向量满足下面的最优性条件 i i ( a 一丑观1 1 = 恋：。m 一 咖i | ( 3 1 4 ) 的珥作为新的近似特征向量，称之为精化向量从上面的式子可以看1 t t 坼是子空间 妒口n ( 圪) 所能提供的关于五和2 一范数的对特征向量的最佳逼近。 假定z ，是( 4 一互，) 的最小右奇异值所对应的右奇异向量，则 脏警 ( 3 1 5 ) ( a 一 ，) “，i o m i 。( ( 一一a f t ) 圪) 。 定理3 6 设是毫一互，的虽小右奇异值。( 毫一互，) 所对应的右奇异向量，那么 我们有 “。= k 刁，且 忖一互啦扣( t 一互7 ) = 抓l 一互啦，卜鹰凇气1 2 ( 3 1 6 ) 证明由a = 匕l + 以+ i v 。+ l p 。t 4 又肛彳一互酬i ：| r e 胛m i n i i ( a x j 两i i = m i n i i ( a 一互，) 匕z i i = o r m i n ( 露一互7 ) 设毛为乏一互7 的最小奇异值对应的右奇异向量，那么 ( 露一互7 ) = k 一互) z ，卜珐陆tt 2 口 定理3 7 t 7 1 如果s e p ( 互，g ) 2s e p f f t ，g ) 1 互捌， 那么 s i n z ( 工，习( 1 + i 兰些；三二生! ! 兰唑) s ( 3 1 7 ) l 一占2 ( 占号p ( 五，g ) 一l 五一 i 算法3 3 显式重新启动的精化广义l a n c z o s 算法 ( 1 ) 开始：给定k r y l o v 子空间维数m ，所求的内特征对个数k s 搠，控制 精度t o l 和单位长初始向量v 1 ( 2 ) 广义l a n z o s 过程：完成m 步广义l a n c o s 过程( 算法3 1 ) ，形成三对 角反对称阵乇，元和列正交阵圪 ( 3 ) 计算近似特征值：计算瓦的r i t z 值互，i = 1 , 2 ，m ，选取其中k 个互 i = 1 , 2 ，k ，作为a 的特征值的近似 ( 4 ) 计算近似特征向量，根据( 3 1 5 ) 计算精化向量“，i = 1 , 2 ，j | ( 5 ) 检验收敛：根据( 3 1 6 ) 计算精化r i t z 对瓴，) ，i = l ，2 ，i 的残量范 数川l ，若它们均小于t o l ，则算法停止，否则继续进行 ( 6 ) 重新开始：利用s a a d m 构造新的初始单位长初始向量v 1 ，转( 2 ) 3 6 数值试验 例1 我们选取了矩阵市场 1 的矩阵b p 6 0 0 矩阵的阶数为8 2 2 ， 取爿= j 一岔，取子空间维数为2 0 ，我们计算了矩阵按虚部最大的一个特征值和 相应的特征向量初始向量选为随机生成的单位向量，停机准则为1 0 一，计算结 果为五= 4 0 8 i ，实验结果如下 广义l a n c z o s 算法精化广义l a d c z o s 算法 ml t e rt l m e 1 t e r t l m e 2 0 9 7 2 6 8 52 4 3 06 51 55 1l _ 3 i4 。3 10 9 72 70 9 1 例2 这个矩阵来源于矩阵测试集 3 ，矩阵文件g r e l1 0 7 ，矩阵的阶数为11 0 7 用相同的方法产生反对称矩阵，子空间维数为2 0 ，计算矩阵按虚部最大的一个 特征值和相应的特征向量选取初始向量为随机生成的单位向量，停机准则为 l o ，计算结果为五= 5 2 3 i ，实验结果如下 广义l a n c z o s 算法精化广义l a n c z o s 算法 mi t e ft i m e i t e r t l m e 2 01 5 75 6 1 3 5 5 1 3 01 1 54 51 0 23 6 4 09 63 87 63 1 从上面的两个例子可以看出上述两种算法对于计算反对称矩阵特征问题是 非常有效的，精化变形需要的迭代次数更少 1 6 第四章 解大规模反对称矩阵内部特征问题的 广义调和l a n c z o s 方法 4 1 引言 考察大规模反对称阵特征问题 爿纯= 五仍，( 4 1 ) 其中a 是玎玎实反对称阵，( 五，织) 是a 的特征对且忪j i = l ，i = l ，玎我们要求复 平面上的点f 附近的特征值以及相应的特征向量 对于内部特征问题( 4 1 ) ，m o r g a n 【1 l 】提出了一种特殊的斜投影方法用来求 解大规模矩阵内部部分特征问题，这种方法隐式地完成了矩阵( a r i ) 的求逆 过程，后来这种方法被称为调和r a y l e i g h - r i t z 方法调和r a y l e i g h - r i t z 方法已经 成为求解大规模矩阵内部特征问题的最有效的方法之一 对于反对称矩阵a ，按照调和r a y l e i g h - r i t z 方法的思想，本文借助于广义 l a n e z o s 算法提出了一种用来求解大型反对称矩阵部分内部特征问题的广义调和 l 柚c z o s 方法，这种方法可以借助于简单的三项递推关系生成求解k r y l o v 子空间 的一组标准正交基，利用调和投影过程将原来的大规模矩阵部分特征问题转化成 了一个小型的广义特征问题求解因此，只需要很少的计算量和存储量就可以得 到问题( 4 1 ) 的部分近似解 4 2 广义调和l a n c z o s 方法 对于反对称矩阵a ，求解在r 附近部分特征对问题采用位移求逆的技 术，即 ( 彳一f ，) 一绣：一馈 ( 4 2 ) 丘一z - 这样，可以将求a 的在f 附近的内特征值问题转化为( 一f ，) 1 端部特征问 题来求解对给定的f ，调和投影方法寻求防，嚣) 满足调和投影喊9 l i 识j 0 ( 爿，v 1 ) ， i ( 爿一 j ) 竹上( a 一玎) 量。( a ，v 1 ) ， 防，i ) 称为a 在子空间j 乙( 爿，v i ) 中的调和r i t z 值和调和鼬t z 向量 l a n e z o s 过程，上述过程等价于求解广义特征问题 j 瓯一巩) ”岛2 去( 亏一r i ) ”( 亏一r i ) g j ， b ：_ 静 其中i = ( ) 。，由c s 2 ，和c 4 。，得 q 。一t l 了g j 在实际计算中( 4 4 ) 式的求解通常由q z 算法来完成 4 3 调和r i t z 对的收敛性分析 4 。3 。1 调和r i t z 值的收敛性 设b = ( 乙一巩) ”，c = ( 瓦一f l ) ”( 7 ：，一f l ) 定理4 1 吲设l 是m 步产生r a y l e i g h 商，则有一个矩阵e 满足 l i e u 寿( 1 a i i l 4 i f 刊彳1 1 2 ) ， 使得z 是b 。c + e 的一个特征值 定理4 2 嘲存在b 一一c 的一个特征值互，使得 i 丑一互i s ( 2 8 4 l + i i e i i ) 。i1 1 e 1 1 i 4 3 2 调和r i t z 向量的收敛性 设防妞一 s ( 4 3 ) 利用广义 ( 4 4 ) ( 4 5 ) ( 4 6 ) ( 4 7 ) 毋 戌 h，+ 瑶 卜 土扣 定理4 3 嘲如果s 印( 五，g ) 0 那么 s m l ( x ，刁s ( 1 + 型善掣) 1 一s 2 j 印( z ，g ) ( 4 8 ) 4 4 显式重瓤启动广义调和l a n c z o s 算法 将s a a d ”1 的重新启动策略应用到广义l a n c z o s 方法上便得到显示重新启动 的广义调和l a n c z o s 算法 算法4 1显式重新启动的广义调和l a n c z o s 算法 ( 1 ) 开始：给定k r y l o v 子空间维数m ，目标点f ，所求的内特征对个数k s m ， 控制精度t o l 和单位长初始向量v 1 ( 2 ) 广义l a n z o s 过程：完成m 步广义l a n c o s 过程( 算法3 1 ) ，形成三对 角反对称阵l ，毫和列正交阵k ( 3 ) 计算近似特征对：计算调和r i t z 对阮，万l f ：1 , 2 ，m ，选取其中k 个 作为a 的特征对( 五，鳃) 的近似 ( 4 ) 检验收敛：如果调和砌位对晤，万l f = l ，2 ，k 的残量范数l 均小于t o l ， 则算法停止，否则继续进行 ( 5 ) 重新开始：利用s a a d t ”1 构造新的单位长初始向量e ，转( 2 ) 4 5 数值试验 例1 我们随即生成了一个2 0 0 x 2 0 0 阶的矩阵互取彳= j 一，取子空间维 数为2 0 ，我们计算了矩阵按虚部最小的一个特征值和相应的特征向量初始向量 选为随机生成的单位向量，停机准则为1 0 4 算法2 的收敛情况如下图，迭代1 2 8 次用时3 6 秒残量范数达到3 4 x 1 0 一 9 j l j 一一 l 例2 这个矩阵来源于矩阵测试集 3 ，矩阵文件名b p l 0 0 0 ，矩阵的阶数为 8 2 2 用相同的方法产生反对称矩阵选取初始向量为随机生成的单位向量，我们 计算矩阵按虚部最小的一个特征值和相应的特征向量停机准则为l o ，子空间 维数为2 0 ，下图给出了算法2 的收敛情况，迭代9 4 次用时2 7 秒残量范数达到 了5 a 1 0 4 瓣 _ 黪 万 _ 滁一 万：i 菇。 1 ，i ， 涮 。，r。h，hn。，r。ff 一 铲 矿 铲 铲 矿 铲 1 0 一一 1 矿 ，一i 、，、一 1 0 。i - 1 0 - ： 1 一l 1 矿1 1 d 4 一 从上面的两个例子可以看出算法4 1 对于计算反对称矩阵特征问题是非常 有效的 本文作者在读硕士学位期间发表的有关学术论文 第四章的结果已整理成文解大规模反对称矩阵内部特征问题的广义调和 l a n c z o s 方法，已在宁德师专学报( 自然科学版2 0 0 6 年第2 期) 上发表 第三章的结果已整理成文解大规模反对称矩阵特征问题的广义l a n c z o s 方 法和精化广义l a n c z o s 方法已投福建师范大学学报( 自然科学版) 参考文献 1 z b a i ，r b a r r e t ，d d a y ，j d e l e la n dj d o n g a r r a ，t e s tm a t r i xc o l l e c t i o n f o rn o n h e r m i t i a nm a t r i xe i g e n p r o b l e m ，t e c h n i q u er e p o r tm a t h e m a t i c s u n i v e r s i t yo fk e n t u c k y ，u s ，1 9 9 5 2 旦羔主巳；z 塑墨主b ：墨i 兰羔：g q ! 丛垒主i 兰丛i 竖旦主 3 3 g h g o l u ba n dc f v a n l o a n ，m a t r i xc o m p u t a t i o n ，z n d ，j o h n sh o p k i n s u n i v e r s i t yp r e s s ，b a l t i m o r e ，1 9 8 9 4 噱h c 。p a a r d e k o o p e r ，a ne i g e n v a l u ea l g o r i t h m f o r s k e w - s y m m e t r i c m a t r i c e s n u m e r m a t h 1 7 ( 1 9 7 1 ) ，1 8 9 2 0 2 5 陈桂芝，解大规模非对称矩阵特征问题的一些精化算法，大连理工大学博士 论文，2 0 0 0 【6 】z 。j i a ，t h ec o n v e r g e n c eo fh a r m o n i cr i t zv a l u e s ，h a r m o n i cr i t zv e c t o r s a n dr e f i n e dh a r m o n i cr i t zv e c t o r s ，m a t h c o m p 7 z j i a 。t h er e f i n e dh a r m o n i ca r n o l d im e t h o da n da ni m p l i c i t l yr e s t