摘要
本文中,我们构造了四阶完全非线性Cahn-Hilliard(CH)型方程和Allen-Cahn/Cahn-Hilliard(AC/CH)方程组的局部间断有限元方法,并证明了一般非线性情形下,CH型方程和AC/CH方程组的LDG方法在任意维数、网格和精度下的能量稳定性。该方法具有高精度,非线性稳定以及h-p自适应的优点。关于一维和二维空间下的CH型方程和AC/CH方程组的数值实验说明了LDG方法的精度和能力,表明了LDG方法在求解这类完全非线性高阶方程时十分有效。
我们构造了三角形网格下行人流动态反应行人平衡模型的DG算法。该模型由关于行人流密度的守恒律方程控制,并且流通量的方向通过Eikonal方程隐式依赖于行人流密度。在数值求解过程中,每一时间步内我们利用三角形网格的快速扫描算法求解Eikonal方程,并通过求解在两个有不同障碍物的站台内的行人流算例来说明该算法的能力,从而快速有效地解决了任意几何区域上行人流模型的求解问题。
为了提高求解LDG空间离散具有高阶导数的偏微分方程后得到的常微分方程组的效率,我们研究了三种半隐时间离散方法。由于LDG空间离散后的半离散形式常微分方程组在时间上呈现多尺度,因此刚性部分要求显式时间离散的时间步长非常小。我们将着重讨论半隐谱延迟校正(SDC)时间离散方法,以及结合LDG空间离散算子后它的稳定性和精度。同时我们也将讨论另外两种时间离散方法,additive Runge-Kutta(ARK)方法和指数时间离散(ETD)方法。并比较三种方法结合LDG空间离散方法在求解含有高阶导数方程时的效率。我们看到三种半隐方法相比显式时间离散方法都是高效的。要指出的是,SDC方法可以轻易推广到任意阶精度,而ARK方法在我们的数值试验中所需的CPU时间最少。
In this thesis we develop local discontinuous Galerkin(LDG)methods for the fourth-order fully nonlinear Cahn-Hilliard(CH)type equations and Allen-Cahn/Cahn-Hilliard(AC/CH)system.The energy stability of the LDG meth-ods is proved for any orders of accuracy on arbitrary triangulations in any space dimension for the general nonlinear case.The LDC discretization results in high order accuracy,nonlinear stable and suitable for hp-adaptation scheme.Numeri-cal examples for the Cahn-Hilliard equations and the Allen-Cahn/Cahn-Hilliard system in one and two dimensions are presented and the numerical results illus-trate the accuracy and capability of the methods.These results indicate that the LDC method is a good tool for solving such nonlinear equations in mathematical physics.
We also develop a discontinuous Galerkin method on triangular meshes to solve the reactive dynamic user equilibrium model for pedestrian flows.The pedestrian density in this model is governed by the conservation law in which the flow flux is implicitly dependent on the density through the EikonaI equation.To solve the Eikonal equation efficiently at each time level,we use the fast sweeping method.Two numerical examples are then used to demonstrate the effectiveness of the algorithm.This algorithm efficiently solves the pedestrian flows problem on arbitrary geometry domain.
We explore three efficient time discretization techniques for the LDG meth-ods to solve partial differential equations(PDEs)with higher order spatial deriv-atives.The main difficulty is the stiffness of the LDC spatial discretization op-erator,which would require a unreasonably small time step for an explicit local time stepping method.We focus our discussion on the semi-implicit spectral deferred correction(SDC)method,and study its stability and accuracy when coupled with the LDG spatial discretization.We also discuss two other time discretization techniques,namely the additive Runge-Kutta(ARK)method and the exponential time differencing(ETD)method,coupled with the LDG spatial discretization.A comparison is made among these three time discretization tech-niques,to conclude that all three methods are efficient when coupled with the LDG spatial discretization for solving PDEs containing higher order spatial deriv-atives.In particular,the SDC method has the advantage of easy implementation for arbitrary order of accuracy,and the ARK method has the smallest CPU cost in our implementation.
引文
[1]R.Alexander.Diagonally implicit Runge-Kutta methods for stiff ODEs.SIAM J.Numer.Anal.,14:1006-1021,1977.
[2]R.Alexander and J.Coyle.Implicit Runge-Kutta methods and differentialalgebraic systems.SIAM J.Numer.Anal.,27:736-752,1990.
[3]A.Araujo,A.Murua,and J.Sanz-Serna.Symplectic methods based on decomposition.SIAM J.Numer.Anal.,34:1926-1947,1997.
[4]D.N.Arnold,F.Brezzi,B.Cockburn,and L.Marini.Unified analysis of discontinuous Galerkin methods for elliptic problems.SIAM J.Numer.Anal.,39:1749-1779,2002.
[5]M.Asano,A.Sumalee,M.Kuwahara,and S.Tanaka.Dynamic cell-transmissionbased pedestrian model with multidirectional flows and strategic route choices.Transportation Research Record.in press.
[6]J.Barrett and J.Blowey.Finite element approximation of a model for phase separation of a multi-component alloy with non-smooth free energy.Numer.Math.,77:1-34,1997.
[7]J.Barrett and J.Blowey.Finite element approximation of a degenerate AllenCahn/Cahn-Hilliard system.SIAM J.Numer.Anal.,39:1598-1624,2001.
[8]J.Barrett and J.Blowey.Finite element approximation of an Allen-Cahn/CahnHilliard system.IMA J.Numer.Anal.,22:11-71,2001.
[9]J.Barrett,J.Blowey,and H.Garcke.Finite element approximation of the CahnHilliard equation with degenerate mobility.SIAM J.Numer.Anal.,37:286-318,1999.
[10]J.Barrett,J.Blowey,and H.Garcke.On fully practical finite element approximations of degenerate Cahn-Hilliard systems.M2AN Math.Model.Numer.Anal.,35:713-748,2001.
[11]F.Bassi and S.Rebay.A high-order accurate discontinuous finite element method for the numerical solution of the compressible Navier-Stokes equations.J.Comput.Phys.,131:267-279,1997.
[12]K.Bey and J.Oden.hp-version discontinuous galerkin methods for hyperbolic conservation laws.Comput.Meth.Appl.Mech.Eng.,133:259-286,1996.
[13]K.Bey,A.Patra,and J.Oden.hp-version discontinuous Galerkin methods for hyperbolic conservation-laws- a parallel adaptive strategy.Int.J.Numer.Methods Eng.,38:3889-3908,1995.
[14]J.Blowey,M.Copetti,and C.Elliott.Numerical analysis of a model for phase separation of multi-component alloy.IMA J.Numer.Anal.,16:111-139,1996.
[15]J.Blowey and C.Elliott.The Cahn-Hilliard gradient theory for phase separation with nonsmooth free energy.Ⅱ.Numerical analysis.European J.Appl.Math.,3:147-179,1992.
[16]M.Boue and P.Dupuis.Markov chain approximations for deterministic control problems with affine dynamics and quadratic cost in the control.SIAM J.Numer.Anal.,36:667-695,1999.
[17]J.Butcher.The Numerical Analysis of Ordinary Differential Equations:RungeKutta and General Linear Methods.Wiley-Interscience,New York,1987.
[18]J.Cahn and J.Hilliard.Free energy of non-uniform system.Ⅰ.Interracial free energy.J.Chem.Phys.,28:258-267,1958.
[19]J.Cahn and A.Novick-Cohen.Evolution equations for phase separation and ordering in binary alloys.J.Star.Phys.,76:877-909,1994.
[20]G.Chavent and B.Cockburn.The local projection p~0 P~1-discontinuous Galerkin finite element method for scalar conservation.M~2AN,23:565-592,1989.
[21]G.Chavent and G.Salzano.A finite-element method for the 1-d water flooding problem with gravity.J.Comput.Phys.,45:307-344,1982.
[22]S.Choo and Y.Lee.A discontinuous Galerkin method for the Cahn-Hilliard equation.J.Appl.Math.Comput.,18:113-126,2005.
[23]B.Cockburn.Discontinuous Galerkin methods for convection-dominated problems.In T.Barth and H.Deconinck,editors,High-Order Methods for Computational Physics,volume 9 of Lecture Notes in Computational Science and Engineering,pages 69-224.Springer,Berlin,1999.
[24]B.Cockburn,S.Hou,and C.-W.Shu.The Runge-Kutta local projection discon-tinuous Galerkin finite element method for conservation laws Ⅳ:the multidimensional case.Math.Comp.,54:545-581,1990.
[25]B.Cockburn,G.Karniadakis,and C.-W.Shu.The development of discontinuous Galerkin methods.In B.Cockburn,G.Karniadakis,and C.-W.Shu,editors,Discontinuous Galerkin Methods:Theory,Computation and Applications,volume 11of Lecture Notes in Computational Science and Engineering,pages 3-50.Springer,Berlin,2000.
[26]B.Cockburn,S.-Y.Lin,and C.-W.Shu.TVB Runge-Kutta local projection discontinuous Galerkin finite dement method for conservation laws Ⅲ:one dimensional systems.J.Comput.Phys.,84:90-113,1989.
[27]B.Cockburn,M.Luskin,C.-W.Shu,and E.Suli.Enhanced accuracy by postprocessing for finite element methods for hyperbolic equations.Math.Comp.,72:577-606,2003.
[28]B.Cockburn and C.-W.Shu.TVB Runge-Kutta local projection discontinuous Galerkin finite element method for conservation laws Ⅱ:general framework.Math.Comp.,52:411-435,1989.
[29]B.Cockburn and C.-W.Shu.The local discontinuous Galerkin method for timedependent convection-diffusion systems.SIAM J.Numer.Anal.,35:2440-2463,1998.
[30]B.Cockburn and C.-W.Shu.The Runge-Kutta discontinuous Galerkin method for conservation laws Ⅴ:multidimensional systems.J.Comput.Phys.,141:199-224,1998.
[31]B.Cockburn and C.-W.Shu.Runge-Kutta discontinuous Galerkin methods for convection-dominated problems.J.Sci.Comput.,16:173-261,2001.
[32]B.Cockburn and C.-W.Shu.Foreword for the special issue on discontinuous Galerkin method.J.Sci.Comput.,22-23:1-3,2005.
[33]M.Copetti and C.Elliott.Numerical analysis of the Cahn-Hilliard equation with logarithmic free energy.Numer.Math.,63:39-65,1992.
[34]S.Cox and P.Matthews.Exponential time differencing for stiff systems.J.Comput.Phys.,176:430-455,2002.
[35]C.Dawson.Foreword for the special issue on discontinuous Galerkin method.Comput.Meth.Appl.Mech.Engin.,195:3183,2006.
[36]A.Dutt,L.Greengard,and V.Rokhlin.Spectral deferred correction methods for ordinary differential equations.BIT,40:241-266,2000.
[37]C.Elliott and D.French.A nonconforming,finite-element method for the twodimensional Cahn-Hilliard equation.SIAM J.Numer.Anal.,26:884-903,1989.
[38]C.Elliott,D.French,and F.Milner.A second order splitting method for the Cahn-Hilliard equation.Numer.Math.,54:575-590,1989.
[39]C.Elliott and H.Garcke.On the Cahn-Hilliard equation with degenerate mobility.SLAM J.Math.Anal.,27:404-423,1996.
[40]D.Eyre.Systems of Cahn-Hilliard equations.SIAM J.Appl.Math.,53:1686-1712,1993.
[41]X.Feng and O.Karakashian.Fully discrete dynamic mesh discontinuous Galerkin methods for the Cahn-Hilliard equation of phase transition.Math.Comp.,76:1093-1117,2007.
[42]X.Feng and A.Prohl.Analysis of a fully discrete finite element method for the phase field model and approximation of its sharp interface limits.Math.Comp.,73:541-567,2004.
[43]D.Furihata.A stable and conservative finite difference scheme for the CahnHilliard equation.Numer.Math.,87:675-699,2001.
[44]S.Gottlieb and C.-W.Shu.Total variation diminishing Runge-Kutta schemes.Math.Comp.,67:73-85,1998.
[45]P.Gremaud and C.Kuster.Computational study of fast methods for the Eikonal equations.SIAM.J.Sci.Comput.,27:1803-1816,2006.
[46]E.Halter and G.Wanner.Solving Ordinary Differential Equations Ⅱ,Stiff and Differential-Algebraic Problems.Springer-Verlag,Berlin,2nd edition,1996.
[47]S.Hoogendoorn and P.Bovy.Dynamic user-optimal assignment in continuous time and space.Transportation Research Part B,38:571-592,2004.
[48]S.Hoogendoorn and P.Bovy.Pedestrian route-choice and activity scheduling theory and models.Transportation Research Part B,38:169-190,2004.
[49]S.Hoogendoorn,P.Bovy,and W.Daamen.Walking infrastructure design assess-merit by continuous space dynamic assignment modeling.Journal of Advanced Transportation,38:69-92,2003.
[50]L.Huang,S.Wong,M.Zhang,C.-W.Shu,and W.Lam.A reactive dynamic user equilibrium model for pedestrian flows:A continuum modeling approach.Transportation Research Part B.submitted.
[51]R.Hughes.A continuum theory for the flow of pedestrians.Transportation Research Part B,36:507-535,2002.
[52]A.-K.Kassam and L.Trefethen.Fourth-order time stepping for stiff problem.SIAM J.Sci.Comput.,26:1214-1233,2005.
[53]13.Kay and R.Welford.A multigrid finite element solver for the Cahn-Hilliard equation.J.Comput.Phys.,212:288-304,2006.
[54]C.Kennedy and M.Carpenter.Additive Runge-Kutta schemes for convectiondiffusion-reaction equations.Appl.Num.Math.,44:139-181,2003.
[55]J.Kim,K.Kang,and J.Lowengrub.Conservative multigrid methods for CahnHilliard fluids.J.Comput.Phys.,193:511-543,2004.
[56]J.Kim,K.Kang,and J.Lowengrub.Conservative multigrid methods for ternary Cahn-Hilliard systems.Commun.Math.Sci.,2:53-77,2004.
[57]A.Kv(?)nφ,S.Nφrsett,and B.Owren.Runge-Kutta research in Trondheim.Appl.Num.Math.,22:263-277,1996.
[58]D.Levy,C.-W.Shu,and J.Yan.Local discontinuous Galerkin methods for nonlinear dispersive equations.J.Comput.Phys.,196:751-772,2004.
[59]M.Minion.Semi-implicit spectral deferred correction methods for ordinary differential equations.Commun.Math.Sci.,1:471-500,2003.
[60]J.Morral and J.Cahn.Spinodal decomposition in ternary systems.Acts Metall.,19:1037-1045,1971.
[61]J.Palaniappan and R.J.R.B.Haber.A spacetime discontinuous Galerkin method for scalar conservation laws.Comput.Meth.Appl.Mech.Eng.,193:3607-3631,2004.
[62]J.Qian,Y.-T.Zhang,and H.-K.Zhao.Fast sweeping methods for Eikonal equations on triangular meshes.SIAM J.Numer.Anal.,45:83-107,2007.
[63]R.Rawlinson and M.Sambridge.Wave front evolution in strongly heterogeneous layered media using the fast marching method.Geophys.J.Internat.,156:631-647,2004.
[64]W.Reed and T.Hill.Triangular mesh methods for the neutrontransport equation. La-ur-73-479,Los Alamos Scientific Laboratory,1973.
[65]J.Remacle,X.Li,M.Shephard,and J.Flaherty.Anisotropic adaptive simulation of transient flows using discontinuous Calerkin methods.Int.J.Numer.Methods Eng,62:899-923,2005.
[66]J.Sethian.Fast marching method.SIAM Review,41:199-235,1999.
[67]J.Serbian and A.Vladimirsky.Fast methods for the Eikonal and related HamiltonJacobi equations on unstructured meshes.Proc.Natl.Acad.Sci.USA,97:5699-5703,2000.
[68]F.Shakib,T.Hughes,and Z.Johan.A new finite-element formulation for computational fluid-dynamics:10.The compressible Euler and Navier-Stokes equations.Comput.Meth.Appl.Mech.Eng.,89:141-219,1991.
[69]C.-W.Shu.TVB uniformly high-order schemes for conservation laws.Math.Comp,49:105-121,1987.
[70]C.-W.Shu and S.Osher.Efficient implementation of essentially non-oscillatory shock-capturing schemes.J.Comput.Phys.,77:439-471,1988.
[71]A.Smolianski,O.Shipilova,and H.Haario.A fast high-resolution algorithm for linear convection problems:particle transport method.Int.J.Numer.Methods Eng.,60:655-684,2007.
[72]Z.Sun.A second-order accurate linearized difference scheme for the twodimensional Cahn-Hilliard equation.Math.Comp.,64:1463-1471,1995.
[73]C.Tong and S.Wong.A predictive dynamic traffic assignment model in congested capacity-constrained road networks.Transportation Research Part B,34:625-644,2000.
[74]Y.Tsai,L.Cheng,S.Osher,and H.Zhao.Fast sweeping algorithms for a class of Hamilton-Jacobi problems.SIAM J.Numer.Anal.,41:673-694,2003.
[75]J.Tsitsiklis.Efficient algorithms for globally optimal trajectories.IEEE Trans.Automat.Control.,40:1528-1538,1995.
[76]B.van Leer.Towards the ultimate conservation difference scheme.Ⅱ.monotonicity and conservation combined in a second-order scheme.J.Comput.Phys,14:361-376,1974.
[77]G.Wells,E.Kuhl,and K.Garikipati.A discontinuous Galerkin method for the Cahn-Hilliard equation.J.Comput.Phys.,218:860-877,2006.
[78]Y.Xu and C.-W.Shu.Local discontinuous galerkin methods for three classes of nonlinear wave equations.J.Comput.Math.,22:250-274,2004.
[79]Y.Xu and C.-W.Shu.Local discontinuous Galerkin methods for nonlinear Schrodinger equations.J.Comput.Phys.,205:72-97,2005.
[80]Y.Xu and C.-W.Shu.Local discontinuous Galerkin methods for two classes of two dimensional nonlinear wave equations.Physica D,208:21-58,2005.
[81]Y.Xu and C.-W.Shu.Local discontinuous Galerkin methods for the KuramotoSivashinsky equations and the Ito-type coupled KdV equations.Comput.Methods Appl.Mech.Engrg.,195:3430-3447,2006.
[82]J.Yah and C.-W.Shu.A local discontinuous Galerkin method for KdV type equations.SIAM J.Numer.Anal.,40:769-791,2002.
[83]J.Yan and C.-W.Shu.Local discontinuous Galerkin methods for partial differential equations with higher order derivatives.J.Sci.Comp.,17:27-47,2002.
[84]H.Zhao.Fast sweeping method for Eikonal equations.Math.Comp.,74:603-627,2005.