Dans cet article on va résoudre l'équation x3=50 par dichotomie et par l'algorithme de Raphson, en mode "normal" et en mode "multiprécision". Pour ce dernier cas, on utilisera la bibliothèque Big.js. Mais d'abord on va voir comment la notion de dichotomie peut être introduite en dehors du contexte des résolutions d'équations, avec un jeu qui peut être vu en seconde comme activité préliminaire:
Chaque matin, un animateur radio annonce un montant aléatoire dont on sait uniquement qu'il est inférieur ou égal à 100 €, et donné par un nombre entier. Puis il téléphone à un auditeur au hasard et lui demande s'il connaît le montant de la "valoche". Mais l'auditeur n'était à ce moment précis, pas en train d'écouter la radio. L'animateur lui propose de deviner en quelques essais, et lui dit si ses tentatives tombent en dessous ou au dessus du montant réel. En combien de tentatives maximum peut-on être sûr de deviner le montant ?
L'algorithme est intéressant parce que
Cette version également, est intéressante, puisqu'en plus des aspects précédents, elle incite assez naturellement à chercher quels sont les nombres qui nécessitent beaucoup d'essais avec la dichotomie. Et permet d'explorer les nombres maximaux autres que 100.
Pour résoudre l'équation x3=50, on va la réécrire x3-50=0, et déterminer deux nombres a et b tels que a3-50<0 et b3-50>0. La dichotomie permet de rapprocher a et b jusqu'à ce qu'ils soient tous deux proches de la solution de l'équation. En renommant ƒ la fonction x3-50, on économise du code et on peut facilement modifier le script pour résoudre d'autres équations (attention toutefois au cas où ƒ est décroissante, il y a plus de choses à changer).
Attention à ne pas aller au-delà de 10-15, la précision de la machine ne permettant pas de distinguer a et b dans ce cas. Pour faire mieux il faut utiliser une bibliothèque de précision comme Big.js:
On voit que ça prend un certain temps pour trouver que la racine cubique de 50 vaut environ 3,6840314986403866057798228335798072219172581174381826692564614945772359755087770427815054848656019769...
Le principe est que la résolution de l'équation ƒ(x)=0 revient à résoudre x-ƒ(x)/ƒ'(x)=x puisque ces équations sont équivalentes. Or pour résoudre une équation du type g(x)=x, on peut simplement itérer g: Le théorème des accroissements finis permet de prouver que, plus la dérivée de g est petite, et plus la convergence est rapide. Or, en la solution de l'équation g(x)=x, la dérivée de g est nulle, on peut difficilement faire plus petit...
Le problème avec la méthode de Raphson est qu'elle nécessite la dérivée de ƒ: En calculant cette dérivée par un algorithme, on court le double risque de rallonger le temps de calcul, et de perdre en précision. On a donc tout intérêt à calculer la dérivée par calcul formel avant de rédiger l'algorithme. Dans le cas présent, ƒ'(x)=3x² donc g(x)=x-(x3-50)/(3x²)=2x/3+50/(3x²). En fait il est possible de décomposer la suite en deux suites adjacentes. On va utiliser la suite des itérés de x-ƒ(x)/ƒ'(x) pour calculer rapidement la racine cubique de 50: On choisit une valeur initiale quelconque (par exemple u0=1) et on pose un+1=2un/3+50/(3un2):
La convergence est assez rapide pour permettre d'explorer empiriquement (déterminer par exemple qu'il faut boucler 11 fois pour avoir 15 décimales correctes). L'avantage des suites adjacentes est qu'on a une condition de sortie de boucle (comme dans la dichotomie ci-dessus).
On recommence mais en version Big.js:
On boucle 11 fois, on affiche la valeur de u trouvée, puis on calcule g(u)-u, et on affiche le résultat: On constate qu'il n'est pas tout-à-fait nul.
Alors on essaye avec une autre valeur que 11, et (rapidement si on opère par dichotomie comme dans la première partie !) on trouve que 12
tours de boucle suffisent pour avoir la racine cubique à 10-99 près. En commençant par Big.DP = 1000, il faut moins d'une
minute de dichotomie sur le nombre de boucles pour déterminer que 16 tours de boucle donnent la racine cubique de 50 à 1000 décimales près: