（计算数学专业论文）大型稀疏线性方程组的预条件解法.pdf

摘要 f 人，靶稀疏线性代数方程组是从偏微分方程离散出来的，使用预条仆如阼米加 速趟方法f u j , u e 敛性是通常所采用的方法。不完全分解和使用近似逆作为预条什 了是剥称m 矩阵经常使用的手段，但是剥 二一般的别称市定矩阵就没有这十彻0 结论，i i 使用高阶有限元离散出来的矩阵就是剥称i f 定矩阵。) 本文r h 我们使川 列角补偿约化，将对称正定矩阵约化成剥称的m 矩阵，经对角补偿约化后的川 阵的分裂收敛，原矩阵的相应分裂就收敛，原问题的预条件就变化成剥_ ：列称n 0 m 知，阵作预条什，如果使用多分裂预条件也是如此。这有效地将剥称湃定矩阼 的预条件问题转化成对称m 矩阵的预条件问题。将不完全分解和刘角补偿约化 棚结龠就得到对称一定矩阵的多分裂预条件方法。 从定常的不可压缩n a v i e r s t o k e s 方程组离散和稳定化后得到的系数甜! 【j 1 = 址 忖0 称不定的，木文将对于稳定化后的系数矩阵使用块三角预条仲，并给预条 件后的特征值估计、收敛性分析，适当地选择t m 条1 ，| ：r ，使甜j 特 l l ：f i i ( 的抖川高 敞化过雅- l ，刚姒的人小兀关。同时，我们给“i 了数位结果，使川州4 i i 叫i 1 | ( j 稳定 化一憋体稳定和局部稳定，通过数值结果可以看出使用块三角预条件于的训辫：效 果足棚当理想的，尤其是对于局部稳定化的情况，工作量几乎是无稳定化项叫的 j i 皇。 笑键嗣：列角补偿约化，n a v i e r s t o k e s 方程组，多分裂，预条件r 。 a b s t r a c l 】fs o m e o n ew a n tt os o l v et h e1 i n e a ra l g e b r a i ce q u a t i o n sw i t hl a r g ea n ds p a t s e c o c f f i c i e n t n m t r i c e s ，a r i s i n g f o r i n s t a n c e ，f r o n l t h ed i s c r e t i z a t i o no f p a l 1 1 a l d j l l b l e m i a le q u a t i o n s t h e ni ti sq u i t ec o m m o nt ou s ep r e c o n d i t i o n i n gt oa c c e l e r a t et h e c o n v e r g e n c e o fab a s i ci t e r a t i v e s c h e n l e i n c o m p l e t e f a c t o r i z a t i o n sa n d s p i n s e a p p r o x i m a t ei n v e r s ec a np r o v i d ee f n c i e n tp r e c o n d i t i o n i n gm e t h o d sb u tt h e i le x i s t e n c e a n dc o u v e r g e n c et h e o r yb a s e dm o s t l yo nm ，m a t r i c e s ，n o tt h es y m m e t r i cp o s i t i v e d e f i n i t cm a t r i xt h i si st h ec a s e f o fi n s t a n c e w h e n h i g h e r o r d e r f i n i t ee l e m e n t a p p l 。o x i m a t i o n sa r eu s e d w h i c hi st y p i c a lf o rs t r u c t u r a lm e c h a n i c sp r o b l e m s n o wi r l t h i sp a p e r w ew i l lu s ed i a g o n a l l yc o m p e n s a t e dr e d u c t i o nm e t h o da n dt i r ep l o b l c m t h a ta b o u tt h es y m m e t r i c p o s i t i v ed e f i n i t em a t r i xb e c o m e t h a to f s y m m e t r i cm m a t ! i x w h e nt h e s p l i t t i n g o fa s y m m e t r i c m m a t r i x c o n v e r g e n t ，w h i c h i s d i a g o n a l l y c o n l p e n s a t e d r e d u c t b y a s y m m e t r i cp o s i t i v e d e f i n i t em a t r i x ，t i r e c o r r e s p o n d i n g s p l i t t i n g o ft h es y m m e t r i cp o s i t i v ed e f i n i t ei sa l s o c o n v e r g e n c e a n dw eu s et h e s p l i t t i n g o fs y m m e t r i cm - m a t r i xa st h ep r e c o n d i t i o n e ro ft h e s y m m e t r i cp o s i t i v e d e f t n i t em a t r i xw ec a ns e et h ev a l i d i t yb yn u m e r i c a le x p e r i m e n t s d i s c r e t i z a t i o na n dl i n e a r i z a t i o no ft h e i n c o m p r e s s i b l e f l o wn a v i e t s t o k e s e q u a t i o n sg i v er i s et oan o n s y m m e t r i ci n d e f i n i t ei i n e a rs y s t e mo fe q u a t i o n s i nt h i s p a p e r ，w ei n t r o d u c ep f e c o n d i t i o n i n gt e c h n i q u e sf o rs u c hs y s t e m sw i t ht h ep r o p e rt y t h a tt h ee i g e n v a l u e so ft h ed r e c o n d i t i o n e dm a t r i c e sa r eb o u n d e di n d e p e n d e n t l yo l m e s hs i z eu s e dj nt h ed i s c r e t i z a t i o n i nt h en u m e r i c a 】e x p e r i m e n t s w ei l s et h eg l o b a l s t a b i l i z a t i o na n dt h el o c a ls t a b i l i z a t i o n w ec o n c l u d et h a tt h er e s u l to f u s i n gt h eb l o c k t r i a n g u l a rp r e c o n d i t i o n i n gi ss a r i s f y i n g ，e s p e c i a l l y i nt h ec o n d i t i o no ft h e g l o b a l s t a b i l i z a t i o n ，o fw h i c h c o m p u t a t i o n a lc o m p l e x i t y i sa h n o s ta sh a l fa st h a to l n o n s l a b i l i z a t i o n k e y w o r d s ：d i a g o n a l l yc o m p e n s a t e dr e d u c t i o n ，n a v i e r s t o k e s e q u a t i o n m u l t i s p l i t t i n g ，p r e c o n d i t i o n e r 2 第一章引言 当前，商性能并行计算机科学技术发展迅速，许多的挑浅t l f - 1 题摆在人们m l i 辩。世界上的发达国家提出发展速度和储存性能均高于目前已有型号数f 倍的高 性能计算机，以实现武器设计三维全物理过程的数值模拟。剥于三维问题形成的 大型稀疏线性代数方程组的迭代算法，如何充分发挥成1 ：_ l 干个c r un 勺j i = j ： | 强 机f l j 滞化j 何r i ：能足一个大滩题。算法和软什技术均矧i 人的考验，j 川r ，人 的j 1 ： j ：数值应用软件的研制与开发已迫在眉睫，它们主要来自叫方【f 【l 的动力： 、 为我们国家的高技术提供有效的高技术的软件，大幅度增加全物理过程的数值模 拟能力；二、建立更科学的算法，改变算法和软件研制相对滞后于高性能的并行 - t 算机的现状，以便能更好地适应并行计算机的迅猛发展。 线性代数方程组的数值求解在科学与工程计算中应用 “分广泛。众所周知， 许多实际问题最后都归结为一个或一些大型稀疏矩阵的线性代数方程组a x = b ， 巾彳是一个阶数比较高的矩阵，通常是几。r 万阶其至是j l 百万阶，乃至更多， 而刑r 这种方程组一般采用迭代法求解，且尽可能地保留其原有的稀疏眺。这样 大规模的矩阵在实际计算时使用一股的迭代法通常需要用较多的迭代步数j 收 敛，即便象用g m r e s 方法等的长递推方法在理论上已经证明是对1 二某些满足条 什的矩阵是有限步中止的方法，但也可以有例子举出它在前面的相当多的步数挪 收敛得非常非常地慢，只有在相当接近于它的阶数时爿迅速收敛，这剥、】二大型m 题是非常致命的，主要是占有计算机的大量的内存和耗费c p u 相当惊人的叫| 1 j ， 当j 上预条件因子以后情况就会好多了。预条件因子( 预条件矩阵) m 的选墩应 满足以下的几个条件： 1 预条件矩阵m 在某一方面是a 的一个较好的逼近。 2 ，构造预条引：矧嗍：m 有一定的内存需要_ ：| c i ) u 花赞 j n 侏障。 ： 矩f 1 j ”。爿的条件数会比a 的条件数大大地减少，其最小的奇片位也会 变火。 4 方程组m y = v 要比方程组a x = b 容易求解得多。 我们通常称这样的非奇异矩阵为预条件矩阵，采用了预条件矩阵以后，矩阶 m 。a 在选抒适当的迭代法后会具有较好的特性，收敛速度会较先前快，方程射l 的迭代步数会成倍减少，在这种情况下，我们将求解线性系统m “彳x = m 。b 来 代替原先给出的系统a x = b 。当然这跟预条件矩阵的选取很有关系的，要足选的 矩阵不是很理想的话，会使得迭代步数不但没有降低反而增加了，因此，什么样 的系数矩阵选取什么样的预条件矩阵合适就成为了现在很多数值计算的一个 l 重要的研究方向。 另外，预条件矩阵的选取是也影响算法的收敛速度，如果矩阵预条件以后| 1 算法本身是收敛的，但收敛速度很慢，这不仅使人工和机器时间比较浪费，而f 还不一定能得出所需要的结果，因为预条件矩阵本身的求解需要耗费汁算机定 的州州。存实际的操作巾，预条件矩阵的选取直接影哪计算帆f f j l 上j 存和c i u 的 1 工作时间，预条件矩阵选取是否有效是很关键的环节。而在求解大型稀疏的线。r ： 代数方程组的过程中，我们利用预条件矩阵m 的另外一个很重要的因素存j 矩 阵爿的逆很难求，相对来说，我们所构造的预条件矩阵m 就要好求得多，闪此， 这利t 思想方法是实际运用的需要。如果将预条件矩阵m 构造成剃a 距离较远的 矩阵，也就足没有充分继承a 的特性，那么，预条件的效果就不会很好，迭代 的速度不会改善很多，相反地，如果取的预条件矩阵m 和爿的差异很小，那么， 同样是不太成功的，因为，爿的逆很难求，选取的m 跟它很接近就意味着m 的 逆也很难求。所以，选择预条件矩阵和原方程组的系数矩阵之间的距离也应该足 一个比较难掌握的尺度。由此可见，预条件矩阵应该怎样取比较好( 当然，我们 希望是达到最好的效果) 是一件相当难的事情。在一般的情况下，我们认为一个 较好的预条件矩阵应具备： 1m 对称正定； 2 m 应该与爿的稀疏性差不多： ：j m “爿的特征值分布相对要集中些； 1 迭代f l 】每一步都相当于要求解一个形如m z = r 的力_ 生纣【，凶此，我们婴 求这一方程组要容易求些，即m 应具有某些特殊的形状，如块剥角，或 三角矩阵的乘积等。 众所周知，预条件共轭梯度法成败的关键在于预条件矩阵的选择是否恰当。 在共轭梯度法发展的初期，由于人们只是利用一些矩阵的简单分裂方式来选取预 条件矩阵，以致于使得很多情况下收敛速度的提高并不十分明显，因而使共轭梯 度法自问世之后，二十多年来一直没有得到广泛的应用，直到七十年代后期，两 位荷兰数学家m e i j e r i n k 和v a nd e rv o r s t 才将c h o l e s k y 分解法和共轭梯度法 巧妙地结合起来，提出了一种称作是不完全分解预条件共轭梯度法。这类方法， 山丁收敛速度快因而其运算量较小，而又具有节省内存的优点，因此受到人们的 推崇，成为七、八十年代研究的热点，这使得线性方程组的求解方法经历了 口划 长的平稳发展叫期以后，终于发生了突破性的进展。 所滑不完全c h o l e s k y 分解，就是将a 分解成 爿= l l 7 + r“1 ) 其中是下三角矩阵，r 称作剩余矩阵，r 一般不为零。由于这罩有r 可以变化， 闪此，可以仟意指定的稀疏性质。获得不完企分解l 圈r 的l 的力法彳 u 多， 蜮为常见的是下列无填充不完全c h o l e s k y 分解策略( i c ( 0 ) ) ： 若d ，苹0 ，讨算z 。| 若= 0 ，取0 = 0 巾，c l 。是矩阵彳的元素，。是l 的元素。这样，我们就可以要求与爿保持 同样的稀疏性，或者具有我们希望的稀疏性，从而克服了c h o l e s k y 分解破坏爿 的稀疏性的缺点。 所渭不完全分解预条件共轭梯度法，就是首先对爿进行形如( 1 1 ) 的不完全 1 c 1 【) 1e s k y 分解，然后，以m = l l 7 作为预条什矩阵来应用p c g 方法。冈此，为 了使所得到的预条什共轭梯度法( p c g ) 收敛尽可能地快，就需要l 孓川能地 接近丁a 。如果采用不完全c h o l e s k y 分解作为共轭梯度法的预处理，则要求j e 成小完企分解的汁算量很小，对于一些离散的方稿吲算f r 也比较小。小完个 0 o 】e s k y 分解和共轭梯度法相结合是目前最有效的串行预处理方法。 形如( 1 1 ) 的分解有相对大的灵活性，一是的哪些元素为零可根 ) ： ：不同的 要求束指定，二是r 的选择上亦有相对大的自山度。近十年来，人们引剥不刚 类型的问题，利用分解( 1 1 ) 的灵活性，已经提出了各种各样的不完全分解。 进入九十年代以来，微电子技术迅速发展，基于r i s c ( r e d u c e dl i s t f u c l j0 1 1 s e tc o m p u t e r ) 指令系统的微处理芯片的性能每年增长一倍，内存容量每年增k 3 4 倍，而网络通汛技术也得到快速发展，这些都对并行汁算机的发展产牛甄 要的影响。至九十年代中期，微处理器的性能就已经非常强大了，能提供每秒儿 亿到卜几亿的浮点运算速度。并行计算环境包括并行硬件环境和并行软件环境， 吲此，改善并行软件环境即提高并行化的程序设计，以期能解决目前软件没州 对滞厉于计算机的高速发展的需要。 0 l e a f y 和w h i t e 在1 9 8 5 年提出了并行求解线性代数方程组的多分裂方法， 神：此以后，中外很多的数学工作者都对这一问题表示出极大的兴趣。在求解大难 f r ：j 茅l l 超大型的稀疏线性方程组的时候，多分裂方法起到了非常大的作用，这给并 行带来很多的优点，其中最为主要的是易于实现，便于编程。大规模的线7 t 4 数 方程组就要求有一个很有效的预条件子，预条件子的选取在现会仍是人们关注的 个热点。大型稀疏线性代数方程组的并行预条什了，通；i i i y j 近似逆拽术、多分 裂披术和多项式技术。 求解大型线性方程组( 1 1 ) ，其中，a 是非奇异矩阵，令m ，、利e ， 都是n n 矩阵，= l ，2 ，口，若满足： ( 1 ) a = m ，一n f ，m i 存在； ( 2 ) 岛= ，( i j q n n 单位矩阵) ，岛是非负对角矩阵。 则称三元组( m ，n ，e ，) ，1 = 1 ，2 ，口，为a 的一个多分裂。把方程( 1 1 ) 写成 x = m t 。n i x4 - m j t b j n 权矩阵e ，组合这a 个方程，得到 = h x + g 6 3 6m 写 。n z m m 毋 。m l i z 毋 。埘 i i r 其。t h ：羔日m ，n ，g = 羔日肘i 1 ，再对上面的方程组使川迭1 法 ，：l ，= l x ( + ”= h x l “4 - g b ，k = o ，1 ，2 ， 这格式被称为多分裂迭代格式，i t 称为多分裂迭代方法的迭代矩阵。从这格 式看，如果有一台具有一个主机与“个处理器的并行机，那么这样的算法就 以并行实现，每台处理机处理一个局部迭代( 列，= l ，2 ，a 利川 = n ，x ( + b 求解y ，) ，将局部迭代的值y ，送到主机，主机对y ，进行t j | | 权、r 均 而得到整体迭代值x “”，x n “= e ，y ，。如果e ，的某个对角元素为0 t m i j y ，n o i i 剥应分量就无需汁算，从而大大地节省了工作量。由此可见，e ，也起到了涧配 各处理器卜的工作量的作用。我们应恰当地选择e ，使得各个处理器之洲人敛 做刘负载，i 五撕，以减少同步等待的_ 丌销。可见，多分裂具有自然的， ：行。肚，多分 裂迭代可以看成是经典的块j a c o b i 迭代法的并行推广。 多分裂技术中的不完全l u 分解目前来讲还是一种比较好的技术，它1 i 仪仅 使用在低维的偏微分方程离散出的线性代数方程组，同样地也能适用1 ：高维( i 维) 。多分裂技术可以使用到g u a s s s e i d e l 松弛、j a c o b i 松弛、s s o r 松弛等等。 多分裂能和精典的迭代手段紧密结合，所以，这一技术是现今使用比较频繁的，i f _ 行化方法。我们可以把这一技术使用到日常生活的各个方面中，如对流扩敞方f i ! 组的求解，油藏的数值模拟。 下面我们来看几个例子。 例1 ：非定常圆柱绕流问题 没! 卜径为口的圆柱，位于静止的流体中，当f20 时，无穷远处有一均匀水 流绕流该圆柱。 作坐标变换 ，= 口e 对，0 = a r ， 这使得计算区域变成半带形区域：0 f 0 0 ，0 s ，7 1 。由于# 不必很火，r 可能 已经；j 人，因此，把区域限制在0 兰孝。是合理的。若采用这样的假设，哪 么，使用涡一流函数方法的无量纲形式可化成如下的初边值问题： g丝+警+百a(voot- r e ( 警+ 等 = o ， 。 a 孝 。 a 玎la 2 。a 叩2j “ 警+ 等吲 4 初始条f ， ：y ( ，”，o ) = 0 ，f ( 孝，q ，0 ) = 0 边界条件：= 墨警= o ，在孝= o ，o ，7 l 上 d 亡 妒一2 8 ，硝8 m 石叩 ，征 ，o ( 7 7 - 口。f ，= j ，2 ，n ，那么，称矩阵a f 是严格剥角占优。 剥了二a 的一个分裂a = m 一，如果m 。0 且n 120 ，那么，分裂被称为 是j i j 则分裂。如果m 1 0 ，且肘1 n 0 ，那么分裂叫作左弱j f i 则分裂。如果它 是二i 弱j f 则分裂，而且n m “0 ，那么它是双边弱i f 则分裂。如果p ( m “ ，1 1 ， 那么，分裂是收敛的。设a 是对称的，如果m 和均是对称的，那么，分裂 a = m j 就称为对称的。 a n 0 一个多分裂如 2 2 中的定义，它是三重的集合( m 。，n 。，e 。) ， k = 1 ，k ，满足： ( i ) a = 帆一n ；，k = l ，托 8 一 ( i i ) m 。对丁k = l ，k 是非奇异的 ( i i i ) e 。，a ：l ，k ，是剥角阵，列角元为非负，使得e 。= ，。 我们导1 1 1 步多分裂预条件r 的主要l 具是对角补偿约化 2 。现扯j l 。些 们柬引进这一概念，稍加推广【2 中的对角补偿约化方法就可以得到f 面的描述， 并日在使用剥角补偿约化的基础上剥矩阵进行预条f l 二。 设a 是一个对称正定矩阵，另外，矩阵r 是对称的和非负的。考虑约化如 阵 b = a r ( 2 1 ) j j 任意选择一个f 的( 权) 向量v ，然后，定义a 的对角补偿约化矩阵 a ：d + b ， ( 2 2 ) 鼢i ，j 】) 是一个对角矩阵，它是由 d v r v 所定义。d 足约化元素矩阵r 的对角补偿矩阵。注意 a 变成如下的分裂 a = a f d 一月1 ( 2 3 ) d 0 且av a v ，月5 么， ( 2 d ) 洲为d 0 ，r 01 1 1 ( d 一o v 0 ，所以，d r 赴j i ：半定，1 邝1 ，川此，a ai i ! 、r 一i 定，且剥任意的特征值旯，( a 爿) 我们有 一i ，( 爿爿) l ( 2 5 ) 另外，i 殳 爿= m n( 2 6 ) 是带j 卜定矩阵m 的对称分裂。那么，成立下面的收敛性分裂结沦。 引理2 1 ( 见 2 ) 发a 是一个n n 对称正定矩阵，且a = d + b 是a 的个刘j 补偿约化矩阵，那么， 0 五j ( m 一爿) 旯，( m 。1j 4 ) ，j = l ，胛 山此，如果分裂a = m n 是收敛的，那么，分裂 a = m n 址收敛的( 其t i ；n = m - - a ) 。 我们注意到，如果约化矩阵b 是一个z 矩阵( 即a 的所有的j r ( 1 , 1 - i i j g 、j 角元 被约化元素矩阵r 约化了) ，那么，爿= d + b 也是z 矩阵。因为爿一爿是j r 半定 9 矩阶，a 是一个s t ie l t j e s 矩阵( 即a 是个别称l ：定的z 矩阵) 。 x h l e ，a 址 个剥称j f 定的m 矩阵( 见 3 1 ) 。那么，山引理2 1 ，对一个刘称i f 。定矩阶构 造一个收敛分裂的问题总能约化成一个对s t i e l t j e s 矩阵( 对称正定的m l 阵) 构造个收敛分裂。因此，当我们从对称正定矩阵a 构造出剥角补偿约化矩阵a 的时候，我们总使得a 是一个s t i e l t j e s 矩阵。 我们也注意到( 2 2 ) 和( 2 3 ) 意味着可以选择一个d 使得a 是，7 格剥角i ， 优的。，此，剥j i 别称i f 定矩阼a 总能构造占的个严格刘们i 优的ij t 、。 对f 】补偿约化矩i j 乍a 。 引理2 2 ( 见 1 ，9 ) 设爿是一个对称j 下定矩阵，a 有分裂a # m j ，m 足刘 称汇定的，且h = m 1 n 满足p ( h ) l 。那么，由分裂得到的m 步预条件了 。，= m ( 1 + h + 一+ 何”。1 ) 。是对称j f 定的。 训则：因为= 卜一ma ，我们有 盯。一= h 。m = h ( ，一h ) a 。 j = 0j = 0 一i = ( ，一h ) = ( ，一m 。1 爿) m 。 ( 2 7 ) ( 2 7 ) 式说明了盯：是对称的。因为 = i m a = a2 ( ，一a2 m 。a 2 ) a2 ， 的所有特征值都是实的。现在，我们得到 爿j k 扣j = 彳i ( ：a ) a j = a 一2 ( i h ”) 爿一。 凶为，一h 的所有特征值都是正的，所以盯l 是对称i _ f 定的。口 从引理2 2 ，我们知道为了证明m 步预条件子盯。是有效的( 符合第一章 的要求，包括要盯。是对称正定的) ，必须给出分裂( 1 2 ) 巾的矩阵m 是别称 定的，几迭代矩阵h ；m 1 n 是收敛的。 第三节主要结论 一1n 一 设a 是一个n h 别称砸定矩阵，我们将通过剥角补偿约化束决定ai l j 多分 裂( m 。，n 。，e k ) ，k = 1 ，k 。假设爿经过对角补偿约化历的s t i e l t j e s 矩阵a l 终被构造米。 3 1 块对角协调多分裂 第利- 类型的多分裂是块列角协调多分裂( 见 5 中的定义2 ) 。 设a 被分成g q 块 a = a l c 2 ： 一q c 1 9 c 2 v ： ： a q ( 3 1 ) 其q 1 a ，j = 1 ，q ，是 ，= n 的n ，。_ 矩阵。因为a 是一个s t i e l t i e s * 邮车 j = l 那么，f 块a ，( j = 1 ，q ) 也是s t i e l t j e s l i i i ! i ：。对j i ，f ，j = 1 ，q f c 。= c j 0 。 “+ 、“ 设a ，= m ，一n ，k = 1 ，k ，是爿，( = 1 ，g ) 的分裂。我们构造 个a 的多分裂( m 。，| t ，b ) ，a = l ，k ，有下列形式： m l d i m r n k = m 一a ， ( ： 2 ) ( 3 3 ) 其r i - o c f l ，kc ：1 ，且，：1 ，q 是”，n ，单位阵。 盟然，当= ff l , 3 一个多分裂( m 。，n 。，e 。) ， = l ，k ，定义了，那么，a 的多分裂( m 。，n 。，b ) ，a = 1 ，k 也就有定义。这两种多分裂的不同之处r i ： j 刑j 二k = l ，k ，n k = m 一a ，而n = m 女一a 。 定理3 1i 5 2a 足t 个对称正定矩阵，而a 足一的任何一个剥角补偿约化肝甜剑 的s l ie i j e s 矩阵，分块形式如( 3 1 ) 。假设a 和a 分别有多分裂( m t ，t ，e ) 和( 彳。，t ，e ) ，k = i ，k ，其中m 。和b 是( 3 2 ) 和( 3 3 ) 叶j 所给出的， n ( 1 相应的分裂a ，：m ，一，= 1 ，k ，= 1 ，q ，是对称弱正则分裂，m i 是对称l e 定的。那么，从a 的多分裂( m 。，n 。，玩) ，k = 1 ，k 得到的i n 步预 条件予r 。是对称正定的。 证明：列丁k = l ，k ，我们有 a = m 一 c z c l 。i n ( 女)j n2 c 2 口l ， ( ： 1 ) 一( ) i c 啦n q 1 k k “ g = 巨们i ，= i - g a = b 肘i n t ( ：3 5 ) t = i = i 显然，a 的分裂a = m 。一n k ，k = 1 ，k ，是对称弱正则的，m 。是对称正定的。 吲为a 是一个s t i e t j e s 矩阵，则a 是单调的。显而易见，a 的从多分裂 【m 。，t ，e ) ，k = l ，k ，得到的多分裂迭代法是收敛的( 见 2 2 ”p 的定理l ( a ) ) 。也就是p ( h ) l 且g 是非奇异的。令h = i - g a ，那么，我们有两个! f l 一1 2 分裂 ， 十 a = g 一一g 一1 h 基m r n ， a = g 一g 一1h 三m n ( ： 6 ) ( 3 2 ) ，( 3 3 ) 和( 3 5 ) 说明g 是对称正半定的。注意，g 也是非奇异- ( f j 。洲 此，g 和m 都是对称萨定的。从引理2 1 ，( 3 6 ) 和p ( h ) 1 ，我们得p ( h ) 】。 那么，i 土1 引理2 2 知，k 。，= m ( i + h + + h 。) “是对称正定的。口 n一一t l 如果a 的每一个子块a ，= 吖 ”一，t = “，彪，_ ，= l ，叮，是从小先 全c h o i e s k y 分解( i c f ) 得到( 因为a ，是对称的m 矩阵，它们的不完全c h 0 1 e s k y 分解必存在 2 3 ) ，那么，肘= 掣三j ”，其中，? 是一个下三角的m 矩阵， nf 女、 n n ，0 。根据定理3 1 ，我们得到个基于不完全c h o l e s k y 分解的剥称i i 二定 的l i ) 步多分裂预条件子。因此，定理3 1 改善和拓展了 5 中的定理4 的结论， 5 中是假设a 是一个对称的m 矩阵，在此我们仅要求它是对称正定矩阵。 肚j | i ：述的讨论，容易看出 5 ”f j 给的刘于求解系数甜i 阼足剥称m 矩阶 ( sl i e 【t i e s 组) 的线性系统所使用的多分裂预条件p c g 迭代法的技l 也i i f f u 以 运用于求解对称正定矩阵的线性系统。 3 2对称多分裂 第二种类型的多分裂是对称多分裂，它在 9 中给出。 令a 是一个 对称正定矩阵，并且令a 的多分裂是( 吖。，n 。，e 。) ， k = 1 ，k ，那么，我们构造并行对称多分裂算法如下( 见 3 3 ) 。 x p “= x ”+ g r p ，( ：j 7 ) 其t ， r g = 寺( e m i 。+ 肘，e 。) 和r ”= b - a x ” ( 3 8 ) j = j ( 3 7 ) 的迭代矩阵是 i i = i g a 如果g 足非奇异的，迭代能从a 的个单分裂推出： a = g 一一g 一1 h 现在，我们有对角补偿约化的手段，也有众所周知的多分裂，因此，希望能 将两者结合起来，以期能构造出新的预条件于，达到迭代方法收敛速度加快的效 果。为了u ：我们能使用对角补偿约化来确定多分裂( m 。，m ，) ，女= l ，k 。 一l3 一 世爿的一个对角补偿约化矩阵二l ( s t i e l t j e s 矩阵) ( 见第二1 ，) 。尚先，假砹 s t i e l t j e s 矩阵a 是被分成k k 块 a = 爿1 一c 1 2 c 2 i 爿2 c ( ： 9 ) 一 “ 其一i ，爿，j = 1 ，k ，是_ 一阶矩阵，_ = 。因为一是一个s t i t e j e s f = l 矧i 阵，那么，子块a ，= 1 ，k ，也是s t i e l t j e s 矩阵，且剥丁， i ，= 1 ，k 都有c 。= c j 0 。 n 剥二a 的每一个子块爿，= 1 ，k ，有分裂a ，= b ，一c ，。我们构造a 的多 t ，e 。) ，k = 1 ，k ，有下面的形式 m d j ， b k c + l b “ 一c n nk = m k d 蛰i 。 k 其h 0 d j 1 ，d j = 1 ，且，i = l ，足，是一。一阶单位矩阵。 i = f 很明昆，对rl i i ! i i j ) i i ，如果令| v 。= m 。一a ，那么，a 的多分裂 ( 3 1 0 ) ( 3 1 1 ) k r g q 舭 一 一 、， ( m 。，女，瓯) ，a = 1 ，k 有定义。根扪多分裂的定义，从i ：i f i i i i j ( 一1 ( ) ) ，i r h 我们可以得到下面的等式： m ：j = 何 口1 c k + 口i b i ：, k b c 。i 口i 。 b ； ( 3 1 2 ) 在具体的多分裂实际操作中，所需要使用到的矩阵g 和矩阵h ，我们将在下i l 给出 g ：圭( b 圻t + m i 7 剐 = i j ! ( b 一t + 昕，) 掣巧t c ：，所i 口_ c 型 2 ：c 篮 2 b , - 7 c 1 2 b ；7 珂+ 巧7 ) b ；c f 2 b ； h = i g a = 二1 ( b 7 - + 碟) h l lhb 2 h 2 lh 2 2 矗r i厅岸2 h l k h 2 k ： h k k ( 3 j ： ) ( 3 14 ) 定理3 2 假设a 是对称正定矩阵，爿是爿的任何一个对角补偿约化后得到的 s t i e l t i e s 矩阵，爿的多分裂( m 。，n k ，e k ) ，t = i ，k ，是形如( 3 1 0 ) 和( 3 1 1 ) 的，刈j 二i = 1 ，k ，爿，= b ，一c ，均是双弱正则分裂。那么，g 是非奇异的 p ( h ) 1 。 址l 刿：凶为a 是一个s t i e l t j e s 矩阵，且爿的分裂爿，= b ，c ，i = 1 ，k 是双弱正则的。我们有b , - 1 0 ，e 。c o e 。7 c 7 0 且对于i , j = l ，k ，c ，0 1 5 一 略醒 k q q 町 区 掣：雄1 ， ( j ，) 。从( 3 1 3 ) 和( 3 1 4 ) 知 g 0和 h 0 ( 3 15 ) 从( 3 1 3 ) m t 也容易看出，g 的每一行至少有一个非零元。如果再考查( 3 1 5 ) ， a20 日：，一g a ，利用 3 3 巾的定理l ，得到g 是非奇异矩阵_ 凡p ( j 【，) l 。 至此，定理得到证明。口 我们现存年i l 麻地有a 和a 两个单分裂 爿：g 一g 一1 h ；m n和 a = g 一一g 。h 。 ( 3 1 6 ) 另外，第二个分裂是收敛的，也就是p ( h ) 1 。首先，我们有以下的结果。 定理3 3 设a 是对称讵定矩阵，a 是a 的任何一个对角补偿约化后得到的 s t i e l t j e s 矩阵，a 的分块情z 兄女u ( 3 9 ) 。假设爿和爿分别有多分裂( m ，n ，e 女) 和( m 。，_ 女，e ) ，t = 1 ，k ，其中m 和e 是( 3 1 0 ) 和( 3 1 1 ) q 给出的， 刈 f - ，k ，a ，的分裂a ，= b ，一c ，是双弱正则分裂。如果( 3 1 3 ) m 0 矩 阵g 是对称正定的，刃l l z , ，使用并行对称多分裂方法得到的m 步多分裂预条1 ，| ： 了k 。，= g ( ，+ h + + i t ”1 ) 。是对称正定的。 1 9 j ：定邢3 2 说明了p ( ) 1 ，即a 的分裂a = g 一g t t 足 ；j j ( f i 4 l 。从j 2 1 知，a 的分裂a = g 一一g h ；m n 是收敛分裂，这就是等r p u s ) k ，有 e t = d l k l i d ( ) = 0( 3 1 8 ) g = ： 口一+ b _|口一十口；， 1 7 ， u f i 一一 d 。h 一 北， d ( 一 o g = r ，列 慨 我们现存给一些对称多分裂的例了使得( ： 1 7 ) 的g 或( ： l9 ) r ，j ( j 上l ! = 刈 称1 l i 定的，测此，使用并行剥称多分裂方法( 3 7 ) 得到f jm 步多分裂预条， 。，= g 。( ，+ + + ”1 ) 一1 是对称正定的。 设a ，：d ，己，一三，i = 1 ，k ，其中d ，= d l a g a ，) l ，是a ，的，“格下二 ( i )带状分裂：a ，= b ，一c ，在此，新昭 口， = d i a g a ，) 且b 是一个 对称带状矩阵，它包含有a ，的一些( 对称) 对角元。 ( ii )j a c o b i 分裂：a ，= d ，( 三，+ l ，) 。显然，这可以看成是特殊情况 三。= j 笔 扣一珊跏j 0 1 5 , ( 刍，一甜晶一z 一曲 一粤 ! ( ( 1 一甜) 占。+ 甜i ， 2 一珊f 0 1 【( i _ 印) 刍，+ 埘i ：】 ( iv )i c f 分裂 2 3 ：a ，= 己，己，r ，；m ，一n ，其中，是一个下三角 的m 矩阵且n ，0 。 定理3 5 设a = ( d 。) 是一个疗 对称正定矩阵，那么，存在a 的一个列角补偿 约化矩阵a 使得a 是一个严格对角占优的s t i e l t j e s 矩阵。假设a 分块如( 3 9 ) 表达。如果a 的一个多分裂( m 女，女，峨) ，：l ，k ，形如( 3 1 0 ) 、( 3 1 1 ) ， 列1 ：i = 1 ，o oo ! k ，a ，的分裂是( j ) 带状分裂或( i j ) j a c o b i 分裂。那么， m j i t ：an 勺多分裂( 肘。，。，量) ，净l ，足，使用并行对称多分裂方法( 3 7 ) 一1 8 得到的n 1 步多分裂预条件予盯。：g - ( ，+ h + + h ) 。是剥称旷定的。 证明：首先我们构造矩阵a 的一个对角补偿约化矩阵a ，而a 是一个如f n , jj “ 格剥角占优的s t i e l t j e s 矩阵： 我们先构造约化矩阵b ：( 6 。) ，使得对于i = 1 ，n ，有6 。= n 且如果d ， o ) 的流体。我们的 1 的是要找 到在速度场中，的“和流体的压力p ，使得在q 中 一l ，z ，+ ( bv ) u + v p = 厂 讲v “= 0 ( 1 2 ) 边界条件是讹，其中b 是一个给定的散度向量场。通常( 1 1 ) 和( 1 2 ) 可以写成 变分形式，这通过在( 1 1 ) 的等式两边乘上一个任意的测试速度向量。x ，在 ( 1 2 ) 的等式两边乘上一个任意的测试压力向量g m ，然后在q 上积分。这掣 肘= 瑶( q ) = q i q r ( q ) ，q 擒= o ，x = 【h j ( q ) 】7 r ( q ) = ( j 2 把 0 ，它和h ，v 无关，使得 r m l 卜 成立。 在本章的剩余的章节中，将表述如下的内容。在第二节中，我们将介绍三角 预条件技巧，并且给出一个关于预条件系统的特征值的估计。在第三节中，我制 使用预条件g m r e s 方法求解( 1 1 2 ) 的收敛速度，这里的预条件矩阵为块上三角 矩阵。最后，在第四节中将给出一些数值试验的结果，以说明我们所使用的三角 预条件子的有效性，同时将看到对于各种不同的雷诺数，使用整体稳定化后的预 条件效果和使用局部稳定化后的预条件效果的差异。 第二节特征值估计 = ! l i 本。h 我们对d i v 一稳定系统讨论 1 3 l | ，的三角预条1 ；，i ：。我们刈通常的 线性系统( 1 1 2 ) 使用这样的预条件子，并分析预条件系统的谱，给出广义特征值 的实部和虚部的界，而所估计出来的界也是和网格参数h 无关的常数，它只和一 致稳定化条件( 1 1 5 ) 中的y 、r 相关。如同在文献 1 3 中，我们在此假设( 1 1 2 ) 中的矩阵b 是满秩的。 设块三角预条件取为 3 l io一-btlo ， - ， 一j 心 m = ( - c f ) lo v f 一- 1 州b t m a m “2 l b “ 一洲；1j = 。切，0 ( b f + c ) m - ， 仫z ， 2 i 胛。v 。b 7 + 1 j 2 2 显然，预条件矩阵a m 一有凡个值为l 的特征值和”，个特征值