Algorithme de calcul de la racine n-ième

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

La racine n-ième d'un nombre réel positif A, notée \sqrt[n]{A}, est la solution réelle positive de l'équation x^n=A avec n \in \mathbb{N}^*. Pour tout entier naturel non nul n, il existe n racines complexes distinctes pour cette équation si A>0. Une seule d'entre elles est réelle et positive.

L'algorithme de calcul de la racine n-ième utilise une suite définie par récurrence pour trouver une valeur approchée de cette racine réelle :

  1. Choisir une valeur approchée initiale x_0.
  2. Calculer x_{k+1} = \frac{1}{n} \left[{(n-1)x_k +\frac{A}{x_k^{n-1}}}\right].
  3. Recommencer à l'étape 2 jusqu'à atteindre la précision voulue.

Vitesse de convergence[modifier | modifier le code]

Cet algorithme est itératif, ce qui signifie qu'il approche la solution par une suite de valeurs approchées de plus en plus précises. Il converge très rapidement. Sa vitesse de convergence est quadratique, ce qui signifie que le nombre de chiffres significatifs corrects double à chaque itération asymptotiquement. Pour cette raison, cet algorithme est souvent employé par les ordinateurs pour calculer les racines carrées.

Pour de grandes valeurs de n, le calcul de x_k^n à chaque étape nécessite d'utiliser un algorithme efficace d'élévation à une puissance.

Lien avec la méthode de Héron[modifier | modifier le code]

La méthode de Héron est un cas particulier de l'algorithme de calcul de la racine n-ième. Il suffit de remplacer n=2 dans la formule récurrente à la deuxième étape :

x_{k+1} = \frac{1}{2}\left(x_k + \frac{A}{x_k}\right)

Lien avec la méthode de Newton[modifier | modifier le code]

L'algorithme de calcul de la racine n-ième peut être considéré comme un cas particulier de la méthode de Newton, qui permet de trouver une approximation précise d'un zéro d'une fonction f. Cette méthode repose elle aussi sur une suite définie par récurrence :

  1. Soit f(x) = x^n - A une fonction de \mathbb{R}^*_+ dans \mathbb{R}.
  2. Choisir une valeur approchée initiale x_0.
  3. Calculer x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)}.
  4. Recommencer à l'étape 3 jusqu'à atteindre la précision voulue.

Le calcul de la racine n-ième peut alors se ramener au calcul d'un zéro de la fonction f. Cette fonction est dérivable sur \mathbb{R}_+ et sa dérivée est donnée par :

\forall x\in\mathbb{R}_+, f^\prime(x) = n x^{n-1}

D'où la relation de récurrence :

x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)}
 = x_k - \frac{x_k^n - A}{n x_k^{n-1}}
 = x_k - \frac{x_k}{n}+\frac{A}{n x_k^{n-1}}
 = \frac{1}{n} \left[{(n-1)x_k +\frac{A}{x_k^{n-1}}}\right]

On retrouve la relation de récurrence de l'algorithme de calcul de la racine n-ième.

Nombres négatifs[modifier | modifier le code]

Si A est négatif, on distingue deux cas :

  • Si n est pair :
L'équation x^n=A n'admet aucune solution réelle. Il existe néanmoins des solutions complexes.
  • Si n est impair :
Calculer \sqrt[n]{A} revient à calculer -\sqrt[n]{-A}. Comme -A est positif, l'algorithme décrit précédemment s'applique.

Autres méthodes[modifier | modifier le code]

Exponentielle[modifier | modifier le code]

La racine n-ième d'un nombre réel positif A peut aussi s'exprimer sous la forme :

\sqrt[n]{A} = A^{1/n} = \exp \left (\frac{1}{n} \ln A \right ).

Ceci découle de la relation exprimant un nombre strictement positif élevé à une puissance quelconque :

si a > 0 et \quad b \in \mathbb R, alors a^b = \exp \left (b. \ln a \right ).

On peut donc calculer une valeur approchée d'une racine n-ième en utilisant le développement limité d'une fonction exponentielle.

Algorithme de la potence[modifier | modifier le code]

Article détaillé : Algorithme de la potence.

L'algorithme de la potence permet de calculer une approximation d'une racine n-ième avec la précision désirée. Sa vitesse de convergence est plus lente que l'algorithme de calcul de la racine n-ième.

Règle à calcul[modifier | modifier le code]

Article détaillé : règle à calcul.
Échelles d'une règle à calcul

Les règles à calcul comprennent généralement des échelles à une, deux et trois décades permettant de déterminer directement les racines carrées et cubiques d'un nombre a. Pour la racine carrée, il s'agit du nombre sur l'échelle à une décade (A) situé face au nombre a sur celle à deux décades (D) ; pour la racine cubique, il s'agit du nombre sur l'échelle à une décade (A) en vis-à-vis du nombre a sur celle à trois décades (T).

Pour les autres racines, on peut utiliser la formule :

\sqrt[n]{a} = \exp \left( n^{-1}\log a \right).

Dans ce cas les étapes de calcul de la racine énième d d'un nombre a sont alors les suivantes :

  1. Détermination du logarithme b = log a (utilise les échelles A et L);
  2. Détermination du quotient c = b/n (utilise A et B) ;
  3. Détermination de l'exponentielle d = exp c (utilise L et A).

La précision est de l'ordre de 0,1 % à 1 % selon le type de règle et le soin du manipulateur.

Sources[modifier | modifier le code]

Liens internes[modifier | modifier le code]