théorie des nombres, algorithme de Heron, calcul des rainces

Trouver la racine carrée d'un nombre n'est pas si facile ! Les Anciens (Héron d'Alexandrie – Livre I des Métriques) avaient déjà un truc assez performant, et, qui est encore utilisé aujourd'hui.

On trouve facilement deux nombres encadrant la racine cherchée. La moyenne de ces deux nombres est une bonne approximation de la racine. Une meilleure valeur est obtenue en recommençant l'opération…

Héron donne sa méthode à l'occasion du calcul de la racine de 720 = 12 x 5 x 4 x 2. Il calculait alors l'aire d'un triangle (7, 8, 9) avec la formule qu'il avait trouvée.

Voir Introduction avec exemple sur racine de 2

Devinette

Trouvez n minimum tel que .

Solution

Approche
Étape 1	Littéral	Exemple
Soit un nombre A:	A	A = 10 A = 3,16…
Si A est une valeur supérieure à la racine de A.	A < A	A = 10 (exemple) 3,16 < 10
Considérons la valeur du ratio	A / A	10 / 10 = 1
La valeur de ce ratio est inférieure à la racine de A	A / A < A	1 < 3,16
Bilan		1 < 3,16 < 10
Ayant trouvé deux valeurs encadrant la solution, il est tentant d'en prendre la moyenne, en pensant que la nouvelle valeur est une meilleure approximation..	r = 1/2 (A + A/A)	r = 1/2 (10 + 1) = 5 + 0, 5 = 5, 5
Étape 2
Reprenons le procédé avec cette nouvelle racine	r₁ = 1/2 (r + N/r)	r₁ = 1/2 (5,5 + 10/5,5) = 2,75 + 0,909 = 3,659
Etc. Nous allons converger vers la racine		r_k = 3,16 …

RACINE de DEUX – Méthode de Héron ou Algorithme de Babylone
Calcul de la racine carrée de A Méthode de calcul par itération: nouvelle valeur = f(ancienne valeur) En commençant par une valeur approchée (dite semence), imaginée a₀
Formule de Héron
Exemples Exemple de calcul avec racine de 2: 2 = 1, 414 213 562 373 095 048 … On a pris A = 2. Les fractions successives sont les réduites obtenus à partir de la fraction continue de la racine. Notez l'extrême rapidité de la convergence (10 décimales en 4 itérations). La quantité de décimales exactes est doublée à chaque itération (convergence quadratique) Exemple de calcul avec racine de 10: 10 = 3, 162 277 660 168 … On prend A = 10. Note personnelle Vers 1970, j'ai eu à programmer cette méthode en assembleur pour calculer une racine carrée intervenant dans une équation radar. Le calculateur spécialisé que nous avions conçu comportait une fonction addition et une fonction multiplication en dur (en circuits électroniques).

Voir Héron et ses contemporains / Héron = cas particulier de Newton

SEMENCE – Valeur de l'initialisation
On a vu que pour démarrer l'algorithme, il faut choisir une valeur initiale de A. C'est la semence a₀. Évidemment, plus cette valeur est proche de A plus la convergence sera rapide (on aura plus vite une grande précision). Dans les exemples précédents, on a simplement pris a₀ = A. Voyons quelle valeur simple peut-on utiliser: Convergence selon la valeur de la semence On donne l'écart en puissance de 10. Exemple avec A = 1,4 et 10 itérations, l'écart est 10 ^-2350
Choix de la semence La valeur la plus efficace et qui se calcule facilement est la racine du carré parfait le plus proche du nombre dont on veut calculer la racine. Exemple: pour calculer la racine de 98, on prendra 10 car 10² = 100. La troisième itération produira déjà 17 décimales. Illustration: Il s'agit du calcul de la racine de 1000. En abscisse, la quantité d'itérations et en ordonnées, la quantité de décimales exactes obtenues. La courbe en bas à droite correspond à a₀ = 1000. Les deux courbes en haut à gauche correspondent à a₀ 31 et 32. Évidemment, plus la valeur initiale se rapproche de la racine et plus la convergence est rapide. Avec 31 ou 32 et dix itérations la racine est connue avec plus de 2000 décimales. Reste qu'il faut faire les calculs!

RACINE des NOMBRES de 2 à 10
On calcule l'écart après 5 itérations: E = 10^-e	On donne e₅
On calcule le nombre d'itérations I_i pour obtenir un écart inférieur à 10^-i	On donne *I₁₀ , 2₁₀ , I₁₀₀*
a₀ = A/2 Conclusion Pour les petits nombres, même sans estimation de la racine (a = A/2), avec 5 itérations, on obtient au moins 10 décimales. Ce qui suffit pour bon nombre d'applications.

JUSTIFICATION DE LA MÉTHODE
Justification algébrique
Si a est proche de *A, h* est petit:	A = a² + h
C'est le début du développement d'un carré:	a² + h + … = (a + …)²
Que l'on peut écrire:	a² + h + h²/4a² = (a + h/2a)²
h est petit et, h² est petit au 2^e ordre.	a² + h (a + h/2a)²
Or, le premier membre est égal à A.	A (a + h/2a)²
Et, la racine:	A a + h/2a
Essayons de s'affranchir de h.
On trouve la relation cherchée.
Justification analytique	Voir Algorithme de Newton
Utilisation de la méthode de Newton pour la recherche des racines. Elle consiste à s'approcher de la courbe par marches d'escalier jusqu'à atteindre la racine sur l'axe des x (valeur de y pour x = 0). Illustration On dessine les courbes y = x² – A dont la valeur est A pour x = 0 et la courbe des valeurs calculées y' = r² – A.	(Échelle non respectée)
On donne les deux valeurs de y et y' au cours des itérations