Algorithme de calcul de la racine n-ième

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.

Le principal 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.

C'est une généralisation de l'extraction de racine carrée.

Vitesse de convergence

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

La méthode de Héron pour le calcul d'une racine carrée est un cas particulier de l'algorithme de calcul de la racine n-ième. Il suffit de remplacer n par 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

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} _{+}\quad f^{\prime }(x)=nx^{n-1}$

D'où la relation de récurrence :

${\begin{aligned}x_{k+1}&=x_{k}-{\frac {f(x_{k})}{f'(x_{k})}}\\&=x_{k}-{\frac {x_{k}^{n}-A}{nx_{k}^{n-1}}}\\&=x_{k}-{\frac {x_{k}}{n}}+{\frac {A}{nx_{k}^{n-1}}}\\&={\frac {1}{n}}\left[{(n-1)x_{k}+{\frac {A}{x_{k}^{n-1}}}}\right].\end{aligned}}$

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

Nombres négatifs

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

Exponentielle

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 $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

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

É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.

Notes et références

• Cet article est partiellement ou en totalité issu de l'article intitulé « Calcul de la racine n-ième d'un nombre » (voir la liste des auteurs).

Article connexe

Algorithme de recherche d'un zéro d'une fonction