METROPOLIS ALGORITHME DE

Carte mentale

Élargissez votre recherche dans Universalis

Inventé en 1953 par Nicholas Metropolis et ses collaborateurs (dont Edward Teller, le « père » de la bombe H) du laboratoire de Los Alamos au Nouveau-Mexique, l'algorithme de Metropolis était d'abord destiné à faire calculer par des ordinateurs les équations d'états de mélanges de molécules en interactions. Il s'est depuis lors révélé bien adapté pour résoudre de nombreux problèmes de mécanique statistique et de chimie. L'outil principal de l'algorithme est une chaîne de Markov : on tire au hasard une boule et on déplace son centre d'une distance d ; le mouvement est accepté si la nouvelle configuration des boules reste sans recouvrement.

L'algorithme de Metropolis est un outil fréquemment utilisé dans les simulations numériques, mais sa vitesse de convergence n'est pas précisément connue. Un pas décisif dans la compréhension de cette efficacité vient d'être accompli par trois mathématiciens de l'université de Nice et de l'université Stanford (Californie). Titré « Analyse géométrique pour l'algorithme de Metropolis dans des domaines de Lipschitz », l'article de Persi Diaconis, Gilles Lebeau et Laurent Michel, publié dans la livraison d'août 2011 de la revue Inventiones Mathematicae, analyse un cas particulier important : la distribution de N boules de rayon r sans recouvrement.

Persi Diaconis et ses collaborateurs ont mené une analyse spectrale de cette chaîne de Markov dans le cas où la densité (le produit Nr2) est petite. Ils ont montré que, près de la valeur 1, le spectre est discret, et ils ont pu estimer la distance à la mesure d'équilibre en fonction du produit Nd2. Cette distance est une estimation de la vitesse de convergence de l'algorithme. Leur travail introduit de nouveaux concepts géométriques – le nombre de composantes connexes de l'espace de configuration et la structure des singularités au bord de cet espace –, lesquels devraient permettre de généraliser leur étude au cas, plus intéressant, où la densité n'est pas faible.

—  Bernard PIRE

Écrit par :

  • : directeur de recherche émérite au CNRS, centre de physique théorique de l'École polytechnique, Palaiseau

Classification

Autres références

«  METROPOLIS ALGORITHME DE  » est également traité dans :

PHYSIQUE - Physique et informatique

  • Écrit par 
  • Claude ROIESNEL
  •  • 6 728 mots

Dans le chapitre « Méthode de Monte-Carlo »  : […] La méthode de Monte-Carlo consiste à échantillonner un système dont on connaît l'expression mathématique de la distribution de probabilité des configurations à l'équilibre. Une configuration est définie par un ensemble arbitraire des valeurs de toutes les variables qui décrivent le système. Les propriétés du système sont obtenues en moyennant sur un échantillon de N configurations. Si les configu […] Lire la suite

Pour citer l’article

Bernard PIRE, « METROPOLIS ALGORITHME DE », Encyclopædia Universalis [en ligne], consulté le 26 octobre 2020. URL : https://www.universalis.fr/encyclopedie/algorithme-de-metropolis/