求解抛物型方程的若干有限差分并行算法的研究
|
摘要
在自然科学的许多领域中,如热传导以及其它扩散现象、某些生物形态、化学反应等等,是用抛物型方程或方程组描述的.在一些需要快速计算的大型复杂的科学工程计算问题中,需要利用它们内部的并行性,设计出合理的并行算法,然后在并行机上用并行算法求解.通常这些方程必须通过有限差分法求解.因此,我们需要不断完善和改进已有的传统的差分方法,针对具体问题,构造出合理的具有并行性的新的差分算法.
本文以简单的一维热传导方程为例,利用Saul’yev非对称格式,其中, r =ΔΔxt2,构造出分组显示GE法, GE法在r =ΔΔxt2≤1时稳定,其截断误差比单独使用非对称格式有了明显改善,误差为O (Δt +Δx).在不同的时间层交替使用GEL和GER法,得到交替分组显式AGE方法,其数学描述如下其中, k =0,2,4,L.通过研究得到AGE方法是绝对稳定的,稳定性得到了基本改善,同时其截断误差分别为交替分组显式AGE方法的截断误差为O (Δt +Δx).
进而,将AGE方法推广到求解二维抛物型方程有限差分的并行计算中,该方法具有并行性且是无条件稳定的.以二维扩散抛物型方程的初边值问题为例:边界条件为初始条件为u ( x,y,0)= f(x,y) 0< x,y<1 AGE方法定义为:其中, k =1,2,L.
交替差分块方法是受到解二维问题AGE差分方法的启发而产生的一类新的解决二维问题的方法,在一定条件下这种方法能进行并行计算,并且稳定性较好.
最后,针对一维抛物方程,依据分组交替的思想用Saul’yev非对称格式建立了一种新的具有并行性质的差分算法,新算法的一般描述为:其中增长矩阵矩阵G1和G 2为非负定的,利用Kellogg引理得出新算法是绝对稳定的.
最后,通过数值实验对AGE算法和新算法进行了比较,当r <1, =1或> 1时,可以看出新算法都是收敛的,其误差都是可控的.这从实验的角度证明了前面对新算法稳定性的理论分析,即新算法是绝对稳定的.
In many areas of natural sciences, such as heat conduction, other diffusion phenomena, certain biological morphology and chemical reactions, they are described through parabolic equation or equations. In some large complex scientific and engineering computing problems, they need fast computation. Reasonable parallel algorithm should be designed according to their internal parallelism, and then the answer will be obtained with parallel algorithm in parallel machine. Generally, these equations must be solved by the finite difference method. Therefore, those existed and traditional difference methods have to be constantly refined and perfected. New difference algorithm with parallelism should be constructed reasonably for specific questions.
A simple one-dimensional parabolic equation is used as an example, Using Saul’yev Asymmetric format Among them, r =ΔΔxt2, GE grouped method is constructed, When r =ΔΔxt2≤1, GE is stable. Compared with the non-symmetric form alone, the truncation error has significantly improved, and the error is o (Δx+Δt).
When GEL and GER are used alternatively at different time layers, AGE will be obtained. The description of Alternating Group Explicit is as follows:
The research shows that AGE method is absolutely stable. The truncation errors are showed respectively in the following expressions:
The truncation error of AGE is o (Δx+Δt).
Then, the AGE method is extended to solve the two-dimensional finite difference parabolic equations in parallel computing, the method contains parallelism and is unconditionally stable. Take the initial boundary value problem of two-dimensional parabolic diffusion as an example: Boundary conditions are Initial condition is u ( x,y,0)= f(x,y) 0< x,y<1 AGE method can be defined as
Alternating difference block methods is a new method used to solve two-dimensional problem inspired by the solution method of AGE difference. It makes use of the difference relationship between adjacent grid points to solve the problem. It includes the differential block Law and complementary difference block methods. Under certain conditions, this method is capable of doing parallel computing, and has good stability.
For one-dimensional parabolic equation, according to the ideological group alternate format by Saul’yev asymmetric, a new difference algorithm with parallelism is established, which is generally described as: where Growth Matrix:
Matrix G1 and G 2 set are non-negative. The new algorithm is absolutely stable according to Kellogg lemma.
Finally, numerical experiments are done to compare the AGE algorithm and new algorithm, when r <1, =1 or > 1, the new algorithms are convergent and its errors are controllable. The previous theoretical analysis on the stability of the new algorithm is proved, namely, the new algorithm is absolutely stable.
本文以简单的一维热传导方程为例,利用Saul’yev非对称格式,其中, r =ΔΔxt2,构造出分组显示GE法, GE法在r =ΔΔxt2≤1时稳定,其截断误差比单独使用非对称格式有了明显改善,误差为O (Δt +Δx).在不同的时间层交替使用GEL和GER法,得到交替分组显式AGE方法,其数学描述如下其中, k =0,2,4,L.通过研究得到AGE方法是绝对稳定的,稳定性得到了基本改善,同时其截断误差分别为交替分组显式AGE方法的截断误差为O (Δt +Δx).
进而,将AGE方法推广到求解二维抛物型方程有限差分的并行计算中,该方法具有并行性且是无条件稳定的.以二维扩散抛物型方程的初边值问题为例:边界条件为初始条件为u ( x,y,0)= f(x,y) 0< x,y<1 AGE方法定义为:其中, k =1,2,L.
交替差分块方法是受到解二维问题AGE差分方法的启发而产生的一类新的解决二维问题的方法,在一定条件下这种方法能进行并行计算,并且稳定性较好.
最后,针对一维抛物方程,依据分组交替的思想用Saul’yev非对称格式建立了一种新的具有并行性质的差分算法,新算法的一般描述为:其中增长矩阵矩阵G1和G 2为非负定的,利用Kellogg引理得出新算法是绝对稳定的.
最后,通过数值实验对AGE算法和新算法进行了比较,当r <1, =1或> 1时,可以看出新算法都是收敛的,其误差都是可控的.这从实验的角度证明了前面对新算法稳定性的理论分析,即新算法是绝对稳定的.
In many areas of natural sciences, such as heat conduction, other diffusion phenomena, certain biological morphology and chemical reactions, they are described through parabolic equation or equations. In some large complex scientific and engineering computing problems, they need fast computation. Reasonable parallel algorithm should be designed according to their internal parallelism, and then the answer will be obtained with parallel algorithm in parallel machine. Generally, these equations must be solved by the finite difference method. Therefore, those existed and traditional difference methods have to be constantly refined and perfected. New difference algorithm with parallelism should be constructed reasonably for specific questions.
A simple one-dimensional parabolic equation is used as an example, Using Saul’yev Asymmetric format Among them, r =ΔΔxt2, GE grouped method is constructed, When r =ΔΔxt2≤1, GE is stable. Compared with the non-symmetric form alone, the truncation error has significantly improved, and the error is o (Δx+Δt).
When GEL and GER are used alternatively at different time layers, AGE will be obtained. The description of Alternating Group Explicit is as follows:
The research shows that AGE method is absolutely stable. The truncation errors are showed respectively in the following expressions:
The truncation error of AGE is o (Δx+Δt).
Then, the AGE method is extended to solve the two-dimensional finite difference parabolic equations in parallel computing, the method contains parallelism and is unconditionally stable. Take the initial boundary value problem of two-dimensional parabolic diffusion as an example: Boundary conditions are Initial condition is u ( x,y,0)= f(x,y) 0< x,y<1 AGE method can be defined as
Alternating difference block methods is a new method used to solve two-dimensional problem inspired by the solution method of AGE difference. It makes use of the difference relationship between adjacent grid points to solve the problem. It includes the differential block Law and complementary difference block methods. Under certain conditions, this method is capable of doing parallel computing, and has good stability.
For one-dimensional parabolic equation, according to the ideological group alternate format by Saul’yev asymmetric, a new difference algorithm with parallelism is established, which is generally described as: where Growth Matrix:
Matrix G1 and G 2 set are non-negative. The new algorithm is absolutely stable according to Kellogg lemma.
Finally, numerical experiments are done to compare the AGE algorithm and new algorithm, when r <1, =1 or > 1, the new algorithms are convergent and its errors are controllable. The previous theoretical analysis on the stability of the new algorithm is proved, namely, the new algorithm is absolutely stable.
引文
[1] Evans DJ,Aabdullah A R.Group explicit method for parabolic Equations[J]. Inter.J.Computer Math,1983(14):73-105.
[2]B.K.萨乌里耶夫(Saul’yev),抛物型方程的网格积分法,袁兆鼎译,科学出版社,l963.
[3]张宝琳.求解扩散方程的交替分段显-隐式方法[J].数值计算与计算机应用,1991,12:245-253.
[4]ZHANG BAOLIN,SU XIUMIN.Alternating segment Crank-Nicolson scheme [J]. Chinese Journal of Computational Physics,1994,12:115-120.
[5]CHEN JIN,ZHANG BAOLIN.A class of alternating block Crank-Nicolson method [J]. Computer Math,1994,45:89-112.
[6]张宝琳,谷同祥,莫则尧.数值并行计算原理与方法[M].北京:国防工业出版社,1999.
[7]V K Saul,yev,Integration of Equations of parabolie Type by Method of Nets,New York: Pregamon Press, 1964.
[8] Evans DJ,Aabdullah A R.A New Explicit Method for the Diffusion-convection Equations[J].Comp and Math with Appl,1985,11:145-154.
[9]康立山,全惠云.数值解高维偏微分方程的分裂法[M].上海:上海科学技术出版社,1990.
[10]陈景梁.并行算法引论.北京:石油工业出版社,1992.
[11]Evans DJ,Abdullah A R B.A new explicit method for the solution of 2222yuxuxu??? =??+? .Intern .J. Computer Math.,1983,14:325-353.
[12]李荣华.偏微分方程数值解法[M].北京:高等教育出版社,2005: 151-153.
[13]陆金甫,张宝琳,徐涛.求解对流扩散方程的交替分段显-隐式方法[J].数值计算与计算机应用,1998,19:161-167.
[14]陆金甫,张宝琳,徐涛.二维BurGERs方程的AGE方法与并行计算[J].计算物理, 1998,15(2):225-233.
[15]王湘浩等,离散数学.吉林:吉林大学出版社,1998.
[16]张宝琳,袁国兴,刘兴平,陈劲.偏微分方程并行有限差分法[M].北京:科学出版社,1994.
[17]张宝琳,符鸿源.一类交替块Crank-Nicolson方法的差分图[J].科学通报,1999, 40(11):1148-1152.
[18]王文洽.求解扩散方程的一类交替分组显式方法[J]山东大学学报中,2002,37(3): 194-199.
[19]Li Wenzhi,Zhang Baolin.A mixed scheme for diffusion equation.应用数学, 1996,9:378-381.
[20]张宝琳.交替差分块方法及其差分图[J].中国科学(E辑),1998,28(4):357-362.
[21] M.J.QUINN, Designing Efficient Algorithms for Parallel Computers, McGrawHill, Inc. 1987.
[22]黄明游等.数值计算方法.北京:科学出版社.
[23]孙志忠.偏微分方程数值解法.北京:科学出版社.
[24] Evans D J, Sahimi M S. The alternating group explicit(AGE) iterative method for solving parabolic equations I: 2-dimensional problems. Intern. J. Computer Math. 1988, 24: 311-341.
[25] Evans D J.Alternating group explicit method for the diffusion equation. Appl.Math. Modelling, 1985, 19: 201-206.
[26] Zhang Baolin , Li Wenzhi. On alternating segment Crank-Nicolson scheme. Parallel Computing, 1994, 20: 897-902.
[27] Zhang Baolin , Li Wenzhi. AGE method with variable coefficient for parallel computing. Parallel Algorithms and Applications, 1995, 5: 219-228.
[28] Zhang Baolin. Parallelization of the ADI method for the two-dimension diffusion equation. In China-Italy Workshop on High Performance Computing, Beijing. 1996, 28-29.
[29]杨丹丹.求解抛物型方程的一种有限差分并行格式[D].吉林:吉林大学数学研究所, 2010.
[30]吕桂霞.抛物方程有限差分并行算法理论[D].吉林:吉林大学数学研究所,2004.
[2]B.K.萨乌里耶夫(Saul’yev),抛物型方程的网格积分法,袁兆鼎译,科学出版社,l963.
[3]张宝琳.求解扩散方程的交替分段显-隐式方法[J].数值计算与计算机应用,1991,12:245-253.
[4]ZHANG BAOLIN,SU XIUMIN.Alternating segment Crank-Nicolson scheme [J]. Chinese Journal of Computational Physics,1994,12:115-120.
[5]CHEN JIN,ZHANG BAOLIN.A class of alternating block Crank-Nicolson method [J]. Computer Math,1994,45:89-112.
[6]张宝琳,谷同祥,莫则尧.数值并行计算原理与方法[M].北京:国防工业出版社,1999.
[7]V K Saul,yev,Integration of Equations of parabolie Type by Method of Nets,New York: Pregamon Press, 1964.
[8] Evans DJ,Aabdullah A R.A New Explicit Method for the Diffusion-convection Equations[J].Comp and Math with Appl,1985,11:145-154.
[9]康立山,全惠云.数值解高维偏微分方程的分裂法[M].上海:上海科学技术出版社,1990.
[10]陈景梁.并行算法引论.北京:石油工业出版社,1992.
[11]Evans DJ,Abdullah A R B.A new explicit method for the solution of 2222yuxuxu??? =??+? .Intern .J. Computer Math.,1983,14:325-353.
[12]李荣华.偏微分方程数值解法[M].北京:高等教育出版社,2005: 151-153.
[13]陆金甫,张宝琳,徐涛.求解对流扩散方程的交替分段显-隐式方法[J].数值计算与计算机应用,1998,19:161-167.
[14]陆金甫,张宝琳,徐涛.二维BurGERs方程的AGE方法与并行计算[J].计算物理, 1998,15(2):225-233.
[15]王湘浩等,离散数学.吉林:吉林大学出版社,1998.
[16]张宝琳,袁国兴,刘兴平,陈劲.偏微分方程并行有限差分法[M].北京:科学出版社,1994.
[17]张宝琳,符鸿源.一类交替块Crank-Nicolson方法的差分图[J].科学通报,1999, 40(11):1148-1152.
[18]王文洽.求解扩散方程的一类交替分组显式方法[J]山东大学学报中,2002,37(3): 194-199.
[19]Li Wenzhi,Zhang Baolin.A mixed scheme for diffusion equation.应用数学, 1996,9:378-381.
[20]张宝琳.交替差分块方法及其差分图[J].中国科学(E辑),1998,28(4):357-362.
[21] M.J.QUINN, Designing Efficient Algorithms for Parallel Computers, McGrawHill, Inc. 1987.
[22]黄明游等.数值计算方法.北京:科学出版社.
[23]孙志忠.偏微分方程数值解法.北京:科学出版社.
[24] Evans D J, Sahimi M S. The alternating group explicit(AGE) iterative method for solving parabolic equations I: 2-dimensional problems. Intern. J. Computer Math. 1988, 24: 311-341.
[25] Evans D J.Alternating group explicit method for the diffusion equation. Appl.Math. Modelling, 1985, 19: 201-206.
[26] Zhang Baolin , Li Wenzhi. On alternating segment Crank-Nicolson scheme. Parallel Computing, 1994, 20: 897-902.
[27] Zhang Baolin , Li Wenzhi. AGE method with variable coefficient for parallel computing. Parallel Algorithms and Applications, 1995, 5: 219-228.
[28] Zhang Baolin. Parallelization of the ADI method for the two-dimension diffusion equation. In China-Italy Workshop on High Performance Computing, Beijing. 1996, 28-29.
[29]杨丹丹.求解抛物型方程的一种有限差分并行格式[D].吉林:吉林大学数学研究所, 2010.
[30]吕桂霞.抛物方程有限差分并行算法理论[D].吉林:吉林大学数学研究所,2004.