Méthode de Broyden

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 f(x) = 0 utilise la matrice jacobienne, J, à 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 n × n, la méthode de Broyden converge en au plus 2n 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 f′ au point x_n est remplacée par une approximation aux différences finies :

${\displaystyle f'(x_{n})\simeq {\frac {f(x_{n})-f(x_{n-1})}{x_{n}-x_{n-1}}},}$

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

${\displaystyle x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}},}$

où n est l’indice d’itération.

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

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

${\displaystyle \mathbf {f} (\mathbf {x} )=\mathbf {0} ,}$

où f est une fonction vectorielle de x :

${\displaystyle \mathbf {x} =(x_{1},x_{2},\dotsc ,x_{k}),}$

${\displaystyle \mathbf {f} (\mathbf {x} )=\left(f_{1}(x_{1},\dotsc ,x_{k}),\dotsc ,f_{k}(x_{1},\dotsc ,x_{k})\right).}$

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

${\displaystyle \mathbf {J} _{n}(\mathbf {x} _{n}-\mathbf {x} _{n-1})=\mathbf {f} (\mathbf {x} _{n})-\mathbf {f} (\mathbf {x} _{n-1}).}$

Mise à jour quasi-Newtonienne

La jacobienne approchée J_n est mise à jour selon :

${\displaystyle \mathbf {J} _{n}=\mathbf {J} _{n-1}+{\frac {\Delta \mathbf {f} _{n}-\mathbf {J} _{n-1}\Delta \mathbf {x} _{n}}{\|\Delta \mathbf {x} _{n}\|^{2}}}\Delta \mathbf {x} _{n}^{\mathrm {T} },}$

où :

• ${\displaystyle \Delta \mathbf {x} _{n}=\mathbf {x} _{n}-\mathbf {x} _{n-1},}$
• ${\displaystyle \Delta \mathbf {f} _{n}=\mathbf {f} (\mathbf {x} _{n})-\mathbf {f} (\mathbf {x} _{n-1}).}$

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

${\displaystyle \mathbf {x} _{n+1}=\mathbf {x} _{n}-\alpha \mathbf {J} _{n}^{-1}\mathbf {f} (\mathbf {x} _{n}),}$

où ${\displaystyle \alpha }$ 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 :

${\displaystyle \mathbf {J} _{n}^{-1}=\mathbf {J} _{n-1}^{-1}+{\frac {\Delta \mathbf {x} _{n}-\mathbf {J} _{n-1}^{-1}\Delta \mathbf {f} _{n}}{\Delta \mathbf {x} _{n}^{\mathrm {T} }\mathbf {J} _{n-1}^{-1}\Delta \mathbf {f} _{n}}}\Delta \mathbf {x} _{n}^{\mathrm {T} }\mathbf {J} _{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 :

${\displaystyle \mathbf {J} _{n}^{-1}=\mathbf {J} _{n-1}^{-1}+{\frac {\Delta \mathbf {x} _{n}-\mathbf {J} _{n-1}^{-1}\Delta \mathbf {f} _{n}}{\|\Delta \mathbf {f} _{n}\|^{2}}}\Delta \mathbf {f} _{n}^{\mathrm {T} }.}$

Voir aussi

• Méthode de la sécante
• Méthode de Newton
• Méthode quasi-Newton
• Méthode de Broyden-Fletcher-Goldfarb-Shanno

Références

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Broyden's method » (voir la liste des auteurs).

1. C. G. Broyden, « A Class of Methods for Solving Nonlinear Simultaneous Equations », American Mathematical Society, vol. 19, n^o 92,‎ 1965, p. 577–593 (DOI 10.1090/S0025-5718-1965-0198670-6 , JSTOR 2003941)
2. D. M. Gay, « Some convergence properties of Broyden's method », SIAM, vol. 16, n^o 4,‎ 1979, p. 623–630 (DOI 10.1137/0716047)