Méthode de Quasi-Newton

La 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 \to\mathbb{R}^n$ dont on ne connaît pas forcément l'expression analytique.

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)$ , mais celle-ci pose quelques problèmes pratiques :

si le système est assez grand, le calcul de la matrice jacobienne est très long,
de même, la résolution du système linéaire $Df(x_k)^{-1}\cdot f(x_k)$ 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$ 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\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) ~.$

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.

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}{^ts_k\, B_{k}y_k} (^ts_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$ (voir ci-dessous).

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 + \rho_k \cdot 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}$

avec, comme ci-dessus,

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

s k = x k + 1 - 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-Goldfarb-Shanno (BFGS) qui est encore plus efficace.

Voir aussi

Sources

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

v · 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 · Méthode de Héron · Méthode de Laguerre · Méthode du cercle de séparation
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 Halley · Méthode de Householder. Méthode de Quasi-Newton

Portail de l'analyse

Catégories :

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Méthode de Quasi-Newton de Wikipédia en français (auteurs)

Игры ⚽ Поможем написать реферат

Regardez d'autres dictionnaires:

Methode de Newton — Méthode de Newton Isaac Newton En analyse numérique, la méthode de Newton, ou méthode de Newton Raphson[1], est un algorithme efficace pour trouver des approximations d un zéro … Wikipédia en Français
Methode de la corde — Méthode de Newton Isaac Newton En analyse numérique, la méthode de Newton, ou méthode de Newton Raphson[1], est un algorithme efficace pour trouver des approximations d un zéro … Wikipédia en Français
Méthode De Newton — Isaac Newton En analyse numérique, la méthode de Newton, ou méthode de Newton Raphson[1], est un algorithme efficace pour trouver des approximations d un zéro … Wikipédia en Français
Méthode de Newton-Raphson — Méthode de Newton Isaac Newton En analyse numérique, la méthode de Newton, ou méthode de Newton Raphson[1], est un algorithme efficace pour trouver des approximations d un zéro … Wikipédia en Français
Méthode de la corde — Méthode de Newton Isaac Newton En analyse numérique, la méthode de Newton, ou méthode de Newton Raphson[1], est un algorithme efficace pour trouver des approximations d un zéro … Wikipédia en Français
Méthode de newton — Isaac Newton En analyse numérique, la méthode de Newton, ou méthode de Newton Raphson[1], est un algorithme efficace pour trouver des approximations d un zéro … Wikipédia en Français
Methode de Heron — Méthode de Héron En mathématiques, la méthode de Héron ou méthode babylonienne est une méthode efficace d extraction de racine carrée. Elle porte le nom du mathématicien Héron d Alexandrie mais certains calculs antérieurs semblent prouver que la… … Wikipédia en Français
Methode de Laguerre — Méthode de Laguerre En analyse numérique, la méthode de Laguerre est un algorithme de recherche d un zéro d une fonction polynomiale. En d autres termes, la méthode de Laguerre peut être utilisée pour trouver une valeur approchée d un solution d… … Wikipédia en Français
Méthode De Héron — En mathématiques, la méthode de Héron ou méthode babylonienne est une méthode efficace d extraction de racine carrée. Elle porte le nom du mathématicien Héron d Alexandrie mais certains calculs antérieurs semblent prouver que la méthode est plus… … Wikipédia en Français
Méthode De Laguerre — En analyse numérique, la méthode de Laguerre est un algorithme de recherche d un zéro d une fonction polynomiale. En d autres termes, la méthode de Laguerre peut être utilisée pour trouver une valeur approchée d un solution d une équation de la… … Wikipédia en Français

Dictionnaires et Encyclopédies sur 'Academic'

Méthode de Quasi-Newton

Sommaire

Méthode de Broyden

Méthode de Davidon-Fletcher-Powell

Voir aussi

Sources

Regardez d'autres dictionnaires:

Share the article and excerpts

Dictionnaires et Encyclopédies sur 'Academic'

Wikipédia en Français

Méthode de Quasi-Newton

Sommaire

Méthode de Broyden

Méthode de Davidon-Fletcher-Powell

Voir aussi

Sources

Regardez d'autres dictionnaires:

Share the article and excerpts

Direct link