Méthode de quasi-Monte-Carlo

En analyse numérique, la méthode de quasi-Monte-Carlo est une méthode d'intégration numérique et la résolution de problèmes numériques par l'utilisation de suites à discrépance faible. Elle s'oppose donc à la méthode de Monte-Carlo qui utilise des suites de nombres pseudo-aléatoires.

 

256 points tirés selon un générateur pseudo-aléatoire (en haut) et la suite de Halton (en bas)

Les méthodes de Monte-Carlo et quasi-Monte-Carlo se basent sur le même problème : l'approximation de l'intégrale d'une fonction f par la moyenne des valeurs de la fonction évaluées en un ensemble de points x₁,…, x_N:

$\int _{[0,1]^{s}}f(u)\,{\rm {d}}u\approx {\frac {1}{N}}\,\sum _{i=1}^{N}f(x_{i}),$

avec x_i, un vecteur de s éléments. La différence entre les méthodes de Monte-Carlo et quasi-Monte-Carlo tient dans le choix des valeurs x_i. Alors que la méthode de Monte-Carlo utilise une suite de nombres pseudo-aléatoires, la méthode de quasi-Monte-Carlo utilise la suite de Halton, la suite de Sobol ou la suite de Faure, connue pour leur discrépance faible. L'un des avantages est de permettre une convergence plus rapide de la méthode par l'utilisation de suites à discrépance faible (de l'ordre de O(¹⁄_N), alors que la méthode de Monte-Carlo est en O(¹⁄_√N).

La méthode de quasi-Monte-Carlo, comme la méthode de Monte-Carlo, trouve son intérêt dans le calcul précis d'intégrales à grand nombre de dimensions, particulièrement demandé en mathématiques financières .

Estimations d'erreurs d'approximation de la méthode de quasi-Monte-Carlo

L'erreur d'approximation de la méthode de quasi-Monte-Carlo est bornée par un terme proportionnel à la discrépance de la suite des nœuds de calcul x₁…, x_N. Plus précisément, l'inégalité de Koksma-Hlawka borne l'erreur par

$\left|\int _{[0,1]^{s}}f(u)\,{\rm {d}}u-{\frac {1}{N}}\,\sum _{i=1}^{N}f(x_{i})\right|\leq V(f)D_{N}$,

où V(f) est la variation de Hardy-Krause de la fonction f et D_N est la discrépance de l'ensemble (x₁,…,x_N) :

$D_{N}=\sup _{Q\subset [0,1]^{s}}\left|{\frac {\#Q}{N}}-\mathrm {volume} (Q)\right|,$

où Q est un pavé rectangulaire inclus dans [0,1]^s dont chaque face est parallèle aux faces du cube unité et #Q représente le nombre de nœuds contenus dans Q. Cette inégalité permet de montrer que l'erreur d'approximation par une méthode de quasi-Monte-Carlo est en $O\left({\tfrac {(\ln N)^{s}}{N}}\right)$, alors qu'au mieux, la méthode de Monte-Carlo a une erreur en probabilités de $O\left({\tfrac {1}{\sqrt {N}}}\right)$. Ceci n'est cependant qu'une estimation théorique, la pratique montrant une convergence plus rapide.

Liens internes

• Méthode de Monte-Carlo
• Suite à discrépance faible

Références

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Quasi-Monte Carlo method » (voir la liste des auteurs).

• R. E. Caflisch, Monte Carlo and quasi-Monte Carlo methods, Acta Numerica vol. 7, Cambridge University Press, 1998, p. 1–49.
• Josef Dick et Friedrich Pillichshammer, Digital Nets and Sequences. Discrepancy Theory and Quasi-Monte Carlo Integration, Cambridge University Press, Cambridge, 2010, (ISBN 978-0-521-19159-3)
• Michael Drmota et Robert F. Tichy, Sequences, discrepancies and applications, Lecture Notes in Math., 1651, Springer, Berlin, 1997, (ISBN 3-540-62606-9)
• William J. Morokoff et Russel E. Caflisch, Quasi-random sequences and their discrepancies, SIAM J. Sci. Comput. 15 (1994), no. 6, 1251–1279 (At CiteSeer:[2])
• Harald Niederreiter. Random Number Generation and Quasi-Monte Carlo Methods. Society for Industrial and Applied Mathematics, 1992. (ISBN 0-89871-295-5)
• Harald G. Niederreiter, Quasi-Monte Carlo methods and pseudo-random numbers, Bull. Amer. Math. Soc. 84 (1978), no. 6, 957–1041
• Oto Strauch et Štefan Porubský, Distribution of Sequences: A Sampler, Peter Lang Publishing House, Frankfurt am Main 2005, (ISBN 3-631-54013-2)
• Eric Thiémard, Sur le calcul et la majoration de la discrépance à l'origine, Lausanne, 2000