Méthode de brent

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 robuste méthode de dichotomie si besoin est. Cela donne une méthode alliant robustesse et rapidité, qui se trouve être très populaire et très appréciée. L'idée d'allier ces méthodes différentes est due à Theodorus Dekker (1969) et à Richard Brent (1973).

La 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, disons a₀ et b₀, tels que f(a₀) et f(b₀) aient des 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_k est l'itération courante, c.-à-d. l'approximation courante de la racine de f;
a_k est le "contrepoint," c.-à-d. un point tel que f(a_k) et f(b_k) aient des signes opposés. Ainsi, l'intervalle [a_k, b_k] contient à coups sûr la solution. De plus, |f(b_k)| doit être plus petit (en magnitude) que |f(a_k)|, de telle sorte que b_k soit une meilleure approximation de la racine que a_k;
b_k−1 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

$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 b_k et m, alors il peut devenir le prochain itéré (b_k+1 = s), et dans le cas contraire, le point milieu entre en jeu (b_k+1 = m).

Alors, la valeur du nouveau contrepoint est choisi de tel sorte que f(a_k+1) et f(b_k+1) aient des signes opposés. Si f(a_k) et f(b_k+1) sont de signe opposé, alors le contrepoint ne change pas: a_k+1 = a_k. Sinon, f(b_k+1) et f(b_k) sont de signe opposé et le nouveau contrepoint devient a_k+1 = b_k.

Finalement, si |f(a_k+1)| < |f(b_k+1)|, alors a_k+1 est probablement une meilleure approximation de la solution que b_k+1, et par suite, les valeurs de a_k+1 et b_k+1 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.

La 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 b_k converge très lentement (en particulier, |b_k − b_k−1| 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ée 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} \frac12 \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} \frac12 \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 N² 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 inverses plutôt que l'interpolation linéaire (qui apparaît dans la méthode de la sécante) si f(b_k), f(a_k) et f(b_k−1) 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 (3a_k + b_k) / 4 et b_k.

Exemple

On cherche à identifier une racine de f(x) = (x + 3)(x − 1)². On prend [a₀; b₀] = [−4; 4/3] comme intervalle initial. On a f(a₀) = −25 et f(b₀) = 0,48148 (tous les nombres de cette section sont tronqués); ainsi les conditions f(a₀) f(b₀) < 0 et |f(b₀)| ≤ |f(a₀)| 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).

Graphe de f(x) = (x + 3)(x − 1)²

Dans la première itération, on utilise une IL entre (b₋₁; f(b₋₁)) = (a₀; f(a₀)) = (−4; −25) et (b₀; f(b₀)) = (1,33333; 0,48148), ce qui conduit à s = 1,23256. Cette valeur tombe entre (3a₀ + b₀) / 4 et b₀ et, par conséquent, cette valeur est acceptée. En outre, f(1,23256) = 0,22891, ce qui donne a₁ = a₀ et b₁ = s = 1,23256;
Dans la deuxième itération, une IQI entre (a₁; f(a₁)) = (−4; −25) et (b₀; f(b₀)) = (1,33333; 0,48148) et (b₁; f(b₁)) = (1,23256; 0,22891) donne 1,14205; cette valeur est entre (3a₁ + b₁) / 4 et b₁. De plus, l'inégalité |1,14205 − b₁| ≤ |b₀ − b₋₁| / 2 est satisfaite; cette valeur est donc retenue. Enfin, comme f(1,14205) = 0,083582, on pose a₂ = a₁ et b₂ = 1,14205;
Dans la troisième itération, on utilise une IQI entre (a₂; f(a₂)) = (−4; −25) et (b₁; f(b₁)) = (1,23256; 0,22891) et (b₂; f(b₂)) = (1,14205; 0,083582), ce qui donne 1,09032. Cette valeur est entre (3a₂ + b₂) / 4 et b₂;mais la condition supplémentaire de Brent bloque: en effet, l'inégalité |1,09032 − b₂| ≤ |b₁ − b₀| / 2 n'est pas vérifiée: la valeur en cours est donc rejetée. À la place, on calcule le point milieu de intervalle [a₂; b₂]: m = −1,42897. On a f(m) = 9,26891; on pose alors a₃ = a₂ et b₃ = −1,42897;
Dans la quatrième itération, la valeur −1,15448 est obtenue par IQI entre (a₃; f(a₃)) = (−4; −25) et (b₂; f(b₂)) = (1,14205; 0,083582) et enfin (b₃; f(b₃)) = (−1,42897; 9,26891). Cette valeur ne tombe pas entre (3a₃ + b₃) / 4 et b₃). Par conséquent, on calcule à la place le milieu m = −2,71449; on a f(m) = 3,9393. On pose finalement a₄ = a₃ et b₄ = −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 − b₄| ≤ |b₄ − b₃| / 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: a₅ = −3,35724 et b₅ = b₄;
Dans la sixième itération, l'IQI est interdite car b₅ = b₄. Par conséquent, on la remplace par une IL entre (a₅; f(a₅)) = (−3,35724; −6,78239) et (b₅; f(b₅)) = (−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 a₆ = a₅ et b₆ = −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 a₇ = b₆ et b₇ = −3,00219 (a₇ et b₇ sont échangés afin que |f(b₇)| ≤ |f(a₇)| soit vraie);
Dans la huitième itération, on ne peut considérer une IQI parce que a₇ = b₆. 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: b₉ = −3 + 6·10⁻⁸ et b₁₀ = −3 − 3·10⁻¹⁵.

