Monte carlo cinétique

Méthode de Monte-Carlo cinétique

La méthode de Monte-Carlo cinétique, kinetic Monte Carlo (KMC) en anglais, est une méthode de Monte-Carlo de simulation informatique permettant de simuler des processus se produisant à des taux connus. En cela elle permet de simuler exactement le comportement de systèmes évoluant selon une équation maîtresse.

C’est une méthode peu gourmande en temps de calcul permettant d’explorer des échelles de temps et d’espace importantes. Elle permet en particulier d’étudier des phénomènes à probabilité faible.

Les taux doivent être connus à l'avance, l'algorithme ne fait que les utiliser.

L'algorithme Monte-Carlo cinétique porte plusieurs noms : algorithme à temps de résidence residence-time algorithm, Bortz-Kalos-Liebowitz (BKL) (Bortz 1975), n-fold way algorithme, algorithme ou méthode de Monte-Carlo dynamique ou encore algorithme de Gillespie (Gillespie 1976), ...

Sommaire

1 Algorithme
- 1.1 Taux de transfert indépendants du temps
- 1.2 Taux de transfert variants au cours du temps
2 Autres algorithmes
3 Utilisation
4 Notes et références

Algorithme

Taux de transfert indépendants du temps

À chaque étape, le système dispose de plusieurs états accessibles, les taux de transferts vers chacun des états étant supposés connus.

L'algorithme de Monte-Carlo cinétique est utilisé pour modéliser les sauts aléatoires d'un système d'un état initial vers un ensemble d'états finaux possibles, le nombre total $N t$ de sauts effectués à un instant $t$ étant modélisé par un processus de Poisson. À l'issue de chaque saut, on évalue les conséquences de la transition entre l'état initial et le nouvel état : arrêt de la simulation, nouvelle étape de simulation avec ou sans changement des taux de transfert, etc.

Choix de l'état final : une variable aléatoire est tirée entre 0 et

Γ tot

; la probabilité que le système évolue vers l'état

i

est proportionnelle à

Γ i

Pour se familiariser avec l'algorithme, on suppose dans cette section que les taux de transfert restent constants pendant l'intervalle de temps séparant deux sauts successifs, ce qui correspond à un processus de Poisson homogène. L'algorithme est donné par les étapes suivantes :

On note $t 0$ le temps actuel.
On forme une liste de l'ensemble des taux de transfert $Γ i$ du système, $i = 1,..., N$ , et l'on note $Γ tot = \sum Γ i$ le taux de transfert total.
Le temps $T$ au bout duquel le système quitte son état initial est donné par la formule $T = - ln(U)/Γ tot$ , où $U$ est une variable aléatoire uniformément répartie entre 0 et 1.
On choisit un deuxième nombre aléatoire $U'$ uniformément réparti entre $0$ et $Γ tot$ qui va servir à tirer au hasard l'état final de la transition (voir la figure ci-contre).
Si $U'$ est compris entre $0$ et $Γ 1$ , le système transite vers l'état 1 ; entre $Γ 1$ et $Γ 1 +Γ 2$ le système transite vers l'état 2 ; et si $U'$ est entre $S i -1$ et $S i$ , où $S 0 = 0$ et $S_i = \textstyle\sum_{j=1}^i \Gamma_j$ , le système transite vers l'état $i$ .
Prendre en compte cette transition en effectuant les calculs correspondants.
Changer le temps en $t 0 + T$ et recommencer l'étape 1.

