title: Méthode de quasi-Monte-Carlo
text: # 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.
  
  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_1,…,$ $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(^1⁄_N),$ alors que la méthode de Monte-Carlo est en $O(^1⁄_{√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_1…,$ $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_1,…,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
  