Méthode de Brent

Modèle:Voir homonymes

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 à Modèle:Lien (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^[1]Modèle:,^[2].

Méthode de Dekker

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 aModèle:Ind et bModèle:Ind, tels que f(aModèle:Ind) et f(bModèle:Ind) soient de signes opposés. Si f est continue sur [aModèle:Ind, bModèle:Ind], le théorème des valeurs intermédiaires indique l'existence d'une solution entre aModèle:Ind et bModèle:Ind.

À chaque itération, trois points entrent en jeu:

bModèle:Ind est l'itération courante, c'est-à-dire l'approximation courante de la racine de f;
aModèle:Ind est le contrepoint, c'est-à-dire un point tel que f(aModèle:Ind) et f(bModèle:Ind) soient de signes opposés. Ainsi, l'intervalle [aModèle:Ind ; bModèle:Ind] contient à coup sûr la solution. De plus, |f(bModèle:Ind)| doit être plus petit (en valeur absolue) que |f(aModèle:Ind)|, de telle sorte que bModèle:Ind soit une meilleure approximation de la racine que aModèle:Ind;
bModèle:Ind est l'itération précédente (pour la première itération, on pose bModèle:Ind = aModèle:Ind).

Deux candidats à la prochaine itération sont calculés: le premier est obtenu par la méthode de la sécante

s = b_{k} - \frac{b_{k} - b_{k - 1}}{f (b_{k}) - f (b_{k - 1})} f (b_{k}),

et le second par la méthode de dichotomie

m = \frac{a_{k} + b_{k}}{2} .

Si le résultat de la méthode de la sécante, s, tombe entre bModèle:Ind et m, alors il peut devenir le prochain itéré (bModèle:Ind = s), et dans le cas contraire, le point milieu entre en jeu (bModèle:Ind = m).

Alors, la valeur du nouveau contrepoint est choisie de telle sorte que f(aModèle:Ind) et f(bModèle:Ind) soient de signes opposés. Si f(aModèle:Ind) et f(bModèle:Ind) sont de signes opposés, alors le contrepoint ne change pas : aModèle:Ind = aModèle:Ind. Sinon, f(bModèle:Ind) et f(bModèle:Ind) sont de signes opposés et le nouveau contrepoint devient aModèle:Ind = bModèle:Ind.

Finalement, si |f(aModèle:Ind)| < |f(bModèle:Ind)|, alors aModèle:Ind est probablement une meilleure approximation de la solution que bModèle:Ind, et par suite, les valeurs de aModèle:Ind et bModèle:Ind sont échangées.

En arrivant à ce point, la méthode vient de réaliser une itération. La méthode est répétée jusqu'à convergence.

Méthode de Brent

La méthode de Dekker est efficace si f se comporte raisonnablement bien. Toutefois, dans certaines circonstances, chaque itération emploie la méthode de la sécante mais la suite des bModèle:Ind converge très lentement (en particulier, |bModèle:Ind − bModèle:Ind| peut devenir arbitrairement petit). Dans une telle configuration, la méthode de Dekker nécessite alors plus d'itérations que la méthode de dichotomie.

Brent propose une petite modification pour éviter ce problème: un test supplémentaire doit être vérifié avant que le résultat de la méthode de la sécante soit accepté comme la prochaine itération. En particulier, si l'étape précédente utilisait la méthode de dichotomie, l'inégalité

| s - b_{k} | < \begin{matrix} \frac{1}{2} \end{matrix} | b_{k} - b_{k - 1} |

doit être vraie, sinon le point milieu m devient le prochain itéré. Si l'étape précédente utilisait l'interpolation, alors l'inégalité

| s - b_{k} | < \begin{matrix} \frac{1}{2} \end{matrix} | b_{k - 1} - b_{k - 2} |

est utilisée à la place. Cette modification permet de remplacer la méthode de la sécante par la méthode de dichotomie lorsque la première progresse trop lentement. Brent a prouvé que cette méthode requiert au plus NModèle:Exp itérations, où N représente le nombre d'itérations pour la méthode de dichotomie. Si la fonction f se comporte bien, la méthode de Brent utilise au choix l'interpolation quadratique inverse ou l'interpolation linéaire, auquel cas la vitesse de convergence est superlinéaire.

La méthode de Brent se base sur l'interpolation quadratique inverse plutôt que l'interpolation linéaire (qui apparaît dans la méthode de la sécante) si f(bModèle:Ind), f(aModèle:Ind) et f(bModèle:Ind) sont distincts. Ceci améliore significativement l'efficacité. Par conséquent, la condition pour accepter la valeur d'interpolation s est modifiée: s doit tomber entre (3aModèle:Ind + bModèle:Ind) / 4 et bModèle:Ind.

Exemple

On cherche à identifier une racine de f(x) = (x + 3)(x − 1)Modèle:Exp. On prend [aModèle:Ind; bModèle:Ind] = [−4; 4/3] comme intervalle initial. On a f(aModèle:Ind) = −25 et f(bModèle:Ind) = 0,48148 (tous les nombres de cette section sont tronqués); ainsi les conditions f(aModèle:Ind) f(bModèle:Ind) < 0 et |f(bModèle:Ind)| ≤ |f(aModèle:Ind)| sont vérifiées. Nous allons détailler l'utilisation de Brent, qui utilise soit l'interpolation linéaire (abrégée en IL) soit l'interpolation quadratique inverse (IQI).

Dans la première itération, on utilise une IL entre (bModèle:Ind; f(bModèle:Ind)) = (aModèle:Ind; f(aModèle:Ind)) = (−4; −25) et (bModèle:Ind; f(bModèle:Ind)) = (1,33333; 0,48148), ce qui conduit à s = 1,23256. Cette valeur tombe entre (3aModèle:Ind + bModèle:Ind) / 4 et bModèle:Ind et, par conséquent, cette valeur est acceptée. En outre, f(1,23256) = 0,22891, ce qui donne aModèle:Ind = aModèle:Ind et bModèle:Ind = s = 1,23256;
Dans la deuxième itération, une IQI entre (aModèle:Ind; f(aModèle:Ind)) = (−4; −25) et (bModèle:Ind; f(bModèle:Ind)) = (1,33333; 0,48148) et (bModèle:Ind; f(bModèle:Ind)) = (1,23256; 0,22891) donne 1,14205; cette valeur est entre (3aModèle:Ind + bModèle:Ind) / 4 et bModèle:Ind. De plus, l'inégalité |1,14205 − bModèle:Ind| ≤ |bModèle:Ind − bModèle:Ind| / 2 est satisfaite; cette valeur est donc retenue. Enfin, comme f(1,14205) = 0,083582, on pose aModèle:Ind = aModèle:Ind et bModèle:Ind = 1,14205;
Dans la troisième itération, on utilise une IQI entre (aModèle:Ind; f(aModèle:Ind)) = (−4; −25) et (bModèle:Ind; f(bModèle:Ind)) = (1,23256; 0,22891) et (bModèle:Ind; f(bModèle:Ind)) = (1,14205; 0,083582), ce qui donne 1,09032. Cette valeur est entre (3aModèle:Ind + bModèle:Ind) / 4 et bModèle:Ind;mais la condition supplémentaire de Brent bloque: en effet, l'inégalité |1,09032 − bModèle:Ind| ≤ |bModèle:Ind − bModèle:Ind| / 2 n'est pas vérifiée: la valeur en cours est donc rejetée. À la place, on calcule le point milieu de l'intervalle [aModèle:Ind; bModèle:Ind]: m = −1,42897. On a f(m) = 9,26891; on pose alors aModèle:Ind = aModèle:Ind et bModèle:Ind = −1,42897;
Dans la quatrième itération, la valeur −1,15448 est obtenue par IQI entre (aModèle:Ind; f(aModèle:Ind)) = (−4; −25) et (bModèle:Ind; f(bModèle:Ind)) = (1,14205; 0,083582) et enfin (bModèle:Ind; f(bModèle:Ind)) = (−1,42897; 9,26891). Cette valeur ne tombe pas entre (3aModèle:Ind + bModèle:Ind) / 4 et bModèle:Ind). Par conséquent, on calcule à la place le milieu m = −2,71449; on a f(m) = 3,9393. On pose finalement aModèle:Ind = aModèle:Ind et bModèle:Ind = −2,71449;
Dans la cinquième itération, une IQI donne −3,45500, qui tombe dans l'intervalle requis. Toutefois, l'itération précédente était une étape de dichotomie et l'inégalité |−3,45500 − bModèle:Ind| ≤ |bModèle:Ind − bModèle:Ind| / 2 doit être satisfaite, ce qui n'est pas le cas. On utilise alors le point milieu m = −3,35724, pour lequel f(m) = −6,78239. Ainsi, m devient le nouveau contrepoint: aModèle:Ind = −3,35724 et bModèle:Ind = bModèle:Ind;
Dans la sixième itération, l'IQI est interdite car bModèle:Ind = bModèle:Ind. Par conséquent, on la remplace par une IL entre (aModèle:Ind; f(aModèle:Ind)) = (−3,35724; −6,78239) et (bModèle:Ind; f(bModèle:Ind)) = (−2,71449; 3,93934). Il en résulte s = −2,95064, qui satisfait toutes les conditions. On calcule f(s) = 0,77032 et on pose aModèle:Ind = aModèle:Ind et bModèle:Ind = −2,95064;
Dans la septième itération, on utilise encore une IQI ce qui donne s = −3,00219, qui vérifie toutes les conditions. Maintenant, f(s) = −0,03515, et on pose donc aModèle:Ind = bModèle:Ind et bModèle:Ind = −3,00219 (aModèle:Ind et bModèle:Ind sont échangés afin que |f(bModèle:Ind)| ≤ |f(aModèle:Ind)| soit vraie);
Dans la huitième itération, on ne peut considérer une IQI parce que aModèle:Ind = bModèle:Ind. L'IL donne à la place s = −2,99994, valeur qui est acceptée;
Dans les itérations suivantes, la racine x = −3 est approchée rapidement: bModèle:Ind = −3 + Modèle:Nb et bModèle:Ind = −3 – Modèle:Nb.