Justification de l'étape 3: La variable aléatoire $T$ représente le temps d'attente avant que le système quitte l'état initial. Sa densité de probabilité est $ρ T (t) = Γ tot exp( - Γ tot t)$ pour $t \in [0, +\infty[$ . La formule utilisée dans l'étape 3 correspond au changement de variable $U = exp( - Γ tot T)$ , ce qui donne bien la même densité de probabilité : $\rho_T(t) = \rho_U(u) \left|\frac{du}{dt} \right|$ si l'on considère $ρ U (u) = 1$ sur $]0, 1]$ .
Justification de l'étape 5: La probabilité que l'état final soit l'état $i$ est $p i = Γ i ⁄ Γ tot$ , ce qui est égal à; $p_i = \frac {\Gamma_i} {\Gamma_\text{tot}} = \frac {S_i-S_{i-1}} {\Gamma_\text{tot}} = \int_{S_{i-1}}^{S_i} \frac{1}{\Gamma_\text{tot}}du' = P(S_{i-1}<U'<S_i)$

Cet algorithme simule l'évolution du système au cours du temps et n'a pas a priori de condition d'arrêt. En pratique, on arrête la boucle lorsque le temps dépasse une certaine valeur ou lorsque le système a effectué un certain nombre de sauts ; la suite des états $i$ suivis par le système au cours du temps est appelée une trajectoire Monte-Carlo ; on répète ensuite cette boucle de manière à obtenir un nombre important de trajectoires, auxquelles on peut appliquer une analyse statistique. Puisque les trajectoires sont indépendantes les unes des autres, il est facile de paralléliser l'algorithme de Monte-Carlo cinétique.

Taux de transfert variants au cours du temps

L'algorithme est essentiellement le même si l'on suppose que les $Γ i$ dépendent du temps, mais les formules reliant $U$ et $U'$ à $T$ et à l'état final $i$ sont différentes :

$T$ est donné par la formule $\int_{t_0}^{t_0+T} \sum_{i=1}^N \Gamma_i(t) dt = -\log u$ , qu'il est nécessaire d'inverser pour trouver $T$ ;
Les sommes $S i$ sont à évaluer en $t = t 0 + T$ . Ceci provient du fait que jusqu'au temps t₀+T le système est encore dans l'état initial (Chotia 2008). Cette absence de "mémoire" est caractéristique d'un processus de Markov.

Autres algorithmes

Un algorithme très similaire est l'algorithme de première réaction First Reaction Method (FRM). Il consiste à choisir la réaction $i$ arrivant la première, tout en utilisant un côté probabiliste stochastique afin de ne pas oublier les autres réactions. Pour cela on choisit $N$ nombres au hasard $u i$ et on choisit le temps de réaction $Δ t i$ qui est le temps minimal parmi ceux déterminés par les $N$ formules

$\int_{t_0}^{t_0+\Delta t_i} \Gamma_i(t) dt = -\log u_i$

Si les taux $Γ i$ sont indépendant du temps les algorithmes KMC et FRM se simplifient naturellement et un autre algorithme souvent plus rapide existe dit de sélection aléatoire Random Selection Method (RSM). Contrairement aux deux autres algorithmes il ne donne pas, à chaque pas de temps, nécessairement lieu à une réaction. Au contraire, il calcule un intervalle de temps $\Delta t = \min_i \, 1/\Gamma_i$ où une seule réaction au maximum est possible. Il choisit ensuite au hasard (entre $1$ et $N$ ) une réaction possible $i$ et un nombre aléatoire associé $u$ . Si $u / Γ i < Δ t$ la réaction est effectuée, elle ne l'est pas dans le cas contraire. Dans tous les cas on met à jour le temps.

Utilisation

L'algorithme Monte-Carlo cinétique est utilisé pour simuler les phénomènes physiques tels que la diffusion de surface, l'épitaxie, l'évolution et la croissance de domaines ou la mobilité des agrégats.

Évidemment cette méthode peut être utilisée de façon beaucoup plus large dès qu'un système évolue selon une équation maîtresse, c’est-à-dire si les processus d'évolution suivent une loi de Poisson et sont non corrélés ; dans ce cas, la méthode de Monte-Carlo cinétique donne le résultat exact de l'évolution du système au cours du temps.

Notes et références

(Bortz 1975): A. B. Bortz and M. H. Kalos and J. L. Lebowitz, Journal of Computational Physics 17 (1975) 10
(Fichthorn 1991): K. A. Fichthorn and W. H. Weinberg, Journal of Chemical Physics 95 (1991) 1090
(Gillespie 1976): D. T. Gillespie, Journal of Computational Physics 22 (1976) 403
(Jansen 2003): A.P.J. Jansen [pdf]An Introduction To Monte Carlo Simulations Of Surface Reactions
(Nordlund 2006): Kai Nordlund Basics of Monte Carlo simulations (Kinetic Monte Carlo)
(Chotia 2008): A. Chotia, M. Viteau, T. Vogt, D. Comparat and P. Pillet, Kinetic Monte Carlo modelling of dipole blockade in Rydberg excitation experiment, New Journal of Physics 10 pages 045031 (2008)

Portail de l’informatique
Portail de la physique
Portail de la chimie
Portail des probabilités et des statistiques
Portail de l’économie

Ce document provient de « M%C3%A9thode de Monte-Carlo cin%C3%A9tique ».

Catégories : Algorithme numérique | Probabilités | Hasard et aléatoire | Physique statistique

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Monte carlo cinétique de Wikipédia en français (auteurs)

Игры ⚽ Поможем сделать НИР

Regardez d'autres dictionnaires:

Methode de Monte-Carlo cinetique — Méthode de Monte Carlo cinétique La méthode de Monte Carlo cinétique, kinetic Monte Carlo (KMC) en anglais, est une méthode de Monte Carlo de simulation informatique permettant de simuler des processus se produisant à des taux connus. En cela… … Wikipédia en Français
Méthode De Monte-Carlo Cinétique — La méthode de Monte Carlo cinétique, kinetic Monte Carlo (KMC) en anglais, est une méthode de Monte Carlo de simulation informatique permettant de simuler des processus se produisant à des taux connus. En cela elle permet de simuler exactement le … Wikipédia en Français
Méthode de Monte Carlo cinétique — La méthode de Monte Carlo cinétique, kinetic Monte Carlo (KMC) en anglais, est une méthode de Monte Carlo de simulation informatique permettant de simuler des processus se produisant à des taux connus. En cela elle permet de simuler exactement le … Wikipédia en Français
Méthode de monte-carlo cinétique — La méthode de Monte Carlo cinétique, kinetic Monte Carlo (KMC) en anglais, est une méthode de Monte Carlo de simulation informatique permettant de simuler des processus se produisant à des taux connus. En cela elle permet de simuler exactement le … Wikipédia en Français
Méthode de Monte-Carlo cinétique — La méthode de Monte Carlo cinétique, kinetic Monte Carlo (KMC) en anglais, est une méthode de Monte Carlo de simulation informatique permettant de simuler des processus se produisant à des taux connus. En cela elle permet de simuler exactement le … Wikipédia en Français
Méthode cinétique Monte Carlo — Méthode de Monte Carlo cinétique La méthode de Monte Carlo cinétique, kinetic Monte Carlo (KMC) en anglais, est une méthode de Monte Carlo de simulation informatique permettant de simuler des processus se produisant à des taux connus. En cela… … Wikipédia en Français
Methode de Monte-Carlo — Méthode de Monte Carlo Pour les articles homonymes, voir Monte Carlo (homonymie). On appelle méthode de Monte Carlo toute méthode visant à calculer une valeur numérique, et utilisant des procédés aléatoires, c est à dire des techniques… … Wikipédia en Français
Méthode De Monte-Carlo — Pour les articles homonymes, voir Monte Carlo (homonymie). On appelle méthode de Monte Carlo toute méthode visant à calculer une valeur numérique, et utilisant des procédés aléatoires, c est à dire des techniques probabilistes. Le nom de ces… … Wikipédia en Français
Méthode de Monte Carlo — Pour les articles homonymes, voir Monte Carlo (homonymie). On appelle méthode de Monte Carlo toute méthode visant à calculer une valeur numérique, et utilisant des procédés aléatoires, c est à dire des techniques probabilistes. Le nom de ces… … Wikipédia en Français
Méthode de monte-carlo — Pour les articles homonymes, voir Monte Carlo (homonymie). On appelle méthode de Monte Carlo toute méthode visant à calculer une valeur numérique, et utilisant des procédés aléatoires, c est à dire des techniques probabilistes. Le nom de ces… … Wikipédia en Français

Dictionnaires et Encyclopédies sur 'Academic'

Monte carlo cinétique

Méthode de Monte-Carlo cinétique

Sommaire

Algorithme

Taux de transfert indépendants du temps

Taux de transfert variants au cours du temps

Autres algorithmes

Utilisation

Notes et références

Regardez d'autres dictionnaires:

Share the article and excerpts

Dictionnaires et Encyclopédies sur 'Academic'

Wikipédia en Français

Monte carlo cinétique

Méthode de Monte-Carlo cinétique

Sommaire

Algorithme

Taux de transfert indépendants du temps

Taux de transfert variants au cours du temps

Autres algorithmes

Utilisation

Notes et références

Regardez d'autres dictionnaires:

Share the article and excerpts

Direct link