（计算数学专业论文）求解某些特殊稀疏线性系统的数值解法.pdf

中文摘要 摘要 大型稀疏线性系统来源于很多应用领域，譬如流体动力学，结构分析，电磁场 计算等等将描述自然现象的偏微分方程离散后，通常就会得到一个稀疏的线性 系统这样一来，实时高效的求解大型的稀疏线性系统对整个应用问题的解决有 着至关重要的作用因此，近年来无论国内还是国外，大规模稀疏线性系统的求解 算法的研究已成为大规模科学与工程计算的一个重要研究领域进一步，由于许 多实际问题产生的大规模稀疏线性系统，其系数矩阵往往都是具有某种特殊形式 或者某种特殊结构，因此本文主要研究的是一些特殊形式的稀疏线性系统快速、 有效的数值求解方法全文共分为五章 第一章介绍了大规模稀疏线性系统问题的来源、历史、发展现状以及本文所 涉及的几种特殊稀疏线性系统 在第二章，我们给出了求解大规模稀疏位移线性系统的一种增广的重新启动 g m r e s 方法：每次重新启动时，将母系统所得到的多个误差向量添加到求解的 k r y l o v 子空间中去，在新的增广的空间中求解母系统，而子系统的解通过强行使 其残量和母系统的残量平行得到这样不仅能使我们在同一个空间中求解子母系 统，还能加速求解位移线性系统重新启动g m r e s 方法的收敛速度，数值试验也 表明这种方法的高效性 第三章针对块三对角系统，给出了一种切频率过滤预条件子的变形新的预 条件子是建立在块三对角矩阵的一种组合分解基础上，并满足特定的过滤性质得 到的，新的预条件子有着天然的并行性我们简单分析了新的预条件子的一些性 质，在实际运用中，我们将所得的新的预条件子与传统的i l u ( o ) 按照某种乘法 的形式结合起来使用数值试验详细比较了这种新的预条件子与传统的预条件子 的数值效果，给出了这种预条件子的优势和缺陷 第四章我们给出了对于求解s y l v e s t e r 方程的一种预条件的梯度迭代方法，预 条件通过合理的选择两个辅助矩阵实现这一想法可以看做为一般化线性系统的 分裂迭代到s y l v e s t e r 方程中来我们在数值试验中比较了这种迭代格式和原始 的迭代法，结果表明预条件的梯度迭代法在求解s y l v e s t e r 方程时收敛得要更快， 另外我们也通过试验数值上分析了步长参数对于算法收敛的影响 中文摘要 i i 在第五章，我们提出并且分析了对于一般鞍点问题的一种预条件子，这种预 条件子是建立矩阵分裂和最近提出的一种双参数的分裂迭代技术 z zb a ia n d g h g o l u b ，i m aj n u m e r a n a l ，2 7 ，( 2 0 0 7 ) ，p p 1 2 3 】基础上的我们详细分析 了预条件后矩阵谱的性质，并且通过数值试验验证了我们的理论和这种预条件子 的效率 关键词：k r y l o v 子空间方法；位移线性系统；块三对角矩阵；s y l v e s t e r 方程； 鞍点问题 英文摘要 a b s t r a c t 1 1 1 l a r g es c a l es p a r s el i n e a rs y s t e m sa r i s ei nm a n ya r e a ，s u c ha sf l u i dd y n a m i c s ， s t r u c t u r a la n a l y s i s ，n u m e r i c a lc a l c u l a t i o no fe l e c t r o m a g n e t i cf i e l d s ，a n ds oo n w h e nd i s c r e t i n gt h ep d e sw h i c hd e s c r i b et h ep h e n o m e n a ，w eg e n e r a l l yo b t a i n s p a r s el i n e a rs y s t e m s t h e r e f o r e ，s o l v i n gt h e s es y s t e m se f f i c i e n t l yi so fv i t a l i m p o r t a n c ef o rs o l v i n gt h ew h o l ep r o b l e m s o ，s t u d yo nt h en u m e r i c a lm e t h o d sf o r s o l v i n gl a r g es p a r s el i n e a rs y s t e m si sa ni m p o r t a n tf i e l di nl a r g es c a l es c i e n t i f i ca n d e n g i n e e r i n gc o m p u t a t i o n f u r t h e r m o r e ，m a n yl a r g es c a l el i n e a rs y s t e m sa r i s i n g i np r a c t i c a lp r o b l e m sa r eo f t e no fs o m es p e c i a lf o r m so rp a r t i c u l a rs t r u c t u r e s ， t h e r e f o r e ，t h i st h e s i si n v e s t i g a t e st h ef a s ta n de f f i c i e n t l yn u m e r i c a lm e t h o df o r s o l v i n gs o m es p e c i a ll i n e a rs y s t e m s ，t h et e x ti sd i v i d e di n t of i v ec h a p t e r s c h a p t e r1g i v e sa ni n t r o d u c t i o no ft h eo r i g i n ，h i s t o r y , s t a t eo fi t e r a t i v em e t h - o d sf o rs o l v i n gl a r g es p a r s el i n e a rs y s t e mo fe q u a t i o n s a n dw ea l s ob r i e f l yi n t r o - d u c et h es p e c i a ll i n e a rs y s t e m sw h i c hw e r es t u d i e di nt h i sp a p e r i nc h a p t e r2 ，an o v e lr e s t a r t e dg m r e sm e t h o df o rs o l v i n gl a r g e s p a r s e s h i f t e dl i n e a rs y s t e m si sd e v e l o p e d r e s t a r t i n gi sc a r r i e do u tb ya u g m e n t i n g t h ek r y l o vs u b s p a c e sw i t hs o m ee r r o ra p p r o x i m a t i o n sg e n e r a t e db yt h es e e d s y s t e m ，w ef i r s t l ys e e kt h es o l u t i o no ft h es e e ds y s t e mi nt h ea u g m e n t e dk r y l o v s u b s p a c e sa n da c q u i r et h es o l u t i o n so fa d ds y s t e m sb ym a k i n gt h er e s i d u a lv e c t o r s p a r a l l e lt ot h er e s i d u a lv e c t o ro fs e e ds y s t e m t h en e wm e t h o dp r e s e r v e st h en i c e p r o p e r t yt h a ta l l o w ss o l v i n gt h es e e da n da d ds y s t e m si no n es u b s p a c e a n di t a l s oe f f e c t i v e l ya c c e l e r a t e st h ec o n v e r g e n c eo ft h er e s t a r t e dgm r e sm e t h o df o r s o l v i n gt h es h i f t e dl i n e a rs y s t e m s n u m e r i c a le x p e r i m e n t si n d i c a t e st h ee f f i c i e n c y o ft h en e wm e t h o d i nc h a p t e r3 ，w ec o n s i d e r st h eb l o c k t r i d i a g o n a ll i n e a rs y s t e mo fe q u a t i o n s ， av a r i a n to ft a n g e n t i a lf i l t e r i n gp r e c o n d i t i o n e r si sp r o p o s e d t h en e wv a r i a n ti s b a s e do nat w i s t e dn o & f a c t o r i z a t i o na l o n gw i t hc e r t a i nf i l t e r i n gp r o p e r t y i n t h ep r a c t i c a la p p l i c a t i o n ，ac l a s so fc o m p o s i t ep r e c o n d i t i o n e r sa r et e s t e d ，w h i c h a r ec o n s t r u c t e db yc o m b i n i n gt h et w i s t e dt a n g e n t i a lf i l t e r i n gd e c o m p o s i t i o np r e - c o n d i t i o n e rw i t ht h ec l a s s i c a li l u ( o ) p r e c o n d i t i o n e ri nam u l t i p l i c a t i v ew a y t h e 英文摘要 l v p e r f o r m a n c eo ft h en e wp r e c o n d i t i o n e r sa r ec o m p a r e dw i t ho t h e rc l a s s i c a lp r e c o n d i t i o n e r s ，t h es u p e r i o r i t ya n dt h ew e a k n e s so ft h ep r e c o n d i t i o n e r sa r ep r o p o s e d i nc h a p t e r4 ，w ei l l u s t r a t et h ep r e c o n d i t i o n e dg r a d i e n tb a s e di t e r a t i v em e t h o d w h i c hc a nb ed e r i v e db yr e a s o n a b l ec h o i c eo ft w o a u x i l i a r ym a t r i c e s t h es t r a t e g y i san a t u r a lg e n e r a l i z a t i o no ft h es p l i t t i n gi t e r a t i o nm e t h o d sf o rl i n e a rs y s t e m s o fe q u a t i o n s t h ep e r f o r m a n c eo ft h ep r e c o n d i t i o n e dg r a d i e n tb a s e di t e r a t i v e m e t h o di sc o m p a r e dw i t ht h eo r i g i n a lm e t h o do ns e v e r a ln u m e r i c a le x a m p l e s a b e t t e rc o n v e r g e n c eb e h a v i o ri sr e v e a l e d ，a n dt h ei n f l u e n c eo fa ns t e p - s i z ep a r a m e t e ri se x p e r i m e n t a l l ys t u d i e d i nt h el a s tc h a p t e r ，w ep r o p o s eap r e c o n d i t i o n e rf o rac l a s so ft h eg e n e r a l i z e d s a d d l ep o i n tp r o b l e m s t h ep r e c o n d i t i o n e ri sb a s e do nm a t r i xs p l i t t i n g ，a n da n e wp r o p o s e dt w op a r a m e t e r ss p l i t t i n gi t e r a t i o nt e c h n i q u e z zb a ia n dg h g o l u b ，i m aj n u m e r a n a l ，2 7 ，( 2 0 0 7 ) ，p p 1 2 a t h es p e c t r a lp r o p e r t i e so ft h e p r e c o n d i t i o n e dm a t r i xa r ed i s c u s s e di nd e t a i l n u m e r i c a le x p e r i m e n t sa r eg i v e n t os h o wt h ec o n c l u s i o na n dt h ee f f i c i e n c yo ft h ep r e c o n d t i o n e r 厦门大学学位论文原创性声明 本人呈交的学位论文是本人在导师指导下，独立完成的研 究成果。本人在论文写作中参考其他个人或集体已经发表的研 究成果，均在文中以适当方式明确标明，并符合法律规范和厦 - j 大学研究生学术活动规范( 试行) 。 另外，该学位论文为() 课题( 组) 的研究成 果，获得() 课题( 组) 经费或实验室的资助，在 ( ) 实验室完成。( 请在以上括号内填写课题或 课题组负责人或实验室名称，未有此项声明内容的，可以不作 特别声明。) 声明人( 签名) ：毒垮畛 1 年6 月日 厦门大学学位论文著作权使用声明 本人同意厦门大学根据中华人民共和国学位条例暂行实 施办法等规定保留和使用此学位论文，并向主管部门或其指 定机构送交学位论文( 包括纸质版和电子版) ，允许学位论文进 入厦门大学图书馆及其数据库被查阅、借阅。本人同意厦门大 学将学位论文加入全国博士、硕士学位论文共建单位数据库进 行检索，将学位论文的标题和摘要汇编出版，采用影印、缩印 或者其它方式合理复制学位论文。 本学位论文属于： ( ) 1 经厦门大学保密委员会审查核定的保密学位论文， 于年月日解密，解密后适用上述授权。 () 2 不保密，适用上述授权。 ( 请在以上相应括号内打 ”或填上相应内容。保密学位 论文应是已经厦门大学保密委员会审定过的学位论文，未经厦 i 、- j 大学保密委员会审定的学位论文均为公开学位论文。此声明 栏不填写的，默认为公开学位论文，均适用上述授权。) 声明人( 签名) ： 1 年6 月- 王净哮 日 绪论 第一章绪论 1 1 线性系统的研究背景与现状 众所周知，很多实际问题都是通过偏微分方程来描述的，离散这些偏微分方 程往往会得到下面的稀疏线性系统 a x = b 为了对产生这些问题的现象进行模拟，不可避免的就需要求解上面的稀疏线 性系统一般来说离散化的精度越高，模拟的效果就会越好，但是同时所得到系统 的规模就越大，从而就使大部分的时间花费在对线性系统的求解上例如地下水 道模拟领域，所涉及的线性系统求解时间占到总的模拟时间的8 0 p 因此大规 模稀疏线性系统的求解问题成了模拟问题的核心，如何有效快速的求解大规模稀 疏线性系统成为科学工程计算的一个热门，国内外研究都非常的活跃 一般来说，线性系统的求解方法分为两大类，即直接法和迭代法 直接法是利用高斯消去过程对系数矩阵a 进行l u 分解 2 ，将原系统转化 为两个相对简单的三角系统来求解，即 a = l u l y = b ，u x = y 。 其中l 为下三角阵，u 为上三角阵如果系数矩阵的阶数为r t ，那么上面所描述 的直接法所需要的的运算量和存储量为0 ( 1 2 3 ) ，所以对于一般的大规模稀疏线性 系统，直接法是不适用的，但是也不是说直接法就失去了用武之地，现代实用的直 接法可以利用系数矩阵的稀疏结构以及计算机的等级存储结构来对高斯消去过 程优化，从而避免某些零元的存储和运算，并且直接法还是一种相对来说比较健 壮的算法，所以在许多结构分析以及电路网络模拟领域，直接法仍然发挥着不可 替代的作用目前关于直接法有很多流行的软件包，譬如i s d u f f 等人开发的一 系列代码【3 ，4 ，x i a o y el i 和j d e m m e l 等人开发的s u p e r l u 5 等关于直接法 软件包总结可以参考f 6 】虽然这些基于直接法的软件包优化了高斯消去过程所 需要的存储量和运算量，但是对高维复杂问题离散所产生的超大规模的稀疏线性 系统，采用直接法求解就会对现行计算机硬件提出挑战，往往会造成内存不足的 问题一般来说，对于大规模稀疏线性系统，首选的是迭代法 绪论 2 迭代法的发展来已经经历了快2 0 0 年的历史，其发展经历了几个阶段从g a u s s - s e i d e l 算法到松弛类型迭代法，从r i c h a r d s o n 算法到c h e b y s h e v 半迭代格式，从 c g 到现在流行的k r y l o v 子空间类型算法， 尽管早在1 9 5 0 年初就已经提出了l a n c z o s 算法 7 ，a r n o l d i 算法【8 以及 c g 9 1 等k r y l o v 子空间算法，但是，k r y l o v 子空间算法真正得到认可并且快速发 展是从1 9 7 0 开始的，其中j k r e i d 在1 9 7 1 年的工作 1 0 起到了推动性的作 用在那篇文章中，作者注意到如果系数矩阵的条件数不是太大的情况下，c g 算 法能够在远小于n 步内达到收敛因此，2 0 年后人们再次考虑c g 以及其他类型 的k r y l o v 子空间算法伴随着预条件的深入研究，根据系数矩阵不同的性质人 们逐步提出了m r ，c g rb i c g ，b i c g s t a b l e ，c g s ，b i c g s t a b l e ( 1 ) ，g m r e s ， g m r e s e ，g m r e s d ，i d r 等等不同的算法，这些算法都极大的丰富了k r y l o v 子空间算法的内容预条件技术的发展使k r y l o v 子空间方法更加完善，特别是j a m e i j e r i n k 和h a v a nd e rv o r s t 11 1 等人不完全分解预条件子方面的工作极 大的推动了k r y l o v 子空间迭代算法的发展 值得一提的是目前将求解线性系统的方法严格分为直接法和迭代法已经不 准确，对大规模问题来说，往往会将这两类方法结合起来使用，最典型的例子就是 系数矩阵的不完全分解可以作为迭代法的预条件子另外，在s u p e r l u 软件包中， 在得到的近似解精度不够的情况下，也会采用几步迭代来修正近似解此外，许多 直接法的策略可以用来为迭代算法构造预条件子因此很多学者都研究如何将直 接法和迭代法结合起来构造多水平的求解算法下面我们就简单介绍下本文所涉 及的几种特殊形式的稀疏线性系统 1 2 位移线性系统 记a 为一n 阶非奇异方阵，实数q 为位移，其中q 使a + q 也为非奇异 的，我们考虑下面的线性系统 a x = b ，( 1 2 ) 和 a x = b ，( 1 3 ) 其中a = a + a i ，q 为某些指定的参数我们把( 1 2 ) ( 1 3 ) 统称为位移线性系统 其中( 1 2 ) 为母系统，a 为母矩阵，系统( 1 3 ) 为子系统( 或者附加系统) ，a 为子 矩阵位移线性系统问题来源于科学计算的很多领域，譬如q c d 问题 1 2 ，1 3 】， 绪论 3 用t i k h o n o v - p h i l l i p s 正则化来求解病态最小二乘问题 1 4 】也会产生这样的线性 系统，另外在控制理论 1 5 和偏微分方程数值求解 1 6 都会产生这样的问题 k r y l o v 子空间方法在求解位移线性系统时有着天然的优势，因为对于同一初 始向量r ，母矩阵a 和子矩阵a 产生了相同的k r y l o v 子空间，也就是说 j i c m ( a ，r ) = 瓦m ( a ，r ) = s p a n r ，a r ，a m 一1 r 一般来说可以把求解位移线性系统k r y l o v 子空间方法分为两大类，一类是 基于短递推关系式而另外是基于长递推关系式 基于短递推k r y l o v 子空间方法不需要重新启动，所以此类k r y l o v 子空间方 法在求解位移线性系统时显得非常有吸引力这一类型的方法近年来被人广泛研 究，例如当系数矩阵式对称正定时，j v a nd e re s h o f 和gl g s l e i g p e n 提出了 一种c g 类型的方法 17 很好的解决了这类位移线性系统，而当系数矩阵对称不 定的时候，r f r e u n d ，g g o l u b ，和n n a c h t i g a l 给出了t f q m r 【1 8 】算法，a f r o m m e r 给出了b i c g s t a bf 1 9 算法 对于基于长递推关系式的k r y l o v 子空间迭代方法，例如g m r e sf 2 0 ，由于 建立新的基向量一般都会涉及到前面所有的基向量，所以必须存储所有的基向量， 这样就工作量和存储量就会随着迭代的步数增加为了降低计算量和存储量，特 别对大规模问题，重新启动是必须的但是对于位移线性系统来说，重新启动会带 来新的困难，因为重新启动后母系统和子系统所对应的k r y l o v 子空间有可能不再 相同只有当每次重新启动的子母系统的初始向量都是平行的时候，子母系统才 能在同一个子空间中求解，从而提高计算效率当用f o m ( f u l l0 r t h o g o n a l i z a t i o n m e t h o d ) 2 1 】来求解位移线性系统时，v s i m o n c i n i 2 2 】发现子母系统的残向量 都是平行的，因此把当前的残量作为下一次重新启动的初始向量是非常自然和 有效的原始的重新启动g m r e s 方法在求解位移线性系统时是不效率的，因为 g m r e s 方法是把当前产生的残量作为下一次重新启动的初始向量，对于子母系 统来说，新产生的k r y l o v 子空间不再是同一个子空间为了克服这一困难也就 是为了保证子母系统产生残量的共线，从而使子母系统重新启动后的k r y l o v 子 空间保持一致，f r o m m e r 和g l g s s n e r 2 3 给出了一种g m r e s 方法的变形，记 为s g m r e s ，首先建立母系统的k r y l o v 子空间并对其求解，而子系统的解是通 过强行的使子系统产生的残量和母系统的残量平行所得到当a 正实，q 0 时， f r o m m e r 和g l g s s n e r 证明了他们的所提出的s g m r e s 2 3 1 方法对于子系统和母 系统都是收敛的 s g m r e s 方法尽量能够使子母系统所对应的残向量都平行，但是由于重新 启动，收敛速度变得缓慢，受到求解线性系统的增广压缩重新启动g m r e s e ， 绪论 4 g m r e s d r 2 4 ，2 5 技术的启发，对于位移线性系统，g g u 【2 6 提出一种重新 启动g m r e s 方法的变形，每次重新启动时，把调和r i t z 向量添加到求解空间里 去r b m o r g a nf 2 7 】也对g m r e s d r 变形使之能够适用于位移线性系统，特 别是q c d 问题当已经得知了矩阵小特征值所对应的近似特征向量时，这样的 策略是行之有效的不得不指出的是，当所涉及的矩阵是高度非正规 2 8 ，2 9 ，或 者系数矩阵没有和0 相对接近的特征值时，又或者求解系数矩阵的特征问题代价 很高的时候【2 4 】，这样的策略是不可取的 1 3s y l v e s t e r 方程 把形如 a x + x b = c ， ( 1 4 ) 的矩阵方程成为s y l v e s t e r 方程，其中其中a 冗m x m ，b 佗似n ，x 冗m 加，特 别的当m = 佗，b = a t ，c = c t ，方程( 1 4 ) 称为l y a p u n o v 方程 记x = ( x 1 ，x n ) ，c = ( c 1 ，c 2 ，c n ) ，v e c ( x ) = ( z ，z ；，z ：) ? ， v e c ( c ) = ( 膏，西，c ：) 丁，那么s y l v e s t e r 方程( 1 4 ) 等价于下面的线性方程组 v e c ( x ) = v e c ( c ) ，( 1 5 ) 其中= 厶oa + b tok 7 妒似，这里o 表示k r o n e c k e r 积上述把矩阵 方程转化为线性方程组的过程我们称为线性化，从方程( 1 5 ) 易知，当 入( a ) n 入( b ) = d 时，s y l v e s t e r 方程( 1 4 ) 有唯一解一般来说线性化过程只存在理论价值，因为它 把原问题的规模扩大了很多倍，实际上求解s y l v e s t e r 方程时，都不采用这样的策 略 当问题的规模比较小时，我们可以选择很多直接法来求解上述矩阵方程，譬 如b a r t e l s - s t e w a r t 方法3 2 ，h e s s e n b e r g - s c h u r 方法 3 3 ，3 4 】，这一类方法的主要 思想是将原系统转化为一个特殊的可以用向前或者向后替代来求解的线性系统 迭代法在求解线性系统的最有效的手段之一，近年来，对于s y l v e s t e r 方程， 一些行之有效的迭代法也逐渐被提出来，见文献 3 5 ，3 6 ，3 7 ，3 8 最近f d i n g 和 t w c h e n 3 9 ，4 0 ，4 1 对成对的矩阵方程以及一般的矩阵方程组讨论了梯度迭 代方法对于s y l v e s t e r 方程( 1 4 ) ，梯度迭代方法采用分级识别来求解方程的近 似解，同时【3 9 ，4 0 ，4 1 】也分析了此方法的收敛条件，在某些假设条件下，这种方 法是收敛的 绪论 1 4 鞍点问题 考虑下面的2 2 块的稀疏线性方程组 ( 岛a - b c f ) ( z y ) = ( 三) ， 5 o ra u = ， ( 1 6 ) 其中a 冗似n ，b 1 ，b 2 矽加，一c r m m ，并且凡m ，规定a 0 ，b 1 0 ， b 2 0 如果线性系统( 1 6 ) 系数矩阵中的块a ，b l ，b 2 ，c 满足下面一个或者多 个条件，我们称之为鞍点问题 a 1 a 对称：a = a t a 2 a 的对称部分h = ；( a + a t ) 是对称正定的 a 3 b 1 = b 2 a 4 c 是对称半定的 a 5 c = 0 鞍点问题来自科学和工程中的很多领域，譬如约束最优化，计算流体力学，电 冶金学等等，参照文献 4 2 鞍点问题的求解方法分为两大类，分别是s e g r e g a t e d 方法和c o u p l e d 方法，顾名思义，s e g r e g a t e d 方法就是分开的求解未知量z 和 y ，一般来说先求z 再求y 这类方法包括s c h u rc o m p l e m e n tr e d u c t i o n 4 3 ，n u l l s p a c e 方法 4 4 ，u z a w a - t y p e 方法等等 4 5 ，4 6 ，47 而c o u p l e d 方法是把z ，y 当 做一个整体来求解，这一类方法包括k r y l o v 子空间方法，定点迭代方法等等，参 见文献f 4 2 1 因为4 通常是大规模并且稀疏的，所以用上述方法求解鞍点问题的收敛速 度可能相当缓慢在大多数情况下，预条件子的作用往往比所采用的迭代方法重 要近些年来，在寻找高效的预条件子很多学者做了大量的工作，并且给出了许 多行之有效的预条件子，例如块对角( 块三对角) 预条件子 4 8 ，4 9 ，5 0 ，约束预条 件子【5 1 ，5 2 】，以及其他一些预条件技术b e n z i 和g o l u b 根据白中治所给的h s s 迭代 5 3 提出了一种h s s 预条件子 5 4 ，对于一般的鞍点问题，当采用h s s 预条 件技术来求解时，文献 5 4 ，55 详细分析了预条件后矩阵谱的性质根据文献 5 6 】 所提出的一种新的分裂，p a n 详细分析了由此得到的预条件子 本文主要工作就是针对上述几种特殊的稀疏线性系统，分别研究了其求解 的快速有效的数值算法在第二章我们给出了一种新的添加误差向量重新启动 g m r e s 方法来求解线性位移系统，第三章针对系数矩阵是块三对角形式时，提 出并且简单分析了一种组合的切频率过滤预条件子，通过数值试验描述了了这种 绪论 6 预条件子的可行性在第四章我们给出了求解s y l v e s t e r 方程的一种预条件的梯 度迭代算法，分析了算法收敛性，数值试验表明新的算法比梯度迭代算法要收敛 的快，并且我们通过数值试验描述了步长参数对算法的影响在第五章? 针对鞍点 问题，根据一种分裂迭代格式，我们给出了一种分裂迭代预条件子，分析了预条件 后矩阵谱在参数变化时的聚集性质，通过数值试验验证我们的理论 1 5 本文的一些记号 下面给出本文出现的一些记号 亿m 跏( c m x n ) ，表示仇行礼列实( 复) 矩阵的全体 冗n ( 伊) ，所有实( 复) 扎维列向量的全体 瓦m ( a ，v ) = s p a n v ，a v ，a m 。可) ，表示由4 和r 生成的m 维k r y l o v 子空间 a ( a t ) ，表示矩阵么的共轭转置( 转置) a 一，表示a 的逆矩阵 厶，表示n 阶单位矩阵 e i ，表示n 阶单位矩阵的第i 列 ”ii ，表示欧几里得向量范数以及从属的矩阵范数 忪，表示向量z 的a 范数，当a 对称正定时候为 z + a z p ( a ) ，表示矩阵a 的谱半径 q ，表示矩阵的k r o n e c k e r 乘积此外为了方便，本人了还采用了一些m a t l a b 中 的记号 解位移线性系统的一类添加近似误差的重新启动g m r e s 算法 7 第二章解位移线性系统的一类添加近似误差的重新启动 g m r e s 算法 2 1 引言 考虑下面的线性位移系统 a x = b ， ( 2 1 ) 和 a x = b ， ( 2 。2 ) k r y l o v 子空间方法在求解位移线性系统时有着天然的优势，因为对于同一 初始向量r ，母矩阵4 和子矩阵a 产生相同的k r y t o v 子空间，也就是说 瓦m ( a ，r ) = 瓦m ( a ，r ) = s p a n r ，a r ，a m 一1 r ) 因为基于短递推k r y l o v 子空间方法不需要重新启动，所以此类k r y l o v 子空间方 法在求解位移线性系统时显得非常有吸引力在同一个k r y l o v 子空间中，母系统 和子系统能够同时被求解这一类型的方法近年来被人广泛研究，例如当系数矩 阵对称正定时，j v a nd e re s h o f 和gl g s l e i g p e n 提出了一种c g 类型的方法 17 】很好的解决了这类位移线性系统，而当系数矩阵对称不定时，r f r e u n d ，g g o l u b ，和n n a c h t i g a l 给出了t f q m r 1 8 】算法，a f r o m m e r 给出了b i c g s t a b 【1 9 算法 对于基于长递推关系式的k r y l o v 子空间迭代方法，例如g m r e s 2 0 ，由于 建立新的基向量一般都会涉及到前面所有的基向量，所以必须存储所有的基向量， 这样工作量和存储量就会随着迭代的步数增加为了降低计算量和存储量，特别 对大规模问题，重新启动是必须的但是对于位移线性系统来说，重新启动会带来 新的困难，因为重新启动后母系统和子系统所对应的k r y l o v 子空间有可能不再 相同只有当每次重新启动的子母系统的初始向量都是平行的时候，子母系统才 能在同一个子空间中求解，从而提高计算效率当用f o m ( f u l l0 r t h o g o n a l i z a t i o n m e t h o d ) 2 1 来求解此类位移线性系统时，v s i m o n c i n i 2 2 发现子母系统的残向 量都是平行的，因此把当前的残量作为下一次重新启动的初始向量是非常自然和 解位移线性系统的一类添加近似误差的重新启动g m r e s 算法 8 有效的原始的重新启动g m r e s 方法在求解位移线性系统时是不可取的，因为 g m r e s 方法是把当前产生的残量作为下一次重新启动的初始向量，对于子母系 统来说，新产生的k r y l o v 子空间不再是同一个子空间为了克服这一困难也就 是为了保证子母系统产生残量的共线，从而使子母系统重新启动后的k r y l o v 子 空间保持一致，f r o m m e r 和g l g s s n e r 2 3 给出了一种g m r e s 方法的变形，记 为s g m r e s ，首先建立母系统的k r y l o v 子空间并对其求解，而子系统的解是通 过强行的使子系统产生的残量和母系统的残量平行所得到当a 正实，q 0 时， f r o m m e r 和g l g s s n e r 证明了他们的所提出的s g m r e s 2 3 1 方法对于子系统和母 系统都是收敛的 s g m r e s 方法尽管能够使子母系统所对应的残向量都平行，但是由于重新 启动，收敛速度变得缓慢受到求解线性系统的增广压缩重新启动g m r e s e ， g m r e s - d r 2 4 ，2 5 技术的启发，g g u 【2 6 提出一种重新启动g m r e s 方法 的变形，每次重新启动时，把调和r i t z 向量添加到求解空间里去r b m o r g a n 2 7 】也对g m r e s d r 变形使之能够适用于位移线性系统，特别是对q c d 计算 当已经得知了矩阵小特征值所对应的近似特征向量时，这样的策略是行之有效的 然而，当所涉及的矩阵是高度非正规 2 8 ，2 9 】，或者系数矩阵没有和。相对接近的 特征值时，又或者求解系数矩阵的特征问题代价很高的时候 2 4 ，这样的策略是 不可取的 当用重新启动g m r e s 来求解一般的线性系统时，由于重新启动使得正交基 正交性的失去，从而造成重新启动g m r e s 收敛速度变慢 3 0 因此，保留先前 k r y l o v 子空间某些信息可以对重新启动g m r e s 进行加速这一策略在g c r o 方法 3 1 】所研究最近，a h b a k e r 和他的合作者提出了一种新的加速重新启动 g m r e s 2 s ，称之为l g m r e s ，在每次重新启动时，将之前解的误差添加到当前 的k r y l o v 空间中去，在新的增广空间中来寻求问题的解这种算法部分的恢复了 由于重新启动所丢失启动前的k r y l o v 子空间的信息，从而加快了收敛速度我们 将这一策略推广到位移线性系统中来，具体来说首先我们利用l g m r e s 来求解 母系统的解，接下来通过强行使子系统的残留和母系统的残留平行来求解子系统 的解在实际应用中，这一过程能通过求解一些小规模的线性方程组来实现数值 试验表明了位移线性系统的收敛能被加速 解位移线性系统的一类添加近似误差的重新启动g m r e s 算法 9 2 2 位移线性系统的重新启动g m r e s 方法 在这部分，我们简单回顾下a n d e r sp r o m m e r 和u w eg 1 i s s n e r 所提出的位 移线性系统的重新启动g m r e s 方法【2 3 ，我们将此方法简记为s g m r e s 考虑母系统( 2 1 ) 和子系统( 2 2 ) ，在第j 次循环时，记乃为母系统的残量， 乃为子系统的残量采用标准的g m r e s 方法来计算母系统的解，子系统的解通 过强行使子母系统的残量平行得到过程表述如下 假设 矿o = z o t 0 ，z o 冗， 其中庐o = b 一4 圣o ，r 0 = b a x o ，z o 和圣。分别是母系统和子系统的近似解，对a 和r 0 运行m 步的a r n o l d i 过程 8 】，我们有 a = 月- m + h m + 1 ，m 口m + 1 e m t = + 1 ? m ，( 2 3 ) 其中娟“小h m 高卜么 其中 ( 4 + a s ) v m = + 1 ， 吼q 1 暇i 9 z m = x o + v m y m 是通过g m r e s 求出母系统的近似解，从式( 2 3 ) 有 其中+ 1 = 风e 1 h m y m r m = r 0 一a v m y m = 岛v l 一+ 1 巩 = y m + 1 + 1 ， 解位移线性系统的一类添加近似误差的重新启动g m r e s 算法 1 0 子系统的近似解圣仇= 岔o + 鲕通过下面的强制共线条件得到 = 风7 仇 兮f ：o ( a + q ，) 雪m= 风+ l z m + 1 铮岛强一+ 1 赫风+ 1 + 1 ( 2 4 ) 铮+ 1 ( 鲕+ 风+ 1 ) = 风7 0 营赫+ 风z m + 1 对于未知量赫和风，通过下面的等式求出 阮i l r o l l e x 矾撕) 刊h ， 对固定的m ，文献 2 3 给出了下面的算法来求解位移线性系统 算法2 1 s g m r e s ( m ，p ) ( 2 5 ) 开始：母系统和子系统的初始解z o ，圣。满足鳓= z o r o ；k r y l o v 子空间的维数 2 调用a r n o l d i ( a ，r o ，m ) ，得到a n d 3 计算y m = a r 9 m i n 冗mi l 卢e 1 一月_ m i r 仇= b a x m 彳求解 i ，z m = x o + v m y m ，z m + 1 = p e l 一月- m 痧m ， 撕) 刊h b 形成圣m = 圣o + v ，m 痧m ，并且计算= b a 仝m 置计算相对残量范数黼和俐，检验收敛 解位移线性系统的一类添加近似误差的重新启动g m r e s 算法 1 1 2 3 添加误差的重新启动g