抛物型方程的几种可并行的有限差分方法
|
摘要
抛物型方程是偏微分方程中基本方程之一.在自然科学的众多领域中,许多现象是用抛物型方程或者方程组描述的[1],例如热传导以及其它扩散现象、化学反应、粒子的运输等等.另外在一些问题的数值处理中也经常出现抛物型偏微分方程.在现代数值方法中,最早为人们所注意且理论分析完善的是有限差分法,因此抛物型偏微分方程的有限差分方法一直是人们关心的焦点.随着并行机的问世和发展,传统的有限差分方法在不同方面暴露出各自的弱点.例如,古典显式虽然适合于并行计算,但它是条件稳定的,特别是多维问题中计算步长受到严格的限制;古典隐式和Crank-Nicolson格式是绝对稳定的,但需要求解联立方程组,不便于直接在并行机上应用.因此需要构造具有良好稳定性、并行性和计算精度的新的差分方法.
七十年代初,Miranker指出用有限差分逼近偏微分方程时,主要是组织传统差分方法的并行实现,至于设计新算法,推动力是很小的;之后的十几年高阶差分格式方面的研究得到了发展[3-7].八十年代初,上述情况由于Evans和Abdullah的工作[8-12]而发生了变化,他们设计的分组显式方法保证了数值计算的稳定性,同时由于显式求解而使该方法具有很好的并行性质.它是不同类型Saul'yev非对称格式[13]的恰当组合.由于不同的Saul'yev格式的截断误差中某些项绝对值相等,符号相反,在同一时间层和不同时间层上连续交替使用不同的非对称格式,可带来截断误差的部分抵消,从而提高方法的计算精度.这些非对称格式都是隐格式,但由于它们之间的巧妙结合,可以显式求解,这就是Evans-Abdullah分组显式(GE).这项工作说明了建立满足上述要求的新的差分格式是可能的.但是在将分组显式思想应用于变系数问题时,稳定性的证明遇到了困难.
在此基础上,张宝琳等在[14-16]中提出利用Saul'yev非对称格式构造分段隐式的思想,并恰当的使用交替技术建立了多种显-隐式和纯隐式交替并行方法,取得了稳定性和并行兼顾的研究成果.之后又将方法推广到变系数问题,并用能量法证明了方法的绝对稳定性.在数值试验中发现,分段或分块并行计算的结果一般都比原来相应的未加分裂时的结果精确.所以通过分而治之的策略来建立新算法,不但可以用于并行,还可以提高精度.之后涌现出大量的并行差分算法的研究成果,韩臻在[17,18]中详细研究了一类纯显-隐分段和分块交替方法;[19-21]中冯慧等通过不同点的隐式差分格式之间的相互约化来建立新型迭代方法,此方法和Jacobi方法同样具有并行性,却比Jacobi收敛快.[22]中张志跃等给出变系数抛物型问题的分组显式方法,并用能量方法给出稳定性证明.[23-26]中王文洽等针对不同的方程建立了分段的显隐格式,证明方法的稳定性并给出数值算例.上述的方法在并行性和稳定性方面都有其优良的表现,但是他们都存在一个共同的问题,那就是它们都是基于二阶差分格式建立的,这直接影响数值计算中空间的误差精度.近年来,研究人员开始致力于研究高阶紧致差分格式.[27]中Sanjiva K.Lele提出了高阶的紧致差分格式,文中对格式的误差做了Fourier分析,并将它与经典差分格式做了比较.[28-32]中Mark H.Carpenter等针对不同问题提出高阶紧致格式并给出理论分析.将这些高阶差分格式与交替分组思想结合起来,是否可以得到稳定性好,可并行且精度高的数值算法呢?近年来,涌现出大量的高阶交替分组格式的研究工作[44-52].
本文作者在王文洽教授的精心指导下,就抛物型问题的几类数学模型利用有限差分方法的技巧,构造了具有良好数值性质和计算效果的迭代方法、分组显式方法和交替分段方法,对方法做了理论分析并给出算例说明方法的适用性.本人拓广了前人的工作,不具有重复性.本文共分为五章.
第一章中主要利用[19]中冯慧提出的数值Stencil的概念,将其应用于二维对流扩散方程,建立了比Jacobi迭代收敛快的新型迭代算法.本章首先给出针对对流扩散方程的数值Stencil的概念,经过三次消元过程得到最终的数值Stencil,在此基础上建立了新型迭代算法;通过分析迭代误差证明了方法的收敛性,并与Jacobi迭代比较收敛阶;最后数值试验说明方法的适用性,证实了理论分析的结论.本章内容已被《International Journal of Computer Mathematics》接受.
第一章的创新之处在于将[19]中的方法应用到含有时间项的高维抛物型问题中,建立了收敛速度快、具有并行性质的新型迭代格式,通过分析迭代误差证明了方法的收敛性以及与古典迭代法之间收敛阶的比较;最后用实际例子说明了算法的有效性.
第二章主要运用[22,24]中的构造思想,将中心差分格式与分组显式思想相结合,针对含有变系数的对流扩散方程建立了分组显式方法,并用能量方法证明了该格式的稳定性.本章首先给出基于Crank-Nicolson差分格式的四种非对称的逼近方程,通过它们的巧妙组合建立交替分组显式方法;由于扩散项为变系数,所以采用能量法证明稳定性;最后数值试验说明方法的适用性.本章内容已投到《International Journal ofComputer Mathematics》.
第二章的创新之处在于对于变系数的抛物问题给出和Crank-Nicolson格式相匹配的交替分组显格式,并用能量方法证明了稳定性.
接下来的三章内容中,主要借鉴了[14,23-26,46-48]中交替分组(段)格式的思想,将它与高阶差分格式[27-32]相结合,建立了高阶的交替格式;经证明方法都是绝对稳定的,且具有并行性质;在时间步长足够小时,空间的局部截断误差可达到O(h~4)
第三章中首先给出高阶的显、隐差分格式,在隐格式的基础上构造了四种非对称格式,通过它们之间的巧妙组合建立了交替分段显隐格式;由[33-34]中的Kellogg引理证明了方法的无条件稳定性;得到了方法的局部截断误差;数值算例证实了方法的实用性,并且可以达到O(h~4)的误差精度.本章内容已被《计算物理》接受.
第三章的创新之处在于将高阶差分格式与交替分段显隐格式的思想相结合,构造出高阶的交替分段显隐格式.方法具有良好的数值稳定性,空间误差阶可以达到O(h~4)阶.
第四、五章是在第三章的基础上,引入高阶Crank-Nieolson差分格式并适当变形,构造了八个非对称逼近方程;通过交替使用这些差分格式建立了两种不同的数值计算方法.
第四章是单独应用八个非对称差分格式构造了交替分组显格式,通过Kellogg引理证明方法的稳定性,通过误差分析得到两层抵消部分误差后的误差可以达到O(Τh)阶;数值试验说明了方法的实用性,并且时间步长充分小的前提下误差对于空间来说可以达到四阶.本章内容发表在《山东大学学报》(理学版).
第五章利用交替分段格式思想,引入了在非对称格式之间插入对称格式的思想,从而建立交替分段Crank-Nicolson格式.本格式同样具有数值稳定性、可并行性质,误差分析时由于插入中心对称格式,所以在这些点处两层之间部分抵消后误差较小,这在数值试验中得到了证实.交替分段Crank-Nicolson格式的结果比相应的交替分组显格式结果要好.本章内容已投稿到《应用数学与力学》.
后两章的创新之处在于将高阶差分格式与交替分组、交替分段Crank-Nicolson思想充分的结合,建立与第三章不同的非对称Saul'yev格式,在此基础上构造相应的交替方法.这些方法都具有绝对稳定性、可并行性质;并且在空间上截断误差可以达到O(h~4)阶;最后给出数值算例说明方法的适用性.
Parabolic equation is one of basic partial equations.In many science fields,many phenomena are described by parabolic equation(s)[1],such as the process of heat conduction and diffusion,the chemical reaction etc.Among modern numerical methods, the finite difference method is the earliest and most perfect method.So the finite difference method for solving parabolic equation is always a focal which peoples care about.As the parallel computer comes into being and develops,some disadvantage disappears in different means.For example,the classical explicit scheme is suit for parallel computing but it's conditional stability.Especially for high -dimension problem, the time step is limited very severely.The classical implicit and Crank-Nicolson scheme is absolutely stable,but they can be solved only by solving linear equations. Obviously they are not suit for parallel computing.So it's worthy to constructing other new difference methods which has better stability,parallelism and high-precision.
In the early seventies,Miranker[2]pointed out that organizing the traditional difference method in order to parallel computing is the main method when we approximated the partial equation by finite difference method.Between the seventies,the research was mainly about high-order difference scheme for different equations[3-7]. But since the eighties,the situation changed because of Evans and Abdullah's work[8-12].In the early eighties,Evans and Abdullah proposed the idea which constructed group explicit method by appropriate combination of different Saul'yev asymmetric scheme[13].The group explicit method keeps the stability of numerical computing, and has better parallelism because it can be solved explicitly.Because some terms in the truncation error of different Saul'yev scheme is equal for their absolute value and the sigh is contrast,making use of them alternating in a time layer or different layer may cancel some truncation error and the calculation accuracy can be improved.And these Saul'yev scheme were implicit,but the group scheme can be solved explicitly because of appropriate combination.This is Evans-Abdullah's Group Explicit(GE).This work indicated that it's possible to construct new difference methods which satisfy the above conditions.But when they extended the method to variable coefficient problem, the proving of stability is difficult.
Based on this,Zhang Baolin et al.proposed the idea which constructed the segment implicit scheme by using the Saul'yev asymmetric scheme,and set up a variety of explicit-implicit and pure implicit alternating parallel methods by making use of alternate technology[14-16].These methods can keep the stability and parallelism.After that,they extended it to variable coefficient problem and proved its stability by energy method.In the course of numerical experiments,they found that the result of segment or block parallel algorithm is better than the result of the method no splitting. So constructing new method by divide and conquer strategy can not only be used for parallel computing but also improve calculation accuracy.At the same time,there are many research coming into being.For example,Han Zhen studied a kind of pure explicit-implicit segment and block alternating method in detail[17,18].Fenghui et al. constructed the new iteration method for elliptical equation by elimination between difference scheme of different nodes,and the method had same parallelism as Jacobi method and higher convergence rate[19-21].Zhang Zhiyue gave the group explicit scheme for parabolic problem with variable coefficient and proved the stability by energy method[22].Wang Wenqia et al.constructed alternating segment explicit-implicit scheme for different problem,proved their stability and gave numerical experiments[13-26].Recently,Sanjiva K.Lele proposed high-rate compact difference scheme and do Fourier analyzing about error and compare it with traditional scheme[27].[28-32]Mark H.Carpenter et al.proposed some high-order compact difference scheme for different problem and did numerical analysis.Then what will be obtained by combining the high-order difference scheme with alternating group? There were many research coming into being[44-52].It's the new focal that combining the high-rate scheme and the strategy of dividing and conquering.
Under Prof.Wang Wenqia's carefully instructing,the author constructs some parallel difference methods for some parabolic problem which contain iteration method and high-rate alternating group scheme.And the stability of these methods are proved and some numerical experiments indicate their applicability.The paper extends the work of the predecessors,and has non-repeatability.The paper is divided into five chapters.
In Chapter 1,a new iteration method for 2D convection diffusion problem is constructer by making use of numerical Stencil[19].First,it gives the definition of Stencil for parabolic equation,and obtains the final numerical Stencil after three Stencil elimination. Based on this,the new iteration scheme is constructed.Then the convergence of iteration is proved by analyzing the iteration error and the convergence rate is compared with Jacobi method's.Finally the paper gives numerical experiment to show its applicability.The work about§1 is accepted by《Internatinal Journal of Computer Mathematics》
The new idea of Chapter 1 is that numerical Stencil is first applied to 2D parabolic equation,and the high-rate convergence and parallelism iteration is constructed.The proving of stability is obtained and numerical experiments shows its applicability.
Chapter 2 mainly uses the idea in[22,24]and gives the alternating group explicit for convection diffusion equation with variable coefficient.The alternating group explicit scheme is constructed by combining Crank-Nicolson different scheme and the idea of alternating group.First it gives four asymmetric difference scheme based on Crank-Nicolson difference scheme,and constructs the alternating group explicit scheme by combining these asymmetric difference scheme.Then its stability is proved by energy method and numerical experiment indicates its validity.The work about§2 has been submitted to《International Journal of Computer Mathematics》
The new idea of Chapter 2 is that the alternating group explicit scheme is constructed for convection diffusion equation with variable coefficient by combining the idea of alternating group with Crank-Nicolson scheme.
The following chapters mainly uses the idea in[14,23-26,46-48]and introduces the high-rate difference scheme[27-32].Based on this,some group methods are constructed for convection diffusion equation.These scheme are all absolutely stable and have parallelism. The rate of local truncation error can reach O(h~4).
In Chapter 3,the high-rate explicit and implicit difference scheme are given first. Then four asymmetric schemes are constructed based on implicit scheme and the alternating segment explicit-implicit scheme is constructed by appropriate combination of above difference schemes.The absolutely stability is proved by Kellogg lemma in [33-34]and the local truncation error is obtained by derivation.Finally numerical experiments indicates the applicability and the rate of local truncation error can reach O(h~4).The work about§3 is accepted by《Chinese Journal of Computational Physics》 Chapter 4 gives the alternating group explicit scheme for the same equation.First, it gives high-rate Crank-Nicolson difference schemes.Based on this,eight asymmetric difference schemes are constructed in order to construct the alternating group explicit scheme.Then the absolute stability is proved by the same way,and the truncation error can reach O(τh) because some part of truncation error can be cancelled by using different scheme alternately between two time layers.Finally numerical experiment shows the method is applicable.The work about§4 is published in《Journal of Shan-Dong University》(Natural Science).
Based on Chapter 4,Chapter 5 introduces the idea of alternating segment Crank-Nicolson scheme.It combines the eight asymmetric scheme with high-rate Crank-Nicolson scheme and constructs the high-rate alternating segment Crank-Nicolson scheme.It has absolute stability and parallelism.In addition,the truncation error of the points is much less because more parts are canceled by only using Crank-Nicolson on different time layer.It is proved that the result of alternating segment Crank-Nicolson is better than alternating group explicit scheme in numerical experiments. The work about§5 has been submitted to《Applied Mathematics and Mechanics》
The new idea of the last three chapter is:1.)It introduces high-rate difference scheme in order to construct new alternating group scheme for the first time,2.) these scheme has better stability and parallelism,especially its error precision can reach O(h~4).
七十年代初,Miranker指出用有限差分逼近偏微分方程时,主要是组织传统差分方法的并行实现,至于设计新算法,推动力是很小的;之后的十几年高阶差分格式方面的研究得到了发展[3-7].八十年代初,上述情况由于Evans和Abdullah的工作[8-12]而发生了变化,他们设计的分组显式方法保证了数值计算的稳定性,同时由于显式求解而使该方法具有很好的并行性质.它是不同类型Saul'yev非对称格式[13]的恰当组合.由于不同的Saul'yev格式的截断误差中某些项绝对值相等,符号相反,在同一时间层和不同时间层上连续交替使用不同的非对称格式,可带来截断误差的部分抵消,从而提高方法的计算精度.这些非对称格式都是隐格式,但由于它们之间的巧妙结合,可以显式求解,这就是Evans-Abdullah分组显式(GE).这项工作说明了建立满足上述要求的新的差分格式是可能的.但是在将分组显式思想应用于变系数问题时,稳定性的证明遇到了困难.
在此基础上,张宝琳等在[14-16]中提出利用Saul'yev非对称格式构造分段隐式的思想,并恰当的使用交替技术建立了多种显-隐式和纯隐式交替并行方法,取得了稳定性和并行兼顾的研究成果.之后又将方法推广到变系数问题,并用能量法证明了方法的绝对稳定性.在数值试验中发现,分段或分块并行计算的结果一般都比原来相应的未加分裂时的结果精确.所以通过分而治之的策略来建立新算法,不但可以用于并行,还可以提高精度.之后涌现出大量的并行差分算法的研究成果,韩臻在[17,18]中详细研究了一类纯显-隐分段和分块交替方法;[19-21]中冯慧等通过不同点的隐式差分格式之间的相互约化来建立新型迭代方法,此方法和Jacobi方法同样具有并行性,却比Jacobi收敛快.[22]中张志跃等给出变系数抛物型问题的分组显式方法,并用能量方法给出稳定性证明.[23-26]中王文洽等针对不同的方程建立了分段的显隐格式,证明方法的稳定性并给出数值算例.上述的方法在并行性和稳定性方面都有其优良的表现,但是他们都存在一个共同的问题,那就是它们都是基于二阶差分格式建立的,这直接影响数值计算中空间的误差精度.近年来,研究人员开始致力于研究高阶紧致差分格式.[27]中Sanjiva K.Lele提出了高阶的紧致差分格式,文中对格式的误差做了Fourier分析,并将它与经典差分格式做了比较.[28-32]中Mark H.Carpenter等针对不同问题提出高阶紧致格式并给出理论分析.将这些高阶差分格式与交替分组思想结合起来,是否可以得到稳定性好,可并行且精度高的数值算法呢?近年来,涌现出大量的高阶交替分组格式的研究工作[44-52].
本文作者在王文洽教授的精心指导下,就抛物型问题的几类数学模型利用有限差分方法的技巧,构造了具有良好数值性质和计算效果的迭代方法、分组显式方法和交替分段方法,对方法做了理论分析并给出算例说明方法的适用性.本人拓广了前人的工作,不具有重复性.本文共分为五章.
第一章中主要利用[19]中冯慧提出的数值Stencil的概念,将其应用于二维对流扩散方程,建立了比Jacobi迭代收敛快的新型迭代算法.本章首先给出针对对流扩散方程的数值Stencil的概念,经过三次消元过程得到最终的数值Stencil,在此基础上建立了新型迭代算法;通过分析迭代误差证明了方法的收敛性,并与Jacobi迭代比较收敛阶;最后数值试验说明方法的适用性,证实了理论分析的结论.本章内容已被《International Journal of Computer Mathematics》接受.
第一章的创新之处在于将[19]中的方法应用到含有时间项的高维抛物型问题中,建立了收敛速度快、具有并行性质的新型迭代格式,通过分析迭代误差证明了方法的收敛性以及与古典迭代法之间收敛阶的比较;最后用实际例子说明了算法的有效性.
第二章主要运用[22,24]中的构造思想,将中心差分格式与分组显式思想相结合,针对含有变系数的对流扩散方程建立了分组显式方法,并用能量方法证明了该格式的稳定性.本章首先给出基于Crank-Nicolson差分格式的四种非对称的逼近方程,通过它们的巧妙组合建立交替分组显式方法;由于扩散项为变系数,所以采用能量法证明稳定性;最后数值试验说明方法的适用性.本章内容已投到《International Journal ofComputer Mathematics》.
第二章的创新之处在于对于变系数的抛物问题给出和Crank-Nicolson格式相匹配的交替分组显格式,并用能量方法证明了稳定性.
接下来的三章内容中,主要借鉴了[14,23-26,46-48]中交替分组(段)格式的思想,将它与高阶差分格式[27-32]相结合,建立了高阶的交替格式;经证明方法都是绝对稳定的,且具有并行性质;在时间步长足够小时,空间的局部截断误差可达到O(h~4)
第三章中首先给出高阶的显、隐差分格式,在隐格式的基础上构造了四种非对称格式,通过它们之间的巧妙组合建立了交替分段显隐格式;由[33-34]中的Kellogg引理证明了方法的无条件稳定性;得到了方法的局部截断误差;数值算例证实了方法的实用性,并且可以达到O(h~4)的误差精度.本章内容已被《计算物理》接受.
第三章的创新之处在于将高阶差分格式与交替分段显隐格式的思想相结合,构造出高阶的交替分段显隐格式.方法具有良好的数值稳定性,空间误差阶可以达到O(h~4)阶.
第四、五章是在第三章的基础上,引入高阶Crank-Nieolson差分格式并适当变形,构造了八个非对称逼近方程;通过交替使用这些差分格式建立了两种不同的数值计算方法.
第四章是单独应用八个非对称差分格式构造了交替分组显格式,通过Kellogg引理证明方法的稳定性,通过误差分析得到两层抵消部分误差后的误差可以达到O(Τh)阶;数值试验说明了方法的实用性,并且时间步长充分小的前提下误差对于空间来说可以达到四阶.本章内容发表在《山东大学学报》(理学版).
第五章利用交替分段格式思想,引入了在非对称格式之间插入对称格式的思想,从而建立交替分段Crank-Nicolson格式.本格式同样具有数值稳定性、可并行性质,误差分析时由于插入中心对称格式,所以在这些点处两层之间部分抵消后误差较小,这在数值试验中得到了证实.交替分段Crank-Nicolson格式的结果比相应的交替分组显格式结果要好.本章内容已投稿到《应用数学与力学》.
后两章的创新之处在于将高阶差分格式与交替分组、交替分段Crank-Nicolson思想充分的结合,建立与第三章不同的非对称Saul'yev格式,在此基础上构造相应的交替方法.这些方法都具有绝对稳定性、可并行性质;并且在空间上截断误差可以达到O(h~4)阶;最后给出数值算例说明方法的适用性.
Parabolic equation is one of basic partial equations.In many science fields,many phenomena are described by parabolic equation(s)[1],such as the process of heat conduction and diffusion,the chemical reaction etc.Among modern numerical methods, the finite difference method is the earliest and most perfect method.So the finite difference method for solving parabolic equation is always a focal which peoples care about.As the parallel computer comes into being and develops,some disadvantage disappears in different means.For example,the classical explicit scheme is suit for parallel computing but it's conditional stability.Especially for high -dimension problem, the time step is limited very severely.The classical implicit and Crank-Nicolson scheme is absolutely stable,but they can be solved only by solving linear equations. Obviously they are not suit for parallel computing.So it's worthy to constructing other new difference methods which has better stability,parallelism and high-precision.
In the early seventies,Miranker[2]pointed out that organizing the traditional difference method in order to parallel computing is the main method when we approximated the partial equation by finite difference method.Between the seventies,the research was mainly about high-order difference scheme for different equations[3-7]. But since the eighties,the situation changed because of Evans and Abdullah's work[8-12].In the early eighties,Evans and Abdullah proposed the idea which constructed group explicit method by appropriate combination of different Saul'yev asymmetric scheme[13].The group explicit method keeps the stability of numerical computing, and has better parallelism because it can be solved explicitly.Because some terms in the truncation error of different Saul'yev scheme is equal for their absolute value and the sigh is contrast,making use of them alternating in a time layer or different layer may cancel some truncation error and the calculation accuracy can be improved.And these Saul'yev scheme were implicit,but the group scheme can be solved explicitly because of appropriate combination.This is Evans-Abdullah's Group Explicit(GE).This work indicated that it's possible to construct new difference methods which satisfy the above conditions.But when they extended the method to variable coefficient problem, the proving of stability is difficult.
Based on this,Zhang Baolin et al.proposed the idea which constructed the segment implicit scheme by using the Saul'yev asymmetric scheme,and set up a variety of explicit-implicit and pure implicit alternating parallel methods by making use of alternate technology[14-16].These methods can keep the stability and parallelism.After that,they extended it to variable coefficient problem and proved its stability by energy method.In the course of numerical experiments,they found that the result of segment or block parallel algorithm is better than the result of the method no splitting. So constructing new method by divide and conquer strategy can not only be used for parallel computing but also improve calculation accuracy.At the same time,there are many research coming into being.For example,Han Zhen studied a kind of pure explicit-implicit segment and block alternating method in detail[17,18].Fenghui et al. constructed the new iteration method for elliptical equation by elimination between difference scheme of different nodes,and the method had same parallelism as Jacobi method and higher convergence rate[19-21].Zhang Zhiyue gave the group explicit scheme for parabolic problem with variable coefficient and proved the stability by energy method[22].Wang Wenqia et al.constructed alternating segment explicit-implicit scheme for different problem,proved their stability and gave numerical experiments[13-26].Recently,Sanjiva K.Lele proposed high-rate compact difference scheme and do Fourier analyzing about error and compare it with traditional scheme[27].[28-32]Mark H.Carpenter et al.proposed some high-order compact difference scheme for different problem and did numerical analysis.Then what will be obtained by combining the high-order difference scheme with alternating group? There were many research coming into being[44-52].It's the new focal that combining the high-rate scheme and the strategy of dividing and conquering.
Under Prof.Wang Wenqia's carefully instructing,the author constructs some parallel difference methods for some parabolic problem which contain iteration method and high-rate alternating group scheme.And the stability of these methods are proved and some numerical experiments indicate their applicability.The paper extends the work of the predecessors,and has non-repeatability.The paper is divided into five chapters.
In Chapter 1,a new iteration method for 2D convection diffusion problem is constructer by making use of numerical Stencil[19].First,it gives the definition of Stencil for parabolic equation,and obtains the final numerical Stencil after three Stencil elimination. Based on this,the new iteration scheme is constructed.Then the convergence of iteration is proved by analyzing the iteration error and the convergence rate is compared with Jacobi method's.Finally the paper gives numerical experiment to show its applicability.The work about§1 is accepted by《Internatinal Journal of Computer Mathematics》
The new idea of Chapter 1 is that numerical Stencil is first applied to 2D parabolic equation,and the high-rate convergence and parallelism iteration is constructed.The proving of stability is obtained and numerical experiments shows its applicability.
Chapter 2 mainly uses the idea in[22,24]and gives the alternating group explicit for convection diffusion equation with variable coefficient.The alternating group explicit scheme is constructed by combining Crank-Nicolson different scheme and the idea of alternating group.First it gives four asymmetric difference scheme based on Crank-Nicolson difference scheme,and constructs the alternating group explicit scheme by combining these asymmetric difference scheme.Then its stability is proved by energy method and numerical experiment indicates its validity.The work about§2 has been submitted to《International Journal of Computer Mathematics》
The new idea of Chapter 2 is that the alternating group explicit scheme is constructed for convection diffusion equation with variable coefficient by combining the idea of alternating group with Crank-Nicolson scheme.
The following chapters mainly uses the idea in[14,23-26,46-48]and introduces the high-rate difference scheme[27-32].Based on this,some group methods are constructed for convection diffusion equation.These scheme are all absolutely stable and have parallelism. The rate of local truncation error can reach O(h~4).
In Chapter 3,the high-rate explicit and implicit difference scheme are given first. Then four asymmetric schemes are constructed based on implicit scheme and the alternating segment explicit-implicit scheme is constructed by appropriate combination of above difference schemes.The absolutely stability is proved by Kellogg lemma in [33-34]and the local truncation error is obtained by derivation.Finally numerical experiments indicates the applicability and the rate of local truncation error can reach O(h~4).The work about§3 is accepted by《Chinese Journal of Computational Physics》 Chapter 4 gives the alternating group explicit scheme for the same equation.First, it gives high-rate Crank-Nicolson difference schemes.Based on this,eight asymmetric difference schemes are constructed in order to construct the alternating group explicit scheme.Then the absolute stability is proved by the same way,and the truncation error can reach O(τh) because some part of truncation error can be cancelled by using different scheme alternately between two time layers.Finally numerical experiment shows the method is applicable.The work about§4 is published in《Journal of Shan-Dong University》(Natural Science).
Based on Chapter 4,Chapter 5 introduces the idea of alternating segment Crank-Nicolson scheme.It combines the eight asymmetric scheme with high-rate Crank-Nicolson scheme and constructs the high-rate alternating segment Crank-Nicolson scheme.It has absolute stability and parallelism.In addition,the truncation error of the points is much less because more parts are canceled by only using Crank-Nicolson on different time layer.It is proved that the result of alternating segment Crank-Nicolson is better than alternating group explicit scheme in numerical experiments. The work about§5 has been submitted to《Applied Mathematics and Mechanics》
The new idea of the last three chapter is:1.)It introduces high-rate difference scheme in order to construct new alternating group scheme for the first time,2.) these scheme has better stability and parallelism,especially its error precision can reach O(h~4).
引文
[1] A.J.Chorin, J.E.Maxsdon. A Mathematical Introduction to Fluid Mechanics[M]. Second Edition(1990), Springer-Verlag.
[2] W. I. Miranker. A survey of parallelism in numerical analysis[J]. SIAM Review, 1971,13:524-547.
[3] J. M. Varah. Stability of High Order Accurate Difference Methods for Parabolic Equations with Boundary Conditions[J]. SIAM Journal on Numerical Analysis, 1971, 8(3): 569-574.
[4] Robert E. Lynch; John R. Rice. High Accuracy Finite Difference Approximation to Solutions of Elliptic Partial Differential Equations[J]. Proceedings of the National Academy of Sciences of the United States of America, 1978, 75(6): 2541-2544.
[5] Robert E. Lynch; John R. Rice. A High-Order Difference Method for Differential Equations[J]. Mathematics of Computation, 1980, 34(150): 333-372.
[6] Satteluri R. K. Iyengar, R. C. Mittal. High order difference schemes for the wave equation[J]. International Journal for Numerical Methods in Engineering, 1978, 12(10): 1623- 1628.
[7] Murli M. Gupta, Ram P. Manohar, John W. Stephenson . High-order difference schemes for two-dimensional elliptic equations[J]. Numerical Methods for Partial Differential Equations,1985, 1(1): 71-80.
[8] D. J. Evans and A. R. B. Abdullah. Group explicit methods for parabolic equations[J]. Intern. J. comput. math., 1983, 14(1): 73-105.
[9] D.J.Evans and A.R.B.Abdullah. Anew mthod for the solution of ((?)u)/((?)t)=((?)-2u)/((?)x-2)+((?)-2u)/((?)y-2) [J]. Inter.J.Computer Math.,1983,14:325-353.
[10] D. J.Evans and A. R. B. Abdullah . A New Explicit Method for the Diffusion-Convection Equation[J]. Comput. Math. Appl. 1985,11,145-154.
[11] D. J.Evans. Alternating group explicit method for the diffusion equation[J]. Appl. Math. Modelling, 1985,19:201-206.
[12] D.J.Evans and M.S.Sahimi. The alternating group(AGE) iterative method for solving parabolic equations I:2-dimensional prroblems[J]. Inter. J. Computer Math., 1988,24: 311-341.
[13] V. K.Saul'yev. Integration of Equations of Parabolic Type by the Method of Nets[M], Pregamon Press, New York, 1964.
[14]Zhang Bao-lin and Yuan Guo-xing etc.The Parallel Finite Difference Methods for Partial differential Equation[M].BeiJing:Science Press,(1994):203-218.
[15]Zhang Bao-lin.Alternating segment explicit-implicit method for diffusion equation[J].J.Numer.Method Comp.Appl.,1991,12:245-253.
[16]Chen Jing,Zhang Baolin.Aclass of alternating block Crank-Nicolson method,Inter.J.Comp.Math.,1992(45):89-112.
[17]Han Zhen,Fu Hong-yuan and Shen Long-jun.Pure alternating segment explicit-implicit method for the diffusion equations.Inter.J.Computer Math.1993,53:8-15.
[18]韩臻.抛物型偏微分方程(组)的经济差分方法及并行算法.博士论文,北京应用物理与计算数学研究所,1991.
[19]Feng Hui,Zhang Baolin,Liu Yang.The mathematic stencil of the finite difference approximation and its application for Poisson equation[J],China Science(A)(2005):901-909.
[20]H.Ding,C.Shu,A stencil adaptive algorithm for finite difference solution of incompressible viscous flows[J],Journal of Computational Physics 214(2006):397-420.
[21]Rohallah Tavakoli,Parviz Davami.New stable group exlicit finite difference method for solution of diffusion equation[J],Applied Mathematics and Computation,2006,181:1379-1386.
[22]Zhiyue Zhang and Tongke Wang.The Alternating Group Explicit Parallel Algorithm for Convection Dominated Diffusion Problem of Variable Coefficient[J],Inter.J.Comp.Math.,81(2004),823-834.
[23]Wenqia Wang.A Class Alternating Segment Method for Solving Convection Diffusion Equation[],Numer.Math.JCU,2003:289-297.
[24]Wang Wenqia,The Alternating Segment Crank-Nicolson Method for Solving Convection-Diffusion Equation[J],Computing,2004,73:41-55.
[25]Wang Wenqia and Fu Shu-Jun.Alternating Segment Difference Schemes for Dispersive Equations with Diffusion[J].Chinese Jounal of Computational Physics,2005,22(1):19-26.
[26]Li Changfeng and Yuan Yirang.Domain Decomposition Explicit/Implicit Scheme with Modified Upwind Method for Parabolic Equations[J].Chinese Journal of Computational Physics,2007,24(2):239-246.
[27]S.K.Lele.Compact Finite Difference Schemes with Spectral-like Resolution[J],Journal of Computional Physics.1992(103):16-42.
[28]S.C.R.Dennis and J.D.Hudson.Compact h4 finite-difference approximations to Operators of Navier-Stokes Type[J].Journal of Computational Physics,1989,85(2):390-416.
[29] Mark H. Carpenter, David Gottlieb and Saul Abarbanel. The Stability of Numerical Boundary Treatments for Compact High-Order Finite-Difference Schemes[J]. Journal of Computational Physics, 1993, 108(2): 272-295.
[30] Mark H. Carpenter, David Gottlieb and Saul Abarbanel. Stable and accurate boundary treatments for compact, high-order finite-difference schemes[J]. Applied Numerical Mathematics, 1993, 12(1-3):55-87.
[31] Saul S. Abarbanel and Alina E. Chertock. Strict Stability of High-Order Compact Implicit Finite-Difference Schemes: The Role of Boundary Conditions for Hyperbolic PDEs, I[J]. Journal of Computational Physics, 2000, 160(1): 42-66.
[32] Saul S. Abarbanel, Alina E. Chertock and Amir Yefet . Strict Stability of High-Order Compact Implicit Finite-Difference Schemes: The Role of Boundary Conditions for Hyperbolic PDEs, II[J]. Journal of Computational Physics, 2000, 160(1): 67-87.
[33] R. B. Kellogg, Another Alternating-Direction-Implicit Method[J]. Journal of the Society for Industrial and Applied Mathematics, 1963,11(4), pp. 976-979.
[34] R.B.Kellogg, An Alternating Direction Method for Operator Equations[J], SIAM, 1964,12(4),848-854.
[35] Leon Lapidus, George F. Pinder, Numerical Solution of Partial Diffefential Equations in Science and Engineering, John Wiley Sons New York, 1988.
[36] R. D. Rechtmyer, K. W. Morton. Difference Methods for Initial-Value Problems, Krieger, Malabar, FL., 1994.
[37] B. Gustafsson, H. O. Kreiss, J. Oliger. Time Dependent Problems and Difference Methods, Wiley New York, 1995.
[38] J.M.Thomas . Numerical Partial Differential Equation. New York: Springer-Verlag, 1995. 148-162.
[39] Bernard Bialecki, Ryan I. Fernandes. An Orthogonal Spline Collocation Alternating Direction Implicit Crank-Nicolson Method for Linear Parabolic Problems on Rectangles [J]. SIAM Journal on Numerical Analysis, 1999, 36(5): 1414-1434.
[40] Clint N. Dawson, Qiang Du, Todd F. Dupont. A Finite Difference Domain Decomposition Algorithm for Numerical Solution of the Heat Equation[J]. Mathematics of Computation, 1991, 57(195): 63-71.
[41] Guang-wei Yuan, Long-jun Shen, Yu-lin Zhou. Unconditional Stability of Alternating Difference Schemes with Intrinsic Parallelism for Two-Dimensional Parabolic Systems[J]. Inc. Numer Methods Partial Diffential Eq., 1999, 15(6): 25-636.
[42] Yuanle Ma and Zhangxin Chen. Parallel computation for reservoir thermal simulation of multicomponent and multiphase fluid flow[J], Journal of Computational Physics, 2004, 201(1): 224-237.
[43] J. M.Ortega. Introduction to Parallel and Vector Solution of Linear Systems[M]. New York: Plenum Press, 1988. 169-180.
[44] Jichun Li, Miguel R.Visbal. High-order Compact Schemes for Nonlinear Dispersive Waves[J]. Journal of Scientic Computing, 2006,1(26): 1-23.
[45] Jichun Li, Yitung Chen, Guoqing Liu. High-Order Compact ADI Methods for Parabolic Equations[J]. Computers Mathematics with Applications, 2006, 52(8-9): 1343-1356.
[46] Shaohong Zhu. A higher-order alternating group explicit scheme for the diffusion equa-tion[J]. International Journal of Computer Mathematics, 2005, 82(12), 1497-1503.
[47] Shaohong Zhu a, Zhiling Yu, Jennifer Zhao. A high-order parallel finite difference algorithm[J]. Applied Mathematics and Computation,2006(183):365-372.
[48] Shaohong Zhu, Jennifer Zhao. Alternating Schemes of Parallel Computation for the Diffusion Problems[J]. Journal of Numerical Analysis and Modelling, 2007, 4(2): 198-209.
[49] Peter C. Chu and Chenwu Fan. A three-point sixth-order staggered combined compact difference scheme[J]. Mathematical and Computer Modelling, 2000, 32(3-4): 323-340.
[50] Jun Zhang, Lixin Ge and Jules Kouatchou. A two colorable fourth-order compact difference scheme and parallel iterative solution of the 3D convection diffusion equation [J]. Mathematics and Computers in Simulation, 2000, 54(1-3): 65-80.
[51] Z.F. Tian and S.Q. Dai. High-order compact exponential finite difference methods for convection-diffusion type problems[J]. Journal of Computational Physics, 2007, 220(2): 952-974.
[52] Jichao Zhao, Tie Zhang and Robert M. Corless. Convergence of the compact finite difference method for second-order elliptic equations [J]. Applied Mathematics and Computation, 2006, 182(2): 1454-1469.
[2] W. I. Miranker. A survey of parallelism in numerical analysis[J]. SIAM Review, 1971,13:524-547.
[3] J. M. Varah. Stability of High Order Accurate Difference Methods for Parabolic Equations with Boundary Conditions[J]. SIAM Journal on Numerical Analysis, 1971, 8(3): 569-574.
[4] Robert E. Lynch; John R. Rice. High Accuracy Finite Difference Approximation to Solutions of Elliptic Partial Differential Equations[J]. Proceedings of the National Academy of Sciences of the United States of America, 1978, 75(6): 2541-2544.
[5] Robert E. Lynch; John R. Rice. A High-Order Difference Method for Differential Equations[J]. Mathematics of Computation, 1980, 34(150): 333-372.
[6] Satteluri R. K. Iyengar, R. C. Mittal. High order difference schemes for the wave equation[J]. International Journal for Numerical Methods in Engineering, 1978, 12(10): 1623- 1628.
[7] Murli M. Gupta, Ram P. Manohar, John W. Stephenson . High-order difference schemes for two-dimensional elliptic equations[J]. Numerical Methods for Partial Differential Equations,1985, 1(1): 71-80.
[8] D. J. Evans and A. R. B. Abdullah. Group explicit methods for parabolic equations[J]. Intern. J. comput. math., 1983, 14(1): 73-105.
[9] D.J.Evans and A.R.B.Abdullah. Anew mthod for the solution of ((?)u)/((?)t)=((?)-2u)/((?)x-2)+((?)-2u)/((?)y-2) [J]. Inter.J.Computer Math.,1983,14:325-353.
[10] D. J.Evans and A. R. B. Abdullah . A New Explicit Method for the Diffusion-Convection Equation[J]. Comput. Math. Appl. 1985,11,145-154.
[11] D. J.Evans. Alternating group explicit method for the diffusion equation[J]. Appl. Math. Modelling, 1985,19:201-206.
[12] D.J.Evans and M.S.Sahimi. The alternating group(AGE) iterative method for solving parabolic equations I:2-dimensional prroblems[J]. Inter. J. Computer Math., 1988,24: 311-341.
[13] V. K.Saul'yev. Integration of Equations of Parabolic Type by the Method of Nets[M], Pregamon Press, New York, 1964.
[14]Zhang Bao-lin and Yuan Guo-xing etc.The Parallel Finite Difference Methods for Partial differential Equation[M].BeiJing:Science Press,(1994):203-218.
[15]Zhang Bao-lin.Alternating segment explicit-implicit method for diffusion equation[J].J.Numer.Method Comp.Appl.,1991,12:245-253.
[16]Chen Jing,Zhang Baolin.Aclass of alternating block Crank-Nicolson method,Inter.J.Comp.Math.,1992(45):89-112.
[17]Han Zhen,Fu Hong-yuan and Shen Long-jun.Pure alternating segment explicit-implicit method for the diffusion equations.Inter.J.Computer Math.1993,53:8-15.
[18]韩臻.抛物型偏微分方程(组)的经济差分方法及并行算法.博士论文,北京应用物理与计算数学研究所,1991.
[19]Feng Hui,Zhang Baolin,Liu Yang.The mathematic stencil of the finite difference approximation and its application for Poisson equation[J],China Science(A)(2005):901-909.
[20]H.Ding,C.Shu,A stencil adaptive algorithm for finite difference solution of incompressible viscous flows[J],Journal of Computational Physics 214(2006):397-420.
[21]Rohallah Tavakoli,Parviz Davami.New stable group exlicit finite difference method for solution of diffusion equation[J],Applied Mathematics and Computation,2006,181:1379-1386.
[22]Zhiyue Zhang and Tongke Wang.The Alternating Group Explicit Parallel Algorithm for Convection Dominated Diffusion Problem of Variable Coefficient[J],Inter.J.Comp.Math.,81(2004),823-834.
[23]Wenqia Wang.A Class Alternating Segment Method for Solving Convection Diffusion Equation[],Numer.Math.JCU,2003:289-297.
[24]Wang Wenqia,The Alternating Segment Crank-Nicolson Method for Solving Convection-Diffusion Equation[J],Computing,2004,73:41-55.
[25]Wang Wenqia and Fu Shu-Jun.Alternating Segment Difference Schemes for Dispersive Equations with Diffusion[J].Chinese Jounal of Computational Physics,2005,22(1):19-26.
[26]Li Changfeng and Yuan Yirang.Domain Decomposition Explicit/Implicit Scheme with Modified Upwind Method for Parabolic Equations[J].Chinese Journal of Computational Physics,2007,24(2):239-246.
[27]S.K.Lele.Compact Finite Difference Schemes with Spectral-like Resolution[J],Journal of Computional Physics.1992(103):16-42.
[28]S.C.R.Dennis and J.D.Hudson.Compact h4 finite-difference approximations to Operators of Navier-Stokes Type[J].Journal of Computational Physics,1989,85(2):390-416.
[29] Mark H. Carpenter, David Gottlieb and Saul Abarbanel. The Stability of Numerical Boundary Treatments for Compact High-Order Finite-Difference Schemes[J]. Journal of Computational Physics, 1993, 108(2): 272-295.
[30] Mark H. Carpenter, David Gottlieb and Saul Abarbanel. Stable and accurate boundary treatments for compact, high-order finite-difference schemes[J]. Applied Numerical Mathematics, 1993, 12(1-3):55-87.
[31] Saul S. Abarbanel and Alina E. Chertock. Strict Stability of High-Order Compact Implicit Finite-Difference Schemes: The Role of Boundary Conditions for Hyperbolic PDEs, I[J]. Journal of Computational Physics, 2000, 160(1): 42-66.
[32] Saul S. Abarbanel, Alina E. Chertock and Amir Yefet . Strict Stability of High-Order Compact Implicit Finite-Difference Schemes: The Role of Boundary Conditions for Hyperbolic PDEs, II[J]. Journal of Computational Physics, 2000, 160(1): 67-87.
[33] R. B. Kellogg, Another Alternating-Direction-Implicit Method[J]. Journal of the Society for Industrial and Applied Mathematics, 1963,11(4), pp. 976-979.
[34] R.B.Kellogg, An Alternating Direction Method for Operator Equations[J], SIAM, 1964,12(4),848-854.
[35] Leon Lapidus, George F. Pinder, Numerical Solution of Partial Diffefential Equations in Science and Engineering, John Wiley Sons New York, 1988.
[36] R. D. Rechtmyer, K. W. Morton. Difference Methods for Initial-Value Problems, Krieger, Malabar, FL., 1994.
[37] B. Gustafsson, H. O. Kreiss, J. Oliger. Time Dependent Problems and Difference Methods, Wiley New York, 1995.
[38] J.M.Thomas . Numerical Partial Differential Equation. New York: Springer-Verlag, 1995. 148-162.
[39] Bernard Bialecki, Ryan I. Fernandes. An Orthogonal Spline Collocation Alternating Direction Implicit Crank-Nicolson Method for Linear Parabolic Problems on Rectangles [J]. SIAM Journal on Numerical Analysis, 1999, 36(5): 1414-1434.
[40] Clint N. Dawson, Qiang Du, Todd F. Dupont. A Finite Difference Domain Decomposition Algorithm for Numerical Solution of the Heat Equation[J]. Mathematics of Computation, 1991, 57(195): 63-71.
[41] Guang-wei Yuan, Long-jun Shen, Yu-lin Zhou. Unconditional Stability of Alternating Difference Schemes with Intrinsic Parallelism for Two-Dimensional Parabolic Systems[J]. Inc. Numer Methods Partial Diffential Eq., 1999, 15(6): 25-636.
[42] Yuanle Ma and Zhangxin Chen. Parallel computation for reservoir thermal simulation of multicomponent and multiphase fluid flow[J], Journal of Computational Physics, 2004, 201(1): 224-237.
[43] J. M.Ortega. Introduction to Parallel and Vector Solution of Linear Systems[M]. New York: Plenum Press, 1988. 169-180.
[44] Jichun Li, Miguel R.Visbal. High-order Compact Schemes for Nonlinear Dispersive Waves[J]. Journal of Scientic Computing, 2006,1(26): 1-23.
[45] Jichun Li, Yitung Chen, Guoqing Liu. High-Order Compact ADI Methods for Parabolic Equations[J]. Computers Mathematics with Applications, 2006, 52(8-9): 1343-1356.
[46] Shaohong Zhu. A higher-order alternating group explicit scheme for the diffusion equa-tion[J]. International Journal of Computer Mathematics, 2005, 82(12), 1497-1503.
[47] Shaohong Zhu a, Zhiling Yu, Jennifer Zhao. A high-order parallel finite difference algorithm[J]. Applied Mathematics and Computation,2006(183):365-372.
[48] Shaohong Zhu, Jennifer Zhao. Alternating Schemes of Parallel Computation for the Diffusion Problems[J]. Journal of Numerical Analysis and Modelling, 2007, 4(2): 198-209.
[49] Peter C. Chu and Chenwu Fan. A three-point sixth-order staggered combined compact difference scheme[J]. Mathematical and Computer Modelling, 2000, 32(3-4): 323-340.
[50] Jun Zhang, Lixin Ge and Jules Kouatchou. A two colorable fourth-order compact difference scheme and parallel iterative solution of the 3D convection diffusion equation [J]. Mathematics and Computers in Simulation, 2000, 54(1-3): 65-80.
[51] Z.F. Tian and S.Q. Dai. High-order compact exponential finite difference methods for convection-diffusion type problems[J]. Journal of Computational Physics, 2007, 220(2): 952-974.
[52] Jichao Zhao, Tie Zhang and Robert M. Corless. Convergence of the compact finite difference method for second-order elliptic equations [J]. Applied Mathematics and Computation, 2006, 182(2): 1454-1469.
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |