Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Méthode de Brent
Résumé
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).
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.