Méthode quasi-Newton

Cet article est une ébauche concernant les mathématiques.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

Une méthode quasi-Newton est une méthode numérique utilisée pour résoudre des systèmes d'équations non linéaires, reposant sur un principe similaire à la méthode de Newton. Typiquement, le problème que résout une méthode quasi-Newton est la recherche d'un zéro d'une fonction à valeurs vectorielles dont on ne connaît pas forcément l'expression analytique de la matrice jacobienne ou de la hessienne.

Principe de la méthode quasi-Newton

Le problème posé est le même que celui d'une méthode de Newton : rechercher, pour une fonction $f:\mathbb {R} ^{n}\to \mathbb {R} ^{n}$ , les solutions $x$ tels que $f (x) = 0$ . Pour de tels problèmes, il est en général possible d'utiliser la méthode de Newton-Raphson, dont les itérations sont

x_{k+1}=x_{k}-Df(x_{k})^{-1}\cdot f(x_{k})

où $Df (x)$ désigne la matrice jacobienne de $f$ en $x$ . En dimension 1, on retrouve l'expression de la méthode de Newton-Raphson classique. Celle-ci pose quelques problèmes pratiques :

si la dimension $n$ du système est grande, le calcul de la matrice jacobienne peut prendre trop de temps de calcul,
de même, la résolution du système linéaire $Df (x k) -1 • f (x k)$ est une opération coûteuse en calculs.

L'idée des méthodes quasi-Newton est de remplacer $Df (x k) -1$ par une matrice $B k$ plus facile à calculer, et à laquelle on peut imposer certaines propriétés. Le fait qu'elle soit une approximation de l'inverse du jacobien se traduit par la relation de quasi-Newton

x_{k+1}-x_{k}=B_{k+1}\cdot (f(x_{k+1})-f(x_{k}))

,

ce qui est manifestement la généralisation du coefficient utilisé dans la méthode de la sécante.

Les itérations des méthodes de quasi-Newton sont alors de la forme suivante :

x_{k+1}=x_{k}-\rho _{k}\,B_{k}\cdot f(x_{k})~.

Le paramètre réel $ρ k$ est un coefficient choisi pour optimiser la convergence, et $B k$ est mise à jour à chaque itération selon une formule particulière. Selon les méthodes de quasi-Newton, la formule de mise à jour varie.

Souvent on applique la méthode à la recherche d'un minimum d'une fonction $g (x)$ que l'on traduit en la recherche de $f (x) := \nabla g (x) = 0$ . Dans ce cas il est naturel d'imposer à la matrice $B k$ qu'elle soit symétrique, car elle correspond alors à la matrice hessienne de $g$ .

Méthode de Broyden

Ici la mise à jour de la matrice $B k$ s'écrit

B_{k+1}=B_{k}+{\frac {s_{k}-B_{k}y_{k}}{^{t}s_{k}\,B_{k}y_{k}}}(^{t}s_{k}B_{k})

avec $s k = x k +1 - x k$ , $y k = f (x k +1) - f (x k)$ . Cette méthode s'applique au cas général où le jacobien n'a pas de raison d'être symétrique.

Méthode de Davidon-Fletcher-Powell

C'est historiquement la première méthode quasi-Newton appliquée à l'optimisation, c'est-à-dire au calcul d'un extremum d'une fonction. Par conséquent, elle impose la symétrie des matrices $B k$ . En effet, ici ces matrices sont censées représenter une approximation de l'inverse de la matrice hessienne de la fonction à minimiser. La symétrie de ces approximations est assurée par le fait qu'on utilise une mise à jour d'une forme particulièrement simple, $B_{k+1}=B_{k}+v_{k}\cdot {}^{t}v_{k}$ .

On initialise $B 0 = I$ et $x 0$ assez proche de la solution qu'on cherche. Les itérations sont les suivantes :

On calcule d'abord la direction de déplacement $d k = - B k f (x k)$
le coefficient $ρ k$ s'en déduit, il est nécessairement strictement positif et choisi pour minimiser $f (x k + ρ k d k)$
on trouve le k+1^e terme de la suite $x k +1 = x k + ρ k d k$
$B k +1$ est calculé par la formule de Davidon-Fletcher-Powell

B_{k+1}=B_{k}+{\frac {s_{k}{}^{t}s_{k}}{^{t}s_{k}y_{k}}}-{\frac {B_{k}y_{k}y_{k}{}^{t}B_{k}}{{}^{t}y_{k}B_{k}y_{k}}}

avec, comme ci-dessus,

s k = x k +1 - x k

,

y k = f (x k +1) - f (x k)

.

La méthode DFP a des propriétés satisfaisantes, mais dans la pratique elle est aujourd'hui en général remplacée par la méthode de Broyden-Fletcher-Goldfard-Shanno (BFGS) qui est encore plus efficace.^{[réf. nécessaire]}

Voir aussi

Sources

Claude Brezinski et Michela Redivo-Zaglia, Méthodes numériques itératives, Éditions Ellipses, coll. « Mathématiques à l'université », 15 septembre 2006, 320 p. (présentation en ligne)

Portail de l'analyse

v · m Méthodes de résolution d'équations
Équations polynomiales	Équation du premier degré Équation du second degré Équation cubique Méthode de Cardan Substitution de Viète Méthode de Lagrange Méthode de Tschirnhaus Méthode de Bézout Équation quartique Méthode de Lagrange Méthode de Ferrari Méthode de Descartes Équation quintique Méthode d'Hermite
Recherche d'un zéro	Méthode de dichotomie Méthode de Householder Méthode de Newton Méthode de Halley Méthode de Bernoulli Méthode de la sécante Méthode de Muller Méthode de Brent Méthode de Chandrupatla Méthode de la fausse position Méthode de Héron Méthode de Laguerre Méthode quasi-Newton Méthode du cercle de séparation