Algorithmique et racine carrée en seconde, compléments publié le 03/03/2020  - mis à jour le 19/03/2020

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$.

Animation illustrant la recherche d'une racine carrée par l'algorithme de Héron

Choisissez un nombre dont vous voulez la racine carrée, réglez le nombre d’étapes et appuyez sur la touche "étape suivante" jusqu’à atteindre le nombre d’étapes choisi (au-delà de 5 étapes, les limites de GeoGebra sont atteintes)

L’implémentation attendue dans le devoir maison était la suivante (voir exécution en ligne) :

Bloc de code informatique : voir l'article sur le site.
  
  1. def racine_heron(a, nb_decimales) :
  2.     """cette fonction calcule un encadrement de la racine carrée de a avec le nombre de décimales spécifié"""
  3.     longueur = a
  4.     largeur = 1
  5.     compteur = 0
  6.     while abs(longueur - largeur) > 10**(-nb_decimales) :
  7.         longueur = (longueur + largeur) / 2
  8.         largeur = a / longueur
  9.         compteur = compteur + 1
  10.     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 :

Bloc de code informatique : voir l'article sur le site.
  
  1. >>> racine_heron(2,11)
  2. (1.41421356237, 1.41421356237, 4)

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.

Bloc de code informatique : voir l'article sur le site.
  
  1. >>> racine_balayage(2,7)
  2. (1.4142135, 1.4142136, 14142136)
  3. >>> racine_balayage_opt(2,7)
  4. (1.4142135, 1.4142136, 29)
  5. >>> racine_dicho(2,7)
  6. (1.4142135, 1.4142136, 24)
  7. >>> racine_heron(2,7)
  8. (1.4142136, 1.4142136, 4)
Enoncé du devoir maison sur l'algorithme de Héron (PDF de 152.1 ko)

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

Document joint

Cette archive contient tous les fichiers (fichiers tex, GeoGebra, scripts Python, illustrations,...) utilisés lors de la séquence.