Algorithme

Entrée de a, b, et un pointeur vers une sous-routine pour f
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
répéter jusqu'à ce que f(b) = 0 ou |b − a| soit suffisamment petit (convergence)
- si f(a) ≠ f(c) et f(b) ≠ f(c) alors
  - $s := \frac{af(b)f(c)}{(f(a)-f(b))(f(a)-f(c))} + \frac{bf(a)f(c)}{(f(b)-f(a))(f(b)-f(c))} + \frac{cf(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 répéte
sortir b (renvoie de la racine)

Implémentations

Brent (1973) a publié une implémentation en Algol 60. La librairie Netlib contient une implémentation en Fortran. 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.

Bibliographie

Atkinson (1989). An Introduction to Numerical Analysis (2nd ed.), Section 2.8. John Wiley and Sons. ISBN 0-471-50023-2.
R.P. Brent (1973). Algorithms for Minimization without Derivatives, Chapter 4. Prentice-Hall, Englewood Cliffs, NJ. ISBN 0-13-022335-2.
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. SBN 471-28300-9.

Liens externes

zeroin.f sur Netlib.
Module for Brent's Method par John H. Mathews

Méthodes de résolution d'équations
Résolution d'équations polynomiales	Méthode de Bézout · Méthode de Cardan · Méthode de Sotta · Méthode de Ferrari · Méthode de Descartes · Méthode de Tschirnhaus · Méthode d'Hermite
Recherche d'un zéro	Méthode de dichotomie · Méthode de Newton · Méthode de la sécante · Méthode de Müller · Méthode de Brent · Méthode de la fausse position · Méthode de Héron · Méthode de Laguerre · Méthode du cercle de séparation · Méthode de Halley · Méthode de Householder . Méthode de Quasi-Newton

Portail des mathématiques

Ce document provient de « M%C3%A9thode de Brent ».

Catégorie : Algorithme de recherche d'un zéro d'une fonction

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Méthode de brent de Wikipédia en français (auteurs)

Игры ⚽ Поможем сделать НИР

Regardez d'autres dictionnaires:

Methode de Brent — 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… … Wikipédia en Français
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 … Wikipédia en Français
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 … Wikipédia en Français
Brent (homonymie) — Brent Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Noms Brent est une forme abrégée du nom anglais Brenton Amo te Pavona Localités Brent, localité de la commune suisse de Montreux. Brent (district… … Wikipédia en Français
Methode de Newton — Méthode de Newton Isaac Newton En analyse numérique, la méthode de Newton, ou méthode de Newton Raphson[1], est un algorithme efficace pour trouver des approximations d un zéro … Wikipédia en Français
Methode de Sotta — Méthode de Sotta La méthode de Sotta, imaginée et mise au point par Bernard Sotta, permet de résoudre toutes les équations du troisième degré et peut se généraliser à certaines équations de degré supérieur ou égal à 4 si les coefficients de ces… … Wikipédia en Français
Methode de la corde — Méthode de Newton Isaac Newton En analyse numérique, la méthode de Newton, ou méthode de Newton Raphson[1], est un algorithme efficace pour trouver des approximations d un zéro … Wikipédia en Français
Methode de la fausse position — Méthode de la fausse position Étapes successives de la méthode regula falsi avec l intervalle [a1;b1] comme point de départ. La racine de la fonction est le point en rouge. La méthode de la fausse position ou méthode regula falsi, en analyse… … Wikipédia en Français
Méthode De La Fausse Position — Étapes successives de la méthode regula falsi avec l intervalle [a1;b1] comme point de départ. La racine de la fonction est le point en rouge. La méthode de la fausse position ou méthode regula falsi, en analyse numérique, est un algorithme de… … Wikipédia en Français
Méthode De Newton — Isaac Newton En analyse numérique, la méthode de Newton, ou méthode de Newton Raphson[1], est un algorithme efficace pour trouver des approximations d un zéro … Wikipédia en Français

Dictionnaires et Encyclopédies sur 'Academic'

Méthode de brent