Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Dichotomie et balayage Module : dichotomie et balayage On considère la fonction

Dichotomie et balayage Module : dichotomie et balayage On considère la fonction f définie sur [−1;2] par : f x=x 2−2 . 1. Étude graphique Afficher la courbe représentative de cette fonction sur l'écran de la calculatrice ou à l'aide du logiciel GeoGebra. Combien de solutions l'équation f x=0 atelle ? Donner une valeur approchée de cette (ou ces) solution(s). Combien de solutions l'équation f x=1 atelle ? Donner une valeur approchée de cette (ou ces) solution(s). 2. Un algorithme de dichotomie On se propose, grâce à un algorithme, de donner une valeur approchée aussi précise que possible de la solution de l'équation f x=0 . On considère l'algorithme du tableau 1 : Algorithme Commentaires Variables a, b : nombres réels f : fonction k : entier naturel N : entier naturel m : nombre réel Entrée Saisir a, b, f, N Traitement Pour k variant de 1 à N m prend la valeur ab 2 Si f m et f b sont de même signe alors b prend la valeur m sinon a prend la valeur m Fin Si Fin Pour Sortie Afficher a, b Bornes de l’intervalle d'étude Fonction étudiée Compteur pour la boucle Nombre de fois où la boucle sera parcourue Milieu de l'intervalle (valeur approchée de la solution) On se place au milieu de l'intervalle [a ;b] Si f m et f b sont de même signe alors la solution de l'équation f x=0 est située dans l’intervalle [a ; m] sinon elle est située dans [m ;b] On affiche un encadrement de la solution de f x=0 Tableau 1 – Un algorithme de dichotomie On applique à la main cet algorithme à la fonction f donnée dans le texte. Prendre a = 1, b = 2, N = 3 et compléter le tableau suivant : k 1 2 3 x x a 1 1 1,25 1,375 x b 2 1,5 1,5 1,5 x m 1,5 1,25 1,375 x x f m×f b0 oui non non x x Tableau 2 – Simulation algorithmique M. Gallice Stéphane Page 1 / 8 28/04/10 Dichotomie et balayage 3. Organigramme On représente graphiquement les structures de cet algorithme par un organigramme. Deux notions apparaissent : • la notion de boucle : tant qu'un résultat attendu n'apparaît pas, on recommence les opérations ; • la notion de compteur ou d'incrémentation : on augmente un entier de 1, l'incrément, tant que le résultat attendu n'apparaît pas. M. Gallice Stéphane Page 2 / 8 28/04/10 Dichotomie et balayage 4. Amélioration de l'algorithme de dichotomie a/ Dans l'algorithme précédent, on ne connait pas à priori la précision du résultat. On peut l'améliorer en remplaçant la boucle « Pour... » par une boucle « Tant que... ». Algorithme Commentaires Variables f : fonction p : nombre réel a, b : nombres réels m : nombre réel Entrée Saisir f, p, a, b Traitement Tant que b − a > p faire : m prend la valeur ab 2 Si f m et f b sont de même signe alors b prend la valeur m sinon a prend la valeur m Fin Si Fin Tant que Sortie Afficher a, b Fonction étudiée Précision désirée Bornes de l’intervalle d'étude Milieu de l'intervalle (valeur approchée de la solution) On se place au milieu de l'intervalle [a ;b] Si f m et f b sont de même signe alors la solution de l'équation f x=0 est située dans l’intervalle [a ; m] sinon elle est située dans [m ;b] On affiche un encadrement à 10–p près de la solution de f x=0 Tableau 3 – Un autre algorithme de dichotomie b/ On applique à la main ce nouvel algorithme à la fonction f avec une précision de 10−1. Prendre a = 1, b = 2 et compléter le tableau suivant : Itération 1 2 3 4 x x a 1 1 1,25 1,375 1,375 x b 2 1,5 1,5 1,5 1,4375 x b – a > 0,1 oui oui oui oui non x m 1,5 1,25 1,375 1,4375 x x f m×f b0 oui non non oui x x Tableau 4 – Simulation algorithmique Un encadrement à 10−1 près est [1,375 ;1,4375] après 4 itérations. Un encadrement à 10−5 près est [1,4142074585 ;1,41421508789] après 17 itérations ! Donc les 4 premières décimales sont exactes : 2≃1,4142 . M. Gallice Stéphane Page 3 / 8 28/04/10 Dichotomie et balayage c/ Représentation graphique des structures de cet algorithme par un organigramme. M. Gallice Stéphane Page 4 / 8 28/04/10 Dichotomie et balayage 5. Programmation avec un logiciel a/ Programmation avec AlgoBox b/ Programmation avec XCAS dichoo(f,n,a,b):= { local k; for (k:=1;k<=n;k++) { if (sign((f((a+b)/2)))=sign((f(b)))) b:=((a+b)/2); else a:=((a+b)/2); } return evalf((a+b)/2)+" est la solution trouvée avec "+n+" itérations";} dicho(f,p,a,b):= { local m; while ((ba)>p) { m:=(a+b)/2; if ((sign(f(m))==sign(f(b)))) b:=m; else a:=m;; }; return( "Un encadrement à "+ evalf(p)+" près est ["+evalf(a)+" ; "+evalf(b)+"]."); } M. Gallice Stéphane Page 5 / 8 28/04/10 Dichotomie et balayage 6. Programmation avec une calculatrice Le but de ces programmes est de déterminer les solutions d'une équation du type f x=0 sur un intervalle [ A; B] sur lequel f est tel que f A× f B0 . Ces programmes supposent que la fonction f est enregistré en Y1. • A est la borne inférieure de l'intervalle. • B est la borne supérieure de l'intervalle. • P est la précision souhaitée. • M est le milieu de l'intervalle. On se place au milieu de l'intervalle [ A ; B] . Si f M et f B sont de même signe alors la solution de l'équation f x=0 est située dans l'intervalle [ A ; M ] sinon elle est située dans [ M ; B] . CASIO GRAPH 35+ Texas Instruments TI82 Stats.fr " " → A ? A " " → B ? B " " → P ? P – > While B A P ( + ) A B ÷ → 2 M ( ) If Y1 M × ( )> Y1 B 0 → Then M B → Else M A IfEnd WhileEnd A B Prompt A, B, P While B–A>P (A+B)/2 M → If Y1(M)*Y1(B)>0 Then M B → Else M A → End End Disp A, B « → » est sur le clavier de la calculatrice « → » s'obtient en appuyant sur « sto », en bas à gauche du clavier de la calculatrice « ↵ » s'inscrit dans un programme à chaque fois qu'on tape sur « EXE » pour aller à la ligne « : » s'inscrit dans un programme à chaque fois qu'on tape sur « entrer » pour aller à la ligne Pour revenir au menu principal, il faut utiliser la touche « EXIT » Pour revenir au menu principal, il faut utiliser la touche « 2nde » « quitter » 7. Encadrement par balayage Cette dernière méthode est basée sur une utilisation astucieuse des tableaux de valeurs de la calculatrice pour donner une valeur approchée de la solution de f x=0 . a/ À l'aide de la calculatrice, donner un tableau de valeurs de la fonction f sur l'intervalle [0;1] avec un pas de 0,1. En déduire un encadrement à 10−1 près de la solution de l'équation f x=0 . Avec cet encadrement, donner un nouveau tableau de valeurs de la fonction f avec un pas de 0,01. En déduire un encadrement à 10−2 près de la solution de l'équation f x=0 . En réitérant ce procédé, trouver un encadrement à 10−5 près de la solution de l'équation f x=0 . b/ Adapter cette nouvelle méthode pour déterminer un encadrement à 10−5 près de la solution de l'équation f x=1 . Encadrement f x=0 f x=1 10−1 [1,4 ;1,5] [1,7 ;1,8] 10−2 [1,41;1,42] [1,73;1,74 ] 10−3 [1,414 ;1,415] [1,732 ;1,733] 10−4 [1,4142 ;1,4143] [1,7320 ;1,7321] 10−5 [1,41421;1,41422] [1,73205;1,73206] M. Gallice Stéphane Page 6 / 8 28/04/10 Dichotomie et balayage 8. Application Les formats de papier ont été conçus pour vérifier une propriété remarquable : une feuille coupée en deux parties égales par la longueur donne deux nouvelles feuilles ayant la même proportion entre longueur et largeur que la feuille du départ. Une feuille de papier A0 a une aire d'un mètre carré. L'aire est diminuée d'un facteur 2 si ce rapport vaut 2 : dans la pratique, les dimensions sont arrondies. Format A0 A1 A2 A3 A4 A5 ... Longueur (m) 2 2 2 2 2 2 22 2 4 2 42 ... Largeur (m) 2 2 2 2 2 22 2 4 2 42 2 8 ... Aire (m²) 1 1 2 1 4 1 8 1 16 1 32 ... Une feuille A3 coupée en deux donne deux feuilles A4. La feuille de format A4 est la feuille classique des rames de papier pour photocopieuses : • ce format permet de découper plusieurs types de format dans une même grande feuille sans laisser de chute. • un document format A4 peut être agrandi en A3 sans déformation : les facteurs d'agrandissement de uploads/Geographie/ 2md-10 1 .pdf