（应用数学专业论文）大型稀疏线性系统迭代解法及应用研究.pdf

摘要 摘要 在大规模科学计算与工程技术中，许多问题的解决最终都转化为大型稀疏线性 系统的求解，如流体力学，计算电磁学，最优化问题，线性弹力学等因而，大型稀疏 线性系统的求解研究就具有重要的理论意义和实际的应用价值本文对几类大规模 稀疏线性系统迭代求解进行了深入而系统的研究，主要涉及矩阵分裂迭代法的收敛 性及其比较理论和鞍点问题迭代求解预处理技术 研究预处理a o r ( s o r ) 及g a u s s s e i d e l 迭代法首先，分析修正预处理子结 合g a u s s s e i d e l 方法和a o r ( s o r ) 方法对己矩阵线性系统的收敛性，并给出比较结 果，进而得到修正预处理子的最优结构其次，探讨求解日矩阵线性系统的预处 理g a u s s s e i d e l 迭代法的收敛性条件最后，讨论求解由最d - - 乘问题形成的2 x 2 块 线性系统预处理a o r i 塞代法的收敛性 研究h s s 迭代法及h s s 预处理技术首先，对斜h e r m i t i a r d 反h e r m i t i a n ( l h s s ) 迭 代法和h e r m i t i a n 反h e r m i t i a n ( h s s ) 迭代法的比较，给出一个新优先择取l h s s 迭 代法或h s s 迭代法的判据其次，针对非h e m t i t i a n 正定线性系统，提出修正h s s 迭 代法( m h s s ) 及其非精确的迭代法( i m h s s 迭代法) ，分析二者收敛性条件再次， 将h s s 预处理子应用于经典鞍点闯题，探讨h s s 预处理矩阵的谱分布，给出预处理 矩阵特征值分布的一个新区域并获得其所有特征值为实数的一个新充分条件 最后，研究非零( 2 ，2 ) 块的广义鞍点问题h s s 预处理子谱性质，弥补已有文献只针 对( 2 ，2 ) 块是0 的经典鞍点问题的缺陷，证明在适当条件下，如果广义鞍点问题的系数 矩阵是非h e r m i t i a n 的，那么对于一个充分小的正参数，h s s 预处理矩阵所有特征值 将聚集在( o ，o ) 点和( 2 ，o ) 点附近 研究鞍点问题迭代法主要包括以下5 个方面：1 基于矩阵分裂，给出求解鞍 点问题的一个迭代策略，并讨论该迭代法的收敛性；2 提出修正的对称逐次超松 弛迭代法( m s s o r ) 求解鞍点问题，讨论其收敛性条件并获得迭代参数的最优因子； 3 分析广义鞍点问题含参数块三角预处理子的谱性质并获得预处理矩阵实特征 值及复特征值新的分布区域；4 对混合型时i 皆m a x w e l l 方程离散得到的经典鞍点 问题，依据其特殊的结构，获得最优块对角和块三角预处理子，同时，提出一个新的 单列非零( 1 ，2 ) 块的块三角预处理子并提高原块三角预处理子的应用范围；5 对混 合型时谐m a x w e l l 方程离散产生的( 1 ，1 ) 块不定的鞍点问题提出两类修正的免增广 免s c h u r 余预处理子，通过对预处理矩阵谱的分析，给出最优免增广免s c h u r 余的块 摘要 对角和块三角预处理子，数值实验证实了两类最优预处理子的有效性 关键词：线性系统，l 矩阵，日- 矩阵，特征值，矩阵分裂，i 研l o v 子空间法，鞍点问题， 预处理技术 a b s t r a c t a b s t r a c t s o l u t i o n so fl a r g e - s c a l es p a r s el i n e a rs y s t e m sa r i s ef r o mt h el a r g e s c a l es c i e n t i f i c c o m p u t i n ga n de n g i n e e r i n gt e c h n i q u e ，s u c ha sf l u i dm e c h a n i c s ，c o m p u t a t i o n a le l e c t r o m a g n e t i c s ，o p t i m i z a t i o np r o b l e m sa n d l i n e a re l a s t i c s s o ，r e s e a r c ho fm e t h o d sf o rs o l v i n g l a r g e s c a l es p a r s el i n e a rs y s t e m sh a si m p o r t a n tt h e o r e t i cs i g n i f i c a n c ea n dp r a c t i c a la p - p l i c a t i o n s i t e r a t i v es o l u t i o n so fs e v e r a lc l a s s e so fl a r g e s c a l es p a r s el i n e a rs y s t e m sa r e d e e p l ys t u d i e di n t h i st h e s i s i np a r t i c u l a r , c o n v e r g e n c ep r o p e r t i e sa n dc o m p a r i s o nt h e - o d e so fm a t r i xs p l i t t i n gm e t h o d sh a v eb e e ni n v e s t i g a t e da n dp r e c o n d i t i o n i n gt e c h n i q u e s f o rs a d d l ep o i n tp r o b l e m sh a v eb e e na l s os t u d i e d t h ep r e c o n d i t i o n e da o r , s o ra n dg a u s s s e i d e li t e r a t i v em e t h o d sa r es t u d i e d 。 f i r s t l y , t h ec o n v e r g e n c ep r o p e r t i e so fa m o d i f i e dp r e c o n d i t i o n e rw i t hg a u s s s e i d e la n d a o r ( s o r ) m e t h o d sf o rt h el - m a t r i xl i n e a rs y s t e m sa r ea n a l y z e da n ds o m ec o m p a r i s o n r e s u l t sa r ep r e s e n t e d c o n s e q u e n t l y , t h eo p t i m a ls t r u c t u r eo ft h em o d i f i e dp r e c o n d i t i o n e r i sg i v e n s e c o n d l y , c o n v e r g e n c ec o n d i t i o n so ft h ep r e c o n d i t i o n e dg a u s s s e i d e l f o rt h e h - m a t r i xl i n e a rs y s t e m sa r ed i s c u s s e d f i n a l l y , t h ec o n v e r g e n c ep r o p e r t i e so ft h ep r e c o n d i t i o n e da o rf o rt h e2x2b l o c kl i n e a rs y s t e m sa r i s i n gf r o mt h el e a s t - s q u a r ep r o b l e m s a r ed i s c u s s e d t h eh s si t e r a t i v es c h e m ea n dh s sp r e c o n d i t i o n i n gt e c h n i q u ea r ei n v e s t i g a t e d f i r s t l y , c o m p a r i n gt h el o p s i d e dh e r m i t i a n s k e w h e r r r t i t i a ns p l i t t i n g ( l h s s ) m e t h o da n d h e r m i t i a n s k e w - h e r m i t i a ns p l i t t i n g ( h s s ) m e t h o d ，an e wc r i t e r i o nf o rc h o o s i n gt h e l h s so rh s sm e t h o di sp r e s e n t e d s e c o n d l y , am o d i f i e dh e r m i t i a na n ds k e w - h e r m i t i a n s p l i t t i n g ( m h s s ) a n di n e x a c tm h s s ( i m h s s ) m e t h o d t os o l v en o n h e r m i t i a np o s i t i v e d e f i n i t el i n e a rs y s t e m sa r ep r e s e n t e d t h ec o n v e r g e n c ep r o p e r t i e so fm h s sa n di m h s s m e t h o da r ea n a l y z e d t h i r d l y , w eg i v es o m es p e c t r a lp r o p e r t i e so fh s sp r e c o n d i t i o n e r s f o r t h ec l a s s i c a ls a d d l ep o i n tp r o b l e m s ，o b t a i nan e wi n t e r v a lc o n t a i n i n ga l lt h ee i g e n v a l u e so ft h ep r e c o n d i t i o n e dm a t r i xa n dp r e s e n tan e ws u f f i c i e n tc o n d i t i o nt om a k ea l lt h e e i g e n v a l u e sr e a l f i n a l l y , h s sp r e c o n d i t i o n e r sf o rt h eg e n e r a l i z e ds a d d l ep o i n tp r o b l e m s w i t hn o n z e r o ( 2 ，2 ) b l o c ka r ei n v e s t i g a t e d s o m es p e c t r a lp r o p e r t i e so ft h ep r e c o n d i t i o n e d m a t r i xa l ep r e s e n t e d ，w h i c ha r e t h er e m e d i e sf o r t h ed e f e c tt h a tt h ee a r l i e rr e s u l t sa r eo n l y c o n c e r n e dw i t ht h es a d d l ep o i n tp r o b l e m sw i t hz e r o ( 2 , 2 ) b l o c k i ti ss h o w nt h a tu n d e r m a bs t r a c t c e r t a i nc o n d i t i o n s ，a l le i g e n v a l u e so ft h ep r e c o n d i t i o n e dm a t r i xw i t ht h eo r i g i n a ls y s t e m b e i n gn o n - h e r m i t i a nw i l lf o r mt w ot i g h tc l u s t e r s ，o n ei sn e a r ( 0 ，0 ) a n dt h eo t h e ri sn e a r ( 2 ，0 ) 觞t h ei t e r a t i o np a r a m e t e ra p p r o a c h e st oz e r of r o ma b o v e i t e r a t i v em e t h o d sf o rt h es a d d l ep o i n tp r o b l e m sa r ei n v e s t i g a t e d ，w h i c hc o n s i s t so f f i v ea s p e c t s 勰f o l l o w s ：1 b a s e do nt h em a t r i xs p l i t t i n g ai t e r a t i v es c h e m ei sp r e s e n t e d t os o l v et h es a d d l ep o i n tp r o b l e m sa n di t sc o n v e r g e n c ep r o p e r t i e sa r ed i s c u s s e d ；2 w e p r e s e n tam o d i f i e ds y m m e t r i cs u c c e s s i v eo v e r r e l a x a t i o n ( m s s o r ) m e t h o df o rs o l v i n g t h es a d d l ep o i n tp r o b l e m s ，d i s c u s si t sc o n v e r g e n c ec o n d i t i o n sa n do b t a i ni t so p t i m a li t e r - a t i o np a r a m e t e r ；3 b l o c kt r i a n g u l a rp r e c o n d i t i o n e r sw i t hap a r a m e t e rf o rt 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 sa r ea n a l y z e da n dan e wi n t e r v a lc o n t a i n i n ga l lt h er e a la n dc o m p l e x e i g e n v a l u e so ft h ep r e c o n d i t i o n e dm a t r i xi sd e r i v e d ；4 a c c o r d i n gt ot h es p e c i a ls t r u c t u r e o ft h ec l a s s i c a ls a d d l ep o i n tp r o b l e m sa r i s i n gf r o mt h ed i s c r e t i z a t i o no ft h em i x e dt i m e - h a r m o n i cm a x w e l le q u a t i o n s ，t h eo p t i m a lb l o c kd i a g o n a la n dt r i a n g u l a rp r e c o n d i t i o n e r s a r eo b t a i n e d ，m e a n w h i l e ，as i n g l ec o l u m nn o n z e r o ( 1 ，2 ) b l o c kt r i a n g u l a rp r e c o n d i t i o n e ri s p r e s e n t e da n dt h eo r i g i n a lb l o c kt r i a n g u l a rp r e c o n d i t i o n e r sa r ei m p r o v e d ；5 t w oc l a s s e s o ft h em o d i f i e da u g m e n t f r e ea n ds c h u r c o m p l e m e n t - f r e ep r e c o n d i t i o n e r sf o rt h ei n d e f i n i t e ( 1 ，1 ) b l o c ko ft h es a d d l ep o i n tp r o b l e m sa r i s i n gf r o mt h ed i s c r e t i z a t i o no ft h em i x e d t i m e - h a r m o n i cm a x w e l le q u a t i o n sa r ep r o p o s e d t h eo p t i m a l ，a u g m e n t - f r e ea n ds c h u r c o m p l e m e n t - f r e e ，b l o c kd i a g o n a la n dt r i a n g u l a rp r e c o n d i t i o n e r sa r eo b t a i n e db ya n a l y z i n gt h es p e c t r a lp r o p e r t i e so ft h ep r e c o n d i t i o n e dm a t r i x 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 oi l l u s t r a t et h ee f f i c i e n c yo ft w oc l a s s e so ft h eo p t i m a lp r e c o n d i t i o n e r s k e y w o r d s ：l i n e a rs y s t e m ，l m a t r i x ，h - m a t r i x ，e i g e n v a l u e ，m a t r i xs p l i t t i n g ，k r y l o vs u b s p a c em e t h o d ，s a d d l ep o i n tp r o b l e m ，p r e c o n d i t i o n i n gt e c h n i q u e i v 主要符号对照表 n r r + 0 c n r n c n r m n l a r a + i a i i i a i i ，- i i a t l ( o ，b ) a o a 0 p ( a ) n u l l ( a ) d i & g ( d l ，厶) t r i d i a g ( a ，b ，c ) o 主要符号对照表 数集 l ，2 ，扎) 自然数集 实数集 正实数集 空集 复凡维列向量空间 实亿维列向量空间 m 钆复矩阵集 mxn 实矩阵集 单位矩阵 矩阵a 的转置 矩阵a 的共轭转置 矩阵a 各元素取绝对值的矩阵 矩阵a 的谱范数 矩阵a 的无穷大范数 向量a 6 的e u c l i d e a n 内积 矩阵a 是非负矩阵 矩阵a 是正矩阵 方阵a 的谱半径，若a 为非负矩阵，即为p e r r o n 根 矩阵a 的零空间 以d 1 ，厶为对角元的对角矩阵 以b 为主对角元，o ( c ) 为下( 上) 次对角元的三对角矩阵 k r o n e c k e r 积符号 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 躲勉复一吼彤年三月阳 论文使用授权 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：璺蟛 导师签名： 一 日期：缈歹年z 月夕日 第一章绪论 第一章绪论弟一早硒下匕 1 1 研究背景和意义 世界著名数值分析专家牛津大学教授l l o y dn t r e f e t h e n 和d a v i d b a u i i i 指出： “如果除了微积分与微分方程之外，还有什么数学领域是数学科学基础的话，那就是 数值线性代数 随着计算机科学和信息技术日新月异的发展，科学计算己成为继理论研究及科 学实验后的第三大科学研究工具，正得到广泛的应用许多从事科学研究及工程技 术人员都把科学计算作为研究和解决问题的重要手段当前，科学计算中研究的焦 点之一就是大型稀疏线性系统的高效求解这主要在实践中，如计算流体力学、电 磁计算、材料模拟与设计、石油勘探数据处理、地震数据处理、数值天气预报及 核爆数值模拟等都离不开微分方程的数值求解，而解决这些问题的主要策略是通过 有限差分、有限元、有限体积、区域分解、多重网格、无网格等方法对微分方程 离散而最终转化为求解大型稀疏的线性系统。当今，如何快速有效的求解大型稀疏 线性系统已成为许多专家及学者研究的焦点这主要体现在，在数值计算及其模拟 中，尽管计算机技术发展迅猛，但是求解大型稀疏线性系统所花费的时间往往在求 解整个问题所需的时间中占有很大的比重，有时甚至高达百分之八十以上，成为计 算整个问题的瓶颈 通常，求解线性系统的方法有两类：基于矩阵分解的直接法和基于递归的迭代 法直接法的工作主要集中在上世纪六、七十年代，其主要途径是通过对矩阵进行 变换( 如g a u s s 消元、l u 分解等) ，将原线性系统化为三角或三对角等容易求解的形 式，然后通过回代或追赶等方法得到线性系统的解其优点是在不计舍入误差的情 况下能得到准确解不足之处是当矩阵的条件数很大时，由于舍入误差的存在而导 致所求出的解与准确解相差甚远；当矩阵阶数较大时，由于存储的需求而迫使直接 法相对于其它方法更费时因而，用直接法求解大型稀疏线性系统往往是不可取的， 通常采用运算量小、内存需求小且能充分利用矩阵稀疏性的迭代法当前，迭代法 已成为求解大型稀疏线性系统的主流方法迭代求解大型稀疏线性系统现已成为科 学计算中十分重要的课题之一，其迭代策略一般可分为两类： 一类是基于矩阵分裂的定常迭代法定常迭代法的工作主要集中于上世纪 五、六十年代，其基本途径是通过矩阵分裂而构建迭代格式根据矩阵分裂的 形式不同而形成了许多行之有效的方法，如j a c o b i ，g a u s s s e i d e l ( g s ) ，s u c c e s s i v e o v e r - r e l a x a t i o n ( s o r ) ，a c c e l e r a t e do v e r - r e l a x a f i o n ( a o r ) 等以及这些方法的改进和 1 电子科技大学博士学位论文 加速形式定常迭代法具有结构简单、易于程序实现等优点因此，i 刍j a c o b i 方法诞 生以来，新的定常迭代法层出不穷，备受工程人员及科研人员的青睐目前，这些方 法又有新的发展，如将其作为预处理子与k r y l o v 子空间方法结合一起来求解大型稀 疏线性系统 另一类是非定常迭代法目前，非定常迭代法主要存在两大分支一是 以c o n j u g a t eg r a d i e n t ( c g ) 方法为代表的k r y l o v 子空间迭代法；二是基于矩阵分裂 的分裂迭代法，如非定常r i c h a r d s o n 迭代法、内外迭代法以及非定常多分裂迭 代法等目前，对求解大型稀疏线性系统来说，比较流行的k r y l o v 子空间迭代法 有c o n j u g a t eg r a d i e n t ( c g ) ，m i n i m a lr e s i d u a lm e t h o d ( m i n r e s ) ，g e n e r a l i z e dm i n i m a l r e s i d u a lm e t h o d ( g m r e s ) 等 无论是定常迭代法还是非定常迭代法，其收敛速度都与矩阵的谱性质有着密不 可分的关系对矩阵分裂的定常迭代法来说，在迭代矩阵谱半径小于1 的前提下，迭 代矩阵的谱半径越小其收敛速度越快；对非定常k r y l o v 子空间迭代法来说，其收敛 速度依赖于矩阵的谱分布，谱分布越集中，收敛速度越快 2 5 , 2 7 , 7 7 1 4 1 1 因此，为了提高 迭代法求解线性系统的收敛速度，目前，一个切实可行的途径是采用预处理技术，其 主要目的是预处理后的矩阵的谱更加聚集为特定的大型稀疏线性系统寻找“量身 定做”的预处理子已成为迭代法研究中的重要课题 预处理技术的主要策略是通过利用预处理子将原线性系统转化为易求解的等 价线性系统通常，构建一个好的预处理子已被公认为是艺术与科学的完美结合一 般来说，构造预处理子有两种途径：一是纯代数技术，如不完全分解预处理子，稀疏 近似逆预处理子等；二是从特定问题出发，通过利用较多原问题信息来构建预处理 子，一般情况下，原问题信息利用的越多，构建的预处理子越有效具体地说，对预处 理子的构造可以从以下几个方面考虑： 线性系统的背景； 矩阵本身的性质，如是否具有稀疏性，对称性，占优性等： 预处理部分的计算量比较小： 预处理矩阵特征值分布相对集中； 预处理矩阵需满足一定的性质，如是否具有正定性，是否具有对称性，特征值 是否全是实数 般地，一个切实可行有效预处理子的选择可以从以下几个方面把握： 2 第一章绪论 预处理子在某一方面是系数矩阵的逆矩阵的一个较好逼近( 事实上，构造预处 理子主要目的是使得预处理矩阵为单位阵的近似) ； 构造预处理子需要有一定的内存且c p u 花费要有保障( r p 花费不太大) ； 预处理矩阵的条件数要远小于原系数矩阵的条件数，其最小奇异值会相应的 增大； 新的预处理线性系统要比原线性系统更易求解 本文主要针对几类特殊的线性系统迭代法进行了相应的研究，主要是以研究预 处理技术为目的，以研究数值特性为依托，进而对预处理技术相关数值特性进行了 深入的探讨下面将本文所涉及的相关内容的研究现状作一些简单介绍 1 2 研究现状 1 2 1 预处理经典定常迭代法 在科学计算和工程技术中，许多问题的解决最终都要归结为求解大型稀疏线性 系统： a x = b 非奇异l ( 日) 矩阵的线性系统常常在解决实际问题遇到，如在偏微分方程数值解， 控制论，均衡论及加权最小二乘问题等如前所述，若用直接法求解，则其效果达不 到令人满意的程度常采用迭代法对其求解为了加快迭代法的收敛速度，通常迭代 法需要与预处理子结合一起来求解大型稀疏的线性系统 近年来，对系数矩阵为三( 日) 一矩阵的非奇异线性系统预处理子的构造主要是基 于系数矩阵a 分裂如下形式： a = d l 一矿 预处理子的构造通常是“d + s ”型，其中矩阵s 的元素常取系数矩阵a 的某些非零元 的相反数，如取系数矩阵a 的第一列的相反数【9 l1 2 2 ，取系数矩阵a 的上次对角元的 相反数i s 2 1 0 6 等这种构造预处理子的基本思想是源于g a u s s 消元法，其目的是将系 数矩阵a 的某些对应元素化为0 来减少迭代矩阵的谱半径，进而提高迭代法的收敛 速度其理论依据是迭代矩阵的谱半径越小，矩阵分裂迭代法的收敛速度越快【1 4 a 此类预处理子常常与经典迭代法( 如g s 迭代法，s o r 迭代法及a o r 迭代法等) 结合 一起来求解大型稀疏的线性系统此方法的优点是理论性强，计算代价小；不足之处 3 电子科技大学博士学位论文 是计算的效果相对要差在这类预处理子中，修正预处理方法研究较多，在一定程 度上可看作是g a u s s 消元法的一种扩展目前，国内外很多学者对此进行了相关的研 究【1 6 5 ，箱，9 1 ，1 0 7 ，1 钢，得出了很多理论结果，促进了研发新预处理子的进程 1 - 2 2 非h e r m i t i a n 正定线性系统的迭代法 众所周知，微分方程和偏微分方程在流体力学，电磁计算等领域中有着重要的 应用价值其数值解往往能够反映出所涉及问题的某些特性，如稳定性，流量强度， 电( 磁) 场分布等，故对其数值求解的研究就显得尤为重要现如今，许多科学计算和 工程问题的解决最终都要归结为求解大型稀疏线性系统微分方程和偏微分方程的 数值求解也不例外，常借助有限差分方法将其转化为大型稀疏线性系统，其常见的 大型稀疏线性系统是非h e r m i t i a n 正定的为此，对非h e r m i t i a n 正定线性系统的求解 就成为国内外很多学者研究的一个焦点问题 对非h e r m i t i a n 正定线性系统的求解，在2 0 0 3 年，b a i ，g o l u b 和n g 1 0 提出了h s s 定 常迭代法，给出了其参数的最优因子，并指出了在使用最优因子的情况下，h s s 迭 代法与c g 算法相当其思想主要是源于对线性系统系数矩阵的h e r m i t i a n 和反 h e r m i t i a n 分裂( h s s ) 并结合经典的交替方向隐式迭代技术( a d i ) t 1 删在文【1 2 】中， b a i ，g o l u b 和n g 提出了非精确h s s 迭代法并对其性质给出了理论性分析，并给出 了其收敛条件为了改进h s s 迭代法的收敛速度，b a i ，g o l u b 署l l p a n 在文 1 4 1 中提出 了预处理h s s 迭代法( p h s s ) ，并在文 8 】中给出了系数矩阵为非h e r m i t i a n 半正定 时p h s s 迭代法的收敛条件 由于h s s 迭代法具有结构简单，易于程序实现且有理论上的最优参数值等优 点，因此自h s s 迭代法诞生以来就立即受到了许多专家及学者的重视并由此导致 了许多新的算法，如文 9 】和【1 1 】对h s s 迭代法进行了不同的推广而提出了正定和 反h e r m i t i a n 分裂( p s s ) 迭代法及正规和反h e r m i t i a n 分裂( n s s ) 迭代法对于h s s 迭 代法来说，其迭代过程主要涉及到两个子线性系统的求解：一个是h e r m i t i a n 正 定子线性系统；另一个是反h e r m i t i a n 子线性系统至于前者，由于其系数矩阵 是h e r m i t i a n 正定的，所以对其求解就可以借助于c g 方法；至于后者，由于其系 数矩阵是反h e r m i t i a n 的，所以通常对其求解并不是一件很容易的事跚为了克 服在h s s 迭代法中求解反h e r m i t i a n 子系统所带来的困难，在2 0 0 9 年，b e n z i 【2 0 】提出 了g h s s 迭代法并给出了收敛条件 目前，对h s s 迭代法的研究主要沿着两个方向：其一是对h s s 迭代法经过改进 或修正而形成的迭代法，如l h s s 迭代法【1 0 3 ，p h s s 迭代法f 1 4 3 1 1 ，t s s 迭代法【9 】等；其 4 第一章绪论 二是将h s s 迭代法应用到求解其他实际问题当中，如复线性系统【2 1 1 ，鞍点问题【2 3 】等 1 2 3 鞍点问题的迭代法 在电磁计算，计算流体动力学，限制和加权最小二乘问题，带有限制条件的二次 优化，线性弹力学，椭圆型偏微分方程等许多应用领域中，常常需要求解具有2 2 块 结构的线性系统： 出：ia 矿li 牡l ：i ，i 卸， i j e 7 一c jipli9i 其中a r 似n ，c r m m ，b r m 黼( 可能m n ) 通常，若矩阵a 是对称正定的 且c = o ，则称之为经典的鞍点问题，否则称为广义的鞍点问题对鞍点问题来说，其 系数矩阵4 常具备三个特点：1 ，对称性，i2 ，特征值有负有正，具有强不定性；3 ，对 角元不占优，不具有对角占优性基于特点2 和3 ，鞍点问题直接用k r y l o v 子空间方 法( 如m i n r e s ，g m r e s ，b i c g s t a b 等) 求解，其迭代速度并不是很理想，有时甚至不 收敛由于鞍点问题应用非常广泛，那么如何快速有效的求解鞍点问题一直是斯坦 福大学g o l u b ，艾默里大学b e n z i ，牛津大学w a t h e n 等众多学者研究的热点 经过近几十年不懈的努力，许多学者对鞍点问题的求解已提出了许多行之有效 的方法下面将简单介绍三类迭代法及预处理k r y l o v 子空间方法求解鞍点问题 一、三类迭代法求解鞍点问题 1 u z a w a - 类方法在1 9 5 8 年，a r r o w , h u r w i c z 和u z a w a t 3 】首次基于矩阵分裂而 提出了经典的u z a w a 方法该方法起初是为了求解经济学中的二次优化问题由 于其结构简洁，易于程序实现，因此吸引了许多学者及专家的眼球该方法的 不足之处是每一步迭代都需要精确的计算一个逆矩阵，这对于求解大型稀疏线 性系统来说几乎是不可行的为了克服这个不利因素，文 3 4 ，3 5 ，6 2 提出了非 精确的u z a w a 方法并给出了其收敛条件，从而避免了求逆矩阵所带来的困难在 文 3 8 ，3 9 中，c a o 分别研究了用非线性的u z a w a 方法求解对称及非对称鞍点问题并 相应的给出了收敛条件目前，国内外很多学者对u z a w a 类方法进行了相关的研 究1 5 ，3 5 ，4 5 ，4 6 ，5 1 ，5 2 , 6 7 7 0 9 0 ，1 1o 1 1 1 , 1 1 3 , 1 1 4 , 1 5 9 1 ，得出了丰厚的理论结果，促进t u z a w a 类方 法的研究进程 2 s o r 类方法在迭代法的历史长河中，y o u n g 于2 0 世纪7 0 年代提出的s o r 方 法【1 5 1 】曾经以其优雅简洁的格式而风靡一时，是一类经典的迭代法遗憾的是由于鞍 点问题自身的特殊结构，经典的s o r 迭代法并不适合于求解鞍点问题，这主要因为 鞍点问题的( 2 ，2 ) 块或是零矩阵或是半正定矩阵为了克服经典s o r 迭代法求解鞍点 5 电子科技大学博士学位论文 问题的缺陷，近年来，一些学者开始讨论用广义化的s o r 迭代法求解鞍点问题，并取 得了新的进展l i ，“和e v a n s 在1 9 9 8 年提出了一类广义s o r 迭代法【1 0 4 0 s ，此类方法 保持了s o r 迭代法格式简单、存储量小等优点g o l u b ，w u 和y u a n 在2 0 0 1 年又提出 了s o r 1 i k e 迭代法1 7 3 】，其本质与广义s o r 方法相同，可以看作是广义s o r 迭代法的 另一个版本为了改善s o r 1 i k e 迭代法的收敛速度，b a i ，p a r l e t t 和w a n g 在2 0 0 5 年提 出了广义的s o r 1 i k e 迭代法【1 6 】并获得了最优参数值且推广了文 7 3 】的理论结果近 期，相关s o r 类方法的研究文献可参阅 5 4 ，1 5 6 3 h s s 类方法在2 0 0 4 年，b e n z i 和g o l u b l 2 3 】首次将h s s 迭代法【1o 】应用求解鞍点 问题，给出了求解鞍点问题h s s 迭代法的收敛条件并提出了含一个参数h s s 预处理 子大量的数值实验表明当参数在0 0 1 一o 5 范围内取值时，该类预处理子相当有效 文 4 3 ，1 3 9 详细地讨论了鞍点问题h s s 预处理矩阵的谱性质目前，此类方法刚起 步，发展空间较大 二、预处理k r y l o v 子空间方法求解鞍点问题 由于鞍点问题系数矩阵常常具备强不定性、非对角占优性等特点，所以鞍 点问题通常是病态的以至于直接使用k r y l o v 子空间方法( 如m i n r e s ，g m r e s ， b i c g s t a b 等) 求解鞍点问题，其迭代速度并不是很理想，有时甚至不收敛为了改 善k r y l o v 子空间迭代法求解鞍点问题的收敛速度，通常需要对其采用预处理技术， 进而将其转化为具有较优良性质的等价线性系统对鞍点问题来说，选择预处理子 的一个切实可行的途径是从实际问题出发，利用系数矩阵的性质构造预处理子此 类方法的特点是特定的预处理子大都只能适用于特定的问题，不具备普遍性但是， 正因为存在这样的特点，鞍点问题预处理技术的研究依然是许多学者研究的热点问 题目前，对鞍点问题预处理子的选择，国内外很多学者做了大量的工作，给出了许 多预处理子，其中比较流行的有如下三类： 1 块对角预处理子若a 是对称正定矩阵且c 为零矩阵，则最基本的块对角预 吾b a 三b t 在文 1 2 5 中，m u r p h y ，g o l u b 和w a t h e n 从最小特征多项式的角度分析了此类块对角 预处理子的谱性质，指出了此类预处理矩阵仅有三个不同特征值且对任意具有最 优性质或g a l e r k i n 性质的k r y l o v 子空间方法在三步内就能达到准确解由于该预处 理子含有s c h u r 余，所以在预处理过程中需要精确的计算一个逆矩阵这在实际求解 过程中几乎是不可行的因此，各种各样的近似块对角预处理子就应运而生，如在 第一章绪论 文 6 6 1 q b 就考虑了用尺度化的块对角预处理子代替精确块对角预处理子，这样既能 避免求逆矩阵所带来的困难又能提高迭代法的收敛速度文 1 3 6 ，1 4 1 通过对( 1 ，1 ) 块 一分为二的方式把块对角预处理子推广到应用范围更广的广义鞍点问题，利用矩阵 扰动理论分析了预处理矩阵的谱性质对块对角预处理子的研究，近期相关文献可 参阅 7 2 ，1 3 3 ，1 4 8 ，1 4 9 2 ：块三角预处理子在1 9 8 8 年，b r a m b l e 和p a s c i a k t 3 3 】对广义鞍点问题的求解首 先提出了如下块三角预处理子： ia b t i j0 一( c + b a _ 1 b ? ) i 7 并指出了预处理矩阵特征值全为1 且最小特征多项式次数为2 在不考虑误差的情况 下，任意具有最优性质或g a l e r k i n 性质的k r y l o v 子空间方法在两步内就能达到准确 解在此基础上，i p s e n 在文【9 3 】中将块三角预处理子推广到更为一般的广义鞍点问 题，同样得到上面结果与块对角预处理子一样，求含有s c h u r 余的计算是非常耗时 的，进而用其近似代替原块三角预处理子是一种必然的选择实际上，分析近似块 三角预处理脚l o v 子空间的收敛速度并不是一件很容易的事，而往往只能通过分析 预处理矩阵的谱分布来估计预处理迭代法的收敛速度【2 4 1 对n a v i e r - s t o k e 方程离 散形成的鞍点问题来说，合适的块三角预处理子可确保预处理k r y l o v 子空间方法的 收敛速度与网格的粗细无关【9 8 1 1 7 】对块三角预处理子的研究，近期相关文献可参 阅 4 0 ，4 2 ，6 3 ，1 3 8 3 约束预处理子约束预处理子的结构与原鞍点问题系数矩阵的结构相一致， 只不过是( 1 ，1 ) 块的a 被近似取代( 此处用矩阵m 代替矩阵4 ) ，具体形式如下： lmb rl 【b cj 原则上，要求此类预处理子的逆比较容易求目前，此类预处理子已被广泛的 应用于椭圆型偏微分方程及约束二次优化问题【4 ，”o 】在c = 0 的情况下，k e l l e r , g o u l d 和w a t h e n 在文【9 6 】中分析了预处理矩阵的谱分布及其相对应的特征向量，刻 画了g m i 迮s 迭代法的收敛行为随后