Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Extraction de racine carrée
Résumé
En algorithmique et en analyse numérique, l'extraction de racine carrée est le processus qui consiste, étant donné un nombre, à en calculer la racine carrée. Il existe de nombreuses méthodes pour effectuer ce calcul. C'est un cas particulier de la recherche de calcul de la racine n-ième.
La racine carrée d'un nombre pouvant être un nombre irrationnel, l'extraction de racine carrée est en général approchée.
L'extraction de la racine carrée d'un nombre a est identique à la résolution de l'équation x - a = 0. Les méthodes générales de résolution d'équations polynomiales, et plus généralement les algorithmes de recherche d'un zéro d'une fonction s'appliquent donc. On utilise les mêmes outils pour mesurer les performances des méthodes.
Lorsque l'on ne donne pas de précision supplémentaire, l'extraction de racine carrée se fait dans l'ensemble des nombres réels. On peut cependant s'intéresser à d'autres ensembles de nombres tels que les nombres complexes ou encore les anneaux tels que Z/nZ.
La méthode de Héron est une méthode historique développée par les Babyloniens. En termes plus modernes, c'est un cas particulier de la méthode de Newton.
Pour déterminer la racine carrée du nombre (positif) a, il convient dès lors de considérer la suite définie par récurrence de la façon suivante :
de premier terme x > 0 choisi si possible « assez proche » de , en général la partie entière de .
La vitesse de convergence des approximations successives vers la valeur exacte est quadratique.
On trouve dans un manuscrit indien, dit manuscrit de Bakshali, datant peut-être du , une correction différente de la méthode de Héron, la nouvelle valeur approchée étant . Elle est équivalente à appliquer deux fois de suite la méthode de Héron. L'itération de cette dernière méthode donne une vitesse de convergence bi-quadratique :
Considérons les suites u et v définies par :
est la moyenne harmonique de u et v,
est la moyenne arithmétique de u et v.
Les suites u et v sont adjacentes, et convergent vers la même limite : . L'erreur est majorée par la différence v - u.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.