Méthode de Héron pour extraire les racines carrées

Extraction d'une racine carrée entière d'un nombre entier.

La méthode de Héron est la suivante:

1. Soit A,  le nombre dont on cherche la racine carrée entière.
2. On choisit un nombre entier quelconque p proche de la racine carrée du nombre donné.
3. On effectue la division entière de A par p, on trouve le nombre q.
4. Si p = q, alors p est la racine carrée entière exacte ou approchée par défaut de A, et on a fini.
5. Si p = q ± 1, alors A n'est pas un carré exact, et le plus petit des deux nombres fournit la partie entière de la racine carrée de A, et on a fini.
6. Sinon on prend pour nouvelle valeur de p, la demi-somme entière des nombres p et q.
7. On recommence à partir du point 3.

Ex. 1: Soit à calculer la racine carrée entière de 4.214.751.

•  Soit 2.000, une valeur approchée de la racine carrée.
•  On effectue la division entière 4.214.751 / 2.000, on trouve 2.108.
•  On calcule la demi-somme entière de 2.000 et 2.108, soit 2.054.
•  4.214.751 / 2.054 = 2.051.
•  (2.054 + 2.051) / 2 = 2.052.
•  4.214.751 / 2.052 = 2.053.
•  Mais on a 2.053 = 2.052 + 1, donc 4.214.751 n'est pas un carré exact, et sa racine carrée entière approchée est 2.052.

Ex. 2: Trouver la racine carrée entière de 14.326.225.

•  Soit 4.000, une valeur approchée de la racine carrée.
•  14.326.225 / 4.000 = 3.581.
•  (4.000 + 3.581) / 2 = 3.790.
•  14.326.225 / 3.790 = 3.780.
•  (3.790 + 3.780) / 2 = 3.785.
•  14.326.225 / 3.785 = 3.785.
•  3.785 est la racine carrée entière de 14.326.225 et comme 3.785² = 14.326.225, on a trouvé la racine carrée exacte.

Application de la méthode de Héron pour trouver une racine carrée approchée d'un nombre décimal quelconque.

Dans ce cas il s'agit plus exactement de la méthode de Newton-Raphson.

Cette méthode calcule la racine carrée par approximations successives à partir d'une valeur quelconque non nulle x₀ en utilisant la formule de récurrence :

1. Soit A le nombre dont on cherche la racine carrée à moins de ε près.
2. On choisit un nombre décimal quelconque p proche de la racine carrée du nombre donné.
3. On effectue la division de A par p, on trouve le nombre q.
4. Si | p - q | ≤ ε, alors p et q sont des valeurs approchées à moins de ε de la racine carrée de A. Le plus petit des deux nombres est la valeur approchée par défaut, le plus grand, la valeur approchée par excès. La valeur absolue de la différence des deux nombres donnera l'erreur réelle maximale.
5. Sinon on prend pour nouvelle valeur de p, la demi-somme des nombres p et q.
6. On recommence à partir du point 3.

N.B.: Les divisions peuvent se faire théoriquement à n'importe qu'elle précision, mais de préférence il faut un nombre de décimales d tel que 10^-d < ε pour que l'algorithme converge (càd vérifie la relation 4).
Si d n'est pas assez grand (10^-d ≥ ε), on arrête l'algorithme quand les valeurs de p et de q deviennent identiques ou commencent à osciller indéfiniment autour d'une certaine valeur. L'erreur sera de 10^-d et non de ε.

Ex. : Trouver la racine carrée de 1000 à moins de 0.01 près.

•  Soit 30, une valeur approchée de la racine carrée.
•  On effectuera les divisions jusqu'à 4 décimales pour être sûr de converger (10^-4 = 0,0001 < 0,01).
•  On calcule 1000 / 30, soit 33,3333. On vérifie l'erreur :| 30 - 33,3333 | = 3,3333 > 0.01, trop grand, on continue
•  On calcule (30 + 33,3333) / 2, on trouve 31,6666.
•  1000 / 31,6666 = 31,5790. | 31,6666 - 31,5790 | = 0.0438 > 0.01, on continue
•  (31,6666 + 31,5790) / 2 = 31,6228.
•  1000 / 31,6228 = 31,6227. | 31.6228 - 31.6227 | = 0.0001 < 0.01, on a fini, la racine carrée par défaut de 1000 à 0.01 près est 31,6227, la valeur par excès est 31,6228. L'erreur réelle maximale est donc de 0,0001 ce qui indique que 31,6227 est exact jusqu'à la quatrième décimale.

 
Dernière mise à jour, le 29 Janvier 2007