（计算数学专业论文）块三对角矩阵的不完全分解预条件方法.pdf

摘要 摘要 在用有限差分或者有限元方法离散p d e 方程的时候，很多的时候都产生的是 块三对角线性系统。所以对于块三对角线性系统的研究一直是一个热点，人们一 直努力使求解块三对角系统更加的快速有效。对这样的大型系统，直接解法需要 太多的存储要求，所以通常用k r y l o v 子空间迭代法求解。但是对这样的系统，逶 常并不能保证迭代法的收敛性或收敛速度很慢。为了提高迭代法的收敛速度，通 常对此系统做预条件处理。i l u 分解被认为是一种强有力的预条件技术，但是i l u 分解存在不易并行化的缺点。y u n 提出了一种新的计算块三对角m 矩阵或者h 矩 阵预条件的算法，这种方法具有天然的并行性，解决了i l u 分解不易并行化的缺 点，能有效的节约计算时间；并且在同m u ( o ) 的比较中，预条件共轭梯度法的收 敛速度也较快。 在本文中，以对称m 矩阵作为例子，这种方法被改进构造新的预条件子需 要的计算量将被证明比旧的预条件子所需要的计算量少。并且，新的预条件共轭 梯度法还将被证明收敛速度比y u n 的预条件共轭梯度法的快。定理和定理证明将 会给出。另外，y u n 提出的方法和改进后的方法还能够被推广到一般的m 矩阵和 h 矩阵，使得在构造这一类矩阵的不完全分解预条件方法的时候，能够更加快速 有效，严格的定理证明将会给出。在文章的最后，数值实验将会给出，以证明我 们的定理结论。 关键词：m 矩阵；h 矩阵：并行计算；不完全分解预条件 a b s t r a c t a b s t r a c t t h ed i s c r e t i z a t i o no fp a r t i a ld i f f e r e n t i a le q u a t i o n s ( p d e s ) i n2 do r3 d ，b yf i n i t e d i f f e r e n c eo ff i n i t ee l e m e n ta p p r o x i m a t i o n ，l e a d so f t e nt ol a r g es p a r s eb m c k - t r i d i a g o n a l i n e a rs y s t e m s t h e r e f o r e , h o wt os o v l et h i ss y s t e mf a s t l ya n de f f i c i e n t l yi ss t u d i e db y m a n ys c i e n t i s t s f o rt h i sl a r g el i n e a rs y s t e m ，d i r e c ts o l v e r sb e c o m ep r o h i b i t i v e l y e x p e n s i v eb e c a u s eo f t h el a r g ea m o u n to f s t o r a g er e q u i r e d a sa na l t e r n a t i v e , w eu s u s l l y c o n s i d e rt h ek r y l o vs u b s p a c em e t h o d i ng e n e r a l ，t h ec o n v e r g e n c ei sn o tg u a r a n t e do r m a yb ee x t r e m e l ys l o w h e n c e , ap r e c o n d i t i o n e ri sa p p l i e dt ot h i ss y s t e mt ot a n s f o r mi t t i nt oam o r et r a c t a b l ef o r m i l uf a c t o r i z a t i o ni sc o n s i d e r e dag o o dp r e c o n d i t i o n t e c h n o l o g y , b u ti l uf a c t o r i z e dp r e c o n d i t i o n e ri sd i f f i c u l tt ob ec o m p u t c di np a r a l l e l j h y u nh a sp r o p o s e dn e wi l uf a c t o r i z a t o np r e c o n d i t i o n e r sf o rb l o c kt r i d i a g o n a i h m a t r i c e sa n dm m a t r i c e s t h e s ep r e c o n d i t i o n e r sc 柚b ec o m p u t e di n p a r a l l e l t h e r e f o r et h et i m et oc o n s t r u c tt h ep r e c o n d i t i o n e r sw i l ld e c r e a s e ；m e a n w h i l et h en u m b e r o ft h ei t e r a t i o n so ft h ek r y l o vs u b s p a c em e t h o d sw i t ht h i sk i n do fp r e c o n d i t i o n e r si s s m a l l e rt h a nw i t hi l u ( o ) i nt h i sp a p e r , t om a k ea nm m a t r i xa sa l le x a m p l e ，t h i s m e t h o di si m p r o v e dt om a k ei tn e e dl e s se x p e n s eb u tm o r ee f f e c t i v e f u r t h e r m o r e , t h i s m e t h o di sp r o v e dt h a ti ss u i t a b l ef o rb l o c km - m a t r i c e sa n dh - m a t r i c e s t h e o r e t i c a l p r o p e r t i e d so ft h ep 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 ht h o s eo fb l o c ki l up r e c o n d i t i o e r s a p o p o s e db yj h f u n ，t h e ns o m et h e o r e m sa r ed r a w n l a s t l y , t h en u m e r i c a lr e s u l t so f t h em e t h o d sw eh a v ep r o p o s e da r ec o m p a r e dw i t l lt h eo l dm e t h o d st os e et h e e f f e c t i v e n e s so ft h ep r o p o s e dm e t h o d s k e y w o r d s ：m - m a t r i x ；h m a t r i x ；p a r a l l e l ；i n c o m p l e t ef a t o r i z a i o np r e e o n d i t i o e r 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：泣勇k 艮一日期：加年i ，月衫日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：三姆蕴导师签红乏鱼之乡 日期：f 年t r - y | 7 , 4 日 第一章引言 1 1 选题背景 第一章引言 随着计算机技术的突飞猛进，特别是并行计算技术和并行计算机的日益普及， 大量的科学和工程领域开始对研究的问题建立更精确，复杂的模型，并采用计算 机对这些数学模型进行高精度求解。几乎所有的学科都走向定量化和精确化，从 而残生了一系列的如计算物理、计算化学、计算生物学、计算地质学、计算气象 学等一系列学科，在世界上形成了一门计算性的学科分支计算科学与工程。 由于科学计算的重要性，世界各国都十分重视这一新领域。自从第一台电子 计算机( e n i a c ，1 9 4 6 年) 在美国问世以来，美国一直在科学计算领域处于领先地 位。即使这样，美国不少科学家还时常呼吁，要充分重视科学计算领域的国际竞 争。1 9 9 1 年美国参议院提出了“高性能计算与通讯”的议案( 简称h p c c 议案) ， 以确保美国在高科技的优势地位和竞争能力。之后美国有推出了a s c i 计划，将达 到完全用计算机模拟核试验。 总所周知，许多实际问题都归结为求解一个大型稀疏线性方程组，在多介质 辐射流体力学熟知模拟和辐射输运模拟计算中，大型线性代数方程组的求解的计 算量占总计算量的9 0 以上。在这些学科课题中产生的大型稀疏线性方程组他们 的阶数一般都是几万阶，几十万阶，甚至上百万，千万阶。对于这些方程组，直 接解法要求大量的运算和存储空间，现今的计算机性能还达不到这种要求，从而 我们通常不使用直接解法。而是采用迭代方法求解，而如果用一般的迭代法进行 求解其收敛速度太慢，甚至不收敛。所以求解稀疏线性方程组越来越成为科学研 究的瓶颈，这样迫使我们对这样的方程组寻找更有效的求解方法。于是为了减少 迭代时间我们首先对系数矩阵进行预处理，使得线性方程组的稀疏矩阵的谱相对 集中，之后利用迭代法进行求解。通过对线性方程组的预处理，减少了迭代次数， 提高了算法求解的速度，可以节约大量的时间，将大大加速和推动科学计算和工 程学科的研究工作。 预条件这一概念首先是由美国著名学者提出，随后c o n c u s ，g o l o u b 和o l e a f y 电子科技大学硕士学位论文 等著名科学家进行了深入研究并将其应用到科学计算中，是科学计算的重大突破。 此后，该技术引起了国内外学多学者的关注，并被大量应用于科学计算，计算物 理、计算电磁学、计算地质学、经济学、最优控制理论等等相关领域。我们可以 确认，大规模线性方程组的迭代解法及其预处理技术的研究在科学工程计算和国 防建设中有着重要的理论价值和广阔的应用前景。 1 2 迭代法简介 迭代法一般有定常和非定常两类，定常的经典迭代法，如我们熟知的j a c o b i 迭 代，g u a s s s e i d e l 迭代，松弛迭代法等等，尽管数学形式比较优美，但是有严重的 缺陷，比如收敛参数缺乏充分的一般性，并且难于确定。近几年来，产生了一些 新的定常迭代，如g o h b 和白中治研究员针对非h e r m i t i a n 正定线性方程组提出p s s 迭代方法等。非定常迭代主要是指k r y l o v 子空间方法等方法。 k r y l o v 子空间方法是强有力的解大型稀疏线性方程组的算法，特点是对于一些 问题例如二维三维的数理方程导出的线性方程非常有效。k r y l o v 子空间方法是一 种非定常迭代法。对于以阶线性方程组 a x b ，( 1 2 1 ) 其中a 是大型稀疏非奇异方阵。设初值为，定义r o - b 一钒为残量。用k r ) ，1 0 v 子空间方法迭代m 步产生坍维的k r y l o v 子空间j 0 ，) - s p a n ( r o ，爿r 0 ，爿”1 ，0 ) 和 近似解x e x o + 五乙并满足p e t r o v g a l e r k i n 条件 k 上l ， 其中乙是一个m 维的子空间。k r y l o v 子空间方法的本质就是在( 仿射) k r y l o v 子 空间上寻找满足性质近似解的迭代法，不同的k 产生不同的算法。当t - a 繇时 产生最小二乘类算法，例如g r ，g c r ，g m r e s ，o r t h o d i r 等等。这些算法都 是使近似解的剩余2 一范数极小。当选取l e 则可导致一类g a l e r k i n 型算法， 例如c g ，f o m ，o r t h o r e s 算法等等。k 还可以选定其他子空间，例如 ，坩7 ，0 ) ， 鼢7 ，a ，a 7 r o ) 等等并且建立相应的算法。从数值稳定性，健壮性，并行性，存储 2 第一章引言 量，计算量等等方面考虑，c g ，b i c g s l a b 和g m r e s 法是值得推荐的。 c g 法运用于对称正定线性方程组，有许多种变形算法，一个较一般的预条件 c g ( p c g ) 算法可以表示为 x o 一0 ，号一r o ；b ，届；0 ，k 一1 , 2 ， 解方程组 纪r 1 - r x 1 ， 黟k - ( z k - l ，k - 1 ) ( ，k - 1 ，r x 1 ) ， p i z x 4 + p x p x - t ， 哝- ( z 。- 1r x 。) ( 巴，a 名) ， k r x 1 一必。 当k i 满足某种条件，则停止。这里当m ；j 时，就是古典的c g 方法。 从p c g 算法的收敛性我们知道 定理1 2 1 【5 ，p 1 8 7 i i x , - x 1 1 舞卜。l | ， 这里r k ( m - 1 - 4 ) 1 k ( m - 1 彳) ，a h ( m 一) 和k 。( m 一) 表示m 一的最大和最 小特征值。 下面我们简单介绍一下预条件b i c g s t a b 算法 1 4 1 。 3 电子科技大学硕士学位论文 选定一个初值而一0 ，晶一r o - b a x o ； 选择一个i ，使得( i ，r o ) 一0 ，i c ，r o 一； 对i 1 0 ，1 , 2 ，解k q , ；p t ；令h 一4 q ； 呸z 磊，r , ) c o ，h ) ；墨一一q u ； 解r t , 一墨；u t - a t , ； w s 一 ，墨) ，吨) ； 五+ i - 五+ q 吼+ m 岛r t + l _ 墨一m “f 5 当1 1 r , 。i i l l b it f ，则停止； 否则屈= ( 岳，。) 佤，吩) ) ( q w f ) ； p t + 1 1 r t + 1 + 3 a p , 一m 畸) ； 1 3 预处理方法简介 1 3 1 预条件方法的简介 通常，我们在使用k r y l o v 子空间法的时候，我们并不总是能保证其收敛或者 其收敛速度特别慢，这时候我们就需要对原系统进行处理来降低它的条件数，使 它的谱相对集中，从而加快迭代的速度。所以，我们将构造一个易于求逆的矩阵p 使原问题转化为 p 。1 4 x t p 一协 4 ( 1 3 1 ) 第一章引言 而矩阵p 。1 爿具有较好的条件数。( 1 3 1 ) 我们可以称之为左预条件。相应的我们也 可以右预处理系统( 1 2 1 ) 使之成为如下等价形式 a p y = b 其中y p x 。这样的矩阵p 我们称为预条件矩阵或者预条件子。有数学家还提出 了分裂预条件，即 耳迎1 y 一耳1 6 ，x = 只- 1 y ， 这里的预条件子是p - 耽。 ( 1 3 2 ) 我们引入预条件矩阵的目的在于减少迭代次数，最终的目的在于减少运算时 间。当然如果能并行计算预条件矩阵，那么效果将会更好。不完全l u o l r 0 分解方 法是常用的构建预条件矩阵的方法， 1 3 2 预处理方法的类型 近几年来，国内外所采用的预处理技术及主要迭代有： 1 稀疏近似逆方法( s a d ：稀疏近似逆预条件子是一类应用时具有天然并行 性的方法。已有证据显示这类预条件子可解一些i l u 预条件子难以求解的问题。 这种方法大体分为三大类： ( 1 ) 基于对a m 。i 近似求解来构造稀疏近似逆，一般归结为求解以来某种稀 疏性的约束的f r o b e n i u s 范数极小化的最优问题： ( 2 ) 基于分解的s a i ，现有f s 舢，a i n v 和s a i n v 等形式，这些方法的缺点 在于此技术的的实现依赖于一个稀疏模式，并且一般稀疏矩阵没被很好的研究。 ( 3 ) 基于i l u 分解的s a i 。这种算法通过系数矩阵的不完全l u 分解因子构造 其稀疏近似逆。 5 电子科技大学硕士学位论文 2 对角尺度化( d i a g o n a ls c a l i n g ) 预条件子：对比较病态的稀疏矩阵的方程组， 如一般二维椭圆型方程组的差分方程，其稀疏矩阵往往是弱对角占优。为此常常 采用对角尺度化预条件方法来增强对角优势获得好的收敛效果。 3 不完全分解方法( i l u ) ：计算线性系统的不完全分解预条件时，同常是在 用高斯消元法对系数矩阵进行分解过程中，用某种方法去除在此过程中产生的填 充，这样我们将会得到简单和有用的预条件矩阵p 三疗，这里三和d 是系数矩阵 的不完全( 近似) 分解因子。所谓填充就是在系数矩阵的分解过程中，在系数矩 阵的零元素位置出现了非零元，这样就增加了我们的存储空间。填充的去除方法 主要有几种标准：通过填充的位置，数值大小和同时使用位置和数值大小两种方 法。 我们用n x n 来表示系数矩阵a 中的所有元素的位置，n = l 2 。m 。我们首先 固定一个雄，l 的子集p ，通常我们选择p 是主对角和4 d _ o 的位置。l u 因子中的 填充只有在位置属于p 的时候我们才被保留。我们可以用一个简单的式子来表示 这么一个不完全分解过程： 驴r 荨魏嬲( i , j ) 硭e p p 这种选取填充的方法我们称为i l u ( o ) 。 ( 1 3 3 ) 第二种去除填充的方法是通过填充的数值大小。我们首先固定一个正数f ( a d r o pt o l e r a n c e ) 如果产生填充的绝对值大于f ，那么我们保存它。例如，当我们在 消去第i 行的时候，如果它的绝对值大于f0a ；i i ：，那么我们保存它，a i 表示4 的 第i 行。这种方法的这种方法的缺点是我们无法事先选择一个好的f 。另一个困难 在于我们无法预测我们需要多少空间来储存不完全分解的因子。 为了解决上述问题，$ a a d 在【6 】中提出了双重标准，这就是第三种方法固定一个f 和p ， p 表示在不完全分解因子工和c ，的每行中允许的的填充数。在每一步消元过程中，去掉那些 小于f0a ；l i ：的填充；对所有的保存下来的填充，我们从大到小最多保存p 个。我们表示这 种方法得到的预条件矩阵m u t ( z ，p ) 6 第一章引言 1 3 3 块三对角矩阵的块不完全分解预条件 对于形如 a = 马c 1 日口2 0 e 2 00 0o c 2 0 b 3 0 0 b 产生在很多的差分p d e 方程中，对它的块不完全分解预条件，主要使用以下方法： 1 令z l - b 1 且z 1 是z i l 的一个近似； 2 i l 2 ，n ，计算 z i - b j e l x “c l - l ； 3 令z ；是z , - 1 的近似； 4 令x 是z 。的近似。 这样4 的块不完全分解预条件定义如下： p = x 0 易l 0 e 2 00 0 0 0 0 e 0 ： 0 k ，k - 1 c 1 o， oo 0o o y ；l c 2 ， o o 0 0 ： j 第1 步的近似和最后一步的近似方法的不同，也可以相同近似z i l 的时候要注 意保持这个s c h u r 补的稀疏性，这些近似的不同可以产生不同的算法。 7 电子科技大学硕士学位论文 1 4m 矩阵和h 矩阵简介 m 矩阵在均衡论、投入产出分析和增长模型的研究中产生。而在控制论及神 经网络大系统的稳定性，线性时滞系统的稳定性研究中产生了h 矩阵。而近年来 h 矩阵的研究成为了计算数学的一个热点。 定义1 2 1e 1 0 1 设彳一心) r ，若4 可以表示为a = s i - b ，其中b ，0 ，则 当5 p ( b 1 时，称a 为非奇异m 矩阵，简称m 矩阵；若a 满足 a h 主0 1 f _ 歹s 珂， 则称4 为z 矩阵；若a e z 且满足 a h 0 ，i l 2 , ， ， 则称彳为l 矩阵。现在我们给出h 矩阵的定义。 定义1 2 2 a o l 设彳= 0 “) r ，设d = d i a g “，) ，c = d - a ，则称矩 阵l d i _ i c i 为爿的比较矩阵，记为( a ) ：即 ( 爿) 兰 i 口，。l i 。：i 一l a 。 一l a ：，i1 4 。l 一l a ：。 一l a 。i k ：i “k l 若( a ) 时非奇异的m 矩阵，则称彳为非奇异的h 矩阵，简称h 矩阵。 1 5 本文的主要工作 在用有限差分或有限元方法离散2 维或者3 维偏微分( 椭圆) 方程时，常常产生 大型的稀疏块三对角线性系统在本文中，我们将研究线性系统： a xt b ，x ，b r 4 ， 8 ( 1 4 1 ) 第一章引言 其中a 是大型稀疏块三对角h ( 或m ) 矩阵。a 具有这样的形式： a = bc l e lb 2 0e 0o o0 c 2 0 岛0 0 以 ( 1 4 2 ) 我们假定a 的对角块且都是方阵，且维数相同。因为a 是一个大型稀疏矩阵，那 么直接解方程组( 1 4 1 ) 需要巨大的运算量和存储空间，这样的花费很大，所以 我们常常采用k r y l o v 子空间方法进行求解，比如：共轭梯度法( c g ) ，g m r e s ，q m r 和b i - - c g s t a b 等方法。我们引入系数矩阵的预条件子从而减少迭代次数，最 终的目的在于减少运算时间。当然如果能并行计算预条件矩阵，那么效果将会更 好。不完全l u ( i l u ) 分解方法是常用的构建预条件矩阵的有效的方法。它的缺点在 于不易并行化。但是在文章在【1 、1 1 、1 2 、1 3 】中y u n 提出了一种并行计算块三对 角矩阵预条件的方法，这种方法我们将在第二章详细介绍。我们在此基础上对这 种方法进行了改进使之运算量更小速度更快。 9 电子科技大学硕士学位论文 第二章块三对角对称m 矩阵的并行不完全l u 分解预条件方法 2 1 对称m 阵的不完全分解 对于m 矩阵和h 矩阵我们总能保证它们的不完全分解的存在性，并且对于对 称的m 矩阵如下定理成立。 定理2 1 1 ( j a ch c o ny u n 1 1 如果a 是对称m 矩阵。对任意的稀疏结构p ， 都存在上三角矩阵u 一 d ) ，对角元是_ 1 的对角矩阵d 和矩阵r 一心) ，则 一一u 7 d u r 是a 的正规分裂且u 也是m 矩阵。 定理2 1 2 ( j a eh e o ny u n 【1 】) 如果a 和b 都是n x n 对称m 矩阵，设 a u 1 r d 。u 。一r ，和b u 2 r d ：u ：一r 2 是相应于相同的对称稀疏模式p 的不完全 分解。如果a s b ，则u 2 一墨u 1 r d 2s d l 。 定理2 1 3 ( r o g e rah o r n ，c h a r l e sr j o h n s o n 【3 ，p - 1 1 4 ) 设4 是z 矩阵。如果 a l u ，这里下三角矩阵u 上三角矩阵且所有的对角元都是正的，则彳是肘 矩阵。 定理2 1 4a 是上( 下) 三角z 阵。如果a 的对角元是正的，则a 是m 阵。 证明我们从定理2 1 4 得到了2 1 3 。 定理2 1 5 ( r o g e r a h o m ，c h a r l e sr j o h n s o n 【3 ，p - 1 1 7 ) 如果4 是一个m 阵，口 是一个z 阵。若a 墨b ，则b 是一个m 阵，且b 。1s a 一。 定理2 1 6 ( a x e l s s o n 【4 ，p 2 1 9 】设彳一墨一1 一k 2 一2 都是4 的正规分裂。 如果k 2 。1k l 一，则 p ( k n 1 ) sp ( k 2 n 2 ) 。 这里p ( 匠1 川) 表示k 4 n i 的谱半径，i 一1 ，2 。 1 0 第二章块三对角对称m 矩阵的并行不完全l u 分解预条件方法 2 2 对称块三对角m 矩阵的并行不完全分解预条件方法 在 1 l e e ，j a eh e o n y u n 提出了方程组 a x b ，x ，b e r “， 的并行块i c 分解预条件子，其中a 是一个大型稀疏对称块三对角m 矩阵并具有 以下的结构 4 薯 岛 一 0 ； 一c 1 1 b 2 一 ： oo 且给出以下的定理。 oo 一气0 b 0 0 e ( 2 2 1 ) 定理2 2 1 ( j a eh e o n y u n 【1 1 ) 设a 是一个大型稀疏对称块三对角m 矩阵如 ( 2 2 1 ) 且e u i r d , v ；一r i 是尽的一个正规分裂。b i 的一个正规分裂可以通过 对且的不完全分解过程得，f = 1 ，2 ，n 。假设岛满足u t 7 q 置主cse j ， i = 1 ，2 ，万一1 。令 d u d 1 0 0 d 2 00 ： o0 o0 o o d 3 0 0 见 矾一c l 0 0 u 2 一c 2 00 u 3 o0o 0 0 0 ： u 。 ，ut 1 1 u 1 00 ou 0 00 u 3 oo0 0 0 0 ： u 。 电子科技大学硕士学位论文 【，= u u - e 1 0 u 2 0o o0 o 0 一e 2 0 乩 0 0 以 u p j d i ) 4 c 。 0 u 2 0o 0o 0 一( u ；d ：) 。1 c ： u 3 0 0 0 0 ： u 。 m u 7 d u ，牙。扩7 d 扩，詹，d 7 d 疗和麝s 疗7 d 扩。那么以下的结论成立： ( a ) r m 一一o , r 一一m 一一a 2 0 ，j 圣z 竹一a 芝0 ，且蠢。m 一a 0 ， ( ”0 s u 一1s 扩一1s d - 1s d ， o c ) 0 s m 。1s j i 歹一1 蔓詹一1s 詹一1 ， ( d ) a m r面一面_ 詹一矗- 露一蠢都是彳的正规分裂， ( e ) p a 西一1 r ) 蔓p ( 腑一1 尺) 皇p ( 厅一1 r ) p ( m 一1 r ) 1 。 j a eh e o ny u n 的这四种i c 分解预条件子可以通过并行计算得到。块i c 分解 预条件子厨都不会被应用到实际的计算中去因为它要求保留太多的填充元素，这 样就要求巨大的存贮空间和运算量。块预条件m 是最具有并行性的预条件子，因 为无论是计算m 还是将它应用到p c g 中都可以并行计算。但是对是四种预条件子 里面效果最差的，因此我们推荐肪。在文章【1 】中证明应用僻+ 1 ) 块预条件子的p c g 迭代算法比应用k 块预条件子的p c g 迭代算法收敛速度更快，其中k 表示分解时， 分解的块为k 个皿的大小，见【1 】。因此k 越大，p c g 迭代算法收敛更快。但是k 越 大，【，7 d 的阶越大，因此计算u 7 d 的逆越复杂，花费越大，从而增加了迭代的时 间。这是这个算法的不足，为了弥补其不足，我们提出了以下的改进。 1 2 第二章块三对角对称m 矩阵的并行不完全l u 分解预条件方法 2 3 对称块三对角m 矩阵的并行不完全分解预条件算法的改进 引理2 3 1 设a 是对称块三对角m 矩阵，其具有形式 爿，f 苎， _ l 1 ( 2 3 1 ) 令b ；u i r b u ；一r i 是皿地正规分裂，这样地分裂可以通过马的不完全c h o l e s k y 分解得到i = 1 ，2 ，其中分解的稀疏模式设为p c 只。并且令彳一v 7 却一r 是爿的正 规分裂，它也可一通过对彳的不完全c h o l e s k y 分解得到，其中分解的稀疏模式也 为p c 只，这里v r 1 葛1 ) ，6 一( 正d ：) 。令u 。( 譬曼) ，。2 ( 0 三) ， 球；( l 。芝) ，d4 ( d 1d ：) 。那么我们，可以得至u “s u 和d = 。a 证明令丑一( 且丑：) 。因为4 是一个m 矩阵，所以口也是一个m 矩阵我们 能够容易的发现 一7 出一，和b 。u 7 d u 一豆 都是相应于同一个稀疏模式p 不完全c h o l e s k y 分解。由定理2 1 4 ，us u 和d 苫d 。 因此我们能得n u l u l ，2 u 2 ，d l2d 1 和d 2 苫d 2e 撑 为了证明我们改进后的算法不仅克服了已有算法的缺点并且比以前的算法收 敛速度更快，我们首先考虑对以下相对简单形式的对称块三对角矩阵的块i c 分解 4 i 皿 一c ： 0 o 我们令 一c 1 b 2 一c 2 7 o 0 一c 2 岛 一c 3 7 0 0 一g b 电子科技大学硕士学位论文 岛一舻怯 因为爿是一个m 矩阵，卢。和卢：都是对称m 矩阵。从i c 分解过程中，我们发现 上三角矩阵1 ，；，对角矩阵d ，和矩阵使得肛= v 。t d ；u 一是尼的一个正规分裂 i 一1 2 ，见定理2 2 1 。如果彳一k 一是爿的一个分离且置是一个容易求逆的对 称正定矩阵，那么k 就能够作为p c g 算法的一个预条件子。预条件子k 的有效性 取决于k 对于a 的近似程度。 定理2 3 1 设a 是一个对称块三对角m 矩阵，且具有形式( 2 3 2 ) 。相应于稀疏 模式p c 只，令 i v ? 6 y t r ； 是屈的从不完全a m 蛔k y 分解得到的一个正规分躲协这里u 。( h 艺1 ) ， ，z ( 3 葛3 ) ，a ，2 ( d 1d ：) 和6 ：。( d 3d 。) 。假设q f f z k , s qs t 7 d t ，4 c z ， i 一1 ，3 。其中e i 是从 ；7 以) 4 e 去掉了一些填充元素而得到。令 = “l “l 一( u l r d l ) 一1 c 1 u 2 “1一e l i t 2一e 2 u 3 一( u a r d 3 ) 4 c 3 4 历一万7 d e 和旃一五7 砝。那么以下的命题成立： ( a ) ，一旃一a o 且f 一痢一a 乏0 ， 1 4 第二章块三对角对称m 矩阵的并行不完全l u 分解预条件方法 ( b ) 0 - ：t h 。1 历， ( c ) a 一，；l 一，一历一，都是a 的正规分裂， ( d ) p o 话一1 ，) s p 一1 豆) s p 一1 孟) gp 何一1 两p 一1 尺) c 1 ， ( e ) p ( 孑- 1 孟) sp ( 旃- 1 0 s 1 。 这里m ，牙，詹和詹是由定理2 2 1 所定义。我们通过去掉( u ；7 b ) 。1 c i 中的一些填 充得到互使得它具有和e i 一样的稀疏模式。 证明首先我们证明( a ) ，通过计算我们可以得到： ，_ u t r d l “lc 1 - c 1 r u c 2 1 r r d “1 2 - l u d 21 + “1 4 c l 0 0 b c ： 一c 1 b 2 一c 2 7 “1 7 d 1 l b 1 0 一c 2 7 o 0 一c 2 u 3 r d 一3 + c 2 r 2 - i d 2 - 1 “2 - r c 2 一c 3 7 去- c 2 苫，l 丑3一c 3i c 3 7以j 00 00 o 0 0 o c 3 u 4 r d 4 u 4 + c 3 r “3 - 1 d 3 - 1 3 - t c 3 u 3 r d 3 h 3 一岛+ c z r 2 - 1 d 2 - 1 h 2 - t c 2 0 因为屈，f 6 ，吩一是尼的正规分裂，i = l ，2 ，之0 。因此 0 0 o u 4 r d 4 h 4 一b 4 + c 3 r m 3 - 1 d 3 - 1 “3 - t c 3 电子科技大学硕士学位论文 且 ( 譬。”坩1 。f i 即- ，c - 叫，o - 七-1 芑o l c l 7 k x r d l “1 七1 7 d 乒l + “2 r d 2 球2 一b 2 厂。 一舻川3 艺2 ) ：f ”咖，。，c 3 一，勺，后z1 之o 。 i c 3 7 一k 3 r d 3 “3k 3 7 d 3 k 3 + 比z d 4 “4 一b 4j 。9 因此我们知道 则 c 1 一1 7 d l k l 苫0 和c 3 一u 3 t d 3 k 2 之0 。 k 1 7 d l k lsc 1 7 “1 - 1 d l - l u l - 7 c 1 i jk 3 r d 3 k 3s c 3 7 u 3 - 1 d 3 - 1 u 3 - t c 3 。 因为不等式( 2 3 4 ) 和( 2 3 5 ) ，以下的不等式成立： ( i ) “1 r 讯一最之0 ， ( i i ) u 3 r d 3 u 3 一岛z o ， ( i i i ) k ：d 矗+ u ：d i b ：0t ( i v ) k 3 r d 3 k 3 + 4 r d 4 h 4 一b 4 乏0 。 因为不等式( f i i ) 和( i v ) ( 2 3 4 ) ( 2 3 5 ) r r 2 也咕 ，fi_l_ 第二章块三对角对称m 矩阵的并行不完全l u 分解预条件方法 且 c l r “l l d l - 1 l l - t c l + “2 r d 2 “2 一b 2 0 c 3 7 “3 - 1 d s - 1 3 - t c 3 + 口4 t d 4 球4 一b 42 0 ， 因此f 2 0 。通过计算 r 一 “1 7 d l 一马 c 1 7e l r d l 1 0 o c 1 一“1 7 d l e i u 2 r d 2 u 2 一岛+ e 1 7 d 1 8 l c 2 一u 2 r d 2 8 2 0 o c 1 一u l r d l e l 0 0 h 3 ：d 3 “，一b 3 + c 1 - - u l f d l e l e 2 。d 2 e 2 c 3 - u 3 t d 3 e 3 u e 3 4 r r d d 3 4 e u 3 4 - 占1 因为k is e 蔓o i td j ) 一1 c j 和( 2 3 4 ) 署1 1 ( 2 3 5 ) ，我们容易的得到，0 。 和 下面我们证明( b ) 。我们计算牙的逆。通过简单的计算我们得到： 厅- 1 曩 u 1 - 1 ( u l r d l ) 。1 c l u 2 - 1 2 d 2 ) c 2 “3 4 u 2 - 1 2 d 2 ) 1 c 2 u 3 。1 “3 0 u 1 - 1 ( u l r d l ) q c z u 2 i 2 d 2 ) - 1 c 2 “l - | u d 1 ) 1 q 甜2 _ 1 , 2 - 1 ( u 2 r d 2 ) 一c 2 u 1 - 1 ( u l r d l ) 4 c x u 2 。1 u 3 - 1 ( u 3 r d 3 ) 4 c 一4 。1 u 4 - 1 1 7 0 d 叱 c 啪o o r “ do 0 o “ 电子科技大学硕士学位论文 则 一1 l 0 0 o u l - l e l u 2 - 1 e 2 u 3 - 1 “l - l e l 2 - * e 2 u t - l e c l t t 2 1 u 2 e 2 u 31 2e 2 u le 1 “2 “3h 3e 3 4 0 u 4 1 历一1i 牙一1 d 一1 疗一f 苫0 且，瘫一- 五一1 d 一1 瞎一r 0 。 因为e fs i 7 d i ) c t ，豌一1s 历一。 苫0 ， 由于( a ) 和( b ) 成立，那么( c ) 很容易被证明。因为a 是一个m 矩阵且爿一扁- r 一m “一， 都是a 的正规分裂，我们很容易可以看出p 。1 力 1 和p 何- 1 ，) 1 。由定理2 1 6 ( d ) 可以被证明。 众所周知，在m 阵的不完全c h o l e s k y 分解过程中，所有的上三角元素都在减 少。由引理2 3 1 我们发现啦；u 。和以芑d i 。因为d , 币f l d ；都是正元素的对角矩阵 _ r u 。和都是m 矩阵，则峨7 d ；s u f d l 。我们知道7 d ；和以7 4 都是上三角z 阵 且他们的对角元都是正数。由定理2 1 4 ，“；7d j 和u 。7 b 都是m 矩阵。由定理2 1 5 ， 。7 d ；) 4 之( u 。7 d ；) 一。因此 一( u l r d f ) 一1 c is u i t d j ) 。1 c i ， 则u u 。因为“和u 都是上三角的z 阵且它的对角元都是正数，由定理2 1 4 ， “和u 都是m 矩阵。我们得到“- 1 之u - 1 ，则我们可以计算历一；f i - 。d - 1 牙。和 詹。疗4 d 4 疗。这个计算繁复但是不难，我们在这里不再给出它的表达式。通 过计算我们得到扁一1 厨- 1 。而且由于彳，历一，一露一意都是a 的正规分裂且 扁4 2 詹一由定理2 1 6 ， p ( 历4 ，) sp ( 厨。1 j i ) c 1 。 那么由定理2 2 1 ， 1 8 叩o o 一 第二章块三对角对称m 矩阵的并行不完全i j u 分解预条件方法 p ( 历一1 f ) s p a 污- 1 厦) sp ( r - 1 詹) sp ( 面- 1 豆) s p ( m - 1 r ) 1 。 从( d ) 的证明中我们发现一 。7 4 ) - 1 c i 墨一( u j 7 d j ) 一c ；。所以我们得到一e ；量e ；， 因此旃一1 七砑。并且由于4 。旃一，- 詹一矗都是a 的正规分裂且历- 1 2 詹，由 定理2 1 6 ，p 一1 ，) p 1 j 圣) t 1 。这样我们完成了( c ) 的证明。撑 我们将以上的预条件子命名为2 块预条件。定理2 3 1 可以很容易的推广到一 般的对称块三对角m 矩阵的预条件子。 例2 3 1 ：令 彳耳 4 4 - 3 0 8 3 0 4 3 4 7 9 o - 5 3 6 通过计算我们得到 m m o o 一9 7 7 0 0 2 9 8 o 0 6 2 1 2 0 3 0 - 5 0 1 2 6 4 1 8 4 3 6 2 9 o 1 8 6 8 3o83 0 4 790 5 97 7oo o0 6 3 6 5 506 58 5 5 3 62 9 1 29 - 3o一8- 3 0- 4 4 7905 3 6 9 7 7 o0 2 9 o06 2- 1 21 2 5o- 1 26 41 7 3 62 91 21 76 8 4 3 6 2 9 1 2 9 1 1 3 7 舛。o矗捌4钳。o墙4 电子科技大学硕士学位论文 p ( 露一1 豆) = 0 9 6 6 5 和p ( 历一1 f ) 一0 3 9 0 8 。 另外，我们思考具有形式( 2 2 1 ) 对称块三对角m 矩阵的并行块i c 分解预条 件子。把定理2 3 1 推广到形式( 2 2 1 ) 的对称块三对角m 矩阵是很容易的，但是 很繁复，因此我们在这里没有给出证明。 定理2 3 2 令a 是具有形式( 1 ) 的块三对角m 矩阵且令屈一吩6 ；u 一是从不 完全c h o l e s k y 分解得到的屈的正规分裂，i 一1 , 2 ，n 2 。这里我么假设厅是偶数。 令v ；。( “- l 一乏1 ) 和6 。( d 搿。1d 。) 。假设e ，是满足t s eg t 7 d ，4 c ，的矩阵 i = 1 , 2 ，n 2 。令 墨 。一 j 西) 4c l 0 “ o0 00 如一g l 0 u 2 00 ： oo 0 一 ；d ：) c ： 耻3 o 0o e 2 0 u ， 0 0 “。 而t 疗7 d f f 和旃。五7 掘。则下列命题成立： ( a i )