Skip to main content
Erschienen in: BIT Numerical Mathematics 2/2015

01.06.2015

A continuation multilevel Monte Carlo algorithm

verfasst von: Nathan Collier, Abdul-Lateef Haji-Ali, Fabio Nobile, Erik von Schwerin, Raúl Tempone

Erschienen in: BIT Numerical Mathematics | Ausgabe 2/2015

Einloggen

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

We propose a novel Continuation Multi Level Monte Carlo (CMLMC) algorithm for weak approximation of stochastic models. The CMLMC algorithm solves the given approximation problem for a sequence of decreasing tolerances, ending when the required error tolerance is satisfied. CMLMC assumes discretization hierarchies that are defined a priori for each level and are geometrically refined across levels. The actual choice of computational work across levels is based on parametric models for the average cost per sample and the corresponding variance and weak error. These parameters are calibrated using Bayesian estimation, taking particular notice of the deepest levels of the discretization hierarchy, where only few realizations are available to produce the estimates. The resulting CMLMC estimator exhibits a non-trivial splitting between bias and statistical contributions. We also show the asymptotic normality of the statistical error in the MLMC estimator and justify in this way our error estimate that allows prescribing both required accuracy and confidence in the final result. Numerical results substantiate the above results and illustrate the corresponding computational savings in examples that are described in terms of differential equations either driven by random measures or with random coefficients.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Anhänge
Nur mit Berechtigung zugänglich
Fußnoten
1
For the variance estimator, one can also use the unbiased estimator; by dividing by \(\overline{M}_\ell -1\) instead of \({\overline{M}}_\ell \). All discussions in this work still apply.
 
