Méthode de Brent

En analyse numérique, la méthode de Brent est un algorithme de recherche d'un zéro d'une fonction combinant la méthode de dichotomie, la méthode de la sécante et l’interpolation quadratique inverse. À chaque itération, elle décide laquelle de ces trois méthodes est susceptible d’approcher au mieux le zéro, et effectue une itération en utilisant cette méthode. L'idée principale est d'utiliser la méthode de la sécante ou d'interpolation quadratique inverse parce qu'elles convergent vite, et de revenir à la méthode de dichotomie si besoin est. L'idée d'allier ces méthodes différentes est due à (1969) et à Richard Brent (1973). La méthode de Chandrupatla en est une variante plus simple et qui converge plus rapidement pour les fonctions plates au voisinage de leurs racines. L'idée de combiner les méthodes de dichotomie et de la sécante remonte à Dekker. On suppose vouloir résoudre l'équation f(x) = 0. À l'image de la méthode de dichotomie, la méthode de Dekker est initialisée par deux points, notés a et b, tels que f(a) et f(b) soient de signes opposés. Si f est continue sur [a, b], le théorème des valeurs intermédiaires indique l'existence d'une solution entre a et b. À chaque itération, trois points entrent en jeu: b est l'itération courante, c'est-à-dire l'approximation courante de la racine de f; a est le contrepoint, c'est-à-dire un point tel que f(a) et f(b) soient de signes opposés. Ainsi, l'intervalle [a ; b] contient à coup sûr la solution. De plus, |f(b)| doit être plus petit (en valeur absolue) que |f(a)|, de telle sorte que b soit une meilleure approximation de la racine que a; b est l'itération précédente (pour la première itération, on pose b = a). Deux candidats à la prochaine itération sont calculés: le premier est obtenu par la méthode de la sécante et le second par la méthode de dichotomie Si le résultat de la méthode de la sécante, s, tombe entre b et m, alors il peut devenir le prochain itéré (b = s), et dans le cas contraire, le point milieu entre en jeu (b = m).