MANUEL
DE
CALCUL
NUMÉRIQUE
APPLIQUÉ
On trouvera dans l’ouvrage de Yu.A. Shreider cité en bibliographie le développement de cette
technique.
Sur le Wcb(*), 1 e programme matmonte. c réalise l’inversion des matrices du type A particulier
selon la technique développée dans ce paragraphe.
7. Méthode du recuit simulé : recherche du minimum absolu
d’une fonction
On recherche le minimum minimorum d’une fonction f(z, y, z, . ) dans un certain domaine D.
Pour des raisons de commodité d’écriture, on représente par 2, le vecteur de composantes 2%:
yi, zi...
L’algorithme se présente sous la forme suivante :
a. On tire un premier vecteur (initial) aléatoire 20 au moyen du générateur de LehmerGreenberger tel que 2, E D.
b. On tire un vecteur 23 par le même procedé puis 011 calcule la probabilité de transition :
P = exp(-PdF)
avec
LIF = f(z.7) - f(~J-l).
Si p > Seuili, 011 conserve le dernier état, et l’on poursuit les opérations N fois (boucle sur
b).
c. Ensuite, on augmente / 3 qui suit une loi du genre : pn = /?InPl/3c, et l’on effectue N calculs
identiques à b.
d. L’arrêt des calculs s’effectue lorsque af
l
l
aP
< Seuilz.
Cette procédure appelle quelques remarques :
Remarque 1 : Au départ, il faut choisir , 6’ u « petit »
Remarque 2 : Pour passer de *J à zj+r, on a intérêt à ne changer d’état que sur une seule
composante à la fois. On opère alors successivement sur les variables dans l’ordre 2, y, z, .
Remarque 3 : N et pu dépendent, pour ce qui concerne leur choix, des erreurs propagées dans
les calculs, aussi bien lors de la génération des nombres pseudo-aléatoires que dans le calcul de
df et f(X).
Remarque 4 : Il faut veiller à ne pas « descendre trop vite », sinon, nous risquons de rester
dans un minimum local dont on ne peut plus sortir (p < Seuilr). Toutefois, une «descente trop
lente » est source d’instabilité. Il convient de choisir un compromis pour choisir pa et N selon
la fonction à minimiser.
On trouvera sur le Web (*) le programme recuit. c qui réalise cet algorithme sur une fonction
présentant un minimum absolu. Ici, il s’agit de la résolution d’un système de deux équations non
linéaires à deux inconnues f(z, y) = 0 et g(z, y) = 0. Notons qu’il revient au même de minimiser
une forme quadratique :
F(T Y) = f%> YY) + g2b, YY).
*http://www.edpsciences.com/guilpin/
DE
CALCUL
NUMÉRIQUE
APPLIQUÉ
On trouvera dans l’ouvrage de Yu.A. Shreider cité en bibliographie le développement de cette
technique.
Sur le Wcb(*), 1 e programme matmonte. c réalise l’inversion des matrices du type A particulier
selon la technique développée dans ce paragraphe.
7. Méthode du recuit simulé : recherche du minimum absolu
d’une fonction
On recherche le minimum minimorum d’une fonction f(z, y, z, . ) dans un certain domaine D.
Pour des raisons de commodité d’écriture, on représente par 2, le vecteur de composantes 2%:
yi, zi...
L’algorithme se présente sous la forme suivante :
a. On tire un premier vecteur (initial) aléatoire 20 au moyen du générateur de LehmerGreenberger tel que 2, E D.
b. On tire un vecteur 23 par le même procedé puis 011 calcule la probabilité de transition :
P = exp(-PdF)
avec
LIF = f(z.7) - f(~J-l).
Si p > Seuili, 011 conserve le dernier état, et l’on poursuit les opérations N fois (boucle sur
b).
c. Ensuite, on augmente / 3 qui suit une loi du genre : pn = /?InPl/3c, et l’on effectue N calculs
identiques à b.
d. L’arrêt des calculs s’effectue lorsque af
l
l
aP
< Seuilz.
Cette procédure appelle quelques remarques :
Remarque 1 : Au départ, il faut choisir , 6’ u « petit »
Remarque 2 : Pour passer de *J à zj+r, on a intérêt à ne changer d’état que sur une seule
composante à la fois. On opère alors successivement sur les variables dans l’ordre 2, y, z, .
Remarque 3 : N et pu dépendent, pour ce qui concerne leur choix, des erreurs propagées dans
les calculs, aussi bien lors de la génération des nombres pseudo-aléatoires que dans le calcul de
df et f(X).
Remarque 4 : Il faut veiller à ne pas « descendre trop vite », sinon, nous risquons de rester
dans un minimum local dont on ne peut plus sortir (p < Seuilr). Toutefois, une «descente trop
lente » est source d’instabilité. Il convient de choisir un compromis pour choisir pa et N selon
la fonction à minimiser.
On trouvera sur le Web (*) le programme recuit. c qui réalise cet algorithme sur une fonction
présentant un minimum absolu. Ici, il s’agit de la résolution d’un système de deux équations non
linéaires à deux inconnues f(z, y) = 0 et g(z, y) = 0. Notons qu’il revient au même de minimiser
une forme quadratique :
F(T Y) = f%> YY) + g2b, YY).
*http://www.edpsciences.com/guilpin/