Literatur
1.
Zurück zum Zitat Amestoy, P.R., Duff, I.S., L’Excellent, J.Y., Koster, J.: A fully asynchronous multifrontal solver using distributed dynamic scheduling. SIAM J. Matrix Anal. Appl. 23, 15–41 (2001)CrossRefMATHMathSciNet Amestoy, P.R., Duff, I.S., L’Excellent, J.Y., Koster, J.: A fully asynchronous multifrontal solver using distributed dynamic scheduling. SIAM J. Matrix Anal. Appl. 23, 15–41 (2001)CrossRefMATHMathSciNet
2.
Zurück zum Zitat Amestoy, P.R., Guermouche, A., L’Excellent, J.Y., Pralet, S.: Hybrid scheduling for the parallel solution of linear systems. Parallel Comput. 32(2), 136–156 (2006)CrossRefMathSciNet Amestoy, P.R., Guermouche, A., L’Excellent, J.Y., Pralet, S.: Hybrid scheduling for the parallel solution of linear systems. Parallel Comput. 32(2), 136–156 (2006)CrossRefMathSciNet
3.
Zurück zum Zitat Babuška, I., Nobile, F., Tempone, R.: A stochastic collocation method for elliptic partial differential equations with random input data. SIAM Rev. 52(2), 317–355 (2010)CrossRefMATHMathSciNet Babuška, I., Nobile, F., Tempone, R.: A stochastic collocation method for elliptic partial differential equations with random input data. SIAM Rev. 52(2), 317–355 (2010)CrossRefMATHMathSciNet
5.
Zurück zum Zitat Barth, A., Schwab, C., Zollinger, N.: Multi-level Monte Carlo finite element method for elliptic PDEs with stochastic coefficients. Numer. Math. 119(1), 123–161 (2011)CrossRefMATHMathSciNet Barth, A., Schwab, C., Zollinger, N.: Multi-level Monte Carlo finite element method for elliptic PDEs with stochastic coefficients. Numer. Math. 119(1), 123–161 (2011)CrossRefMATHMathSciNet
6.
Zurück zum Zitat Charrier, J., Scheichl, R., Teckentrup, A.: Finite element error analysis of elliptic PDEs with random coefficients and its application to multilevel Monte Carlo methods. SIAM J. Numer. Anal. 51(1), 322–352 (2013)CrossRefMATHMathSciNet Charrier, J., Scheichl, R., Teckentrup, A.: Finite element error analysis of elliptic PDEs with random coefficients and its application to multilevel Monte Carlo methods. SIAM J. Numer. Anal. 51(1), 322–352 (2013)CrossRefMATHMathSciNet
7.
Zurück zum Zitat Cliffe, K., Giles, M., Scheichl, R., Teckentrup, A.: Multilevel Monte Carlo methods and applications to elliptic PDEs with random coefficients. Comput. Vis. Sci. 14(1), 3–15 (2011)CrossRefMATHMathSciNet Cliffe, K., Giles, M., Scheichl, R., Teckentrup, A.: Multilevel Monte Carlo methods and applications to elliptic PDEs with random coefficients. Comput. Vis. Sci. 14(1), 3–15 (2011)CrossRefMATHMathSciNet
10.
Zurück zum Zitat Durrett, R.: Probability: Theory and Examples, 2nd edn. Duxbury Press, Belmont (1996) Durrett, R.: Probability: Theory and Examples, 2nd edn. Duxbury Press, Belmont (1996)
11.
Zurück zum Zitat Giles, M.: Improved multilevel Monte Carlo convergence using the Milstein scheme. In: Monte Carlo and quasi-Monte Carlo methods 2006, pp. 343–358. Springer, Berlin (2008) Giles, M.: Improved multilevel Monte Carlo convergence using the Milstein scheme. In: Monte Carlo and quasi-Monte Carlo methods 2006, pp. 343–358. Springer, Berlin (2008)
13.
Zurück zum Zitat Giles, M., Reisinger, C.: Stochastic finite differences and multilevel Monte Carlo for a class of SPDEs in finance. SIAM J. Financ. Math. 3(1), 572–592 (2012)CrossRefMATHMathSciNet Giles, M., Reisinger, C.: Stochastic finite differences and multilevel Monte Carlo for a class of SPDEs in finance. SIAM J. Financ. Math. 3(1), 572–592 (2012)CrossRefMATHMathSciNet
14.
Zurück zum Zitat Giles, M., Szpruch, L.: Antithetic multilevel Monte Carlo estimation for multidimensional SDEs. In: Monte Carlo and Quasi-Monte Carlo Methods 2012. Springer, Berlin (2013) Giles, M., Szpruch, L.: Antithetic multilevel Monte Carlo estimation for multidimensional SDEs. In: Monte Carlo and Quasi-Monte Carlo Methods 2012. Springer, Berlin (2013)
15.
Zurück zum Zitat Giles, M., Szpruch, L.: Multilevel Monte Carlo methods for applications in finance, pp. 3–48. World Scientific, Singapore (2013) Giles, M., Szpruch, L.: Multilevel Monte Carlo methods for applications in finance, pp. 3–48. World Scientific, Singapore (2013)
16.
Zurück zum Zitat Giles, M., Szpruch, L.: Antithetic multilevel Monte Carlo estimation for multi-dimensional SDEs without Lévy area simulation. Ann. Appl. Probab. (2014) Giles, M., Szpruch, L.: Antithetic multilevel Monte Carlo estimation for multi-dimensional SDEs without Lévy area simulation. Ann. Appl. Probab. (2014)
17.
Zurück zum Zitat Glasserman, P.: Monte Carlo methods in financial engineering. Applications of Mathematics (New York), vol. 53. Stochastic Modelling and Applied Probability. Springer, New York (2004) Glasserman, P.: Monte Carlo methods in financial engineering. Applications of Mathematics (New York), vol. 53. Stochastic Modelling and Applied Probability. Springer, New York (2004)
18.
19.
20.
Zurück zum Zitat Hoel, H., Schwerin, E.v., Szepessy, A., Tempone, R.: Adaptive multilevel Monte Carlo simulation. In: Engquist, B., Runborg, O., Tsai, Y.H. (eds.) Numerical Analysis of Multiscale Computations, no. 82 in Lecture Notes in Computational Science and Engineering, pp. 217–234. Springer, New York (2012) Hoel, H., Schwerin, E.v., Szepessy, A., Tempone, R.: Adaptive multilevel Monte Carlo simulation. In: Engquist, B., Runborg, O., Tsai, Y.H. (eds.) Numerical Analysis of Multiscale Computations, no. 82 in Lecture Notes in Computational Science and Engineering, pp. 217–234. Springer, New York (2012)
21.
Zurück zum Zitat Hunter, J.D.: Matplotlib: a 2D graphics environment. Comput. Sci. Eng. 9(3), 90–95 (2007)CrossRef Hunter, J.D.: Matplotlib: a 2D graphics environment. Comput. Sci. Eng. 9(3), 90–95 (2007)CrossRef
22.
Zurück zum Zitat Jouini, E., Cvitanić, J., Musiela, M. (eds.): Handbooks in Mathematical Finance. Option Pricing, Interest Rates and Risk Management. Cambridge University Press, Cambridge (2001) Jouini, E., Cvitanić, J., Musiela, M. (eds.): Handbooks in Mathematical Finance. Option Pricing, Interest Rates and Risk Management. Cambridge University Press, Cambridge (2001)
23.
Zurück zum Zitat Karatzas, I., Shreve, S.E.: Brownian Motion and Stochastic Calculus, Graduate Texts in Mathematics, 2nd edn, vol. 113. Springer, New York (1991) Karatzas, I., Shreve, S.E.: Brownian Motion and Stochastic Calculus, Graduate Texts in Mathematics, 2nd edn, vol. 113. Springer, New York (1991)
24.
Zurück zum Zitat Kebaier, A.: Statistical Romberg extrapolation: a new variance reduction method and applications to options pricing. Ann. Appl. Probab. 14(4), 2681–2705 (2005)CrossRefMathSciNet Kebaier, A.: Statistical Romberg extrapolation: a new variance reduction method and applications to options pricing. Ann. Appl. Probab. 14(4), 2681–2705 (2005)CrossRefMathSciNet
25.
Zurück zum Zitat Mordecki, E., Szepessy, A., Tempone, R., Zouraris, G.E.: Adaptive weak approximation of diffusions with jumps. SIAM J. Numer. Anal. 46(4), 1732–1768 (2008)CrossRefMATHMathSciNet Mordecki, E., Szepessy, A., Tempone, R., Zouraris, G.E.: Adaptive weak approximation of diffusions with jumps. SIAM J. Numer. Anal. 46(4), 1732–1768 (2008)CrossRefMATHMathSciNet
26.
Zurück zum Zitat Øksendal, B.: Stochastic differential equations. Universitext, 5th edn. Springer, Berlin (1998) Øksendal, B.: Stochastic differential equations. Universitext, 5th edn. Springer, Berlin (1998)
27.
Zurück zum Zitat Sivia, D.S., Skilling, J.: Data Analysis.: A Bayesian Tutorial, 2nd edn. Oxford University Press, Oxford (2006) Sivia, D.S., Skilling, J.: Data Analysis.: A Bayesian Tutorial, 2nd edn. Oxford University Press, Oxford (2006)
28.
Zurück zum Zitat Szepessy, A., Tempone, R., Zouraris, G.E.: Adaptive weak approximation of stochastic differential equations. Commun. Pure Appl. Math. 54(10), 1169–1214 (2001)CrossRefMATHMathSciNet Szepessy, A., Tempone, R., Zouraris, G.E.: Adaptive weak approximation of stochastic differential equations. Commun. Pure Appl. Math. 54(10), 1169–1214 (2001)CrossRefMATHMathSciNet
29.
Zurück zum Zitat Teckentrup, A.: Multilevel Monte Carlo methods and uncertainty quantification. PhD thesis, University of Bath (2013) Teckentrup, A.: Multilevel Monte Carlo methods and uncertainty quantification. PhD thesis, University of Bath (2013)
30.
Zurück zum Zitat Teckentrup, A., Scheichl, R., Giles, M., Ullmann, E.: Further analysis of multilevel Monte Carlo methods for elliptic PDEs with random coefficients. Numer. Math. 125(3), 569–600 (2013)CrossRefMATHMathSciNet Teckentrup, A., Scheichl, R., Giles, M., Ullmann, E.: Further analysis of multilevel Monte Carlo methods for elliptic PDEs with random coefficients. Numer. Math. 125(3), 569–600 (2013)CrossRefMATHMathSciNet
31.
Zurück zum Zitat Xia, Y., Giles, M.: Multilevel path simulation for jump-diffusion SDEs. In: Plaskota, L., Woźniakowski, H. (eds.) Monte Carlo and Quasi-Monte Carlo Methods 2010, pp. 695–708. Springer, Berlin (2012) Xia, Y., Giles, M.: Multilevel path simulation for jump-diffusion SDEs. In: Plaskota, L., Woźniakowski, H. (eds.) Monte Carlo and Quasi-Monte Carlo Methods 2010, pp. 695–708. Springer, Berlin (2012)
Metadaten
Titel
A continuation multilevel Monte Carlo algorithm
verfasst von
Nathan Collier
Abdul-Lateef Haji-Ali
Fabio Nobile
Erik von Schwerin
Raúl Tempone
Publikationsdatum
01.06.2015
Verlag
Springer Netherlands
Erschienen in
BIT Numerical Mathematics / Ausgabe 2/2015
Print ISSN: 0006-3835
Elektronische ISSN: 1572-9125
DOI
https://doi.org/10.1007/s10543-014-0511-3

Weitere Artikel der Ausgabe 2/2015

BIT Numerical Mathematics 2/2015 Zur Ausgabe