46
2 Chaˆ ınes de Markov abstraites
U xn (x n+1 ) = U (x n )+U
(x n ) (x n+1 −x n ) = 0 ⇔ x n+1 = x n −U
(x n )
−1 U (x n )
conduit `
a une descente de gradient li´ ee `
a la courbure autour des ´ etats visit´ es.
Cette d´ ependance permet bien souvent d’acc´ el´ erer la convergence des ´ etats
x n vers l’un des z´ ero x ∞ de la fonction U (x ∞ ) = 0.
La version multidimensionnelle de l’algorithme pr´ ec´ edent est donn´ ee par
les ´ equations
x n+1 = x n − Jac(U )(x n )
−1 U (x n )
(2.7)
o` u Jac(U )(x n )
−1 d´ esigne l’inverse de la matrice Jacobienne Jac(U )(x n ) de U .
On remarquera que cet algorithme n´ ecessite de r´ esoudre le syst` eme d’´ equations
lin´ eaires
Jac(U )(x n ) (x n+1 − x n ) = U (x n )
Bien entendu ces techniques d’approximation numeriques ne sont efficaces
que pour des fonctions suffisamment r´ eguli` eres, et des choix de conditions
initiales pas trop ´ eloign´ ees des z´ eros de la fonction recherch´ es (afin d’´ eviter de
visiter des ´ etats o` u la d´ eriv´ e s’annule, dans le cas unidimensionnel ; ou dans le
cas multi-dimensionnel, ´ eviter des ´ etats o` u le jacobien n’est plus inversible).
Un premier exemple correspond au choix d’un potentiel gradient
U (x) = ∇V (x)
d’une fonction V : E = R
2
→ R de classe C
1 strictement convexe sur E. Dans
ce cas, l’ensemble
U 0 = {x ∈ R
2 : ∇V (x) = 0}
se r´ esume ` a l’unique minimum x 0 de V . Dans ce contexte, les ´ equations (2.7)
prennent la forme suivante
x n+1 = x n − Hess(V )(x n )
−1
∇V (x n )
o` u Hess(V )(x n )
−1 d´ esigne l’inverse de la matrice Hessienne Hess(V )(x n ) de
la fonction V . On notera la diff´ erence entre cet algorithme et l’algorithme de
descente de gradient classique d´ ecrit par les ´ equations
x n+1 = x n − γ n ∇V (x n )
avec un choix de param` etres γ n ≥ 0 tels que lim n→∞ γ n = 0.
Un autre exemple plus probabiliste consiste ` a prendre pour U la fonction
de r´ epartition d’une variable al´ eatoire r´ eelle Y
U : x ∈ E = R → U (x) = P (Y ≤ x) = E (1 Y ≤x ) .
Dans ce contexte, l’ensemble
U 1/2 = {x ∈ R
d : P (Y ≤ x) = 1/2} = {x 1/2 }
est `
a nouveau r´ eduit ` a un point x 1/2 , appel´ e le m´ ediane de la distribution de
la variable al´ eatoire Y .
2 Chaˆ ınes de Markov abstraites
U xn (x n+1 ) = U (x n )+U
(x n ) (x n+1 −x n ) = 0 ⇔ x n+1 = x n −U
(x n )
−1 U (x n )
conduit `
a une descente de gradient li´ ee `
a la courbure autour des ´ etats visit´ es.
Cette d´ ependance permet bien souvent d’acc´ el´ erer la convergence des ´ etats
x n vers l’un des z´ ero x ∞ de la fonction U (x ∞ ) = 0.
La version multidimensionnelle de l’algorithme pr´ ec´ edent est donn´ ee par
les ´ equations
x n+1 = x n − Jac(U )(x n )
−1 U (x n )
(2.7)
o` u Jac(U )(x n )
−1 d´ esigne l’inverse de la matrice Jacobienne Jac(U )(x n ) de U .
On remarquera que cet algorithme n´ ecessite de r´ esoudre le syst` eme d’´ equations
lin´ eaires
Jac(U )(x n ) (x n+1 − x n ) = U (x n )
Bien entendu ces techniques d’approximation numeriques ne sont efficaces
que pour des fonctions suffisamment r´ eguli` eres, et des choix de conditions
initiales pas trop ´ eloign´ ees des z´ eros de la fonction recherch´ es (afin d’´ eviter de
visiter des ´ etats o` u la d´ eriv´ e s’annule, dans le cas unidimensionnel ; ou dans le
cas multi-dimensionnel, ´ eviter des ´ etats o` u le jacobien n’est plus inversible).
Un premier exemple correspond au choix d’un potentiel gradient
U (x) = ∇V (x)
d’une fonction V : E = R
2
→ R de classe C
1 strictement convexe sur E. Dans
ce cas, l’ensemble
U 0 = {x ∈ R
2 : ∇V (x) = 0}
se r´ esume ` a l’unique minimum x 0 de V . Dans ce contexte, les ´ equations (2.7)
prennent la forme suivante
x n+1 = x n − Hess(V )(x n )
−1
∇V (x n )
o` u Hess(V )(x n )
−1 d´ esigne l’inverse de la matrice Hessienne Hess(V )(x n ) de
la fonction V . On notera la diff´ erence entre cet algorithme et l’algorithme de
descente de gradient classique d´ ecrit par les ´ equations
x n+1 = x n − γ n ∇V (x n )
avec un choix de param` etres γ n ≥ 0 tels que lim n→∞ γ n = 0.
Un autre exemple plus probabiliste consiste ` a prendre pour U la fonction
de r´ epartition d’une variable al´ eatoire r´ eelle Y
U : x ∈ E = R → U (x) = P (Y ≤ x) = E (1 Y ≤x ) .
Dans ce contexte, l’ensemble
U 1/2 = {x ∈ R
d : P (Y ≤ x) = 1/2} = {x 1/2 }
est `
a nouveau r´ eduit ` a un point x 1/2 , appel´ e le m´ ediane de la distribution de
la variable al´ eatoire Y .