（计算数学专业论文）求解抛物及双曲方程若干差分格式的加速迭代并行算法.pdf

兰州大学硕士学位论文求解抛物及双曲方程若干差分格式的加速迭代并行算法 摘要 随着电子计算机的发展，偏微分方程的数值解法也得到了巨大的发展。差分 方法是一种求解偏微分方程的主要方法。众所周知，显式差分格式有理想的并行 性，适合于并行计算，但是它多为条件稳定，尤其是在处理高维问题时经常受到 限制。一般隐式差分格式是绝对稳定的，但每个时间层上需求解线性方程组。 本文的第一部分首先针对抛物型差分方程的紧格式，构造了加速并行迭代算 法，这种算法是对紧差分格式的线性方程组的系数矩阵进行分裂，然后对每个子 方程组进行分别迭代求解，本文证明了算法的收敛性以及在网格加密时的收敛性 质。接下来对于二维抛物型方程的紧交替方向隐格式，构造了加速并行迭代算法。 本文的第二部分主要是针对双曲型偏微分方程，本文以波动方程的初边值问 题为例，构造了古典隐式差分格式和紧差分格式的加速并行迭代算法。对于二维 双曲型偏微分方程，本文以隐式交替方向差分格式为基础，构造了加速并行迭代 算法。 本文最后进行了数值试验，数值试验的结果与理论分析的结果一致，证明了 算法的有效性。 关键词：有限差分，紧格式，交替方向隐格式，加速并行迭代算法，渐进收敛 性质 兰州大学硕士学位论文 求解抛物及双曲方程若干差分格式的加速迭代并行算法 a b s t r a c t w i t ht h ed e v e l o p m e n to fc o m p u t e r , n u m e r i c a ls o l u t i o nf o rp a r t i a ld i f f e r e n t i a l e q u a t i o n sh a sa l s ob e e nah u g ed e v e l o p m e n t d i f f e r e n c em e t h o di sap r i m a r ym e t h o d f o rs o l v i n gp 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 a sw e l lk n o w n ，t h ee x p l i c i td i f f e r e n c e s c h e m ei ss u i t a b l ef o rp a r a l l e lc o m p u t a t i o n ，b u ti th a st h el i m i t a t i o no fs t a b i l i t y , a n di t i so f t e nr e s t r i c t e de s p e c i a l l yi nt h et r e a t m e n to fh i g h - d i m e n s i o n a lp r o b l e m s t h e i m p l i c i td i f f e r e n c es c h e m ei sa b s o l u t e l ys t a b l eg e n e r a l l y , b u ti ti sn e c e s s a r yt os o l v e d i f f e r e n tl i n e a rs y s t e m sa te a c hl e v e lo ft i m e i nc h a p t e ro n eo ft h ep a p e r , w ec o n s t r u c tap a r a l l e la l g o r i t h mo fa c c e l e r a t i v e i t e r a t i o nf o rs o l v i n gc o m p a c ts c h e m eo fo n e - d i m e n s i o n a lp a r a b o l i cd i f f e r e n t i a l e q u a t i o n s a tf i r s t w es p l i tt h ec o e f f i c i e n tm a t r i xo ft h el i n e a rs y s t e m s 、析t hr e s p e c tt oa c o m p a c td i f f e r e n c es c h e m e ，a n dt h e nw eu s ei t e r a t i v em e t h o d st o s o l v et h e s u b s y s t e m s o n eb yo n e t h ec o n v e r g e n c eo ft h ea l g o r i t h ma n dt h ep r o p e r t yo f a s y m p t o t i cc o n v e r g e n c ea r ep r o v e d f o rt h et w o d i m e n s i o n a lp a r a b o l i cp a r t i a l d i f f e r e n t i a l e q u a t i o n ，w ed i s c u s st h ec o m p a c ta n da l t e r n a t i n gd i r e c t i o ni m p l i c i t s c h e m e t h ep a r a l l e la l g o r i t h mo fa c c e l e r a t i v ei t e r a t i o ni sc o n s t r u c t e d i nt h ec h a p t e rt w o ，w em a i n l ys t u d yt h eh y p e r b o l i cp a r t i a ld i f f e r e n t i a le q u a t i o n t h ei n i t i a la n db o u n d a r yv a l u ep r o b l e mo ft h ew a v ee q u a t i o ni su s e da sa ne x a m p l et o c o n s t r u c tt h ep a r a l l e la l g o r i t h mo fa c c e l e r a t i v ei t e r a t i o nw i t hr e s p e c tt ot h ec l a s s i c a l i m p l i c i td i f f e r e n c es c h e m ea n dt h ec o m p a c td i f f e r e n c es c h e m e t h e nt h ea l t e r n a t i n g d i r e c t i o ni m p l i c i ts c h e m ea n di t sp a r a l l e l a l g o r i t h mo fa c c e l e r a t i v ei t e r a t i o n f o r t w o d i m e n s i o n a lh y p e r b o l i cp a r t i a ld i f f e r e n t i a le q u a t i o na r ea l s od i s c u s s e d t h en u m e r i c a le x a m p l e sa r ec a r r i e do u ta tl a s t t h er e s u l t so fn u m e r i c a l e x a m p l e ss h o wt h a tt h ea n a l y s i si sc o r r e c ta n dt h ea l g o r i t h mi sf e a s i b l ea n de f f i c i e n t k e yw o r d s ：f i n i t ed i f f e r e n c e ，c o m p a c ts c h e m e , a l t e r n a t i n gd i r e c t i o ni m p l i c # s c h e m e , p a r a l l e la l g o r i t h mo f a c c e l e r a t i v ei t e r a t i o n ，p r o p e r t yo f a s y m p t o t i cc o n v e r g e n c e 原创性声明 本人郑重声明：本人所呈交的学位论文，是在导师的指导下独立 进行研究所取得的成果。学位论文中凡引用他人已经发表或未发表的 成果、数据、观点等，均已明确注明出处。除文中已经注明引用的内 容外，不包含任何其它个人或集体已经发表或撰写过的科研成果。对 本文的研究成果做出重要贡献的个人和集体，均己在文中以明确方式 标明。 本声明的法律责任由本人承担。 论文作者签名： 祧 日期： 关于学位论文使用授权的声明 本人在导师指导下所完成的论文及相关的职务作品，知识产权归 属兰州大学。本人完全了解兰州大学有关保存、使用学位论文的规定， 同意学校保存或向国家有关部门或机构送交论文的纸质版和电子版， 允许论文被查阅和借阅；本人授权兰州大学可以将本学位论文的全部 或部分内容编入有关数据库进行检索，可以采用任何复制手段保存和 汇编本学位论文。本人离校后发表、使用学位论文或与该论文直接相 关的学术论文或成果时，第一署名单位仍然为兰州大学。 保密论文在解密后应遵守此规定。 论文作者签名：捣师签名： 兰州大学硕士学位论文求解抛物及双曲方程若干差分格式的加速迭代并行算法 l 引言 现代科学、技术、工程中的大量数学模型都可以用微分方程来描述，很多近 代自然科的基本方程就是微分方程。遗憾的是，绝大多数微分方程( 特别是偏微 分方程) 定解问题的解不能用实用的解析形式来表示。这就产生了理论与应用的 矛盾：一方面，人们列出了反映客观现象的各种微分方程，建立了大量使用的数 学模型；另一方面，人们有无法得到这些方程的准确解以及定量的描述客观过程。 随着电子计算机的出现和发展，数值模拟已经成为与理论分析、实验研究相 并列的第三种科学手段。由于实施模拟代价低，只要计算程序研究成功，就可以 用来对不同的情况惊醒反复的模拟，所以在科学工程中越来越受到重视。 虽然人们越来越认识到数值模拟这种研究手段的重要性，但是其有效性依赖 于两方面的研究成果。计算机硬件是提供可用计算能力的物理载体，各种软件与 相应的计算方法是实现充分利用计算资源进行高效计算的基石。由于工艺水平和 其它因素的限制，单处理机的性能远远不能满足各种应用领域的实际需要，而单 处理机性能要想大幅度提高不但价格昂贵，而且存在诸多难以解决的问题。因此， 为了满足不断提高的现实应用问题的需求，人们不得不将多台计算机以一定方式 连接起来共同求解同一问题，即构成并行计算机来满足各应用部门的需求。只有 在计算能力强的计算机上，设计高效的并行算法，开发出相应的并行计算软件， 充分利用计算资源，才能实现高效的数值模拟。 线性方程组的迭代算法是一种常见的求解方程组的方法，在数值分析的有关 书【l 】中很多介绍。近些年，关于迭代的并行算法有了很大的发展，很多知识已经 很成熟，关于迭代算法的并行性求解有很多相关的书籍叫】有具体的介绍。 古典显式差分格式表达简单，可以直接进行并行计算，但它多为条件稳定在 处理多维问题时，经常受到苛刻限制。而一般隐式格式是绝对稳定的。构造分段 隐式迭代的思想，是将要求解的差分方程组变成若干个子方程组的迭代解法，解 决了求解方程组时，子方程组的阶数较大以及确定关联方程组有关常数所涉及的 复杂矩阵计算问题【6 1 求解抛物方程的并行迭代法有很大发展，关于方程的稳定性好的隐式差分格 式，文献1 5 j 建立分段显隐式方法和交替分段方法，文献1 6 】设计了将方程组分裂为 若干子方程组进行分别迭代求解的并行算法，并且证明了其收敛性质。 兰州大学硕士学位论文求解抛物及双曲方程若干差分格式的加速迭代并行算法 文献【7 。9 1 在前人研究的基础上，基于隐式差分方程，具体讨论了求解的并行迭 代法，证明了迭代的收敛性质，并且对迭代在网格加密时的收敛速度进行了估计。 文献【1 3 1 进一步研究了关于抛物方程的并行迭代算法，对算法进行- i n 速，文献【1 3 l 以抛物方程的古典隐格式和c - n 格式为基础，具体讨论了算法的收敛性质。 关于双曲方程的并行迭代算法，文献f 1 2 l 给出了很多具体的讨论，其中关于双 曲方程隐式差分格式的并行迭代方法，文献【1 2 】以波动方程为基础进行了具体的讨 论，给出了迭代法的收敛性质。 紧差分格式是求解偏微分方程中的一种常见的差分格式，它具有稳定性好， 精度较高的优点。紧差分格式在计算区域内用较少的网格节点达到较高的的精 度，经济性很好，目前已有的紧格式主要是以原方程为出发点构造的二阶差分格 式l 啪0 1 。交替方向有限差分方法产生于上世纪五十年代，由于其稳定性好，在科 学和工程计算中得到广泛的应用。此格式最早由p e a c e m a nd w 和r a c h f o r dh h 在关于p r 格式的奠基性论文【1 4 】中提出。本文第二章讨论抛物方程，针对扩散方 程的初边值问题： 罢：石0 2 u ，( 硝) ( o ，1 ) x ( o ，佃) a t 瓠2 一。 u ( x ，o ) = 厂( x ) ，xe 【o ，1 】 u ( 0 ，) = c o ( t ) ，“( 1 ，f ) = 少( r ) ，( 0 ，佃) 以文献【1 0 】介绍的扩散方程的紧差分格式为基础，讨论了其加速并行迭代法， 讨论了其收敛性质和渐进收敛性质。对于二维的情形，本文以紧交替方向隐格式 为基础，对其收敛性质进行了讨论。 本文第三章关于双曲方程进行了具体的讨论。针对波动方程的初边值问题： 争= 窘舡( o ，1 ) ( 0 删 “( x ，o ) = 缈( x ) ，_ 0 u ( x ，o ) = l 矿( x ) ，x 【0 ，l 】 ot。 u ( o ，) = g o ( f ) ，“( 1 ，r ) = g l ( f ) ，( 0 , + o o ) 对其古典隐格式以及紧格式的加速并行迭代进行了讨论，具体分析了方法的 收敛性质和网格加密时的收敛性质。本文第三章的后面对于二维的情形进行了讨 论，对交替方向隐格式和紧交替方向隐格式的加速并行迭代算法进行了分析。 2 兰州大学硕士学位论文求解抛物及双曲方程若干差分格式的加速迭代并行算法 2 抛物型方程的紧差分方程的加速并行迭代法 2 1 一维抛物方程紧格式 2 1 1 算法构造 关于扩散方程初边值问题 婴：百0 2 u ，( 列) ( o ，1 ) ( o ，佃) 8 t瓠z 、 u ( x ，o ) = 厂( x ) ，xe 0 ，1 】 u ( o ，t ) = c 0 ( t ) ，“( 1 ，) = 少( f ) ，( 0 ，佃) ( 2 1 1 ) ( 击_ 圭_ ：，材竺1 + c 丢，“? + 1 + 孚1 一j 1 ，甜譬1 。2 。2 ， = ( 去+ 抄“扣“? + ( 上1 2 + 互1 咖三 一 其中，r ：竺 d = ql m 1d 2 兰州大学硕士学位论文求解抛物及双曲方程若干差分格式的加速迭代并行算法 皿= m f = 511 61 22 11511 1 2261 22 l151l 1 2261 22 115 1 226 o o 0 ，n i = o o 0 其中u m = ( ”：，“：k + l ，甜州k + 1 ) ，b 是由矿妒和沙决定的向量。 对紧差分格式作如下变形： ( 2 1 5 ) + i 石 万 ( 1 + 6 ，) “三：+ ( 1 0 + 1 2 ，) 甜墨。+ ( 1 + 6 ，) “1 + i 石 t 万【( 1 + 6 ，一) z ，? + ( 1 0 + 1 2 ，) 甜鲁。+ ( 1 + 6 ，) 甜三：】 一 去三：专告甜2 + 【( 1 0 + 1 2 r ) 一 去三等】甜| ： “+ ( - 一6 ，) 甜2 1 = 一! l 二i 掣甜三：+ ( 1 + 6 ，) 一! l 二 云掣】甜兰。 ( 2 l 6 ) + 【( 1 0 1 2r ) 一! l 二； 掣】材j + ( 1 + 6 ，- ) 材二。 ( 1 _ 6 咖冉【( 1 0 + 1 2 r ) 一篇彬”一篇k + ：l = ( 1 + 6 ，) 甜二+ 【( 1 0 1 2 ，) 一墅l 掣 “? ( 2 1 7 ) +【(1+6，j一旦l二等掣】“三。一(1-了6石rj)矿(1+6r)“： 用( 2 1 6 ) 式和( 2 1 7 ) 式分别替换各个子矩阵块( 2 1 5 ) 式的第一个方程和最 后一个方程( 其中第一个子方程组只替换最后一个方程，最后一个方程组只替换 笔一个方程1 i i 可d i 烙( ，1 ，) ( 714 ) 式化为- f 硎矩阵形式 d u 。+ 1 ：b 4 ( 2 1 8 ) m m )一厂)一厂力一打力一打 6 1 6 一l二+ 二+ 0 一m 0 一加)一，)一，力一打力一加 6 一l 6 1二+ 二+0一加om 兰州大学硕士学位论文求解抛物及双曲方程若干差分格式的加速迭代并行算法 其中u “1 = ( “： 州，“，“剃k + 1 ) ，b 是由沪矿和少决定的向量。 再将矩阵d 分裂为矩阵m 和n ，并写成如下形式 d = m n m = d i a g ( d l ，d 2 ，d k ) ：g 二堕 1 0 + 1 2 r d 1 = 口= o k = m ，= 0 ll m i0 2n 2 o k n k - m k 4o k 1 0 + 1 2 rl 一6 r 1 6 r1 0 + 1 2 r1 6 r l 一6 r1 0 + 1 2 r 1 6 r l 一6 厂 1 0 + 1 2 ，一! ! 二盟： 1 0 + 1 2 r l o + 1 2 ，一! ! 二盟：l 一6 ， 1 0 + 1 2 ， 1 6 ，1 0 + 1 2 ，1 6 ， l 一6 ，1 0 + 1 2 r 1 6 ， 1 6 ，1 0 + 1 2 ，一! ! 二鱼1 2 ： 1 0 + 1 2 ，一! ! 二盟：1 6 ， 1 0 + 1 2 r l 一6 厂1 0 + 1 2 ，1 6 厂 1 6 r1 0 + 1 2 ， 1 6 ， 1 6 ，l o + 1 2 r o 0 lo o ，m = 0 ol 0 0 ( 2 1 9 ) ( 2 1 1 0 ) 七 其中矩阵d 所有元素都为零，并且m ，= 朋一1 ( 2 鸭伪一1 ) ，根据上面的 5 之峨 兰州大学硕士学位论文求解抛物及双曲方程若干差分格式的加速迭代并行算法 分裂可以得到分段紧格式的加速迭代算法： m u ( 。+ 1 x 5 + 1 ) = n u ( + 1 5 + b但1 1 1 ) fd l u p “如+ 1 = l u + 1 如+ 6 l d 2 u “x 仆1 = m l u r + 1 + 2 u + 1 x + b z ( 2 1 1 2 ) i q q “w 件d = m n 哦譬d + 其中s 代表迭代次数 此时求解方程( 2 1 8 ) 式和求解方程组( 2 1 1 2 ) 的k 个子方程组是等价的，每 个子方程组在每一步迭代中是相互独立的。并且在每一步迭代的过程中，比如对 ( 2 1 1 2 ) 式的求解可以用追赶法。 2 1 2 迭代收敛性分析 为证明构造的差分方程在迭代的过程中是收敛的，在此引入下面的引理： 引理：设m = ( m i j ) 为n n 方阵，n = ( _ ，j ) 为n xm 阵，m 严格对角占优，则： l m n i l 。m 芝k 一k ，i 一k 巾 u=1| j l l 通过引理可以得到上述迭代算法的收敛性质估计： i i m 。1 n i i i i ( 1 6 r ) 2 ( 1 0 ( 1 0 + 1 2 r ) 2 一( 1 6 r ) 2 一( 6 r 一1 ) ( 1 6 r ) 2 1 2 r ) 2 一( 1 6 r ) 2 一( 1 6 r ) + ，1 、 【， 7 ) o ( ，三) 6 显然有p ( m 一1 ) i i m 。n k 1 6 )1 l + 6 广一 而1-6r9 1 8 r ，( ，马6+ 一 丽( 1 01 2 r ) 譬( 6 r 马6 + 2 一( 1 6 r ) 2 一一1 ) + 。、 7 两1 01 2 r ) 譬 o ，贝0d 1 0 。 因此当6 r 一1 0 时： 巧1 o ，g o ，m q o ， 设巧1 = x = ( t ，) ，则有 d 言mq + n = x 、mq + n = 0 x l ，口0 0 “0 0 x 2 q 0 0 x 2 ，l 0 ；i i；： ： o x p i g0 0 一i 10 0 x g ，q 0 0 x q , l 0 所以，8 巧1 ( m 。+ n q ) l l 。= m ( 一， i - x t , q ) ，i = 1 ，2 ，q 令矽( = x i ，l + x i 坷 令( 2 1 1 3 ) 式左右两边同时左乘d q ，可以得到： ( m g + m ) = d q o ，x q ，o ，x l ，0 】 其中，x ，= ( x l ，x 2 ，j ) 7 ，j = l ，2 ，q 所以见五= q ，p 。= 口。，e 。= ( o ，o ，1 ) 7 ，q = ( 1 ，o ，o ) 7 7 ( 2 1 1 3 ) 兰州大学硕士学位论文求解抛物及双曲方程若干差分格式的加速迭代并行算法 利用克莱姆法则【6 1 求解方程组可以得到 t 。= ( 6 r - 1 ) 卜1 k 日 = = 一，q = ( 6 ，一1 ) 旷b ，- l s q 其中，或= i q i ，( g 为方阵d 的阶数，l 砬i 为矩阵对应行列式的值) b t2 b ，5 1 0 + 1 2 r l 一6 厂 l 一6 ，1 0 + 1 2 rl 一6 ， l 一6 ，1 0 4 - 1 2 r1 6 厂 1 6 ，1 0 + 1 2 ，一! ! 二盟： 1 0 + 1 2 r l o + 1 2 ，一( ! 二盟： 1 0 - t - 1 2 r 1 6 ， 所以矽( t g ) = 薯，一- 坷= ! 鱼二二! 二生 p 利用行列式的性质可以知道，b ，有如下递推关系： 一b ，= ( 1 0 + 1 2 r ) 一b ，_ l 一( 1 6 r ) 2 一b ，一2( 0 s ，q ) 其中，一b 。= ，否= 。+ - 2 ，一 苫j 等宅 = ； 一 容易证明，b ，= b l 令1 0 + 1 2 _ ：川+ i ( 1 + 6 r ) 2 = 筇 接下来通过归纳法求b ，： 因为b o = 1 8 灯。b r r c _ 、i 6 l 一 + 1 0 l r2 广 1 6 + 一 0 1 i r r 6 6 一 一l， r r 2 6 1 一 + 1 0 兰州大学硕士学位论文求解抛物及双曲方程若干差分格式的加速迭代并行算法 否= 1 0 + 1 2 r 一! ! 二咝 1 0 + 1 2 r ：口+ 一旦：竺：丝芝：鲨丝壁塑竺= 旦：垡 。 口+ 口+ ( 口+ ) ( 口- f 1 ) 口2 一2 夏= ( 1 0 + 1 2 r ) b l 一( 1 6 r ) 2 b o 却+ 历睇m = 绁笋= 筹 假蕊= 筹，珏巧0 , i _ _ i l l 则b t = ( 1 0 + 1 2 r ) b l 一1 - ( 1 - 6 r ) 2 b ，一2 却峒筹一筇筹 一( 口“2 一筇“1 + 口“1 一“2 ) 一( 筇m 一口，+ 1 f 1 ) 口2 一2 仅| “一8 l + 2 ：= - - - - - - - - 二- - - - - 一 口2 一2 所以b ，一b ，_ ( o i “2 一“2 ) ( a2 一2 ) 同样使用归纳法可以推导出： 耻( 1 0 + 1 2 r - 一篇凰- ( 1 面瓜b z 一( 口2 + a f t + 2 ) ( 口“1 - f l m ) ( 口+ f 1 ) ( a2 一2 ) 仅$ 幢l p i 、) ( 口2 一2 ) ：型：二壁1 + f 1 ) ( a2 一2 ) 毗硝f ，g ) = 睦迅生气差错鲨坳 首先对( f ，g ) 做一个变形： 地g)=(6r-1)-i(aq-+2-flq-(+护2)-t-二(6矿r-1广)q-(a+1-fl,一+1)(a+f1) ：丞墨 二墨 坠二! 二区鱼上 墨翻! 型! ： ( 口9 ”一9 + 3 ) 假设函数矽( f ，g ) 关于变量i 是连续的，接着关于i 求导可以得到： 9 兰州大学硕士学位论文求解抛物及双曲方程若干差分格式的加速迭代并行算法 纵幻，= 骘华呻南c 者州山告c 告) f + 1 乩南c 玉州+ 2 + l n 告( 告) g - m 】 一棚2 铆所以等= 告删墓叫。 因此( f ，g ) 可以变形为下式： 认相，：随坐监曩掣一 设口 由“o + 1 2 ，可以得弛：5 蛳+ 2 面面 i 筇= ( 1 + 6 r ) 2 因此容易得到： 矽7 ( f ，q ) 孚) 所以由导数的性质可以知道，当f 芝 时函 数矽( f ，g ) 单调递增，函数在扛乏 时取得最小值，因此( f ，g ) 的值在边界上取到 最大，即在i = l 或者q 时最大。 当i = l ，q 时，可以求得： 撕，= 丝壁等器掣 再假设函数矽( g ) 关于q 是连续的，函数矽( g ) 对q 求导可得： 认加匣! 竖篙2 一 l o 兰州大学硕士学位论文求解抛物及双曲方程若干差分格式的加速迭代并行算法 ( 矗广1 ( 告广i l n 弘等 ( 矗厂3 + ( 啬厂3 ) ) ( 6 ，- 1 ) 2 即( 脚均 ( 口g + j 一9 + 3 ) 2 又因为筇= ( 6 ，一1 ) 2 ，所以( 鼍= 要j ，可以知道l n 虽= - 2 l n 气尹。 仅 b o c i ( 南) 字一( 告) 孚卜2 妒气州肛咖孚 毗( q ) = l 弋多万了一 因为6 r 一1 口，所以( g ) o ，由导数性质可知( g ) 是单调递减的，因此随 着网格点q 的增加，迭代的收敛速度变快，并且有以下结果： 篇p i i 。专( 等) 2 购专删 ( 2 ) 其次对范数0 研1 虬肚，l i 所1 m 。k 的大小进行分析 设d f l = 彳= ( x “) ，则有： d f l 虬= x n 。= 0 五，q 0 x 2 q 0 x p i 9 0 x q ，q o 0 - 0 0 oo 0o ： 0o 0o 所以由范数的定义可知l 所1 n 。忆= m ( 薯河) ，i = 1 ，2 ，q 令上式左右两边同时左乘d ，可以得到： n q = d l 0 ，x q ，0 ，0 】 其中，= ( x l x 2 矿，g ) 7 所以d l x q = p q ，e q = ( o ，0 ，1 ) r 接下来通过类似于上面对范数0 巧1 ( m 。+ m ) l 的讨论，可以得到0 研1 m 忆， 所1 m 。k 大小的估计值，又因为l 研1 m 。0 。= l i d , 1 n 。忆所以可以得到： 兰州大学硕士学位论文求解抛物及双曲方程若干差分格式的加速迭代并行算法 i 糕阿g 叫等) 2 靳寸佃， i 瓣8 研1 鸠o 。专( 等) 2 翱专删 其中，口= 5 + 6 ，+ 2 石而 由此可知随着网格数量q 的增加，i m - n i i 。逐渐收敛到( 鱼_ ) 2 ，这比文献 门中介绍的算法的收敛速度估计结果8 m - 1 k _ 竺，( g 寸佃) 更快，收敛性质 有所改善。 2 2 二维抛物方程紧交替方向隐格式 考虑二维扩散方； 旱 鲁罢+ 雾锁圳) ( 小1 ，0 斛) 初始条件为 u ( x ，y ，0 ) = 伊( x ，y ) ，( 石，j ，) q 边界条件为 u ( x ，y ，f ) = 少( x ，j ，r ) ，( z ，j ，) f ，0 f t 设缸，少和出为x ，y 和t 方向的网格步长。其中血：一1 ，a y ：三， ( 2 2 1 ) ( 2 2 2 ) ( 2 2 3 ) m ，n 为正 整数，以甜乞表示问题( 2 2 1 ) ( 2 2 3 ) 的解“( t ，y j ，y 。) 在网格点上的近似值，其中： x f = i a x ，i = 0 , 1 ，m ； y = j a y ，= 0 , 1 ，力； 气= 尬f ，k = 0 , 1 ，2 ，。 为简单起见，取a x = 妙= 办，h = 二，m 为正整数，f = f 。 m 在此，考虑紧交替方向隐格式，将其改写成类似p r 型【1 4 1 紧交替方向隐格式。 ( 彳一吾瓯2 ) 玩= ( b + 吾2 ) “! + 吾髟 。- ( 2 2 4 ) ( b 一号2 ) ”等1 = ( 彳+ 吾疋2 ) 玩+ 吾彰 1 2 兰州大学硕士学位论文求解抛物及双曲方程若干差分格式的加速迭代并行算法 d = 其中： 彳哆，：击c _ 4 ，y + ，。h 。，+ q 吐，( 1 手兰亏三：1 ) i v j , y ( f = o ，m ，0 j 聊) 眠，：胁一圳小- 惟嚣1 ) 【v i , y ( ，= o ，m ，0 i 肌) 将( 2 2 5 ) 式和( 2 2 6 ) 式代a ( 2 2 4 ) 式，并且令去= ，整理得到： 力。 ( 2 2 5 ) ( 2 2 6 ) ( 1 6 r ) e _ l + ( 1 0 + 1 2 r ) e ，+ ( 1 6 r ) e + 1 ，_ ， 1 + 6 力吒- l “1 0 _ 1 2 力2 1 ：羔妒6 娥- 2 (227)1，-k+l 1 + ( 1 0 + 1 2 r ) u 嚣1 + ( 1 6 ，) ”：盖l p 7 = ( 1 + 6 ，) 玩一l + ( 1 0 一1 2 r ) e ，+ ( 1 + 6 ，) 玩+ i ，+ 6 烈，j 2 可以将差分方程组写成矩阵形式： id u = 6 l 【d u k , = 6 2 其中 l o + 1 2 r1 6 ， 1 6 ，1 0 + 1 2 r1 6 厂 1 6 ，1 0 - 4 - 1 2 rl 一6 ， 1 6 ，1 0 + 1 2 厂一! ! 二盟： 1 0 + 1 2 厂 ( 一i ) ( m i ) ( 2 2 8 ) b l 是与u j ，缈和关的向量，b ：是与和e 有关的向量。( 玩是交替方向 法中的过渡层上的近似值) 玩= ( 玩，- 2 ，玩1 ，) r ，1 2 ，m - 1 u ? 州= ( 甜孔叫k ，2 ，+ l ，甜) r , i - - 1 2 ，m - 1 1 3 “ 小 办 + + i u t “ “ “ 孙 知 一 一 以 o h 。甜 “ ” 。一矿。一矿 = l i 七一u 七u 2 甜 2 甜 以 兰州大学硕士学位论文 求解抛物及双曲方程若干差分格式的加速迭代并行算法 对( 2 2 7 ) 中的第一个式子进行如下变换： 一涨+ ( 1 0 + 1 2 r ) 一潞( 卜6 慨， = ( 1 + 6 r ) ：j l + ( 1 0 - 1 2 r ) u i + ( 1 + 6 ，) “乞+ l 一(1+6ri)i(1一-6r)材兰1卜，一(1o-t1石2；ri)(芝1_-6r)材7一(1+i石6rj)1(1f-6r)10 1 2 r t - i , j甜三u + 。 + b 广1 1 0 + 1 2 ，1 0 + 1 2 ， k j ” + 6 烈一等磁蔓眨2 m 一糕+ 【( 1 0 + 1 2 r ) 一篇耻( 1 西风j = ( 1 + 6 ，_ ) “乞一l + ( 1 0 - 1 2 r ) u ! j + ( 1 + 6 ，) “：j + 1 一( 1 + 而6 r 矿) ( 1 - 6 r ) 甜三乒l 一( 1o可-1鬲2r)f(1-6r)“。一(1+6r矿)(1-6r)t+l,j1012 r 甜女+ 1 , j + 11 0 + 1 2 ， ”u 1 1 0 + 1 2 ，+ 一篇k + l 【( 1 0 + 1 2 r ) 一篇蟛l + ( 1 _ 6 咖u k + + l ， = ( 1 + 6 r ) g l ，+ ( 1 0 1 2 r ) 瓦+ ( 1 + 6 ，) 玩+ l ，j 一堡鬻玩-i,j-101 2 r一史旦二1掣01 2 r 瓦t , j - i 一旦二掣1 01 2 r z + l ，一。 + + ”1 j - 。 删一等蚓 2 加， 一篇k 巾+ l + ( 1 0 + 1 2 r ) 一篇蚶+ ( 1 - 6 ，川k _ + l 。 一警r 1 ( 1 0 - 矿1 2 r ) ( 1 - 6 r ) + 6 姒一等娥譬 u t , j + l 一紫+ ，一二而翁万二+ ， 用( 2 2 9 ) 的两个式子分别代替( 2 2 8 ) 的第一个方程系数矩阵a 的子矩 阵的第一个方程和最后一个方程( 其中第一个子方程组只替换最后一个方程，最 后一个方程组只替换第一个方程) ，同样用( 2 2 1 0 ) 的两个式子分别代替( 2 2 8 ) 的第二个方程系数矩阵a 的子矩阵的第一个方程和最后个方程( 其中第一个 子方程组只替换最后一个方程，最后一个方程组只替换第一个方程) ，可以将 ( 2 2 8 ) 式的系数矩阵a 分裂成m 和n 矩阵 d = m n ( 2 2 1 1 ) 1 4 嘶 等 嘭 兰州大学硕士学位论文求解抛物及双曲方程若干差分格式的加速迭代并行算法 b = 口= d k = m = d i a g ( d l ，9 2 ，q ) m ，= ：! ! 二盟： 1 0 + 1 2 r q m 1 l q 1 0 + 1 2 r1 6 r 1 6 r1 0 + 1 2 r1 6 r l 一6 r1 0 + 1 2 r l 一6 r m 一1 q 1 6 ， 1 0 + 1 2 ，一! ! 二鱼! 窆 1 0 + 1 2 厂 1 0 + 1 2 ，一( ! 二盟：1 6 ， 1 0 + 1 2 r 1 6 ，1 0 + 1 2 r1 6 厂 1 6 r1 0 + 1 2 r 1 6 r 1 6 ， 1 0 + 1 2 ，一( ! 二盟： 1 0 + 1 2 r 1 0 + 1 2 ，一! ! 二盟：l 一6 ， 1 0 + 1 2 ， 1 6 ，1 0 + 1 2 rl 一6 ， 1 6 ，1 0 + 1 2 厂 l 一6 ， l - 6 r1 0 + 1 2 r o 0 10 0 ，n j = 0 0 1 0 0 k 其中矩阵o i 的所有元素都为零，m ，= m - l ( 2 _ m ， m - 1 ) 。 对( 2 2 8 ) 式变换后可以得到如下迭代形式： 1 5 ( 2 2 1 2 ) m 膨 么似 嚣 枷 似 蟛舯 兰州大学硕士学位论文求解抛物及双曲方程若干差分格式的加速迭代并行算法 对( 2 2 1 2 ) 式中的两个式子分别进行2 1 小节中同样的讨论，可以知道 ( 2 2 1 2 ) 式在迭代中是收敛的，并且随着网格数量的不断增加，迭代的收敛性 质更快。 2 3 数值试验 ( 1 ) 当2 1 小节中的扩散方程初边值问题中f ( x ) = e 。，驴( f ) = e t , y ( f ) = e 件1 ， 该定解问题的精确解为u ( x ，t ) = e 肿。 将系数矩阵分裂成3 个子矩阵进行运算可以得到如下结果： 表2 - 1 不同方法的迭代次数比较( h = 0 1 ，r = 1 0 ，e = 1 0 * e - 8 ) 子矩阵阶数 31 33 3 文【7 】算法迭代次数 1 2 1 08 本文算法迭代次数6 54 表2 - 2r = 1 0 ，h = 0 i 时算法的精度 ( x ，f ) 精确解 数值解绝对误差 o 6 ，o 12 0 1 3 7 5 2 7 0 2 0 1 3 7 5 3 8 l1 1 0 9 2 c - 0 0 6 o 6 ，o 22 2 2 5 5 4 0 9 22 2 2 5 5 4 2 5 61 6 3 5 2 e 0 0 6 o 6 ，o 53 0 0 41 6 6 0 23 0 0 4 l6 8 5 02 4 7 6 6 e 0 0 6 o 6 ，0 63 3 2 0 l1 6 9 23 3 2 0 1 1 9 6 62 7 4 4 9 e - 0 0 6 o 6 ，o 94 4 8 l6 8 9 0 74 4 8 1 6 9 2 7 83 7 10 4 e 0 0 6 o 6 ，1 o4 9 5 3 0 3 2 4 24 9 5 3 0 3 6 5 24 10 0 8 e - 0 0 6 ( 2 ) 考虑2 2 小节中的二维扩散问题( 2 2 1 ) ( 2 2 3 ) ， 其中吣) = e o - 5 ( x + y ) m 川一瓣m t u ( o ，y ，t ) = e o 5 y - tu ( 1 ，y ，) = e 0 5 ( 1 + y ) t , 0 y 1 , 0 t 1 u ( x ，0 ，t ) = e o 5 1 “，u ( x ，1 ，) = e o 5 ( 1 + x ) - t , 0 x 1 , 0 ，1 该定解问题的精确解为u ( x ，y ，) = e o 。5 什m 。 表2 - 3r = 1 0 ，h - - o i 时算法的精度 ( j ，y ，) 精确解数值解绝对误差 0 4 ，0 4 ，0 2 5 1 1 6 1 8 3 41 1 6 1 8 3 45 9 9 8 e - 0 0 7 1 6 兰州大学硕士学位论文求解抛物及双曲方程若干差分格式的加速迭代并行算法 0 4 ，0 4 ，0 5 0 o 9 0 4 8 3 70 9 0 4 8 3 74 6 8 8 e - 0 0 7 0 4 ，0 8 ，0 2 5 1 4 1 9 0 6 81 4 1 9 0 6 74 6 0 0 e - 0 0 7 0 4 ，0 8 ，0 5 0 1 1 0 5 1 7 l1 1 0 5 1 7 l3 6 5 5 e 0 0 7 0 8 ，0 8 ，0 2 5 1 7 3 3 2 5 31 7 3 3 2 5 33 7 1 8 e 0 0 7 0 8 ，0 8 ，0 5 0 i 3 4 9 8 5 91 3 4 9 8 5 92 9 0 1e - 0 0 7 通过表2 1 可以得知算法的收敛速度比较快，跟文献1 7 1 中的算法相比收敛 速度明显加快，而且算法随着网格数量的不断增加收敛速度不断提高，迭代次数 不断较少。并且我们可以从表2 2 和2 3 中得到，迭代算法的比较高，这些都跟 理论推导的结果一致，证明了算法的有效性。 3 双曲型方程的隐式差分方程的加速并行迭代法 3 1 一维双曲方程古典隐格式 3 1 1 算法构造 关于波动方程的初边值问题 害= 窘如，f ) ( o ，1 ) ( 0 一) “( x ，o ) = 缈( x ) ，孚( x ，o ) = ( x ) ，x 【0 ，1 】 ( 3 1 1 ) o t u ( o ，f ) = g o ( f ) ，u o ，) = g l ( ，) ，t ( o ，佃) 在z 空间步长缸和时间步长出将区域( 0 ，1 ) x ( 0 ，+ ) 划分为网格，其中 t = i a x ，( f - o ，l ，m ) ；t k = k a t ，( 七= 0 ，l ，2 ，) 点( x 。，气) 记为( f ，k ) ，记缸= 办，a t = f 。 文斛1 5 1 对于双曲方程( 3 1 1 ) 的隐式差分格式描述如下： 一，觎竺1 + ( 1 + 2 r o )