Méthode De Dichotomie

Méthode de dichotomie

Étapes successives de la méthode de dichotomie avec comme point de départ, l'intervalle [a₁;b₁. Le zéro de la fonction est en rouge.]

La méthode de dichotomie ou méthode de la bissection est, en mathématiques, un algorithme de recherche d'un zéro d'une fonction qui consiste à répéter des partages d’un intervalle en deux parties puis à sélectionner le sous-intervalle dans lequel existe un zéro de la fonction.

Principe

On considère deux nombres a et b et une fonction f continue sur l'intervalle [a, b] telle que f(a) et f(b) soient de signes opposés. Supposons que nous voulions résoudre l’équation f(x) = 0. Nous savons d'après le théorème des valeurs intermédiaires que f doit avoir au moins un zéro dans l’intervalle [a, b]. La méthode de dichotomie consiste à diviser l’intervalle en deux en calculant c = (a+b) / 2. Il y a maintenant deux possibilités : ou f(a) et f(c) sont de signes opposés, ou f(c) et f(b) sont de signes opposés.

L’algorithme de dichotomie est alors appliqué au sous-intervalle dans lequel le changement de signe se produit, ce qui signifie que l’algorithme de dichotomie est en soi récursif.

L’erreur absolue de la méthode de dichotomie est au plus

$\frac{b-a}{2^{n+1}}$

après n étapes. En d’autres termes, l’erreur est diminuée de moitié à chaque étape, ainsi la méthode converge linéairement, ce qui est très lent par comparaison avec la méthode de Newton.

L'avantage par rapport à cette dernière est son domaine d'application plus vaste : il suffit seulement que f(a) et f(b) soient de signes opposés et qu'on puisse déterminer le signe de f(c) à chaque itération. De plus, si on se donne la tolérance relative $\epsilon\,$ , on connaît en théorie le nombre maximum d'itérations nécessaires pour satisfaire cette tolérance :

$2^{n+1} = 1/\epsilon\,$

C'est un cas assez peu habituel en calcul numérique pour être noté.

Programmation

Sous l'hypothèse que le signe de f(c) soit déterminable, voici une représentation de la méthode en langage Visual Basic. Les variables xL et xR correspondent aux réels a et b précédents. Les valeurs initiales de xL et xR doivent être choisies telles que f(xL) et f(xL) soient de signe opposé (elles encadrent le zéro). La variable epsilon indique avec quelle précision le résultat doit être donné.

'Méthode de dichotomie

'Start loop
  While (xR - xL) > epsilon do
  
  'Calcule le milieu du domaine de définition
  xM = (xR + xL) / 2
  
  'Find f(xM)
  If ((f(xL) * f(xM)) > 0) Then
    'jette la moitié de gauche
    xL = xM
  Else
    'jette la moitié de droite
    xR = xM
  End If
Loop

Limite de la méthode

Cette méthode d'une grande robustesse nécessite cependant de connaître à chaque étape le signe de f(c). Dans quelques cas, il peut arriver que la valeur de f(c) soit si proche de 0 que la précision du logiciel de calcul ne permette plus de déterminer le signe de f(c) (le logiciel de calcul assimile f(c) à 0). L'application de l'algorithme risque alors de conduire à l'élimination erronée d'une moitié de l'intervalle et à la convergence vers une valeur éloignée de la racine.

D'une manière plus générale, la détermination du signe de f(c) peut se révéler impossible, même en augmentant la précision du calcul du logiciel. Considérons par exemple un réel $α$ dont on peut calculer des valeurs approchées décimales ou rationnelles $α n$ à toute précision $\frac{1}{n}$ désirée. Considérons maintenant la fonction f affine sur les intervalles $[0, \frac{1}{3}]$ , $[\frac{1}{3}, \frac{2}{3}]$ et $[\frac{2}{3}, 1]$ et telle que $f (0) = - 1$ , $f (1) = 1$ , $f (1 / 3) = f (2 / 3) = α$ . La méthode de dichotomie demande de déterminer le signe de $f (1 / 2) = α$ . Or il n'existe aucun algorithme général permettant de décider si $α > 0$ , $α = 0$ ou $α < 0$ . En effet, un tel algorithme, s'il existait, ne devant effectuer qu'un nombre fini de calcul, devrait prendre sa décision au vu d'un nombre fini de valeurs approchées $α n$ , ce qui est insuffisant pour conclure.

Cette limite conduit les théoriciens^[1] de l'analyse constructive à qualifier la méthode de dichotomie de non constructive et à privilégier l'énoncé alternatif : rechercher une valeur x telle que $| f (x) |$ soit inférieure à une erreur donnée.

Article détaillé : Analyse constructive.

Voir aussi

Référence

Richard L. Burden, J. Douglas Faires (2000), Numerical Analysis, (7th Ed), Brooks/Cole. ISBN 0534382169

↑ Erret Bishop, Douglas Bridges, Constructive analysis, Springer-Verlag (1985), p.8

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 dichotomie ».

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 Dichotomie de Wikipédia en français (auteurs)

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

Regardez d'autres dictionnaires:

Methode de dichotomie — Méthode de dichotomie Étapes successives de la méthode de dichotomie avec comme point de départ, l intervalle [a1;b1. Le zéro de la fonction est en rouge.] La méthode de dichotomie ou méthode de la bissection est, en mathématiques, un algorithme… … Wikipédia en Français
Méthode de dichotomie — Étapes successives de la méthode de dichotomie avec comme point de départ, l intervalle [a1;b1. Le zéro de la fonction est en rouge.] La méthode de dichotomie ou méthode de la bissection est, en mathématiques, un algorithme de recherche d un zéro … Wikipédia en Français
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
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
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

Dictionnaires et Encyclopédies sur 'Academic'

Méthode De Dichotomie