LA DICHOTOMIE
Ce mois-ci nous attaquons une partie des mathématiques qui, on ne le sait pas assez, a eu une énorme influence sur le calcul en général. La dichotomie est un calcul itératif qui divise de deux en deux un intervalle fixé au départ.
Une application que tout le monde a dû déjà expérimenter se trouve dans le jeu du nombre mystérieux : on vous propose de trouver un nombre entre 0 et 10 ; vous proposez 10 + 0/2 = 5 et la réponse sera : « trop élevé » ou « pas assez ». Alors vous raisonnez comme suit : si « trop élevé », on considère l'intervalle [0,5] et vous proposez 0 + 5/2 = 2.5, si « pas assez », on considère l'intervalle [5,10] et vous proposez 5 + 10/2 = 7.5 ; et si vous n'obtenez pas la bonne réponse vous continuez à subdiviser les différents intervalles. C'est un raisonnement très efficace.Le programme ci-après exécute une analyse complexe pour trouver une solution x telle que y = 0, y = f(x) étant une fonction quelconque que l'on programme en ligne 250 par exemple sous la forme y = Ln (3x + 4) -e (x² + 3). ATTENTION ! ! Il faut être prudent : si vous programmez une fonction trigonométrique comme par exemple y = sin (5x -1) la solution x pour laquelle y = 0 vous sera donnée en radians ; si l'on veut le résultat en degré alors on programmera comme suit : 250 deg : y = sin (5x - 1) : rem... La méthode dichotomique a cependant un gros problème : elle ne donne qu'une solution ; or si la courbe (ex : sin (x)) coupe plusieurs fois l'axe des x une unique solution . sera obtenue. On a remédié artificiellement à ce problème en créant des sous-intervalles. Pour plus de clarté nous allons expliquer ligne à ligne le programme en prenant un exemple simple mais montrant des difficultés au niveau du programme. Soit l'équation : y = (x² (2 - x))7 ; on voit que y = 0 si x = 0 ou x = 2. On demande une précision de 8 - ligne 90 - et un intervalle de - 2,3 - ligne 110 — (on n'est pas censé connaître la solution). La ligne 150 calcule y (- 2) ; la ligne 170 donne w = — 1.5 et la ligne 140 calcule y(w) ce qui donne y². Puis les signes de y1et y² sont comparés : s'ils sont égaux (dans ce cas particulier ils sont positifs) alors la courbe est au-dessus ou au-dessous de l'axe des x mais ne l'a pas traversé - ligne 190 -. On revient alors à la ligne 170 qui donne w = — 1 et ainsi de suite jusqu'à ce que le signe de y (- 2) soit différent de celui de y (w). S'il est différent on appliquera alors la méthode de dichotomie sur l'intervalle [a,w] - ligne 200 à 230— ligne 200 on prend la moitié (c) de l'intervalle a c w et on calcule y (c). Ligne 210, si y (c) (y5 dans le programme) est égal au signe de y (a) (y1 dans le programme) alors on considère l'intervalle °c, w§ et on recommence — goto 200 - . Ligne 230 si au contraire le signe de y (c) est différent de celui de y (a) alors on considère l'intervalle °a, c§ et on recommence. Mais revenons plus précisément sur la ligne 210. Si l'on a trouvé une solution dans l'intervalle, on placera cette solution comme borne inférieure du nouvel intervalle. Seulement voilà ; il y a un énorme problème : comme justement elle est la solution, à la ligne 150 y1 sera égal à 0. Il y aurait donc une anomalie à la ligne 190 pour les signes car 0 n'est pas signé. On triche donc un peu en augmentant de 0.2 la nouvelle borne inférieure pour seulement avoir son signe (y1) puis on le retire pour la suite du calcul. Il reste maintenant quelques points à éclaircir. Elle sert à prouver si le pointeur est passé par la ligne 210. S'il n'y est pas passé et que la boucle - ligne 170 - est terminée alors c'est qu'il n'y a pas de solution comme l'indique la ligne 190 après le next. Les lignes 90, 120, 130 sont un ensemble de tests évitant de mauvaises manipulations qui pourraient donner des résultats complètement faux. Faire très attention à la précision que vous demandez : si vous demandez une précision élevée avec un petit intervalle de recherche il est vivement conseillé de changer la ligne 170 en donnant un pas d'incrémentation de l'ordre de 0.1 ou 0.2. Le calcul sera évidemment plus long et la solution d'autant exacte. Comme application pratique la dichotomie peut servir à déterminer le point d'impact d'un projectile connaissant l'équation de son mouvement. (On prend alors la cible comme référence d'axes). G. Ponlicelli, Amstrad Magazine n°18 | ★ AMSTRAD CPC ★ DOWNLOAD ★ |
|
CPCrulez[Content Management System] v8.7-desktop/c
Page créée en 408 millisecondes et consultée 877 foisL'Amstrad CPC est une machine 8 bits à base d'un Z80 à 4MHz. Le premier de la gamme fut le CPC 464 en 1984, équipé d'un lecteur de cassettes intégré il se plaçait en concurrent du Commodore C64 beaucoup plus compliqué à utiliser et plus cher. Ce fut un réel succès et sorti cette même années le CPC 664 équipé d'un lecteur de disquettes trois pouces intégré. Sa vie fut de courte durée puisqu'en 1985 il fut remplacé par le CPC 6128 qui était plus compact, plus soigné et surtout qui avait 128Ko de RAM au lieu de 64Ko. |
|
|
