（基础数学专业论文）双曲型方程在乘积型差商空间中的高精度组合差商算法研究.pdf

双曲型方程在乘积型差商空间中的 高精度组合差商算法研究 摘要 本文针对一阶一维常系数双曲型方程，首先给出了关于乘积型差商空间中组台差商法 的基本定义及一些引理，在此基础上分析了节点分布与差分格式类型和精度之间的关系。然 后在乘积型差商空间中运用组台差商法，构造出一阶常系数双曲型方程的二层或三层，精度 达到三阶或四阶的一系列差分格式。最后给出了方程的并行算法：分组显式算法，半显示与 隐式分段迭代法。本文对嚣格式都进行了数值例子计算，验证了理论分板的结果。 在乘积型差商空间中采用组合差商解法这在理论上是一个创新，本文的算法所构造的差 分格式较以往的格式，精度有了很大的提高，稳定性条件也比较好。在此基础上把串行格式 并行化更是有了较好的结果。 关键词：乘积型差商空阔，组合差商解法，双曲方程，并行算法，高精度。 圈书分类号：0 2 4 1 8 2 h i g h p r e c i s ec o m b i n a t i o n d i f f e r e n c e a l g o r i t h mf o r h y p e r b o l i ce q u a t i o ni np r o d u c t d i f f e r e n c es p a c e a b s t r a c t i nt h i s p a p e rw er e p o r t ac l a s so fh i g h p r e c i s ed i f f e r e n c es c h e m e sf o rt h e o n e - o r d e ro n e d i m e n s i o n a lc o n s t a n tc o e f f i c i e n th y p e r b o l i ce q u a t i o n a tf i r s tw eg i v e s o m eb a s i cd e f i n i t i o n sa n ds o m el e m m a sa b o u tc o m b i n a t i o nd i f f e r e n c ea l g o r i t h mi n p r o d u c t d i f f e r e n c e s p a c e o n t h i sf o u n d a t i o nw ea n a l y z et h er e l a t i o no fn o d e d i s t r i b u t i n ga n dt y p eo fd i f f e r e n c es c h e m e s t h e ni np r o d u c td i f f e r e n c es p a c eb y a p p l y i n gc o m b i n a t i o nd i f f e r e n c ea l g o r i t h mw ec o n s t r u c ts e r i e so fd i f f e r e n c es c h e m e s t h e s es c h e m e sa r eb e l o n gt ot w ol e v e l so rt h r e el e v e l s ，a n dt h e i rp r e c i s ec a ng e tt o t h r e e o r d e ro rf o u r - - o r d e r a tl a s tw eg i v et h e p a r a l l e la l g o r i t h m f o r e q u a t i o n ： g r o u p e x p l i c i ts c h e m e s ；h a l fe x p l i c i ta n di m p l i c i ti t e r a t i v ea l g o r i t h m ；i dt h i sp a p e r e v e r yt y p es c h e m ei s 舀v e nn u m e r i c a lc o m p u t e , a n dt h er e s u l tv a l i d a t e st h et h e o r y a n a l y s i s i n p r o d u c t d i f f e r e n c e s p a c ea p p l y i n g c o m b i n a t i o nd i f f e r e n c e a l g o r i t h m i s i n n o v a t i o ni nt h e o r y t h ed i f f e r e n c es c h e m e si nt h i sp a p e ra r eb e t t e rt h a n t h o s eo f b e f o r ea tp r e c i s ea n ds t a b i l i t y o nt h i sf o u n d a t i o nc o n s t r u c t i n gp a r a l l e la t g o r i t h mi sv e r y 9 0 0 d k e yw o r d s ：p r o d u c td i f f e r e n c es p a c e ，c o m b i n a t i o n d i f f e r e n c e a l g o r i t h m ， h y p e r b o l i ce q u a t i o n ，p a r a l l e la l g o r i t h m ，h i 曲p r e c i s e 2 前言 工程实际中的许多问题，根据不同的其体特点，可以建立不同的数学模型。双曲型方程 是其中的一个重要部分，是刻划信号或波以一定速度传播的物理现象。在空气动力学、非线 性弹性力学、水力学、石油勘探等领域中都有具体应用。 一阶一维常系数双曲方程 一o u + 塑。o ma 五 是双曲方程中的一种最简形式，虽然它的形式简单，但其性质具有一定的典型意义，它可推 广到变系数和多维情形。国内外对它的研究较早也较多。有限元法、有限差分法是解偏微分 方程的两种主要的数值方法。求解上述方程的有限差分法的已有结果： 显格式主要有：偏心格式截断误差为d p + ) ，稳定性条件为| ，ls1 ：中心差分格截断误 差为。扣+ 2 ) ，绝对不稳定：l a x 格式截断误差为d ( r + 2 + 7 形) ，稳定性条件为1 r | s 1 ； l a x - w e n d r o f f 格式截断误差为。一2 + 2 ) ，稳定性条件为hi1 ，它是目前精度最高且稳定性 最好的显格式。这个格式的缺点是右边界无法计算。 半显格式主要有：最简隐格式，截断误差为o ( r + ) ，绝对稳定；w e n d r o f f 格式，截断误 差为d p 2 + 2 ) ，绝对稳定。 隐格式主要有：c r a n k - n i c o l s o n 格式，截断误差为o p 2 + 2 ) ，绝对稳定。 主要传统方法： 特征线法：特征线概念在双曲型方程中有很重要作用，借助于微分方程初值问题的解在 特征线上为常数构造出各种差分格式( 迎风格式，l a x - w e n d r o f f 格式等) 。 数值微分法：即从微分方程出发，利用数值微分的方法，将各个微商用适当的差商近似 地代替，从而得出逼近微分方程的差分格式( 如晟简显、隐格式，蛙跳格式等) 。 积分插值法：实际问题中得出的微分方程，常常反映物理上的某种守恒原理，如质量守 恒，动量守恒等，它们一般也可以 j 积分形式来农示，因此有时可以不从微分方程出发而从 守恒原理的积分形式出发来建立差分格式( 如l a x 格式，w e n d r o f f 格式，l a x w e n d r o f f 格式 等) 。 待定系数法：前先选取形式确定而系数待定的差分格式逼近微分方程，然后侄截断误莠 t ，r 能达到的范【目内，披精度要j j 之定f l ；差分方科的系数，构成贝体的差分格式。这些传统方法 3 之间无严格界限。 由于受这些传统思想与传统方法及c f - l 条件的限制，很少有高精度高稳定的差分格式 出现，目前资料所见格式的精废都没有突破两阶。 组合差商法是我们在近年研究微分方程数值解法中发展起来的一种行之有效的高精度 高稳定方法，是对微分方程数值解法的发展和创新。本文引入了乘积型差商空问的概念。并 在乘积型差商空间中，采用组合差商法，构造了双曲方程的高效率格式，把对双曲方程的高 精度高稳定高效率算法推向了一个新水平。 由于串行格式的影响，双曲型方程的并行求解目前没有很好的算法。e v a n s 和s a h i m i 首 先发现了一阶常系数双曲型方程初边值问题的分组显式格式，张宝琳和陆金甫发现了文章中 有些不妥和错误，中心差分格式有正负号出错；g e r 在一般意义下不稳定，不能用于实际计 算；在右边界给了条件，导致方程不适定。张宝琳1 1 0 1 等给出了分组显示格式，误差为 。如+ + 2 ) ，虽然a g e 格式是绝对稳定的，可当网比取得大一点对，就会导致误差太大， n 故也不实用。特别：当二h = o ( 1 ) 时收敛性就会成问题。别的算法目前不常见本文给出了 n 一组较上述算法好的g e 格式。 对于隐格式的求解最后化成求解线性方程组，关于乏对角方程组的并行求解已有大量并 行算法，主要有：递推耦合算法【”1 ，循环约化方法，类似于w a n g 的分裂法的并行算 法1 和类似于s u n xi - i t ”1 提出的基于系数矩阵积贫鳃枫蒉行算法”一1 ，嵌套迭代法”， 上述并行算法都是基于分治策略。s u nxh 与嵌套迭代法是求解强对角占优三对角系数阵 的分治算法，对系数矩阵的限制条件太苛刻，计算量也不能有效降低。本文从新的角度给出 求解三对角占优方程组的并行算法，取得了较好的结果。 4 第一章基本概念、引理及定理 本文讨论的模型问题是一维双曲型方程初边值问题 丝o t + n 丝o x 工1 u , 印2o 工t = l j ，f 己u “0 ，0 ) = 庐0 )x e o , l 】 h ( o ，t ) 一妒( f ) t 0 其中a 为非零常数。 构造微分方程的有限差分格式，第一步是将求解区域进行网格剖分，这里采用分别平行 于z 轴与y 轴的直线所形成的网覆盖求解区域，它们的交点称为网格节点。其中 f 。n g ，n - 0 , 1 , 2 ，工，= 曲，j = 0 , i ，2 ，一，n h = 【 f ，h 分别是f ，z 方向的网格步长，表示取整， ，t 。) 就是网格节点，o o ，t 。) 及0 ，t o ) 为 边界节点。 区域剖分后，取一个局部节点集，它是一个包含0 ；，t 。) 及其几个相邻节点的集合。住 局部节点集上构造逼近微分方程定解问题的差分格式。 下面引入本文所需要的基本定义及引理定理。 倒 1 1 基本定义及引理 应用差分方法，关键在于恰当地选取逼近微分方程中的导数的差商。 差商的构造：既可直接由t a y l o r 展式单独构造，又可伴随微分方程构造。 对割i ( 1 ) 直接由t a y l o r 展式导出的熟知的差商有如： ，阻 ；，【“】；+ ，【“ ：。v ，【h 】n ，+ l ，v 。阻 弼，v ，m 】蒿，及中心差商等，其中，袭示t 方向的向前差商，v 表示t 方向的向后差商。它们实际上就是函数的增量与自变量的增量的 比值。 ( 2 ) 利用微分方程构造。对皇竺+ 4 堕：o ，当微分方程的解充分光滑时， 彳i ma x 5 筹- ( _ 盟o x m + ，揪叩；+ 1 - i - c 2 u 捆近并( 慨脚圳c l c z 为系数。由 设 “怖和丢斜 斟 吖， 知嗍+ 鼢爿n 澍n 叫， 咖，+ 1 i c 2 u 呻。+ 吃焖；+ 婶一鲁巳，剖：+ 尝导卜+ 剥： 2 + 咿州， 令 c 1 - i - 。2 0 有 噤挚丑a t i s + 意2 ( 1 讣赤2 ( 1 计咿+ 争( 1 + 。+ 兰) a r 2 i ，+ 秕2 r 。r 令k ；一0 表示在节点o ，t 。) 处的差分格式，在节点0 j ，t 。) 处，微分方程为 忙“i ：= 0 t r ；一l ，h ；一陋“】；为用差分算子代替微分算子所引起的截断误差。 定义1 差商口称为差商组卢l ，卢2 ，卢，的个线性组合，如果有数域p 中的数 k 1 ，k 2 ，一，k ，使鬲k i p l + k 2 卢2 + 一+ 七，成。 当差商。是差商组届，岛，展的一个线性组台时，我们就说8 可以经差商组 岛，芦：，成线性表出。 定义2 如果筹商组中至少有一差商可以经其它差商线性表出，那么这个差商组称为线 性相关，否则称为线性无关。 定义3 在一个局部节点集上，通过一个微商的所有线性无关的时间差商所张成的空间 称为时间差商空问，所有线性无关的空间差商所张成的空间称为空问差商空问，其中所有这 些线性无关的差商就是此筹商空间的一组基，称之为基本差商。 定义4 川基本若商的组合逼近一个微商的新差商称为组合差商。 定义5 笑1 ：h j 问导数j j 空问导数的基奉筹商构成的时空荠商空问的耦合称为乘积型差 6 商空间，记为sx 其中s ，是空问差商空问ts ，是时间差商空间。其中晟大彼此线性无 关的基奉差商构成乘积型差商空问的一组基。在时空差商空间中利用基本时间差商和空间差 商的组合逼近微分算子而构造差分格式的方法称组合差商法。 在分析差分格式的稳定性与迭代法的收敛性时，常需用到以下引理： 引理1 ( m i l l e r ) q ：对于二次多项式p ( z ) t a z 2 + k + c ( a o ) 的根z l ，z 2 的模的大小， 设z 。= p e ”，z ：= d e i q a ，r pz d 。g g l a l = i c o ) p = de 1 的充要条件是 a b = b c , 及i b l s2 i 。l 。 ( 2 ) p = d = 1 ，z 。一2 ：的充要条件是a b = 6 c 及燃c2 l 口i 引理2 ( 胡家赣) ”1 ：设m 一帆) 为n 阶方阵，n = ，j ) 奠j n x m 阵，m 严格对优， 则i l m - n i i 。s 峄( ；| r a i ，吲啊。 引理3 ( l m x ) m 1 ：若边值问题的解“充分光滑，差分方程按i i 。满足相容性条件，且 格式稳定，则差分解“如按1 | 1 l 。收敛到边值问题的解，且有和l i r ，o ) 1 1 。相同的收敛阶。 引理4 ( 对角占优) ”：如果4 一( n u ) 。r “”或( c “”) 为严格对优势阵或不可约对 角伉势阵，则a 是非奇异的。 引理5 ( 选代法的基本定理) 9 1 ：设有方程组z 一丑x + ，对于任意初始向量z o 及任 意，解此方程组的迭代法( 即x “1 一b x + ，) 收敛的充要条件是p p ) f + ( ，2 r 2 l 叩3 4 1 2 一+ 6 1 y 。= 三 1 y s 芝 ，+ 矽一t + ( ，2 + + 2 n ， ( 一8 + 2 m 一+ ( _ 2 一 乃车：+ ( 7 + 2 ，f ：；0 1 6 j = 1 , 2 一1t 所得的差分格式也为( 2 1 3 ) 。这刚好也验证了定理6 的结论。 由f 一二a ，故格式( 2 1 _ 3 ) 的截断误差实为e ：叫+ ) 。 口 特殊情形： 当a 是一个负数时，如果# 1 ，则差分格式( 2 1 3 ) 变为 “；+ “二l = “；4 + ，n - i 如果r = - 2 , 则差分格式( 2 1 _ 3 ) 变为 “互l 一“n - i 当a 是一个正数时，如果r = l ，则差分格式( 2 1 3 ) 变为 “；+ “；+ 1 皇m ；- 1 + h j n _ 1 - 1 如果r _ 2 ，则差分格式( 2 1 3 ) 变为 ( 2 1 4 ) ( 2 1 5 ) ( 2 1 6 ) “；+ 1 一h 嚣 ( 2 1 7 ) 2 稳定性与收敛性 用f o u r i e r 分析法得特征方程为 粤+ t 2 , - r 2 小等+ r 2 一峥n 邮等一半 2 a 量 ， + 了r - 1 一i r2 ) c o s 幽+ f 三s i n 础a 。 o h 。 砒 3 2 显然l a l 一1 对任意的，和o h 都成立。即格式( 2 1 3 ) 是绝对稳定的。 综合上述并根据l a x 的稳定性与收敛性等价性定理，可得如下定理 定理8 ：差分格式( 2 1 _ 3 ) 的截断误差为6 + 4 ) ，绝对稳定且收敛。l r | s1 时，对角占 优，且为正型格式。 3 数值例子 对一维双曲型方程第一边值1 u j 题 i o u + i o u ；o , x e o ，2 】，f 0 加缺 “0 ，0 ) = s i n x “( o ，t ) = s i n ( 一) 1 7 础一曲 n 一 s sr 一2 一r 一 f 一 1 一 一 + 一 k 一一k 7 + 一 十 一弓 + 一 + ，一6一，o 一 一 一、 精确解为u ( x ，t ) = s i n ( x 一) ，以下各节所有的数值例子的模型都为此模型，输出的都为点 ( 04 ，8 0 0 r ) 、( 0 8 ，8 0 0 r ) 、( 1 2 ，8 0 0 0 、( 1 6 ，8 0 0 r ) & _ 的近似值及误差，其中r 分别取0 6 、1 。 利用本文格式( 2 1 3 ) 求数值解，并与精确解比较。 1 ) ：对于h 1 ，系数矩阵是一个强对角占优三对角阵，可用追赶法计算。 2 ) ：对于r = - + 1 ，系数矩阵是一个上( 下) 三角矩阵，可直接用代入法计算。 3 ) ：对于r = - 2 ，利用格式“h = “，n “- 1 ；r = 名利用格式“a l 一“，n q - 1 。算法简单，但需加一内 边界。 4 ) ：对于h ，1 且h 一2 ，系数矩阵是一个非对角占优阵，追赶法失效。 计算结果如下： 为分析的方便，右边界用准确值代替。其中空问步k 取0 0 2 ，时间层数为4 0 ( ) 0 层，r 是 网比。 0 40 81 21 6 r = o6 近似值0 4 5 8 3 2 2 0 ，0 7 6 0 4 0 - 0 3 1 8 2 5 8 0 6 6 2 3 0 3 误差3 8 7 4 3 0 e _ 0 62 3 5 4 3 8 e 一0 61 6 0 9 3 3 e 0 67 1 5 2 5 6 e 一0 7 r = l近似值 0 8 7 2 4 4 40 6 1 3 2 6 00 2 5 7 2 5 6_ 0 1 3 9 3 6 3 误差2 9 8 0 2 3 e 4 1 75 9 6 0 4 6 e 一0 88 9 4 0 7 0 e 0 81 4 9 0 1 2 e 一0 7 由上可以看出，对不同的，差分格式( 2 1 3 ) 的解与精确解都有很好的吻合，这个数值 结果与理论分析有很好的一致性。 对于，t 0 的情况，结果类似。数值侧子略。 2 2 二层三阶精度半显格式 1 格式构造 设局部节点集为 ，- l ，t 。) ，o j ，) ，o 一，f 。) ，0 j t ) ， j ，f 。) 如下图所示： n + 1 层 n 层 则基本差商为4 个。，扣e + a ，i u l ，【“e + a 【“】：是局部节点集上的一组时间和空问若 f ；i 。 易i 征它们线性无笑，则构成乘积犁差商空间的一组基。令 。s p a n ( a 【“】：一a ，【“ ) ，s ，一s p a n ( a j “n 。，a ，m 】：) ，则乘微型差商空问s s ，x s ，。 t a v l o r 展式 “喵一t = 华一孙+ 争 + d p 3 + f 2 h + h r 2 ) ，a h 2 口2 r h 一【- 丁+ 丁+ “叫2 唑掣2 辨1 a 2 2 r 舻d2 u r n a 3 。 u2 掰a3 u l ： 删，华哥矧+ 等讣叫， 叫喵2 监芦= 封+ 鲁+ 等窘卜，+ i 萨i 枷( 易证差商的渐近展开式线性无关，故最高只能达到3 阶精度。 令仇 一1 ，2 ) ，y ，( f = 3 ，4 ) 是组合系数，作组合差商，并令 l h u ；2 * i j a t t - j ；一1 + r 2 a 。m r + 扎，m r l + a a 。t u 7 一。 当系数满足下列关系时，格式达到三阶精度。 叩l + ，7 2 ；1 托+ r 4 1 叩。+ 三一i l h + i 1r = 。叩- + 五一i h + j 7 2 0 三哺一三 + ! ；0 i 7 7 ，一三叩，一一6 + 一6 2 解得 1 一，2 + r5 + r1 一r 2 r 2 r ，y 32 - g - ，“。f 令h ；- i ：u ；，把系数代入得格式： 2 ( 1 一，讧岔十2 ( 2 + ，弘；“t r 2 + 3 r + 2 u 7 一，一( 2 r 2 + 2 r 一4 沁；+ ( ，2 一r ) h ；。( 2 2 ) 按上述方法，可得对称格式是： 2 ( 2 一，) “；“+ 2 ( 1 + ，) h ；i = r 2 + r ) “互，- ( 2 r 2 2 r 一4 ) h ；+ ( r 2 3 r + 2 ) 0 ， ( 2 3 ) 2 稳定性分折 采用j | jf o u l i e r 分折法。 ( 2 2 ) 特征方程为 t 2 ( 1 r ) ( c o s a h i s i n o h ) + 2 ( 2 + r ) l z = f ，2 + 3 r + 2 ) ( c o s a h 一s i n a h ) 塑护 ! 。 d 一 一( z r2 + 2 r 一4 ) + ( ，2 一r ) ( c o s a h i s i n a h ) 易证 | a 1 1 。r e 一2 ，一1 u 【o ，1 】 ( 2 3 ) 特征方程为 【2 ( 1 + r ) ( c o s a h + i s i n a h ) + 2 ( 2 一r ) 】a 1 ( ，2 + r ) ( c o s a h i s i n a h ) 一2 r 2 + 2 r + 4 + ( r 2 3 ，+ 2 ) ( c o s a h + i s i n a h ) 易证 a s 1 静r e 一t , 0 7 综上，可得如下定理 定理9 ：( 2 2 ) 格式的精度为三阶，稳定性条件， - 2 , - 1 u 1 0 ，t ( 2 3 ) 格式的精度为三阶，稳定性条件r 卜1 ，o 3 数值例子： 格式为( 2 2 ) ，数学模型及输出点同2 1 中的数值例子。其中h = o 0 2 ，时间层数为4 0 0 0 。 o 40 81 。21 6 r = o 6 近似值0 4 5 8 3 2 6o ，( 玎6 0 3 7 - 0 3 1 8 2 5 6 0 6 6 2 3 0 4 误差2 9 8 0 2 3 e _ 0 81 4 9 0 1 2 e 4 1 8 5 9 6 0 4 6 e - 0 85 ，9 6 0 4 6 e - 0 8 r ：1近似值 0 8 7 2 4 4 4 0 6 1 3 2 6 1o 2 5 7 2 5 6_ 0 1 3 9 3 6 3 误差0 0 0 0 0 0 e + 0 00 o o o ( ) o c + 0 0o o 【) 0 0 0 e + 0 0o o ( ) 0 0 0 e + o o 对于格式( 2 2 ) ，如，卜2 ，一1 】时，要采用一个数值内边界，从右往左计算。数学模型 类似2 1 中的数值例子不过左边界条件换成右边界。其中h = o 0 2 ，时间层数为4 0 0 0 。 空间节氖下标值 2 0 4 06 08 0 r 一1 6近似值 0 3 9 4 2 8 80 0 0 5 2 9 3- 0 3 8 4 5 3 8- o 7 1 3 6 5 9 误差- 5 9 6 0 4 6 e 加1 8 1 0 8 1 6 0 8 e 0 8- 2 9 8 0 2 3 e 0 80 0 0 0 0 0 e 十0 0 r 一2 近似值1 7 7 8 2 0- 0 5 4 6 9 9 60 8 2 9 8 1 2m 9 8 1 6 2 0 误差 4 4 7 0 3 4 8 e - 0 80 0 ( ) 0 0 0 e + 0 05 9 6 0 4 6 4 e - 0 80 0 ( ) 0 0 0 e + 0 0 对于格式 2 3 ) 有相似的结果。 第三章双曲型方程的三层高精度半显式与隐式差分格式 3 1 三层四阶精度半显格式 1 格式构造 设局部节点集 o h ，t 。) ，o h ，t “) ，o ，t 。) ，o j ，t “) ，o j ，t 。) ，o ，t 。) j 一1j n4 - 1 层 ，z 层 h 一1 层 其基本差商为，【h 写- 1 ，a ，m z 。越阻e 二： 4 m 】；。，d ，m 】；，易证点扣r 。4 阻】；线性无 关，皿 ：+ a ，【u + n - 1 。，a “翠：也线性无关。则乘积型差商空间s = s 足。其中 s 。= s p a n ( 6 。1 , 3 7 一。，6 。【“ ；) s ，- s p a n ( a ；【“】：。，a ，【“】：，a ，【“ n 卜+ ，1 ) 。 基本差商的渐近展开式： 州喵，型磐 。= 甜卜警+ a 3 。t2 d3 u 飞n + c 了a h3 + t a 3 t 2 h 专a u e + d ( r4 + h 4+v2 h2 ) 喵= 华= 斜一a 3 - t 20 3 u i n 嘶4 ) 咄：= 堕荨盟= 堕o x 卜争睾卜孚+ 譬+ 争軎| i 一( 譬+ 等+ 了a h 2 一k + 爿h a 刮0 4 u t 嘶4