Inscription / Connexion Nouveau Sujet
Dichotomie et méthode de Newton
Bonjour, j'aimerais avoir votre aide pour un exercice sur la méthode de dichotomie et la méthode de Newton. Je bloque sur une question qui m'empêche de pouvoir écrire un algorithme. Voici l'énoncé:
La méthode de dichotomie est un algorithme de recherche d'un zéro d'une fonction qui consiste à Réiterer des partages d'un intervalle en deux moitiés puis à sélectionner celui dans lequel se trouve le zéro de la fOnction.
Voici l'algorithme :
Lire à, b, E.
Tant que (b-a)>E
C prend la valeur (à+b)/2
Si f(à)*f(b)>0 alors
A prend la valeur c
Sinon
B prend la valeur c
Fin si
Fin tant que
Afficher c
La première question consiste à trouver le nombre d'or solution positive de l'équation x2-x-1=0
Pour la deuxième question, il faut recopier l'algorithme et le tester pour qu'il affiche certains encadrement.
J'ai réussi ces deux questions, mais je bloQue pour la 3.
3) soit (Pn)n
0. P0=1 et pn+1=Pn/2
a. Que représente Pn? Justifier qu'elle est décroissante et exprimer Pn en fonction de n.
b. Écrire puis programmer un algorithme qui prend d'entrée E et qui retourne le plus petit entier n tel que Pn<E.
c. A l'aide du programme, déterminer le plus petit entier n tel que Pn soit inférieur à 0,1 ; 0,01 ; 0,001 ; 0,0001 ; 0,00001
Commenter l'efficacité de l'algorithme de dichotomie à partir des résultats obtenus.
Je bloque à la question 3. Je comprends pas ce que représente Pn. J'ai calculé pn+1-pn pour prouver que la suite est décroissante. Comme la raison est 1/2, le terme général de Pn est (1/2)n.
Pouvez vous m'aider pour la question 3 s'il vous plaît ? Je n'arrive pas à programmer mon algorithme. Merci d'avance 
Bonjour,
la réponse à la question "que représente Pn" telle qu'elle est posée est "philosophique"
Pn représente le terme de rang n de la suite (P) défini dans l'énoncé 
une réponse plus pertinente sera apportée plus loin.
3b)
principe :
initialiser P = valeur de P0, et n = 0
tant que on n'a pas trouvé (c'est à dire qu'il est faux que P < E, qu'il est vrai que P ≥ E)
incrémenter n
P prend la valeur suivante de la suite (selon sa formule de récurrence)
fin
afficher n
ce squelette d'algorithme est valable pour toutes les suites
3c)
faire tourner ce programme ainsi obtenu.
jusqu'ici aucun rapport avec la dichotomie ni les questions d'avant 1 et 2
cette question 3 est donc une question indépendante.
le rapport vient maintenant comme une surprise :
Commenter l'efficacité de l'algorithme de dichotomie
cela veut dire :
l'algorithme de dichotomie utilise un intervalle de largeur P = b-a, initialement on va dire P = 1
tout au moins on peut partir de ça comme valeurs initiales de a et b
alors à chaque boucle, P est divisé par 2
maintenant et maintenant seulement on peut répondre de façon pertinente à la question 3a :
P représente la largeur de l'intervalle dans l'algorithme de dichotomie !!
donc l'encadrement, la précision du résultat obtenu au cours de chacune des boucles successives de l'algorithme de dichotomie
si on veut une précision de 0.001 par exemple
le nombre de boucle effectuées par l'algorithme de dichotomie sera le même que celui de l'algorithme de la suite Pn
d'où la conclusion ("efficacité" veut dire en terme de nombres de boucles)
cette conclusion ne sert pas à grand chose "en soi"
elle n'est pertinente que si on la compare ultérieurement avec l'efficacité de la méthode de Newton
pour montrer que en termes de nombres de boucles, la méthode de Newton est plus efficace que la dichotomie
Ah d'accord je viens de comprendre, merci beaucoup pour votre réponse ! J'avais oublié de préciser que pour l'exercice la fonction f(x)=x2-x-1 était étudiée sur [1;2], c'est donc pour cela que p0=1?
Justement j'ai oublié d'écrire la deuxième partie de l'exercice où on s'intéresse à la méthode de Newton. Dans l'énoncé, il est écrit: partant d'un réel x0 de préférence près du zéro à trouver, on approche la fonction f au premier ordre en la considérant à peu près égale à la fonction affine donnée par l'équation de la tangente à sa courbe représentative au point d'abscisse x0: f(x)
f'(x0)(x-x0)+f(xsub][/sub]0).
On résout l'équation pour obtenir x1. On réitère le processus.
1) justifier qu'on peut définir la suite (xn) telle que xn+1=xn-(f(xn)/f'(xn)).
2) écrire et programmer l'algorithme en considérant la condition d'arrêt |xn+1-xn<E.
J'ai réussi la première question, par contre pour la deuxième, est ce que ça veut dire que je dois mettre la condition d'arrêt dans le "tant que"?
oui
sans oublier ce que veut dire tant que
tant que on n'a pas fini on continue
c'est à dire tant que le contraire de la condition de l'énoncé qui dit quand on a fini
D'accord, et ça reste le même type d'algorithme basique comme celui de la première partie? Dans la boucle tant que, x prend la valeur xn-(f(xn)/f'(xn)), et n prend la valeur n+1?
Annuler
connectez vous