Algorithme

Entrée de a, b, un pointeur vers une sous-routine pour f, e une précision désirée
calculer f(a)
calculer f(b)
si f(a) f(b) >= 0 alors sortie (erreur) fin si
si |f(a)| < |f(b)| alors échanger (a,b) fin si
c := a
mflag := vrai
tant que f(b) != 0 ou |b − a|>e (condition de convergence)
- si f(a) ≠ f(c) et f(b) ≠ f(c) alors
  - $s : = \frac{a f (b) f (c)}{(f (a) - f (b)) (f (a) - f (c))} + \frac{b f (a) f (c)}{(f (b) - f (a)) (f (b) - f (c))} + \frac{c f (a) f (b)}{(f (c) - f (a)) (f (c) - f (b))}$ (interpolation quadratique inverse)
- sinon
  - $s : = b - f (b) \frac{b - a}{f (b) - f (a)}$ (règle de la sécante)
- fin si
- si s n'est pas entre (3a + b)/4 et b ou (mflag est vrai et |s−b| ≥ |b−c| / 2) ou (mflag est faux et |s−b| ≥ |c−d| / 2) alors
  - $s : = \frac{a + b}{2}$
  - mflag := vrai
- sinon
  - mflag := faux
- fin si
- calculer f(s)
- d := c
- c := b
- si f(a) f(s) < 0 alors b := s sinon a := s fin si
- si |f(a)| < |f(b)| alors échange (a,b) fin si
fin tant que
sortir b (renvoi de la racine)

