IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

zero avec Dekker


Sujet :

Algorithmes et structures de données

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Membre éprouvé
    Profil pro
    Inscrit en
    Février 2010
    Messages
    2 051
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Février 2010
    Messages : 2 051
    Par défaut zero avec Dekker
    Bonjour tous,
    je cherche à comprendre l'algo de Dekker qui est sur ce lien :
    http://fr.wikipedia.org/wiki/M%C3%A9thode_de_Brent
    mais je ne comprends pas vraiment...
    la méthode de Dekker combine la dichotomie et la sécante. Si la solution de la sécante est comprise entre celle de la dichotomie et la borne "b" alors on conserve la sécante sinon on conserve la dichotomie.

    Dans le principe je comprends mais j'ai l'impression qu'il y a une erreur sur le lien wikipedia. J'ai donné un exemple sur la pièce jointe.

    On voit que la solution de la sécante est entre celle de la dicho et "b". Du coup, si on écoute wikipedia on doit conserver la solution de la sécante...
    => le soucis est que l'on remarque que si on avait pris la solution de la dichotomie alors ça aurait converger plus vite... du coup, pourquoi pas conserver la solution de la dichotomie ?

    1°) Bref, je me dis donc que wikipedia à fait une erreur et voulais dire que l'on doit prendre la solution de la sécante si S est entre a et m ?

    2°) La deuxieme question que je me pose est sur l'algo qui est expliqué en dessous sur cette même page wikipedia. pourquoi à t on deux inégalités à vérifier et pourquoi la solution cette fois doit être compris entre
    '(3a+b)/4' et 'b' ? et non plus entre 'm' et 'b', je ne comprends vraiment pas là...


    je vous remercie pour l'aide que vous pourrez m'apporter ...

    A+

  2. #2
    Membre Expert
    Avatar de prgasp77
    Homme Profil pro
    Ingénieur en systèmes embarqués
    Inscrit en
    Juin 2004
    Messages
    1 306
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 38
    Localisation : France, Eure (Haute Normandie)

    Informations professionnelles :
    Activité : Ingénieur en systèmes embarqués
    Secteur : High Tech - Électronique et micro-électronique

    Informations forums :
    Inscription : Juin 2004
    Messages : 1 306
    Par défaut
    Bonjour,

    de ce que j'ai compris, la méthode de Dekker est très sensible aux données de départ. Ici certes, |f(b)| < |f(a)|, mais f est particulière : sa dérivée change de signe entre a et b.

    Avec un a et un b bien choisis (f monotone sur [a;b]), Dekker est efficace.

  3. #3
    Membre éprouvé
    Profil pro
    Inscrit en
    Février 2010
    Messages
    2 051
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Février 2010
    Messages : 2 051
    Par défaut
    merci d'avoir pris le temps de répondre.

    mais en fait dans tout les cas, j'aurais dit :
    -> l'idée de l'algo et de prendre l'itération qui se rapproche plus de la racine à chaque iteration c'est bien cela ? mais comment écrire cette condition ?
    -> de plus, si j'inverse a et b il faut que ma condition soit bien écrit et j'ai du mal à le faire

    pourrais tu me faire un petit schéma s'il te plait pour m'expliquer ?

    je te remercie

  4. #4
    Membre Expert
    Avatar de prgasp77
    Homme Profil pro
    Ingénieur en systèmes embarqués
    Inscrit en
    Juin 2004
    Messages
    1 306
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 38
    Localisation : France, Eure (Haute Normandie)

    Informations professionnelles :
    Activité : Ingénieur en systèmes embarqués
    Secteur : High Tech - Électronique et micro-électronique

    Informations forums :
    Inscription : Juin 2004
    Messages : 1 306
    Par défaut
    Citation Envoyé par 21did21 Voir le message
    l'idée de l'algo et de prendre l'itération qui se rapproche plus de la racine à chaque iteration c'est bien cela ? mais comment écrire cette condition ?
    Il n'est pas possible de prendre l'approximation qui est la plus proche de la racine, car cela impliquerait de connaitre la racine de f ou f tout entière. La seule chose que l'algo fait, c'est de choisir l'approximations qui a le plus de chances d'être proche de la racine. Note que justement, l'algo assure un choix efficace quand la fonction est monotone sur [a;b].


    Citation Envoyé par 21did21 Voir le message
    de plus, si j'inverse a et b il faut que ma condition soit bien écrit et j'ai du mal à le faire
    Il ne s'agit pas d'inverser a et b, mais de mieux les choisir. Pour cela, il faut faire des prédictions sur la fonction.

    Citation Envoyé par 21did21 Voir le message
    pourrais tu me faire un petit schéma s'il te plait pour m'expliquer ?
    Il faut voir, un schéma de quoi ?

  5. #5
    Membre éprouvé
    Profil pro
    Inscrit en
    Février 2010
    Messages
    2 051
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Février 2010
    Messages : 2 051
    Par défaut
    merci de prendre le temps de m'aider

    Citation Envoyé par prgasp77 Voir le message
    Il n'est pas possible de prendre l'approximation qui est la plus proche de la racine, car cela impliquerait de connaitre la racine de f ou f tout entière.
    mdr, en effet j'ai été un peu con sur ce coup

    Citation Envoyé par prgasp77 Voir le message
    La seule chose que l'algo fait, c'est de choisir l'approximations qui a le plus de chances d'être proche de la racine.
    d'accord mais je ne comprends pas trop quel choix faire pour assurer cela justement ? Pourquoi le critère a été posé entre b et m plutot que a et m ?

    Citation Envoyé par prgasp77 Voir le message
    Note que justement, l'algo assure un choix efficace quand la fonction est monotone sur [a;b].
    OK ça marche

    Citation Envoyé par prgasp77 Voir le message
    Il faut voir, un schéma de quoi ?
    un exexmple de la méthode qui arrive à me persuader que le fait de choisir la solution entre la borne "b" et la borne "dichotomie" est une bonne idée.
    car quand je me fais des schémas moi même j'ai l'impression que la dichotomie et à chaque fois plus rapide...


    ps: au fait as tu compris la méthode qu'il y a en dessous du paragraphe sur Dekker. Elle a l'air super cette méthode mais cette fois il y a encore plus de conditions qeu je ne comprends pas ....

  6. #6
    Membre Expert
    Avatar de prgasp77
    Homme Profil pro
    Ingénieur en systèmes embarqués
    Inscrit en
    Juin 2004
    Messages
    1 306
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 38
    Localisation : France, Eure (Haute Normandie)

    Informations professionnelles :
    Activité : Ingénieur en systèmes embarqués
    Secteur : High Tech - Électronique et micro-électronique

    Informations forums :
    Inscription : Juin 2004
    Messages : 1 306
    Par défaut
    Si j'ai bien compris l'article de wikipedia, si on prends b_0 = a, b_1 = b, alors b_{k+1} est sensé être une meilleure approximation de la racine que b_k. Or dans ton exemple, |x-a| < |x-b| (x = racine de f sur [a;b]).

    Je n'ai pas d'outil sous la main pour générer un graphique, mais si tu choisissais mieux a et b, ou si tu regardais le comportement de cette méthode après quelques itérations dans l'exemple que tu as donné, je pense que tu verrais l'intérêt du critère « s compris entre m et b ».

    Cdlt,

Discussions similaires

  1. Comment inserrer un zero avec sed
    Par Rany1 dans le forum Unix
    Réponses: 2
    Dernier message: 20/04/2010, 15h59
  2. Comment inserrer un zero avec sed
    Par Rany1 dans le forum Applications et environnements graphiques
    Réponses: 4
    Dernier message: 20/04/2010, 14h26
  3. Réponses: 3
    Dernier message: 11/12/2008, 10h26
  4. [VBA-E]recherche de toutes lignes avec zero
    Par zoumzoum59 dans le forum Macros et VBA Excel
    Réponses: 24
    Dernier message: 10/06/2006, 23h33
  5. Réponses: 2
    Dernier message: 09/03/2006, 14h15

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo