Abstract
The numerical approximation of boundary value problems by means of a probabilistic representations often has the drawback that the Monte Carlo estimate of the solution is substantially biased due to the presence of the domain boundary. We introduce a scheme, which we have called the leading-term Monte Carlo regression, which seeks to remove that bias by replacing a ’cloud’ of Monte Carlo estimates—carried out at different discretization levels—for the usual single Monte Carlo estimate. The practical result of our scheme is an acceleration of the Monte Carlo method. Theoretical analysis of the proposed scheme, confirmed by numerical experiments, shows that the achieved speedup can be well over 100.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Acebrón, J.A., Busico, M.P., Lanucara, P., Spigler, R.: Domain decomposition solution of elliptic problems via probabilistic methods. SIAM J. Sci. Comput. 27, 440–457 (2005)
Bernal, F., Acebrón, J.A.: A comparison of higher-order weak numerical schemes for stopped stochastic differential equations in bounded domains. Submitted (2015)
Buchmann, F.M.: Simulation of stopped diffusions. J. Comput. Phys. 202(2), 446–462 (2005)
Chatterjee, S., Hadi, A.S.: Regression Analysis by Example. Wiley, London (2012)
Freidlin, M.: Functional Integration and Partial Differential Equations. Princeton University Press, Princeton (1985)
Giles, M.B.: Multi-level Monte Carlo path simulation. Oper. Res. 56(3), 607–617 (2008)
Gobet, E., Menozzi, S.: Exact approximation rate of killed hypoelliptic diffusions using the discrete Euler scheme. Stoch. Proc. Appl. 112(2), 201–223 (2004)
Gobet, E., Menozzi, S.: Stopped diffusion processes: overshoots and boundary correction. Stoch. Proc. Appl. 120, 130–162 (2010)
Higham, D.J., Mao, X., Roj, M., Song, Q., Yin, G.: Mean exit times and the multilevel Monte Carlo method. SIAM/ASA J. Uncertain. Quantif. 1(1), 2–18 (2013)
Jansons, K.M., Lythe, G.D.: Exponential timestepping with boundary test for stochastic differential equations. SIAM J. Sci. Comput. 24, 1809–1822 (2003)
Kloeden, P.E., Platten, E.: Numerical Solution of Stochastic Differential Equations. Springer, Applications of Mathematics, vol. 23 (1999)
Mancini, S. : Monte Carlo approximations of boundary value problems: an efficient algorithm. Master thesis, Università degli Studi di Milano (2013)
Mannella, R.: Absorbing boundaries and optimal stopping in a stochastic differential equation. Phys. Lett. A 254, 257–62 (1999)
Milstein, G.N., Tretyakov, M.V.: Stochastic Numerics for Mathematical Physics. Springer, Berlin (2004)
Neter, J., Kutner, M., Wasserman, W., Nachtsheim, C.: Applied Linear Statistical Models, 4th edn. Irwin (1996)
Nocedal, J., Wright, S.J.: Numerical Optimization. Springer, Berlin (2000)
Sabelfeld, K.K.: Monte Carlo Methods in Boundary Value Problems. Series in Computational Physics. Springer, Berlin (1991)
Talay, D., Tubaro, L.: Expansion of the global error for numerical schemes solving stochastic differential equations. Stoch. Anal. Appl. 8(4), 94–120 (1990)
Acknowledgments
This work was supported by national funds through Fundação para a Ciência e a Tecnologia (FCT) under grants UID/CEC/50021/2013, and PTDC/EIA-CCO/098910/2008. FB also acknowledges FCT funding under grant SFRH/BPD/79986/2011.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Mancini, S., Bernal, F. & Acebrón, J.A. An Efficient Algorithm for Accelerating Monte Carlo Approximations of the Solution to Boundary Value Problems. J Sci Comput 66, 577–597 (2016). https://doi.org/10.1007/s10915-015-0033-4
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10915-015-0033-4