# 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.
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. 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 :
    $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 :
    $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 :
    $\mathbf {f} (\mathbf {x} )=\mathbf {0} ,$
où f est une fonction vectorielle de x :
    $\mathbf {x} =(x_{1},x_{2},\dotsc ,x_{k}),$
    $\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** :
    $\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 :
    $\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ù :
* $\Delta \mathbf {x} _{n}=\mathbf {x} _{n}-\mathbf {x} _{n-1},$
* $\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 :
    $\mathbf {x} _{n+1}=\mathbf {x} _{n}-\alpha \mathbf {J} _{n}^{-1}\mathbf {f} (\mathbf {x} _{n}),$
où $\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 :
    $\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 :
    $\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} }.$