L’algorithme d’Héron (du nom du mathématicien ayant conçu la méthode dès le 1er siècle après J.-C.) est une méthode d’extraction de racine carrée (c’est-à-dire qui permet d’obtenir une valeur approchée de la racine carrée). C’est en réalité un cas particulier de la méthode de Newton appliquée à la fonction \(f(x) = x^2 – a\). C’est un incontournable en prépa pour illustrer la convergence quadratique d’une suite. Dans cet article, nous allons d’abord revenir sur la définition de la suite d’Héron ainsi que sur son étude au travers de scripts Python.
Intuition et définition de la suite d’Héron
Supposons que l’on veuille calculer \(\sqrt{a}\) pour \(a>0\). L’idée d’Héron est de construire un rectangle d’aire \(a\).
On choisit une largeur initiale \(x_n\). Pour que l’aire soit égale à \(a\), la longueur doit être \(a/x_n\).
Si le rectangle n’est pas un carré, l’un des côtés est plus petit que \(\sqrt{a}\) et l’autre est plus grand. Pour se rapprocher du carré (où les côtés seraient égaux à \(\sqrt{a}\)), on définit la largeur suivante \(x_{n+1}\) comme la moyenne arithmétique des deux côtés actuels.
On obtient alors la suite récurrente suivante :
\[x_{n+1} = \frac{1}{2} \left( x_n + \frac{a}{x_n} \right)\]
Étude de la suite d’Héron
Soit \(a > 0\). On considère la fonction \(f(x) = \frac{1}{2}(x + \frac{a}{x})\) sur \(]0, +\infty[\).
Stabilité et variations
On trouve aisément que la dérivée est \(f'(x) = \frac{x^2 – a}{2x^2}\). De ce fait, l’étude du signe du nominateur montre que la fonction est décroissante sur \(]0, \sqrt{a}]\) et croissante sur \([\sqrt{a}, +\infty[\).
En réalisant son tableau de variation, on constate ainsi qu’elle admet un minimum en \(\sqrt{a}\) qui vaut \(f(\sqrt{a}) = \frac{1}{2}(\sqrt{a} + \frac{a}{\sqrt{a}})=\sqrt{a}\).
Ainsi, pour tout \(x_0 > 0\), on a \(x_n \geq \sqrt{a}\) pour tout \(n \geq 1\).
Convergence de la suite
L’intérêt de la suite d’Héron est surtout l’étude de sa convergence. Nous pourrons ainsi ici coder un algorithme Python pour déterminer sa potentielle limite. Voyons cependant quelques résultats mathématiques sur cela.
Pour \(n \geq 1\), on a \(x_{n+1} – x_n = \frac{a – x_n^2}{2x_n} \leq 0\).
La suite \((x_n)_{n \geq 1}\) est décroissante et minorée par \(\sqrt{a}\), elle converge donc vers une limite \(L\) d’après le théorème de la limite monotone.
Par passage à la limite dans la relation de récurrence, on trouve \(L = \frac{1}{2}(L + a/L)\), ce qui donne, en isolant l’inconnu, \(L = \sqrt{a}\).
Définissons donc un script qui permet d’obtenir une valeur approchée de \(\sqrt(a)\) en utilisant l’algorithme d’Héron. Ce script est assez abordable, je ne peux que te conseiller d’essayer de le construire toi-même.
Explication du script
On définit d’abord une fonction qui prend en compte la racine que l’on cherche à approcher et l’approximation voulue (qui a été ici fixée à \(1e^{-12}\)). Si \(a<0\), on ne peut naturellement pas chercher sa racine. Si \(a=0\), on connaît sa racine qui vaut 0. Donc, la question ne se pose que si \(a>0\).
On définit alors la variable \(x\) qui va contenir les valeurs approchées de la racine. On définit en effet « x_suivant » le terme suivant de la suite. Si l’écart entre les deux valeurs consécutives est trop grand, on continue le procédé et s’il est inférieur à notre \(\epsilon\) souhaité, alors on renvoie la valeur approchée de la racine.
Ainsi, comme on sait que la suite d’Héron converge vers \(\sqrt{a}\), alors on obtiendra bien une valeur approchée de \(\sqrt{a}\).
Vitesse de convergence quadratique
Et pourquoi pas un algorithme simple de dichotomie pour obtenir la valeur approchée souhaitée plutôt que la méthode d’Héron ?
En fait, l’algorithme d’Héron est très efficace, car la suite converge très rapidement vers la valeur approchée. En effet, pour calculer \(\sqrt{2}\) avec une erreur de \(10^{-15}\), la dichotomie demande environ 50 itérations, alors qu’Héron n’en demande que 6.
L’erreur \(\epsilon_n = x_n – \sqrt{a}\) vérifie la relation suivante :
\[x_{n+1} – \sqrt{a} = \frac{(x_n – \sqrt{a})^2}{2x_n}\]
Ceci montre que l’erreur au rang \(n+1\) est proportionnelle au carré de l’erreur au rang \(n\). Le nombre de décimales exactes double à chaque itération.
Construisons donc un algorithme qui permet de connaître l’erreur d’approximation commise en fonction du nombre d’itérations. Naturellement, plus le nombre d’itérations est grand, plus la précision est bonne.
Explication du script
On réalise ici le même algorithme que précédemment mais avec le « print » dans la boucle, on calcule l’approximation de la valeur de la racine (à 15 décimales afin d’être précis) et l’erreur d’approximation commise. Cela permet donc de suivre l’amélioration de la précision de la boucle à chaque itération.
Une approche plus complète serait de construire un script qui nous permette d’obtenir la vitesse de convergence. Voyons une proposition de code avec ce qui suit :
Explication du script
On réalise ici le même algorithme, mais on conserve les valeurs approchées de chaque itération en les implémentant dans un vecteur (le vecteur « x_vals » grâce à la fonction « append » qui permet d’accoler une nouvelle valeur à un vecteur déjà existant). On affiche alors le graphique avec en abscisse le nombre d’itérations et la valeur approchée en ordonnée.
On obtient alors le graphique suivant pour \(a=10\) :
On remarque alors que l’approximation est très satisfaisante dès \(n=4\), car la courbe se stabilise très rapidement à partir de ce niveau. C’est en cela que cette suite (et, par là même, cet algorithme) est particulièrement puissante : elle permet de fournir des valeurs très bonnes avec un petit nombre d’itérations !
Conclusion
En définitive, l’algorithme d’Héron est fondamental pour comprendre les problématiques de vitesse de convergence. De plus, en ce qu’elle se base sur une suite, un exercice d’écrit pourrait facilement demander à l’étudiant de l’étudier et, par la suite, de définir un algorithme du même type que ceux que nous avons justement vus plus haut. Il n’y a donc plus qu’à croiser les doigts pour que cette notion tombe aux concours !
Tu peux retrouver ici le méga-répertoire qui contient toutes les annales de concours et les corrigés. Tu peux également accéder ici à toutes nos autres ressources mathématiques !