Implémentations

Brent (1973) a publié une implémentation en Algol 60. La bibliothèque Netlib contient une implémentation en Fortran^[3]. La fonction MATLAB nommée fzero ou la fonction solve de PARI/GP sont d'autres exemples d'implémentation de la méthode de Brent.

Voir aussi

Notes et références

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

Bibliographie

Atkinson (1989). An Introduction to Numerical Analysis (2nd ed.), Section 2.8. John Wiley and Sons Modèle:ISBN
R.P. Brent (1973). Algorithms for Minimization without Derivatives, Chapter 4. Prentice-Hall, Englewood Cliffs, NJ Modèle:ISBN. L'édition originale est disponible sur la page professionnelle de l'auteur à l'Université nationale australienne.
T.J. Dekker (1969). "Finding a zero by means of successive linear interpolation." In B. Dejon and P. Henrici (eds), Constructive Aspects of the Fundamental Theorem of Algebra, Wiley-Interscience, London. Modèle:ISBN

Liens externes

Modèle:En Module for Brent's Method par John H. Mathews
La bibliothèque Modèle:Lien brisé contient une implémentation en C++.

Articles connexes

Modèle:Lien, une variante de la méthode de Brent permettant la recherche d'un minimum d'une fonction

Modèle:Palette Modèle:Portail

↑ https://doi.org/10.1016/S0965-9978(96)00051-8
↑ Modèle:Lien web.
↑ Modèle:En zeroin.f dans la Netlib

[1] ttps://doi.org/10.1016/S0965-9978(96)00051-8

[2] Modèle:Lien web.

[3] Modèle:En zeroin.f dans la Netlib

[1]

[2]

[3]

Méthode de Brent

Sommaire

Méthode de Dekker

Méthode de Brent

Exemple

Algorithme

Implémentations

Voir aussi

Notes et références

Bibliographie

Liens externes

Articles connexes

Menu de navigation

Méthode de Brent

Méthode de Dekker

Méthode de Brent

Exemple

Algorithme

Implémentations

Voir aussi

Notes et références

Bibliographie

Liens externes

Articles connexes

Menu de navigation

Rechercher