（计算数学专业论文）大规模矩阵伪谱计算的数值方法.pdf

厂 j n a n j i n gu n i v e r s i t yo f a e r o n a u t i c sa n d a s t r o n a u t i c s t h eg r a d u a t es c h o o l c o l l e g eo fs c i e n c e n u m e r i c a lm e t h o d sf o rc o m p u t i n g l a r g e m a t r i x p s e u d o s p e c t r a a t h e s i si n c o m p u t a t i o n a lm a t h e m a t i c s b y q i n g y u nm e n g a d v i s e db y a s s o c i a t ep r o f e s s o rz h e n g s h e n gw a n g s u b m i t t e di np a r t i a lf u l f i l l m e n t o ft h er e q u i r e m e n t s f o r t h ed e g r e eo f m a s t e ro fs c i e n c e f e b r u a r y , 2 0 1 0 i 承诺书 本人声明所呈交的硕士学位论文是本人在导师指导下进 行的研究工作及取得的研究成果。除了文中特别加以标注和致 谢的地方外，论文中不包含其他人已经发表或撰写过的研究成 果，也不包含为获得南京航空航天大学或其他教育机构的学位 或证书而使用过的材料。 本人授权南京航空航天大学可以将学位论文的全部或部 分内容编入有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本承诺书) 作者签名：童盘叁 日 期：垫! ! ：i ：! - 南京航窄航天人学硕士学位论文 摘要 矩阵伪谱在很多领域都有重要的理论意义和工程价值，是理解各种矩阵过程的一个非常有 用的工具，拓展了我们对矩阵计算现象的理解。对非正规矩阵，已经证明伪谱是一个很有用的 工具。从科学计算的观点看，非正规矩阵或算子的伪谱要比它的谱更可靠。但是伪谱的计算量 很大，因此需要寻找能够在一定合理时间内计算伪谱的方法。 本文在概述伪谱的理论和算法的基础上，给出了计算人规模矩阵伪谱的一种投影算法，包 括正交投影算法和斜投影算法，并将这种算法推广到矩阵多项式伪谱的计算中。和已有的矩阵 伪谱算法不同，本文提出了求解矩阵伪谱的最佳秩- k 逼近算法，这种方法对于特定矩阵的伪谱 计算有很好的效果。本文还将矩阵伪谱的q r 分解定义推广到了矩阵多项式伪谱。对各种算法， 本文分别给出了数值试验，以验证它们的有效性。 关键词：非正规矩阵，矩阵伪谱，矩阵多项式伪谱，投影算法，最佳秩- k 逼近，q r 分解 大规模矩阵伪谱计算的数值方法 a b s t r a c t t h ec o m p u t a t i o no fm a t r i xp s e u d o s p e c t r a ，w h i c hh a v eb e e nw i d e l yu s e di nm a n yf i e l d s ，i sa n i n t e r e s t i n ga n di m p o r t a n tp r o b l e mf o rd i s c u s s i o nw i t hs p e c i a lt h e o r e t i cs e n s ea n de n g i n e e r i n gv a l u e t h ep s e u d o s p e c t r ao fm a t r i xi sap o w e r f u lc o n c e p tt h a tb r o a d e n so u ru n d e r s t a n d i n go ft h eb a h a v i o u r o fv a r i o u sm a t r i xp r o c e s sa n d p h e n o m e n ab a s e d o i lm a t r i xc o m p u t a t i o n f o rn o n n o r m a lm a t r i c e sa n d o p e r a t o r , m a t r i xp s e u d o s p e c t r ah a db e e np r o v e dt ob en l o 把u s e f u lt h a ne i g e n v a l u e s h o w e v e lt h e c o m p u t i o no fp s e u d o s p e c t r ai sav e r y e x p e n s i v ec o m p u t a t i o n a lt a s k t h u s ，t h eu s eo fh i g hp e r f o r m a c e c o m p u t i n gr e c o u r c e sb e c o m e sk e yt oo b t a i n i n gu s e f u la n s w e r si na c c e p t a b l ea m o u t so ft i m e t h i sp a p e r , b a s e d0 1 1ab r i e fs u m m a r yo fp s e u d o s p e c t r at h e o r ya n da l g o r i t h m s ，p r o p o s e da n a d v a n c e dk i n do fp r o j e c t i o nm e t h o d sf o rc o m p u t i n gt h ep s e u d o s p e c t r ao fl a r g es c a l em a t r i c e s i n c l u d i n go r t h o g o n a l i z a t i o np r o j e c t i o nm e t h o da n do b l i q u ep r o j e c t i o nm e t h o dr e s p e c t i v e l y , w h i c hh a d b e e ng e n e r a l i z e dt ot h ec o m p u t i n go fm a t r i xp o l y n o m i a l sp s e u d o s p e c t r a d i f f e r e n tf o r mt h em e t h o d s t h a th a v eb e e nd e v e l o p e d ，t h i sp a p e rd e v e l o pam e t h o dc a l l e do p t i m a lr a n k & m e t h o df o rt h e c o m p u t i n go fm a t r i xp s e u d o s p e c t r a t h i sm e t h o dh a sg o o dp e r f o r m a n c ef o rc e r t a i nm a t r i c e s a l s o ， t h i sp a p e rg i v ean e wd e f i n i t i o no fp s e u d o s p e c t r ao fm a t r i xp o l y n o m i a l sb yu s i n gq r d e c o m p o s i t i o n ， w h i c hi sg e n e r a l i z e df o r mt h et h eq rd e c o m p o s i t i o nd e f i n i t i o no fm a t r i xp s e u d o s p e c t r a n n u m e r i c a l e x p e r i m e n t si l l u s t r a t et h ee f f i c i e n c yo fd i f f e r e n tm e t h o d s k e y w o r d s ：n o n n o r m a lm a t r i x ，m a t r i xp s e u d o s p e c t r a ，p s e u d o s p e c t r a o f m a t r i xp o l y n o m i a l ， p r o j e c t i o nm e t h o d s ，o p t i m a lr a n k - ka p p r o x i m a t i o n ，q rd e c o m p o s i t i o n i i - 南京航窄航天人学硕士学位论文 目录 第一章绪论一l i 1 问题来源、发展及研究价值1 1 2 伪谱的概念2 1 3 矩阵伪谱计算的数值方法6 1 4 本文的主要工作l o 第二章大规模矩阵伪谱计算的投影算法l l 2 1 正交投影算法1 1 2 2 斜投影算法1 3 2 3 数值试验1 5 2 4 结论1 7 第三章矩阵伪谱的最佳秩- k 逼近算法1 8 3 1 基于s v d 的最佳秩_ k 逼近1 8 3 2 矩阵伪谱的最佳秩一k 逼近算法1 9 3 3 数值试验2 0 3 4 结论j 2 5 第四章矩阵多项式伪谱的q r 分解定义2 7 4 1 矩阵伪谱的q r 分解定义2 7 4 2 矩阵多项式伪谱的q r 分解定义2 8 4 3 结论3 1 第五章矩阵多项式伪谱的投影算法。3 2 5 1 矩阵多项式伪谱的投影算法3 2 5 2 数值试验3 3 5 3 结论3 6 第六章总结与展望。3 7 参考文献3 8 至定谢4 l 在学期间的研究成果及发表的学术论文4 2 l l i 犬规模矩阵伪谱计算的数值方法 图表清单 图2 1 “朴素的伪谱”图像和a m o l d i 算法伪谱图像的比较1 6 图2 2 a r n o l d i 近似和i o m ( q ) 近似的比较1 7 图3 1g - r e a r 矩阵的伪谱图像2 l 图3 2k = 3 0 时的g r e a t 矩阵伪谱图像2 l 图3 3k = 6 0 时的g r c a r 矩阵伪谱图像2 1 图3 4k = 9 0 时的g r c a r 矩阵伪谱图像2 1 图3 5k = 9 3 时的g - r e a r 矩阵伪谱图像2 l 图3 6k = 9 6 时的g r e a t 矩阵伪谱图像2 1 图3 7k = 9 9 时的g r e a t 矩阵伪谱图像。2 1 图3 8f o r s y t h e 矩阵的伪谱图像2 2 图3 9k = 3 0 时的f o r s y t h e 矩阵伪谱图像2 3 图3 1 0k = 6 0 时的f o r s y t h e 矩阵伪谱图像2 3 图3 1 1k = 9 0 时的f o r s y t h e 矩阵伪谱图像2 3 图3 1 2k = 9 3 时的f o r s y t h e 矩阵伪谱图像2 4 图3 1 3k = 9 6 时的f o r s y t h e 矩阵伪谱图像2 4 图3 1 4k = 9 9 时的f o r s y t h e 矩阵伪谱图像2 4 图5 1 直接使用g r i d 方法得到的伪谱图像3 4 图5 2 线性化后用g r i d 方法得到的伪谱图像3 4 图5 3 线性化用a m o l d i 投影再用g r i d 方法( a m o l d i ( 1 0 ) ) 得到的伪谱图像3 4 图5 4 线性化用i o m ( q ) 投影再用g r i d 方法( i o m ( 1 0 ，3 ) ) 得到的伪谱图像3 5 图5 5 用四种方法得到的4 8 x 4 8 维c e p 的伪谱图像( 无等高线标注) 3 5 图5 6 用四种方法得到的1 3 2 x1 3 2 维c e p 的伪谱图像( 无等高线标注) 3 6 表2 1 “朴素的伪谱，和a m o l d i 迭代c p u 时间比较1 6 表3 1g r c a r 矩阵秩- k 算法计算时间比较2 2 表3 2 f o r s y t h e 矩阵秩- k 算法计算时间比较2 5 表5 1 矩阵多项式伪谱各种算法的c p u 时间比较一3 6 i v 南京航空航天大学硕十学位论文 c ，c r ，r c “，c “4 r “4 ，r “” c ”，c “ r ”，r “” ，r l n 席 v 曲1 删 r 淼 c ”，c “ r ”，r ” c 0 。一 c ：一。洲 i ，i n i 鲋 么一1 么+ 注释表 复数域 实数域 刀刀维复矩阵的集合 刀以维实矩阵的集合 m 腮维复矩阵的集合 ，l 刀维实矩阵的集合 咒以维复结构矩阵的集合 ，l 甩维实结构矩阵的集合 ，z 维复向量的集合 n 维实向量的集合 定义了1 范数的咒维复向量 赋范空间 定义了0 0 一范数的m 维复向量 赋范空间 n 刀维单位矩阵 主对角元为1 ，其他元素均为 0 的所，l 维矩阵 矩阵彳的扰动矩阵 矩阵么的逆矩阵 矩阵4 的广义逆矩阵 么r 彳，彳 a ，b ， 鲋 a ( a ) 人。( 彳) 人p 甜( 么) 人警( 彳) 。( 么) a 矩阵4 的转置矩阵 矩阵彳的共轭转置矩阵 矩阵 矩阵彳的扰动矩阵 矩阵4 的谱 矩阵彳的占一伪谱 矩阵彳的占结构伪谱 矩阵彳的占实结构伪谱 矩阵彳的最小奇异值 矩阵4 的第f 个特征值 p ( 彳) 矩阵彳的谱半径 ：宰 ： 。 。 石 玑( 兄) 向量x 的2 一范数 矩阵彳的2 范数 向量的1 一范数或其诱导的矩阵 1 范数 向量的o o 范数或其诱导的矩阵 o o 范数 向量x 的共轭向量 以允为中心占为半径的开球 注：本文中，除伪谱定义中的范数外，用到都是2 一范数，有时会省略范数下标，用悯i ，i h l 表示向量和矩阵的2 一范数。 v l 南京航窄航天大学硕士学位论文 第一章绪论 1 1 问题来源、发展及研究价值 二十世纪九十年代以前，研究矩阵的传统工具是特征值( 谱) ，它们可以揭示线性和非线性 系统的特征，包括稳定性、共振、矩阵迭代的可行性等，因此它们是数学科学的一个重要的标 准工具。在计算数学方面，该问题的理论和数值算法也取得了很多成果。然而，在科学和工程 应用中，人们经常遇到这样的现象：根据特征值或谱的性质所作的判断与许多观察的现象或数 值结果不相匹配。究其原因，主要是这些问题所包含的矩阵往往是非正规的，甚至是高度非正 规的【。所以，特征值( 谱) 对分析非正规矩阵是一个不完美的工具。作为谱的自然延伸，伪 谱( p s e u d o s p e c w a ) 是一个针对非正规系统的新工具。 伪谱是一个非常广泛的概念，拓展了我们对矩阵计算现象的理解。很多实例证明，伪谱对 非正规矩阵或算子是一个非常有用的工具，从科学计算的观点看，非正规矩阵的伪谱要比它的 谱更可靠。近年来，伪谱被应用于越来越多的领域中，比如在谱方法的稳定性、直线法的稳定 性分析【2 】、线性微分方程的瞬态特性的研列3 1 、数值迭代方法的收敛性分析州、大型矩阵的离散 时间的l y a p u n o v 稳定性【5 1 、离散代数l y a p u n o v 方程解的上界分析6 1 、动力系统的稳定性川、特 征值计算的有效性评估1 8 】等方面，伪谱的应用都是必不可少的。特别地，伪谱在判断平衡点的 稳定性的应用中尤为重要，备受关注。 矩阵伪谱问题具有很重要的应用背景。这里简单罗列几个，不详细描述。 伪谱与微分方程( 组) 平衡点的渐进稳定性 伪谱与流体系统的不稳定性 矩阵伪谱在矩阵迭代计算中的应用 矩阵伪谱在控制论中的应用 9 1 0 , 1 1 矩形矩阵伪谱在博弈论中的应用 从上世纪几十年代起，矩阵( 特别是结构矩阵) 伪谱理论与方法研列1 3 。2 1 1 越来越引人注目， 但是目前研究成果相较于标准特征值问题和广义特征值问题还很少。本课题对矩阵和矩阵多项 式的伪谱定义与算法发展现状做简单综述，并探讨了计算矩阵伪谱和矩阵多项式伪谱的新算法。 到目前为止，伪谱的计算方法主要有两类，一类是基于网格的s v d 方法以及对这种方法的 改进，这类方法是把复平面的一个区域离散为网格，然后在每个网格点上计算z ，一彳的最小奇 异值：另一类是投影算法，主要用于求解火规模矩阵的伪谱，这类方法很多，除了将在第二章 介绍的a r n o l d i 迭代和i o m ( q ) 迭代外，任何能够构造矩阵彳的近似不变子空间的正交基的算 法都可以用来计算伪谱。例如，为了在点c 附近得到占伪谱人。( 彳) 的近似，可以应用 1 大规模矩阵伪谱计算的数值方法 s h i f t a n d i n v e r t a m o l d i 算法( 即，对( 一a ) 1 而不是a 应用a m o l d i 迭代) 来构造投影子空间； 类似地，r u h e 研究了利用有理k r y l o v 算法近似伪谱的方法，w r i g h t 利用j a c o b i d a v i d s o nq r 算法计算了矩阵的伪谱，并通过数值实验说明了算法的有效性。 伪谱可以为数值线性代数及稳定性问题的迭代方法提供有用的信息，因此，伪谱的计算方 法可以将定性问题转化为定量问题。然而，在大多数情况下，它的计算会冈为过高的计算损耗 而变得困难，尤其是对一些大规模矩阵，更加难以实现。因此，我们需要从一个新的角度去探 索能简单而又快速地计算矩阵伪谱的新方法；对于矩阵多项式伪谱，由于问题本身的复杂性， 我们可以用一种新的思路来讨论它的定义和计算方法。 1 2 伪谱的概念 关于矩阵或谱的特征值和谱的研究已经是近1 0 0 年来数学上最成熟的领域之一。虽然很少 的几个人已经意识到特征值分析的局限性，但是一直到很多年后，数学家才对由1 f 正规算子和 矩阵引起的一些现象有了更深入的认识，并详细阐述了伪谱的定义。s 伪谱的定义至少由不同 的人独立提出了六次，他们是j m v a r a h ( 1 9 6 7 ) ，h l a n d a u ( 1 9 7 5 ) ，s i cg o d u n o v ( 1 9 8 2 ) ，l n t r e f e t i l e n ( 1 9 9 0 ) ，d h i 埘c l l s e n 和a j p r i t c h a r d ( 1 9 9 2 ) 及e b d a f i e s ( 1 9 9 7 ) 。特别是 l n t r e f e t l l e n ，他不仅提出了占伪谱的定义，并在前人的基础上扩展了这个想法，将伪谱应用 于大量科学家非常感兴趣的实际问题上。在他的积极推广下，自从上世纪九十年代，伪谱很快 地得到了普及。2 0 0 0 年左右，t gw r i g h t 2 2 , 2 3 1 设计了软件系统e i g t o o l ，这是一个计算和图形 化矩阵伪谱的快速、实用工具，可以计算1 0 阶到1 0 0 0 0 阶的不同规模矩阵的伪谱。 对一个正规矩阵，当h l = i i | l ：时，z 越接近彳的特征值，8 ( z ，1 彳) - 10 会等同地变大。伪 谱的重要性体现在远离正规的矩阵上，这种矩阵的预解式l i ( z ，一爿) - 10 可能会很大，甚至当z 远 离a 的谱时。 定义1 2 1 设a c “”，s 0 ，| i i l 是由向量范数诱导的矩阵范数，则a 的g 伪谱( 记 作人，( 彳) ) 由以下等价条件给出： ( i ) 人。( 彳) = z 6 c ：肛一彳) 。1 i i - 占。) ( i i ) 人。( 彳) = z c ：z 人( 彳+ e ) ，l l e l l - 【1 1 ) ： 若存在”c ”，0 u l l = 1 ，使l l ( d 一彳) “l l 占成立， 则存在一单位向量v c ”及；占，使( z ，一a ) u = 西。 由对偶范数理论可知，存在w c ”，满足0w l i = 1 ，w n “= l ， 所以， z u = a u + 删胃u = ( 彳+ ) ” 这意味着z 人( 彳+ e ) ，e = 甜且0 e 0 占。 ( i i ) j ( i ) ： 假如z 人( 彳+ e ) 且0 e 0 占， 则存在一单位向量“c ”，使 我们得到： 即得 大规模矩阵伪谱计算的数值方法 i ( z z - a ) 1 i i 占。 ( i ) j ( i v ) ： 如果i i 1 i 是2 范数，由一个逆矩阵的2 一范数是其最小奇异值的倒数，可立即得证。 显然，o - 伪谱人o ( 彳) 和伪谱a ( a ) 相同，而 a 。( 彳) ) 脚是一簇包含人( 彳) 的严格嵌套的有 界闭集。当彳是正规矩阵时，人。( 彳) 是以a 的特征值为中心的占- 闭球之并，即 人。( 彳) = ud ( 2 ，占) 2 c a ( a ) 其中，d ( 2 ，占) 表示以兄为中心占为半径的闭球。 当a 是正规矩阵时，对占 0 ，人。( 4 ) 是复平面上一个比谱集更大的集( 甚至占 1 的情 况也是如此) ，占一0 0 时，它会充满整个复平面。 上面的定义( i v ) 只给出了在2 范数下的矩阵伪谱，更常用的加权内积和范数的应用可以 在2 一范数的框架下讨论，即通过一个相似变换4hw aw 一，其中是一个非奇异矩阵。 由上可看出，和谱不同，伪谱依赖于范数的选取。乍看来，这种范数不变性的缺乏可能是 伪谱思想中的缺陷，这也在一定程度上解释了为什么有关非正规的理论的发展远远滞后于标准 谱理论的发展( 伪谱是分析中的一个思想，特征值属于代数范畴) 。然而，我们在实际中需要解 决的应用问题通常是范数独立的。例如，很多非正规算子通过一个指数加权内积可以转变成正 规的，但是这样的变换通常会扭曲如能量这样的物理概念，使得这些概念不能正确地认知。 到最小非正则多项式的距离 2 4 , 2 5 和剑最近非可控d 阶系统( 具有相同标准状态空间的系统) 的距剐2 6 1 可以利用矩阵多项式的伪谱求得，因此在诸如控制理论等的系统中，伪谱是研究矩阵 多项式的一个基础工具【3 1 。对于矩阵多项式伪谱的理论分析，l a n c a s t e r 和p s a r r a k o s 2 7 1 在2 0 0 5 年给出了矩阵多项式伪谱的界和连通分量的定量性质，并推导了一个矩阵多项式伪谱界的数字 定义的加速连续算法。2 0 0 8 年，l b o u l t o n ，e l a n c a s t e r 和e p s a r r a k o s t 2 8 1 给出了一个更加精确的 伪谱界，对矩阵多项式伪谱的理论分析起着非常重要的作用。 多项式特征值问题就是寻找( x ，旯) c ”c ，使得 p ( 旯) x = 0 其中p o ) - - 旯”4 ，l + a 雕。1 厶一l + + 4 ，4 c “”，k = o ，1 ，m 。 如果工o ，则称旯为特征值，x 为相应地特征向量ap 的特征值的集合表示为人( p ) 。当 4 ，l 非奇异时，p 称为正则的，并_ f f m n 个特征值。如果4 = 4 ，k = o ，1 ，m ，即尸( 兄) 的 所有系数都是h e r m i t i a n 矩阵，则称p ( a ) 是自伴随矩阵多项式。 多项式矩阵p ( a ) 的伪谱就是那些和p ( 力) 靠得很近的矩阵多项式的特征值的集合。假定 p 是正则的，令 p ( a ) = a ”4 ，l + a ”1 4 ，l l + + 以 4 i l 南京航窄航天人学硕上学位论文 其中4 c ”“。 定义1 2 2 t 2 9 1p 的s 伪谱定义为 人。( p ) = 旯c ：( p ( 旯) + 尸( 允) ) x = o ，3 xo ，其中色t 口。占，尼= o ，1 ，聊 其中非负参数，口2 ，a 。是扰动自由度的度量。通过设定略= 0 ，可以使馘= 0 ，因此保 证4 不扰动。 在上面的定义中，假定p ( a ) + p ( 力) 是正则的。 引理1 2 i 口明人；( p ) = 旯c ：o r u i n ( p ( 旯) ) 占p ( 1 兄i ) 由于p ( 允) + p ( a ) 的特征值对系数矩阵的元素是连续的，由上面的定理可知，占一伪谱的 界可以定义为 t 3 a 。( 尸( 允) ) = 旯c ：( p ( 旯) ) = e p ( 1 x ) ( 1 2 1 ) 其中扒。( p ( 旯) ) 连续依赖于占。 利用计算奇异值的有效算法，引理1 2 1 和( 1 2 1 ) 将成为估计矩阵多项式伪谱的重要工具。 事实上，t i s s e u r 和h i g h a m 2 9 通过在复平面网格中估计。( p ( a ) ) 得到了人。( p ( 旯) ) 的一个 图形表示；l a n c a s t e r p s a r r a k o s 2 7 1 给出了利用曲线追踪技术估计人。( p ( 五) ) 的方法。 下面给出矩阵多项式伪谱的另一种定义【3 1 。 由于矩阵多项式特征值问题p ( 旯) x = o 的表示方式不能表示无穷大特征值，这就给计算任 意多项式p 的伪谱带来了困难。对这个问题的一种比较好的解决方法是，将上面的问题重写为 如下的调和形式： p ( a ，) x = ( 倪4 + 口”- 1 厶一l + + ”4 ) x = 0 在这种情况下，一个特征值对应一对 ，夕) c 2 ，其中位，) ( o ，0 ) 。当m = 1 时，这种 表示就是数值的广义特征值问题p a x = a b x 。显然，0 时，五= 口，无穷犬特征值对 应= 0 的数值对。现在有两种方法来表示矩阵多项式的特征值( 或伪谱) ：数值对 ，) c 2 ， 或定义在扩展复平面c ：= cu o o 上的值旯。 令 , a e ( a ，) = 口“厶+ 口”1 础一l + + ”毛 定义1 2 3 t 3 1 对任意诱导矩阵范数，p 的占伪谱为 人。( p ) = ( 口，) c 2 ( o ，o ) ：( p ( 口，) + p ( 口，) ) 石= o ，9 x 0 ， 其中馘c ”，0 似i | 唯s ，k = o ：聊 其中心是非负参数，表示允许的扰动度量的自由度。例如，u - - 1 是绝对度量，u - - 1 1 馘1 i 是 相对度量。通过设定k = 0 ，可以使必= 0 ，因此保证4 不扰动。 气 i x 七 口 。脚 = 、i ， x ，j p 中其 大规模矩阵伪谱计算的数值方法 引理1 2 2 【3 1 纵p ) = k ) c 2 ( o o ) m 肛忙i n 。i ip ( 口，胁i l 训口i ，i e1 ) 占) 其中p ( x ，y ) 2 荟咋y ”。当人s ( p ) 有界时人s ( 一= 积c = ；m 刈i ：n 。i i p ( 旯h | j n 时，p 通常没有特征值。因为，如果名是p 的特征值，p 必须是秩亏损 的，这就要求定义p 的4 具有某种特殊的关系。通常来说，对充分小的s ，人。( p 1 是空集。 2 0 0 8 年，s a f i q u e 和a l a m i 3 0 1 总结之前有关矩阵多项式伪谱的工作，基于矩阵多形式谱扰动 的系统分析，开发了一种在矩阵多项式赋范线性空间上定义的广义框架。他们通过定义一族多 项式空间上的自然范数，证明了c 叶1 和c “”空间上的几何性质在三。fc 职”l 的矩阵多项式扰动 分析中起着关键作用。这篇文章给出了矩阵多项式伪谱的一个广义定义，已知的矩阵多项式伪 谱是这里所给定义的特殊情况，此外还证明了矩阵多项式的伪谱可以用和矩阵伪谱一样的方式 进行定义和分析。文中将矩阵伪谱形式 人。( a ) = ua ( a + 鲋) 推广到矩阵多项式情况，利用线性算子赋范空间的特征给出了矩阵多项式伪谱的很多性质。 1 3 矩阵伪谱计算的数值方法 伪谱计算的历史只有几十年。除去j d e m m e l ( 1 9 8 7 ) 的一个伪谱图，在1 9 9 0 年以前，伪 谱被认为是不能进行数值计算的。这种情况在上世纪9 0 年代得到了彻底改变，现在，伪谱计算 已经被应用于很多工程和分析领域。同科学计算的发展历史一样，伪谱也是随着硬件和算法的 发展而进步的。t r e f e t h e n 在1 9 9 9 年回顾了当时计算矩阵( 特别是稠密矩阵) 伪谱的最先进的 技术，并且给出了一个m a t l a b 代码【l3 1 。 由伪谱的等价定义( i v ) ，可以得到一个很显然的算法，即在复平面的一个网格上对每个网 格点z 计算o m i n ( z i a ) ，然后根据这些数据画出等高图。( 如果a 是h e r m i t i a n 矩阵，则其伪 谱图关于实轴对称，利用它的对称性可以节省一半的计算量) 。这个方法的计算量很大，对大型 问题的求解速度很慢，我们可以用多种方法对其进行加速，如粗网格法等。其它的加速方法包 括：避免计算复平面上我们不感兴趣的区域的奇异值，在这些区域上或者预解式的模很小或者 没有我们感兴趣的伪谱的界；投影到低维子空间，即将维数为n n 矩阵彳投影到一个维数为 栉 n 的不变子空间上，然后在这个子空间上求解伪谱；带有反迭代或l a f l c z o s 迭代的三角化， 即在计算奇异值之前，先做一个s c h u r 变换使矩阵么酉等价于一个上三角矩阵丁，对上三角矩 阵丁奇异值的计算可以用适用的反迭代或l a n c z o s 方法求解。这三种加速算法可以混合使用， 6 i 南京航空航天人学硕上学位论文 使得算法的计算速度更快。其他算法还有，伪谱的并行计算、全局k r y l o v 子空间迭代和局部 k r y l o v 子空间迭代等。 k r y l o v 子空间作为伪谱计算的一种有效方法，其很多主要思想可以分为两种类型：一种是 用一列k r y l o v 子空间来近似矩阵或算子的伪谱，另一种是对每个z 用k l y l o v 子空间逐点加速 其预解式范数的计算。我们可以认为矩阵伪谱的估计图像是所有大型k r y l o v 子空间计算的一个 常规副产品，由k x y l o v 子空间迭代产生的h e s s e n b e r g 矩阵通常是很小的，因此这种算法的计算 量很小。但是如果需要伪谱的精确图像，那么在多数情况下需要寻找新的算法。 t o h 和t r e f e t h e n 1 4 1 在1 9 9 6 年讨论了用a r n o l d i 迭代及其变形计算伪谱的算法。如果矩阵是 稀疏的微分算子的近似，那么使用合理的a r n o l d i 算法的变形计算的效果会很好。如果矩阵是 稠密的，那么加入加速方法会有一定作用，而且通过对矩阵彳进行简单的特征值分解，然后将 其投影剑一个与特征子空间相关的不变子空间的方法也会有出乎意料的效果。a m o l d i 迭代算法 与所有由于矩阵彳太大而不能直接处理的问题有潜在的关系，有理由相信矩阵伪谱的必要性质 会通过低维数投影方法被发掘。同一年，b r a c o n n i e r 和h i g h a m 1 6 提出了一种基于l a n c z o s 方法 的算法，这个算法含有选择重正交化过程和c h e b y s h e v 加速技术；当与连续和转移与转化技术 联合使用时，这个算法可以有效、可靠地计算大型矩阵的值域和伪谱。 1 9 9 8 年，g o d u n o v 和s a d k a i l e 【1 8 1 讨论了一种分析矩阵伪谱的新技术，并在此基础上给出一 种计算矩阵伪谱的新方法。这个方法有两个主要步骤：第一步基于一种预处理技术，这个过程 可以用一种可靠的方法选择一些预解式( p r e - p r o c e s s i n gt a s k ) 比较人的区域，这个步骤还在继 续完善中，而且可以很容易地对其并行化；第二步是利用每个区域的特征值求解谱投影，进而 计算它们的不变子空间。谱投影器的计算利用的是谱二分技术( s p e c t r a ld i c h o t o m yt e c h n i q u e s ) 的最新成果，并假定感兴趣的区域可以被一个圆、椭圆或多边曲线包围( e n c l o s e d ) 。 由于伪谱提供了在摄动下特征值敏感度的重要信息，近几年，人们广泛地研究了与标准的 和广义的特征值问题相关的伪谱，特别是大型稀疏或结构矩阵的计算得到了长足的进步。对于 这些矩阵伪谱的求解，a m o l d i 、j a c o b i d a v i d s o n 和有理k r y l o v 迭代有着很明显的优势。下面简 要介绍一些计算矩阵伪谱的算法。 反迭代法 基于网格的基本算法很简单但是效率很低。它需要计算z ，一彳的所有奇异值，最简单的改 进是只计算最小奇异值。 因为 am(zi一彳)：smalleste i g e n v a l u eof(zi-a)*(zi-a) - s m a l l e s tp o s i t i v ee i g 饥1 u e o f lj 0 0z o a i l l 7 大规模矩阵伪谱计算的数值方法 因此，最小奇异值可以通过用迭代法求解h e r m i t i a n 特征值问题来计算，很多算法都可以做 到这一点。当彳是大型且稀疏矩阵时，其中的一些算法有很好的效果，就算4 是稠密矩阵，利 用一些简单的迭代法同样可以用较快的速度得到结果。 令b = z ，一彳。最简单的方法是用反迭代法计算b b 的最小特征值，即在( b b 1 上应用 幂方法，b b 的最小特征值对应( b + b ) 的最大特征值。反迭代法的收敛速度取决于b 的两个 最小奇异值之间的分离程度。此外，反迭代法需要计算b - 1 和口_ 1 的乘积，这要求计算曰的l u 分解。z ，一彳在每一个网格点上的l u 分解是这个算法最主要的瓶颈：在每个网格点上需要的 运算量是o ( n 3 ) ，这和计算全部奇异值的渐进复杂度是一样的。因此，在一个有m 2 个点的网 格上，反迭代法总的复杂度就是o lm 2 n 3l 。 预先三角化算法 每个方矩阵彳都有一个s c h u r 分解，即，4 可以通过一个酉相似变换简化为三角形式 彳= 唧 其中t 是一个上三角矩阵。由于酉相似变换并不改变矩阵的2 一范数伪谱，人。( t ) = a 。( a ) 。 这样，我们就可以更有效地使用反迭代法：在每个网格点上z ，一丁已经是三角形式了，因此不 再需要进行叫分解。s c h u r 分解只需要计算一次，其复杂度为0 fn 3l ，而在每个网格点上， 三角系统只需要o ( n 2 ) 次运算就可以得到其最小奇异值，因此总的复杂度为o ( n 3 + 刀2 m 2 ) 。 同时，由于反迭代法通常在几步迭代后就会收敛，这个改进在实际应用中是很明显的。 将彳简化为三角形式是稠密矩阵伪谱计算的基础： 1 将4 简化为三角形式t ( s c h u r 分解) 2 在网格上的z 点迭代计算q 响( z ，一彳) l a n c z o s 迭代 我们可以通过采用更复杂的迭代方法计算最小奇异值来提高算法的计算速度。一个很自然 的选择就是l a n c z o s 方法，也就是在( 矿b ) 上应用a m o l d i 迭代。由于口b 是h e r m i t i a n 矩阵， 这个过程只需三项递推就可以实现。在标准网格点上，逆l a n c z o s 迭代很快就可以收敛到可接 受的精度( 也就是说，5 步或更少的迭代步) 。这个算法并不能改进反迭代法的渐进复杂度( 同 样需要o ( n 3 + 刀2 m 21 次运算) ，但是这个改进仍然是值得的。 网格选取 一个算法怎样自动决定在哪个区域计算人。( a ) ? b r a c o n n i c r 等建议利用数值域( 彳) 来建 立网格的外部边界，占伪谱与形( 彳) 的距离不会超过s 。但是，数值域通常大于我们感兴趣的 伪谱区域。因此，当没有一个好的办法时，我们建议从s c h u r 分解得到的特征值中推导网格的 边界，e i g t o o l 就是通过粗略地将谱的广度扩大两倍米得到默认的网格区域。 如果在计算之前已经知道感兴趣的最大的占的值，我们有很多不同的策略可以很快地将落 8 南京航空航天大学硕上学位论文 在需要的伪谱之外的那些点从计算域排除出去。对小型矩阵，计算后调整s 的技巧( 用e i g t o o l 的图形界面很容易做到) 通常要比上面的排除法的效果要好。对规模很大的问题，计算它的每 个奇异值是很困难的，可以证明，在这种情况下使用排除法是很重要的。 并行计算 网格算法在并行化方面是很有利的：它可以很容易地利用多处理器进行计算。对伪谱算法 来说，s c h u r 分解执行之后，各个网格点上的计算就是相互独立的了。因此，这些计算量可以 分配在不同的处理器上，在分配的过程中需要考虑尽量减少处理机间的通信量。为了最小化通 讯量，可以为每个处理器分配计算域中的一列，即通过为每个处理器分配相邻的计算区域来减 少通讯量。对大规模的矩阵，将矩阵本身分解剑众多的处理机上，并使所有的处理器同时计算 一个区域可能更加必要。 朴素的伪谱 上面的算法都是基于伪谱等价定义( i v ) 的。下面的等价定义( i i ) 是基于扰动特征值的 人。( a ) = 。ua ( a + e ) 上面的等式同样表示了一种计算伪谱的算法：选取随机矩阵e ，使其满足0 e 0 = 占，然后绘 制人( 4 + e ) 的叠加图。人a - t - e ) 的计算可以利用标准的稠密矩阵的特征值算法。计算的结 果就是“朴素的伪谱”，一个围绕着谱的特征值云团，它的密度取决于选取的扰动矩阵的数量和 随机扰动矩阵的分布特性。为了改善计算效率，我们可以将e 的秩限制为l 。如果e 是一个满 秩随机矩阵，那么正规化这个矩阵( 使得0 e 0 s ) 的计算量是o ( 咒3 ) ，而构造和正规化秩i 矩阵的计算量是o ( 甩2l ( 当然，这些秩1 矩阵和具有独立随机元素的矩阵有不同的统计特性) 。 这个方法有一个缺点，即对不同的占的需要重新绘制“朴素的伪谱”，而且只提供a 。( 彳) 的 下界。但是，它可以用较少的计算量给出伪谱的近似。随着更高效的基于网格的伪谱算法的提 出，“朴素的伪谱”的这个优点将变得不那么明显。 其他范数下的伪谱 上面的算法假定伪谱是定义在标准e u c l i d e a n 范数下的，可以将上面的分析技巧应用于由其 他内积定义的范数伪谱上。任意有限维内积可以写成( 五y ) ，= y r l x ，其中l 是可逆矩阵。 肛一么) 一虬 m a x j e c 4