28. INTRODUCTION
AUX MÉTHODESDEMONTE-CARLO
6. Inversion d’une matrice carrée d’ordre n
À y regarder de près, la r&olution de l’équation de Laplace par les techniques du maillage est
équivalente à la résolution d’un syst@me linéaire. En effet, il suffit d’écrire la loi des mailles sur
un ensemble convenablement choisi de points pour obtenir un syst,ème linkaire de rz Cquations à
n, inconnues, n étant lc nombre de nœuds du maillage. Puisque l’on sait résoudre l’équation de
Laplace par une méthode de Monte-Carlo, on est en droit de penser qu’il est possible d’inverser
une matrice également par une mét)hode de Monte-Carlo.
Nous allons simplement donner la technique de résolution dans 1111 cas particulier de matrices
A d’ordre n. qui sont telles que les Pléments de la matrice B = 1~ A (où 1 est la matrice unité)
obéissent aux inégalités suivant,es :
b,i, 2 0
et
c bLj < 1.
j=l
c’est-à-dire que les bii peuvent être interprétés comme des probabilités.
Sans entrer dans 1;: détail, 110~1s allons voir qu’il y a moyen dc décrire des chemins (selon un
processus markovien) dans les lignes et les colonnes de la matrice B qui nous permet de calculer
successivement les lignes de A- l. Pour cela nous allons modifier toutes les lignes en remplac;ant
chaque élément par la somrne des précédents sur chacune des lignes, soit, pour la ligne j :
b .lo
b,o + b,l
bjo+b,,l+b,a
...
b. 70 + bj I + b,,2 e + bi ,<
Dorénavant, on désignera par /?lk ces nouveaux éléments. À prescrit, on peut dkcrire le processus
qui va conduire à l’inversion de la matrice.
a. Souhaitant trouver l’inverse dc la ligne j de A, on commence par tirer ~111 nombre aléatoire &
à distribut,ion rectangulaire sur (0, 1). De ~CLIX choses l’une : ou bien ce nombre est inf&icur
ou égal à l’élément fl,j,, ou bien il lui est supérieur.
b. S’il lui est supérieur on ajoute une unit6 au compteur de la ligne j.
c. S’il lui est infkrieur ou 6gal on cherche la première colonne où l’élément lui est strictement
supérieur ou égal, soit m cette colonne.
d. On tire 1111 autre nombre aléatoire <1 indépendant du premier, et l’on opère avec la ligne m
de la même façon que précédemment. On répète ces opérations jusqu’à ce que l’on trouve un
nombre & correspondant à la ligne T tel que &, > &,, auquel cas on ajoutera 1 au compteur
de la ligne T.
On effectue les opCrations
de (a) à (d) N fois. Désignons par p, les compteurs dc lignes
correspondant donc à l’inversion de la ligne j. Il est possible de montrer que l’on a :
Pour terminer, on traite toutes les lignes selon cette proc6dure ce qui nous fournit l’inverse
(approchée) dc la matrice A.
Dans le cas général, la rnatricc A ne se présente pas sous la forme indiqu& Alors on choisit
des coefficients Yij tels que :
bij = ~2,7~Lj
avec
7rij>O ct
c
7r,i3 < 1.
.j=l
293
AUX MÉTHODESDEMONTE-CARLO
6. Inversion d’une matrice carrée d’ordre n
À y regarder de près, la r&olution de l’équation de Laplace par les techniques du maillage est
équivalente à la résolution d’un syst@me linéaire. En effet, il suffit d’écrire la loi des mailles sur
un ensemble convenablement choisi de points pour obtenir un syst,ème linkaire de rz Cquations à
n, inconnues, n étant lc nombre de nœuds du maillage. Puisque l’on sait résoudre l’équation de
Laplace par une méthode de Monte-Carlo, on est en droit de penser qu’il est possible d’inverser
une matrice également par une mét)hode de Monte-Carlo.
Nous allons simplement donner la technique de résolution dans 1111 cas particulier de matrices
A d’ordre n. qui sont telles que les Pléments de la matrice B = 1~ A (où 1 est la matrice unité)
obéissent aux inégalités suivant,es :
b,i, 2 0
et
c bLj < 1.
j=l
c’est-à-dire que les bii peuvent être interprétés comme des probabilités.
Sans entrer dans 1;: détail, 110~1s allons voir qu’il y a moyen dc décrire des chemins (selon un
processus markovien) dans les lignes et les colonnes de la matrice B qui nous permet de calculer
successivement les lignes de A- l. Pour cela nous allons modifier toutes les lignes en remplac;ant
chaque élément par la somrne des précédents sur chacune des lignes, soit, pour la ligne j :
b .lo
b,o + b,l
bjo+b,,l+b,a
...
b. 70 + bj I + b,,2 e + bi ,<
Dorénavant, on désignera par /?lk ces nouveaux éléments. À prescrit, on peut dkcrire le processus
qui va conduire à l’inversion de la matrice.
a. Souhaitant trouver l’inverse dc la ligne j de A, on commence par tirer ~111 nombre aléatoire &
à distribut,ion rectangulaire sur (0, 1). De ~CLIX choses l’une : ou bien ce nombre est inf&icur
ou égal à l’élément fl,j,, ou bien il lui est supérieur.
b. S’il lui est supérieur on ajoute une unit6 au compteur de la ligne j.
c. S’il lui est infkrieur ou 6gal on cherche la première colonne où l’élément lui est strictement
supérieur ou égal, soit m cette colonne.
d. On tire 1111 autre nombre aléatoire <1 indépendant du premier, et l’on opère avec la ligne m
de la même façon que précédemment. On répète ces opérations jusqu’à ce que l’on trouve un
nombre & correspondant à la ligne T tel que &, > &,, auquel cas on ajoutera 1 au compteur
de la ligne T.
On effectue les opCrations
de (a) à (d) N fois. Désignons par p, les compteurs dc lignes
correspondant donc à l’inversion de la ligne j. Il est possible de montrer que l’on a :
Pour terminer, on traite toutes les lignes selon cette proc6dure ce qui nous fournit l’inverse
(approchée) dc la matrice A.
Dans le cas général, la rnatricc A ne se présente pas sous la forme indiqu& Alors on choisit
des coefficients Yij tels que :
bij = ~2,7~Lj
avec
7rij>O ct
c
7r,i3 < 1.
.j=l
293