Algorithme de calcul de la racine n-ième

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 ${\displaystyle x_{k}^{n}}$ à chaque étape nécessite d'utiliser un algorithme efficace d'élévation à une puissance.

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[2] :

${\displaystyle x_{k+1}={\frac {1}{2}}\left(x_{k}+{\frac {A}{x_{k}}}\right)}$.

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 ${\displaystyle f}$. Cette méthode repose elle aussi sur une suite définie par récurrence :

1. Soit ${\displaystyle f(x)=x^{n}-A}$ une fonction de ${\displaystyle \mathbb {R} _{+}^{*}}$ dans ${\displaystyle \mathbb {R} }$.
2. Choisir une valeur approchée initiale ${\displaystyle x_{0}}$.
3. Calculer ${\displaystyle 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 ${\displaystyle \mathbb {R} _{+}}$ et sa dérivée est donnée par :

${\displaystyle \forall x\in \mathbb {R} _{+}\quad f^{\prime }(x)=nx^{n-1}}$

D'où la relation de récurrence :

${\displaystyle {\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.

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

• Si n est pair :

L'équation ${\displaystyle x^{n}=A}$ n'admet aucune solution réelle. Il existe néanmoins des solutions complexes.

• Si n est impair :

Calculer ${\displaystyle {\sqrt[{n}]{A}}}$ revient à calculer ${\displaystyle -{\sqrt[{n}]{-A}}}$. Comme ${\displaystyle -A}$ est positif, l'algorithme décrit précédemment s'applique.

• 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).

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