Advanced Search
Article Contents
Article Contents

Word combinatorics for stochastic differential equations: Splitting integrators

  • * Corresponding author

    * Corresponding author
J. M. S. has been supported by project MTM2016-77660-P(AEI/FEDER, UE), MINECO (Spain).
Abstract Full Text(HTML) Related Papers Cited by
  • We present an analysis based on word combinatorics of splitting integrators for Ito or Stratonovich systems of stochastic differential equations. In particular we present a technique to write down systematically the expansion of the local error; this makes it possible to easily formulate the conditions that guarantee that a given integrator achieves a prescribed strong or weak order. This approach bypasses the need to use the Baker-Campbell-Hausdorff (BCH) formula and shows the existence of an order barrier of two for the attainable weak order. The paper also provides a succinct introduction to the combinatorics of words.

    Mathematics Subject Classification: Primary: 65C30, 60H05, 16T05.


    \begin{equation} \\ \end{equation}
  • 加载中
  • [1] A. Alamo and J. M. Sanz-Serna, A technique for studying strong and weak local errors of splitting stochastic integrators, SIAM J. Numer. Anal., 54 (2106), 3239-3257.  doi: 10.1137/16M1058765.
    [2] F. Baudoin, Diffusion Processes and Stochastic Calculus, European Mathematical Society, Textbooks in Mathematics Vol. 16, 2014. doi: 10.4171/133.
    [3] S. Blanes and F. Casas, On the necessity of negative coefficients for operator splitting schemes of order higher than two, Appl. Numer. Maths., 54 (2005), 23-37. doi: 10.1016/j.apnum.2004.10.005.
    [4] S. Blanes and  F. CasasA Concise Introduction to Geometric Numerical Integration, CRC Press, Boca Raton, 2016. 
    [5] S. BlanesF. CasasA. FarrésJ. LaskarJ. Makazaga and A. Murua, New families of symplectic splitting methods for numerical integration in dynamical astronomy, Appl. Numer. Math., 68 (2013), 58-72.  doi: 10.1016/j.apnum.2013.01.003.
    [6] S. BlanesF. Casas and A. Murua, Splitting and composition methods in the numerical integration of differential equations, Bol. Soc. Esp. Mat. Apl. SeMA, 45 (2008), 89-145. 
    [7] Ch. Brouder, Trees, renormalization and differential equations, BIT Numerical Mathematics, 44 (2004), 425-438.  doi: 10.1023/B:BITN.0000046809.66837.cc.
    [8] J. C. Butcher, Coefficients for the study of Runge-Kutta integration processes, J. Austral. Math. Soc., 3 (1963), 185-201. 
    [9] J. C. Butcher, Numerical Methods for Ordinary Differential Equations, 3$^{rd}$ edition, John Wiley & Sons Ltd., Chichester, 2016. doi: 10.1002/9781119121534.
    [10] M. P. Calvo, A. Murua and J. M. Sanz-Serna, Modified equations for ODEs, in Chaotic Numerics (eds. P. E. Kloeden and K. J. Palmer), Contemporary Mathematics, Vol. 172, American Mathematical Society, Providence, (1994), 63–74. doi: 10.1090/conm/172/01798.
    [11] M. P. Calvo and J. M. Sanz-Serna, Canonical B-series, Numer. Math., 67 (1994), 161-175.  doi: 10.1007/s002110050022.
    [12] P. ChartierA. Murua and J. M. Sanz-Serna, Higher-order averaging, formal series and numerical integration Ⅰ: B-series, Found. Comput. Math., 10 (2010), 695-727.  doi: 10.1007/s10208-010-9074-0.
    [13] P. ChartierA. Murua and J. M. Sanz-Serna, Higher-order averaging, formal series and numerical integration Ⅱ: the quasi-periodic case, Found. Comput. Math., 12 (2012), 471-508.  doi: 10.1007/s10208-012-9118-8.
    [14] P. ChartierA. Murua and J. M. Sanz-Serna, A formal series approach to averaging: exponentially small error estimates, DCDS A, 32 (2012), 3009-3027.  doi: 10.3934/dcds.2012.32.3009.
    [15] P. ChartierA. Murua and and J. M. Sanz-Serna, Higher-order averaging, formal series and numerical integration Ⅲ: Error bounds, Found. Comput. Math., 15 (2015), 591-612.  doi: 10.1007/s10208-013-9175-7.
    [16] K. T. Chen, Integration of paths, geometric invariants and a generalized Baker-Hausdorff formula, Ann. of Math., 65 (1957), 163-178.  doi: 10.2307/1969671.
    [17] F. Fauvet and F. Menous, Ecalle's arborification-coarborification transforms and Connes-Kreimer Hopf algebra, Ann. Sci. Ec. Norm. Sup., 50 (2017), 39-83.  doi: 10.24033/asens.2315.
    [18] K. Ebrahimi-FardA. LundervoldS. J. A. MalhamH. Munthe-Kaas and A. Wiese, Algebraic structure of stochastic expansions and efficient simulation, Proc. R. Soc. A, 468 (2012), 2361-2382.  doi: 10.1098/rspa.2012.0024.
    [19] M. Fliess, Fonctionnelles causales non-linéaires et indeterminées noncommutatives, Bull. Soc. Math. France, 109 (1981), 3-40. 
    [20] J. G. Gaines, The algebra of iterated stochastic integrals, Stochastics, 49 (1994), 169-179.  doi: 10.1080/17442509408833918.
    [21] E. Hairer, Ch. Lubich and G. Wanner, Geometric Numerical Integration, 2$^{nd}$ edition, Springer, Berlin, 2006.
    [22] E. Hairer, S. P. Nørsett and G. Wanner, Solving Ordinary Differential Equations I, 2$^{nd}$ edition, Springer-Verlag, Berlin, 1993.
    [23] E. Hairer and G. Wanner, On the Butcher group and general multi-value methods, Computing, 13 (1974), 1-15. 
    [24] M. E. Hoffman, Quasi-shuffle products, J. Algbr. Comb., 11 (2000), 49-68.  doi: 10.1023/A:1008791603281.
    [25] P. E. Kloeden and E. Platen, Numerical Solution of Stochastic Differential Equations, Springer, Berlin, 1992. doi: 10.1007/978-3-662-12616-5.
    [26] B. Leimkuhler and C. Matthews, Rational construction of stochastic numerical methods for molecular sampling, App. Math. Res. Express, 2013 (2013), 34-56. 
    [27] B. Leimkuhler and C. Matthews, Robust and efficient configurational molecular sampling via Langevin Dynamics, J. Chem. Phys., 138 (2013), 174102.
    [28] R. I. McLachlan and G. R. W. Quispel, Splitting methods, Acta Numerica, 11 (2002), 341-434.  doi: 10.1017/S0962492902000053.
    [29] R. H. Merson, An operational method for the study of integration processes, in Proceedings of the Symposium on Data Processing, Weapons Researcch Establishement, Salisbury, Australia, (1957), 110.1–110.25.
    [30] G. N. Miltstein and M. V. Tretyakov, Stochastic Numerics for Mathematical Physics, Springer, Berlin, 2004. doi: 10.1007/978-3-662-10063-9.
    [31] A. Murua, The Hopf algebra of rooted trees, free Lie algebras and Lie series, Found. Comput. Math., 6 (2006), 387-426.  doi: 10.1007/s10208-003-0111-0.
    [32] A. Murua and J. M. Sanz-Serna, Order conditions for numerical integrators obtained by composing simpler integrators, Phil. Trans. R. Soc. Lond. A, 357 (1999), 1079-1100.  doi: 10.1098/rsta.1999.0365.
    [33] A. Murua and J. M. Sanz-Serna, Computing normal forms and formal invariants of dynamical systems by means of word series, Nonlinear Anal.-Theor., 138 (2016), 326-345.  doi: 10.1016/j.na.2015.10.013.
    [34] A. Murua and J. M. Sanz-Serna, Vibrational resonance: a study with high-order word-series averaging, Applied Mathematics and Nonlinear Sciences, 1 (2016), 239-246. 
    [35] A. Murua and J. M. Sanz-Serna, Word series for dynamical systems and their numerical integrators, Found. Comput. Math., 17 (2017), 675-712.  doi: 10.1007/s10208-015-9295-3.
    [36] A. Murua and J. M. Sanz-Serna, Averaging and computing normal forms with word series algorithms, in Discrete Mechanics, Geometric Integration and Lie-Butcher Series (eds. K. Ebrahimi-Fard and M. Barbero Liñan), Springer, Berlin, (2018), 115–137. doi: 10.1007/s10208-010-9074-0.
    [37] A. Murua and J. M. Sanz-Serna, Hopf algebra techniques to handle dynamical systems and numerical integrators, in Computation and Combinatorics in Dynamics, Stochastics and Control, The Abel Symposium, Rosendal, Norway, August 2016 (eds. E. Celledoni, G. Di Nunno, K. Ebrahimi-Fard and H. Z. Munthe-Kaas), Springer, (2019), to appear.
    [38] G. A. Pavliotis, Stochastic Processes and Applications, Springer, New York, 2014. doi: 10.1007/978-1-4939-1323-7.
    [39] E. Platen and W. Wagner, On a Taylor formula for a class of Ito processes, Probab. Math. Statist., 3 (1982), 37-51. 
    [40] R. Ree, Lie elements and an algebra associated with shuffles, Ann. of Math., 68 (1958), 210-220.  doi: 10.2307/1970243.
    [41] C. ReutenauerFree Lie Algebras, Clarendon Press, Oxford, 1993. 
    [42] J. M. Sanz-Serna, Geometric integration, in State of the Art in Numerical Analysis (eds. I. S. Duff and G. A. Watson), Clarendon Press, Oxford, (1997), 121–143.
    [43] J. M. Sanz-Serna and M. P. Calvo, Numerical Hamiltonian Problems, Chapman and Hall, London, 1994.
    [44] J. M. Sanz-Serna and A. Murua, Formal series and numerical integrators: some history and some new techniques, in Proceedings of the 8th International Congress on Industrial and Applied Mathematics (ICIAM 2015) (eds. Lei-Guo and Zhiming-Ma), Higher Education Press, Beijing, (2015), 311–331.
  • 加载中

Article Metrics

HTML views(1455) PDF downloads(242) Cited by(0)

Access History

Other Articles By Authors



    DownLoad:  Full-Size Img  PowerPoint