Abstract
A novel probabilistic numerical method for quantifying the uncertainty induced by the time integration of ordinary differential equations (ODEs) is introduced. Departing from the classical strategy to randomise ODE solvers by adding a random forcing term, we show that a probability measure over the numerical solution of ODEs can be obtained by introducing suitable random time steps in a classical time integrator. This intrinsic randomisation allows for the conservation of geometric properties of the underlying deterministic integrator such as mass conservation, symplecticity or conservation of first integrals. Weak and mean square convergence analysis is derived. We also analyse the convergence of the Monte Carlo estimator for the proposed random time step method and show that the measure obtained with repeated sampling converges in the mean square sense independently of the number of samples. Numerical examples including chaotic Hamiltonian systems, chemical reactions and Bayesian inferential problems illustrate the accuracy, robustness and versatility of our probabilistic numerical method.
Similar content being viewed by others
References
Abdulle, A.: Fourth order Chebyshev methods with recurrence relation. SIAM J. Sci. Comput. 23, 2041–2054 (2002)
Abdulle, A., Medovikov, A.A.: Second order Chebyshev methods based on orthogonal polynomials. Numer. Math. 90, 1–18 (2001)
Andrieu, C., Roberts, G.O.: The pseudo-marginal approach for efficient Monte Carlo computations. Ann. Stat. 37, 697–725 (2009)
Benettin, G., Giorgilli, A.: On the Hamiltonian interpolation of near to the identity symplectic map**s with application to symplectic integration algorithms. J. Stat. Phys. 74, 1117–1143 (1994)
Chkrebtii, O.A., Campbell, D.A., Calderhead, B., Girolami, M.A.: Bayesian solution uncertainty quantification for differential equations. Bayesian Anal. 11, 1239–1267 (2016)
Cockayne, J., Oates, C.J., Sullivan, T.J., Girolami, M.: Probabilistic numerical methods for PDE-constrained Bayesian inverse problems. In: AIP Conference Proceedings, vol 1853, p. 060001 (2017)
Cockayne, J., Oates, C.J., Sullivan, T.J., Girolami, M.: Bayesian probabilistic numerical methods. SIAM Rev. 61, 756–789 (2019)
Conrad, P.R., Girolami, M., Särkkä, S., Stuart, A., Zygalakis, K.: Statistical analysis of differential equations: introducing probability measures on numerical solutions. Stat. Comput. 27, 1065–1082 (2017)
Dashti, M., Stuart, A.M.: The Bayesian approach to inverse problems. In: Handbook of Uncertainty Quantification. Springer, pp. 1–118 (2016)
Hairer, E.: Variable time step integration with symplectic methods. Appl. Numer. Math. 25, 219–227 (1997)
Hairer, E., Wanner, G.: Solving Ordinary Differential Equations II. Stiff and Differential-Algebraic Problems. Springer, Berlin (1996)
Hairer, E., Nørsett, S.P., Wanner, G.: Solving Ordinary Differential Equations I. Nonstiff Problems, vol. 8, Springer Verlag Series in Computational Mathematics, Berlin (1993)
Hairer, E., Lubich, C., Wanner, G.: Geometric Numerical Integration. Structure-Preserving Algorithms for Ordinary Differential Equations, Springer Series in Computational Mathematics, vol. 31, 2nd edn. Springer, Berlin (2006)
Hénon, M., Heiles, C.: The applicability of the third integral of motion: some numerical experiments. Astron. J. 69, 73–79 (1964)
Kersting, H., Hennig, P.: Active uncertainty calibration in Bayesian ODE solvers. In: Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence (UAI 2016), pp. 309–318. AUAI Press (2016)
Lie, H.C., Sullivan, T.J., Teckentrup, A.L.: Random forward models and log-likelihoods in Bayesian inverse problems. SIAM/ASA J. Uncertain. Quantif. 6, 1600–1629 (2018)
Lie, H.C., Stuart, A.M., Sullivan, T.J.: Strong convergence rates of probabilistic integrators for ordinary differential equations. Stat. Comput. 29, 1265–1283 (2019)
Lorenz, E.N.: Deterministic nonperiodic flow. J. Atmos. Sci. 20, 130–141 (1963)
Milstein, G.N., Tretyakov, M.V.: Stochastic Numerics for Mathematical Physics, Scientific Computing. Springer, Berlin (2004)
Milstein, G.N., Tretyakov, M.V.: Numerical integration of stochastic differential equations with nonglobally Lipschitz coefficients. SIAM J. Numer. Anal. 43, 1139–1154 (2005)
Oates, C.J., Sullivan, T.J.: A modern retrospective on probabilistic numerics. Stat. Comput. 29, 1335–1351 (2019)
Olsen, L.F.: An enzyme reaction with a strange attractor. Phys. Lett. A 94, 454–457 (1983)
Pavliotis, G.A.: Stochastic Processes and Applications, vol. 60 of Texts in Applied Mathematics. Diffusion processes, the Fokker–Planck and Langevin Equations. Springer, New York (2014)
Pavliotis, G.A., Stuart, A.M.: Multiscale Methods: Averaging and Homogenization. Texts in Applied Mathematics, vol. 53. Springer, New York (2008)
Schober, M., Duvenaud, D., Hennig, P.: Probabilistic ODE solvers with Runge–Kutta means. In: Advances in Neural Information Processing Systems 27. Curran Associates, Inc., pp. 739–747 (2014)
Skeel, R.D., Gear, C.W.: Does variable step size ruin a symplectic integrator? Physica 60, 311–313 (1992)
Störmer, C.: Sur les trajectoires des corpuscules électrisés. Arch. sci. phys. nat. Genève 24, 5–18, 113–158, 221–247 (1907)
Stuart, A.M.: Inverse problems: a Bayesian perspective. Acta Numer. 19, 451–559 (2010)
Sullivan, T.J.: Well-posed Bayesian inverse problems and heavy-tailed stable quasi-Banach space priors. Inverse Probl. Imaging 11, 857–874 (2017)
van der Houwen, P.J., Sommeijer, B.P.: On the internal stability of explicit, \(m\)-stage Runge–Kutta methods for large \(m\)-values. Z. Angew. Math. Mech. 60, 479–485 (1980)
Verlet, L.: Computer “experiments” on classical fluids. I. Thermodynamical properties of Lennard–Jones molecules. Phys. Rev. 159, 98–103 (1967)
Acknowledgements
We thank the two anonymous reviewers whose comments helped improve and clarify this manuscript. This work is partially supported by the Swiss National Science Foundation, Grant No. 200020 172710.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Appendix
Appendix
1.1 A modified stochastic differential equation
In Remark 5, we claim the existence of a modified stochastic differential equation (SDE) whose solution is well approximated by the RTS-RK method. Let us denote by \({\widetilde{f}}\) the function defining the modified equation corresponding to the numerical flow \(\Psi _h\) truncated after l terms, i.e.
Details about the construction of such a function can be found in Sect. 7.2. In particular, analyticity of the function f is needed for a rigorous backward error analysis to hold. Therefore, we will refer in this section to Assumption 5 (see Sect. 7.2). For the additive noise method presented in Conrad et al. (2017), the authors consider the SDE
where W is a d-dimensional standard Brownian motion. It is possible to show (Conrad et al. 2017, Theorem 2.4) that the solution of (51) satisfies
where \(T = Nh\) and \(Y_N\) is the numerical solution given by the additive noise method after N steps. Here, we present a similar construction for the RTS-RK method. In particular, let us consider the modified SDE
where C is given in Assumption 1(iii). Let us denote by \({\widetilde{{\mathcal {L}}}}\) the generator of (52), which can be written explicitly as
and, adopting the semi-group notation, it satisfies
In the following lemma, we consider the error over one step between the numerical solution given by the RTS-RK method and the solution of (52) in the weak sense. The proof is inspired by the calculations presented in Conrad et al. (2017, Section 2.4).
Lemma 9
Under the assumptions of Lemma 1 and if Assumption 5 holds, then
where C is a positive constant independent of h and of y, \({\widetilde{Y}}\) is the solution of (52) and \(Y_1\) is the numerical solution given by the RTS-RK method after one step.
Proof
Let us consider the modified ODE
and denote its flow as \({\widehat{\varphi }}_t\). The generator \({\widehat{{\mathcal {L}}}} = {\widetilde{f}} \cdot \nabla \) satisfies, adopting the semi-group notation,
We can now compute the distance between the solution to (52) and (53) as
Let us recall that equation (10) gives
which implies that
Now, the theory of backward error analysis (see Sect. 7.2 or e.g. Hairer et al. 2006, Chapter IX) guarantees that
Choosing \(l = 2p - q - 1\), we have therefore
which is the desired result. \(\square \)
The error can be then propagated to final time as in Theorem 1, as presented in the following theorem.
Theorem 7
Under the assumptions of Lemma 9 and Theorem 1, and if there exists a constant \(L > 0\) independent of h such that for all \(\Phi \in {\mathcal {C}}^\infty _b({\mathbb {R}}^d, {\mathbb {R}})\)
then it holds
where \(T = Nh\) and C is a positive constant independent of h and of y, \({\widetilde{Y}}\) is the solution of (52) and \(Y_N\) is the numerical solution given by the RTS-RK method after N steps.
Proof
The proof follows by replacing \({\mathcal {L}}\) with \(\widetilde{{\mathcal {L}}}\) and Lemma 1 with Lemma 9 in the proof of Theorem 1. \(\square \)
1.2 Proof of Lemma 6
In the following, we denote by \(\llbracket a, b \rrbracket \) the interval \(\llbracket a, b \rrbracket = [a, b]\) if \(a < b\) and \(\llbracket a, b \rrbracket = [b, a]\) if \(a \ge b\). Let us first consider \(r \ge 2\) and the function \(\gamma _r(x) = x^r \hbox {e}^{-r\kappa /x}\), whose first derivative is given by
Under Assumption 6, we have that \(H_j \le Mh\) almost surely, and hence for any \(t \in \llbracket h, H_j\rrbracket \)
where we exploited that \(\hbox {e}^{-r\kappa /x}\) is a growing function of x. The fundamental theorem of calculus gives
Taking expectation on both sides and since by (33) it holds \({|}\eta _j{|}^r \le C\gamma _r(H_j)\), we obtain
which proves the desired inequality. This is because Assumption 6 and Assumption 1(ii) imply that \(M \ge 1\), and because Mh can be bounded by M. Let us now consider \(r = 1\). In this case, we have for \(t \in \llbracket h, H_j\rrbracket \)
Hence, we apply the same reasoning as above and obtain almost surely
which implies the desired result by proceeding as above. \(\square \)
1.3 Proof of Lemma 7
We first expand the square as
Then, we expand the square in the first sum and obtain
We then rewrite the term appearing in the double sum in (54) as
Substituting expressions (55) and (56) in (54), we finally get
where the remainder R(a) can be written as \(R = R_1 + R_2 + R_3\) where
and the remainder S(a, b) can be written as \(S = S_1 + S_2 + S_3 + S_4\) where
which proves the desired result. \(\square \)
1.4 Proof of Lemma 8
In the following, all the constants are independent of h and n, but can depend on N and q. Moreover, since \(h < 1\), we often apply \(h^r \le h^s\) for \(r \ge s\). We first notice that, under Assumption 2 and Assumption 5, we get for all \(j = 0, \ldots , n-1\) and \(k = q, \ldots , N-1\)
almost surely and where \(C_\Delta \) is independent of h. Above, we exploited that \(Q_{k+1}\) is Lipschitz continuous for all \(k=q, \ldots , N+1\) due to Assumption 5. Let us now consider \(R(\Delta )\). Due to (57) and to Assumption 6, we have
where \(C > 0\) is a positive constant. Now, since \(k \ge q+1\), we get
Hence, for \(R_1(\Delta )\) there exists a constant \({\widetilde{C}}_1\) such that
We now proceed to the second remainder \(R_2(\Delta )\). Applying the Cauchy–Schwarz inequality and (58), we get
where \(C > 0\) is a positive constant. Now, since in the definition of \(R_2(a)\) in (57) we have \(k \ge q+1\) and \(l \ge q\), we have here \(k+l \ge 2q+1\). Therefore, there exists a constant \({\widetilde{C}}_2\) such that
We now consider the term \(R_3(\Delta )\). Since \(H_i\) and \(H_j\) are independent for \(i \ne j\), we have
Computing the two factors singularly, we have due to (57) and to Assumption 6
and analogously for \({{\mathbb {E}}}(H_i^l - h^l) \Delta _{i,l}\). Then, since \(k+l \ge 2q+1\)
Hence, we have for a constant \({\widetilde{C}}_3 > 0\)
Finally, replacing \(t_n = nh\), we can write for a constant \(C > 0\)
Let us now consider \(S(\Delta , \eta )\). First, we notice that under the assumption \(p \ge 3/2\) we have for any \(r \ge 1\), \(\min \{r, p+r-3/2\} = r\), and therefore Lemma 6 simplifies to
We first consider \(S_1(\Delta , \eta )\). Applying Lemma 6 with \(r = 2\), we obtain for a constant \({\widehat{C}}_1 > 0\)
For the second term \(S_2(\Delta , \eta )\), we have by (33) that \({|}\eta _i{|}\le CH^i \hbox {e}^{-\kappa /H_i}\) and \(\eta _j\le CH^j \hbox {e}^{-\kappa /H_j}\) almost surely. These two bounds are independent for \(i \ne j\), and therefore, applying Lemma 6 with \(r = 1\), we have for a constant \({\widehat{C}}_2 > 0\)
We now consider the third remainder \(S_3(\Delta , \eta )\). Applying the Cauchy–Schwarz inequality, we obtain
Applying Lemma 6 with \(r = 2\) to the first factor and (58) to the second, we get
Now, since \(k \ge q\), we have for a constant \({\widehat{C}}_3 > 0\)
Finally, we consider the last term \(S_4(\Delta , \eta )\). Since by (33) it holds \({|}\eta _j{|} \le CH_j \hbox {e}^{-\kappa /H_j}\) almost surely, and this bound is independent of \(H_i\) for \(i \ne j\), applying (59) and Lemma 6 we have
which, since \(k \ge q\), implies that there exists a constant \({\widehat{C}}_4 > 0\) such that
Finally, replacing \(t_n = nh\), we can write
which completes the proof. \(\square \)
Rights and permissions
About this article
Cite this article
Abdulle, A., Garegnani, G. Random time step probabilistic methods for uncertainty quantification in chaotic and geometric numerical integration. Stat Comput 30, 907–932 (2020). https://doi.org/10.1007/s11222-020-09926-w
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11222-020-09926-w
Keywords
- Probabilistic methods for ODEs
- Random time steps
- Uncertainty quantification
- Chaotic systems
- Geometric integration
- Inverse problems