Python algorithme de dichotomie

pinochet
pinochet
dans Logiciels pour les mathématiques
[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

  • fm_31
    fm_31
    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))
  • pinochet
    pinochet
    [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.
  • PetitLutinMalicieux
    PetitLutinMalicieux
    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.
    Ce site est fatigant. Les gens modifient sans cesse leurs messages passés, et on ne comprend plus rien à la discussion. Je suis nostalgique du temps où, si on postait une bêtise, on devait l'assumer. Et si on cite le passage pour l'ancrer, l'administrateur supprime en disant qu'on n'a pas besoin de recopier le message passé.
  • pinochet
    pinochet
    [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.
  • PetitLutinMalicieux
    PetitLutinMalicieux
    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.
    Ce site est fatigant. Les gens modifient sans cesse leurs messages passés, et on ne comprend plus rien à la discussion. Je suis nostalgique du temps où, si on postait une bêtise, on devait l'assumer. Et si on cite le passage pour l'ancrer, l'administrateur supprime en disant qu'on n'a pas besoin de recopier le message passé.
  • fm_31
    fm_31
    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.

Bonjour!

Pour participer au forum, cliquer sur l'un des boutons :

Connexion S'inscrire

Catégories

In this Discussion

Qui est en ligne 33

AmadouChaurienCongruSethMorleyJuniorbiguine_equationmtho5 +27 Invités