Méthode de Broyden

De testwiki
Aller à la navigation Aller à la recherche

Modèle:Traduction à revoir Modèle:À wikifier

La méthode de Broyden est une méthode quasi-Newton utilisée en analyse numérique pour trouver les solutions de systèmes d'équations non linéaires dans plusieurs variables. Cette méthode a été décrite pour la première fois par Charles George Broyden en 1965[1].

La méthode de Newton pour résoudre Modèle:Math utilise la matrice jacobienne, Modèle:Math, à chaque itération. Cependant, calculer cette Jacobienne peut être coûteux, notamment pour des problèmes de grande dimension, comme les équations de Kohn-Sham en mécanique quantique, où le nombre de variables peut atteindre plusieurs centaines de milliers. La méthode de Broyden propose de ne calculer la Jacobienne exacte qu'à la première itération, puis d'effectuer des mises à jour approximatives à faible coût lors des itérations suivantes.

En 1979, Gay a démontré que, pour un système linéaire de taille Modèle:Math, la méthode de Broyden converge en au plus Modèle:Math itérations[2]. Cependant, comme toutes les méthodes quasi-Newtoniennes, elle peut ne pas converger pour certains systèmes non linéaires.

Description de la méthode

Résolution d'une équation non linéaire à une variable

Dans la méthode de la sécante, la dérivée Modèle:Math au point Modèle:Math est remplacée par une approximation aux différences finies :

f′(xn)≃f(xn)−f(xn−1)xn−xn−1,

et on procède comme dans la méthode de Newton :

xn+1=xn−f(xn)f′(xn),

où Modèle:Math est l’indice d’itération.

Résolution d'un système d'équations non linéaires

On considère un système de Modèle:Math équations non linéaires à Modèle:Math inconnues :

𝐟(𝐱)=𝟎,

où Modèle:Math est une fonction vectorielle de Modèle:Math :

𝐱=(x1,x2,…,xk),
𝐟(𝐱)=(f1(x1,…,xk),…,fk(x1,…,xk)).

La méthode de Broyden remplace la Jacobienne exacte Modèle:Math par une approximation Modèle:Math, mise à jour à chaque itération en respectant l'**équation de la sécante** :

𝐉n(𝐱n−𝐱n−1)=𝐟(𝐱n)−𝐟(𝐱n−1).

Mise à jour quasi-Newtonienne

La jacobienne approchée Modèle:Math est mise à jour selon :

𝐉n=𝐉n−1+Δ𝐟n−𝐉n−1Δ𝐱n‖Δ𝐱n‖2Δ𝐱nT,

où :

  • Δ𝐱n=𝐱n−𝐱n−1,
  • Δ𝐟n=𝐟(𝐱n)−𝐟(𝐱n−1).

Cette mise à jour minimise la norme de Frobenius pour limiter les modifications apportées à Modèle:Math. Les variables sont ensuite mises à jour selon :

𝐱n+1=𝐱n−α𝐉n−1𝐟(𝐱n),

où α est un paramètre ajustable, souvent déterminé par une recherche linéaire ou une méthode de région de confiance.

Variantes et applications

Broyden a également proposé d'autres approches, notamment une méthode utilisant la formule de Sherman-Morrison pour mettre à jour directement l'inverse de la jacobienne :

𝐉n−1=𝐉n−1−1+Δ𝐱n−𝐉n−1−1Δ𝐟nΔ𝐱nT𝐉n−1−1Δ𝐟nΔ𝐱nT𝐉n−1−1.

Cette variante est connue sous le nom de « bonne méthode de Broyden ». Une autre variante, appelée mauvaise méthode de Broyden, met à jour l'inverse de la jacobienne selon :

𝐉n−1=𝐉n−1−1+Δ𝐱n−𝐉n−1−1Δ𝐟n‖Δ𝐟n‖2Δ𝐟nT.

Voir aussi

Références

Modèle:Traduction/Référence Modèle:Références

Modèle:Portail

  1. ↑ Modèle:Article
  2. ↑ Modèle:Article
Récupérée de "https://fr.wiki.beta.math.wmflabs.org/w/index.php?title=Méthode_de_Broyden&oldid=21886"