Algorithmique et racine carrée en seconde, compléments publié le 03/03/2020 - mis à jour le 20/09/2023
Parcours sur les algorithmes d'approximation de racines carrées
Algorithme de Héron en devoir maison
Parallèlement à cette séquence qui s’est déroulée sur 3 séances de TP hebdomadaires, un devoir maison de recherche proposait une approche géométrique du calcul d’une racine carrée par la méthode de Héron.
Cette méthode déjà connue par les Babyloniens, est également attribuée au grec Héron d’Alexandrie (1er siècle). Il l’expose dans le premier tome de son ouvrage Metrica, ouvrage qui a été découvert en 1896.
Chez les mathématiciens grecs, extraire la racine carrée de $a$ revient à trouver un carré dont l’aire soit égale à $a$.
En prenant un rectangle de côté arbitraire $L_0=x$ et de même aire $a$, il est nécessaire que l’autre côté ait pour longueur $\ell_0=\dfrac{a}{x}$.
Pour le rendre moins rectangle, il suffit de considérer un nouveau rectangle dont les dimensions vérifient :
- la longueur est la moyenne arithmétique des dimensions du rectangle précédent ;
- pour que l’aire reste égale à $a$, on divise $a$ par cette nouvelle longueur pour trouver l’autre dimension du rectangle.
En réitérant infiniment le processus, le rectangle se transforme progressivement en un carré de même aire. Cette constatation est à la base de la méthode de Héron qui a été étudiée dans le devoir maison pour un nombre réel $a>1$.
L’implémentation attendue dans le devoir maison était la suivante (voir exécution en ligne) :
- def racine_heron(a, nb_decimales) :
- """cette fonction calcule un encadrement de la racine carrée de a avec le nombre de décimales spécifié"""
- longueur = a
- largeur = 1
- compteur = 0
- while abs(longueur - largeur) > 10**(-nb_decimales) :
- longueur = (longueur + largeur) / 2
- largeur = a / longueur
- compteur = compteur + 1
- return round(largeur,nb_decimales), round(longueur,nb_decimales),compteur
La méthode de Héron est un cas particulier de la méthode de Newton pour la détermination de solution d’une équation de la forme $f(x)=0$ avec $f(x)=x^2-a$. Sa vitesse de convergence est très rapide : la convergence de la suite sous-jacente est quadratique donc le nombre de décimales exactes double à chaque tour de boucle.
Par exemple, pour le calcul de $\sqrt{2}$, on atteint 11 décimales exactes dès la 4ème étape :
Lors de la remise des devoirs maison, un temps de synthèse en classe a été ménagé pour comparer la rapidité des algorithmes. Les compteurs installés dans chacune des fonctions ont ainsi permis de comparer le nombre de tours de boucles nécessaires pour atteindre une précision donnée avec chacun des algorithmes.
Paradoxalement, l’algorithme le plus rapide s’est révélé être celui qui s’appuyait sur une méthode géométrique, à savoir l’algorithme basé sur la méthode de Héron.
- >>> racine_balayage(2,7)
- (1.4142135, 1.4142136, 14142136)
- >>> racine_balayage_opt(2,7)
- (1.4142135, 1.4142136, 29)
- >>> racine_dicho(2,7)
- (1.4142135, 1.4142136, 24)
- >>> racine_heron(2,7)
- (1.4142136, 1.4142136, 4)
Ce devoir maison a été proposé aux élèves dans le but de leur faire découvrir une méthode géométrique de calcul de racine carrée.
- Vers l’algorithme de la potence
Cette archive contient tous les fichiers (fichiers tex, GeoGebra, scripts Python, illustrations,...) utilisés lors de la séquence.