Méthode de Quasi-Newton

Un article de Wikipédia, l'encyclopédie libre.

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

Vous pouvez partager vos connaissances en l’améliorant. (Comment ?).

Une méthode de Quasi-Newton est une méthode numérique utilisée pour résoudre des systèmes d'équations non-linéaires. Typiquement, le problème que résout une méthode de Quasi-Newton est $f (x) = 0$ avec $f:\mathbb{R}^n \rightarrow \mathbb{R}^n$ dont on connaît l'expression analytique

Pour de tels problèmes il est toujours possible d'utiliser la méthode de Newton-Raphson, dont les itérations sont $x k + 1 = x k - D f (x k) - 1 . f (x k)$ , mais celle-ci pose quelques problèmes pratiques:

Si le système est assez grand, l'obtention des termes de sa jacobienne est très longue
De même, l'inversion d'une matrice est une opération coûteuse en calculs

L'idée des méthodes Quasi-Newton est de remplacer $D f (x k) - 1$ par une matrice $B k$ qui doit vérifier certaines propriétés:

$B k$ est définie positive
elle est symétrique
$x k + 1 - x k = B k (f (x k + 1) - f (x k))$ (relation de Quasi-Newton)

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

$x k + 1 = x k - ρ k . B k . f (x k)$

Dans cette formule, $ρ 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

[modifier] Méthode de Davidon-Fletcher-Powell

On initialise $B 0 = I d$ 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.^t y_k.B_k}{^t y_k.B_k.y_k}$

[modifier] Sources

Un cours d'optimisation traitant des méthodes de Quasi-Newton
Méthodes numériques itératives, Claude Brezinski, Michela Redivo-Zaglia, Editions Ellipses

v · d · m Méthodes de résolution d'équations
Résolution d'équations polynomiales	Méthode de Bézout · Méthode de Cardan · Méthode de Sotta · Méthode de Ferrari · Méthode de Descartes · Méthode de Tschirnhaus · Méthode d'Hermite
Recherche d'un zéro	Méthode de dichotomie · Méthode de Newton · Méthode de la sécante · Méthode de Müller · Méthode de Brent · Méthode de la fausse position · Méthode de Héron · Méthode de Laguerre · Méthode du cercle de séparation · Méthode de Halley · Méthode de Householder