Python algorithme de dichotomie — Les-mathematiques.net The most powerful custom community solution in the world

Python algorithme de dichotomie

[Il n'est pas correct d'effacer le message initial de la discussion dès lors que quelqu'un s'est donné la peine d'y répondre. Je le rétablis. AD]
Bonjour, je sais que j'avais la solution de ce problème dans le livre de Jean-Philippe PRÉAUX Informatique MP, PC, PT, PSI, sur la différence entre l'utilisation d'un <= ou d'un < lors d'une dichotomie, mais je ne m'en souviens plus.

Voici le code :
from matplotlib.pyplot import *
from numpy import *
from random import *

x = arange(0,10,0.5)

def fonction(x):
return x-3

def dichotomie1(f,a,b):
if(f(a)*f(b) >= 0):
return None
while(abs(b-a)>10**(-2)):
m = (a+b)/2
if(f(a)*f(m)<=0):
b = m
else : a = m
return (a+b)/2

def dichotomie2(f,a,b):
if(f(a)*f(b) > 0):
return None
while(abs(b-a)>10**(-2)):
m = (a+b)/2
print(" a = ", a ," b = ",b)
print(" f(a) = ", f(a) ," f(b) = ",f(b)," f(m) = ",f(m))
print("f(a)*f(m) = ",f(a)*f(m))
if(f(a)*f(m) < 0):
b = m
else : a = m
return (a+b)/2

def dichotomie3(f,a,b):
if(f(a)*f(b) > 0):
return None
while(abs(b-a)>10**(-2)):
m = (a+b)/2
print(" a = ", a ," b = ",b)
print(" f(a) = ", f(a) ," f(b) = ",f(b)," f(m) = ",f(m))
print("f(a)*f(m) = ",f(a)*f(m))
if(f(a)*f(m) > 0):
a = m
else : b = m
return (a+b)/2
Dicho 1 et 3 fonctionnent, mais pas la 2.

Comprenez vous pourquoi ?
Merci bienMerci bien.

[Pour afficher du code python, IL FAUT utiliser le bouton "Code" (5ème par la droite au dessus de la fenêtre d'édition. AD]

Réponses

  • Bonjour ,
    dans ce test très limité , les 3 versions fonctionnent et donnent le même résultat :

    Python 3.8.6 (tags/v3.8.6:db45529, Sep 23 2020, 15:52:53) [MSC v.1927 64 bit (AMD64)] on win32
    Type "help", "copyright", "credits" or "license()" for more information.
    >>>
    ===== RESTART: C:/Users/feclm/Documents/Fernand/python/dicotomie_exemple.py ====
    resul 1: -1.9970703125
    resul 2: -1.9970703125
    resul 3: -1.9970703125
    >>>
    Cordialement
    '''-- dicotomie------------------------------------------------------
    --
    --
    ------------------------------------------------------------------'''
    
    def fonction(x): return x*x - 4
    
    def dichotomie_1(f,a,b):
        if(f(a)*f(b) >= 0): return None  #-- fonctions de même signe
        while(abs(b-a)>10**(-2)):
            m = (a+b)/2
            if(f(a)*f(m)<=0): b = m
            else : a = m
        return (a+b)/2
    
    def dichotomie_2(f,a,b):
        if(f(a)*f(b) > 0):return None
        while(abs(b-a)>10**(-2)):
            m = (a+b)/2
            if(f(a)*f(m) < 0): b = m
            else : a = m
        return (a+b)/2
    
    def dichotomie_3(f,a,b):
        if(f(a)*f(b) > 0): return None
        while(abs(b-a)>10**(-2)):
            m = (a+b)/2
            if(f(a)*f(m) > 0):a = m
            else : b = m
        return (a+b)/2
    
    print("resul 1: " , dichotomie_1(fonction ,-10 , 0))
    print("resul 2: " , dichotomie_2(fonction ,-10 , 0))
    print("resul 3: " , dichotomie_3(fonction ,-10 , 0))
    
    
    
  • [Il n'est pas correct d'effacer un message dès lors que quelqu'un s'est donné la peine d'y répondre. Je le rétablis. AD]
    Le problème est lorsque f(m) = 0, il y a un -0 qui apparait. C'est très rare mais cela peut arriver.
    Vous n'utilisez pas ma fonction, vous modifiez l'algorithme.

    Par exemple :
    def fonction(x): return x - 2
    
    def dichotomie_1(f,a,b):
    if(f(a)*f(b) >= 0): return None #-- fonctions de même signe
    while(abs(b-a)>10**(-2)):
    m = (a+b)/2
    if(f(a)*f(m)<=0): b = m
    else : a = m
    return (a+b)/2
    
    def dichotomie_2(f,a,b):
    if(f(a)*f(b) > 0):return None
    while(abs(b-a)>10**(-2)):
    m = (a+b)/2
    if(f(a)*f(m) < 0): b = m
    else : a = m
    return (a+b)/2
    
    def dichotomie_3(f,a,b):
    if(f(a)*f(b) > 0): return None
    while(abs(b-a)>10**(-2)):
    m = (a+b)/2
    if(f(a)*f(m) > 0):a = m
    else : b = m
    return (a+b)/2
    
    print("resul 1: " , dichotomie_1(fonction ,0 , 4))
    print("resul 2: " , dichotomie_2(fonction ,0 , 4))
    print("resul 3: " , dichotomie_3(fonction ,0 , 4))
    
    C'est dommage quand même de ne pas pouvoir effectuer une dichotomie correctement sur une simple fonction affine ? Même si le but est d'étudier les racines de fonctions un peu plus compliquées... mais bon, on peut au moins essayer de comprendre pourquoi cela ne fonctionne pas.
  • Bonjour

    Ta méthode est douteuse car tu méconnais la bonne réponse. Même si tu la trouves, tu vas continuer à chercher. Si tu coupes ton intervalle en 2, tu n'es jamais à l'abri de tomber sur la bonne réponse. A priori, c'est cela qui manque. Vérifions-le sur les 3 algorithmes.

    Code 1 : Si "m" est la solution, "b" prend la valeur de "m". Et "a" va s'évertuer à se rapprocher de la solution, sans jamais l'atteindre évidemment, par définition même de la dichotomie (on coupe en deux à l'infini).

    Code 2 : Si "m" est la solution, "a" prend la valeur de "m". f(a)=0. Au tour suivant, tu vas choisir un "m" entre la bonne réponse et b. f(m) et f(b) sont alors de même signe. Comme "a" prend la valeur de "m", f(a) et f(b) sont de même signe. Et c'est le drame.

    Code 3: Si "m" est la solution, "b" prend la valeur de "m". Et "a" va s'évertuer à se rapprocher de "b" comme dans le premier code.
  • [Il n'est pas correct d'effacer un message dès lors que quelqu'un s'est donné la peine d'y répondre. Je le rétablis. AD]
    Bonjour, ce n'est pas un problème d'algorithmie, mais de langage de programmation en l'occurence python.
    Les trois algorithmes sont corrects, cependant il y a un problème en langage python.
    Tester le programme ci-contre, et la réponse sera incorrecte dans le cas dicho2 pour ma fonction.
    Merci bien.
  • C'est bien la peine d'avoir pris le temps de détailler. Je n'en peux plus de ces scientifiques tellement vaniteux qu'ils refusent de considérer que leurs algorithmes sont foireux.
    Je n'avais pas exécuté ton code. Je viens de le faire. Et cela me donne totalement raison.
    (' a = ', 0.0, ' b = ', 4.0)
    (...)
    (' a = ', 2.0, ' b = ', 4.0)
    (' f(a) = ', 0.0, ' f(b) = ', 2.0, ' f(m) = ', 1.0)
    ('f(a)*f(m) = ', 0.0)
    (' a = ', 3.0, ' b = ', 4.0)
    
    Quand a=2, c'est la bonne réponse. Du coup, ton code déraille. Au tour suivant a=3 et b=4. Et c'est foutu. Puisque la bonne réponse est 2.

    PS : Connais-tu la différence entre la division entière et la division réelle ? Un petit "a=a*1.0" et "b=1.0*b" ne seraient pas de refus.
  • Les explications de PetitLutinMalicieux que je salue pour sa sagacité m'ont tout de suite convaincu qu'on ne peut remplacer impunément "<=" par "<" dans un algorithme même si ça ne donne pas systématiquement un résultat erroné .
Cette discussion a été fermée.
Success message!