Word combinatorics for stochastic differential equations: Splitting integrators

A. Alamo; J. M. Sanz-Serna

doi:10.3934/cpaa.2019097

Article Contents

2019, Volume 18, Issue 4: 2163-2195. Doi: 10.3934/cpaa.2019097

This issue Previous Article Large-time behavior of solution to an inflow problem on the half space for a class of compressible non-Newtonian fluids Next Article Corrigendum to the paper: Nonuniqueness in Vector-Valued Calculus of Variations in $ L^\infty $ and some Linear Elliptic Systems

Word combinatorics for stochastic differential equations: Splitting integrators

A. Alamo^1, and
J. M. Sanz-Serna^2, ,

1.
Departamento de Matemática Aplicada e IMUVA, Facultad de Ciencias, Universidad de Valladolid, Valladolid, Spain
2.
Departamento de Matemáticas, Universidad Carlos Ⅲ de Madrid, Avenida de la Universidad 30, E-28911 Leganés (Madrid), Spain

^* Corresponding author
^* Corresponding author

Received: April 2018

Revised: November 2018

Published: January 2019

J. M. S. has been supported by project MTM2016-77660-P(AEI/FEDER, UE), MINECO (Spain).

Abstract / Introduction Full Text(HTML) Related Papers Cited by

Abstract

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.

Keywords:

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

Citation:

Full Text(HTML)

Related Papers

Cited by

References

[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. Casas, A Concise Introduction to Geometric Numerical Integration, CRC Press, Boca Raton, 2016.
[5]	S. Blanes, F. Casas, A. Farrés, J. Laskar, J. 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. Blanes, F. 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. Chartier, A. 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. Chartier, A. 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. Chartier, A. 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. Chartier, A. 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-Fard, A. Lundervold, S. J. A. Malham, H. 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. Reutenauer, Free 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.