Algorithme de calcul de la racine n-ième

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 le réel positif solution de l'équation

xn = A

(Pour tout entier naturel non nul n, il existe n nombres complexes distincts solutions de cette équation si A > 0, mais une seule est positive et réelle.)

Il existe un algorithme de calcul d'une valeur approchée de la racine n-ième dont la convergence est très rapide:

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

Un cas particulier connu de cet algorithme est la méthode de Héron. 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)

Il existe plusieurs variantes possibles de cet algorithme. Un mouture le considère comme un cas particulier de la méthode de Newton (également appelée méthode de Newton-Raphson) qui permet de trouver des zéros d'une fonction f en partant d'une valeur approchée initiale. Bien que la méthode de Newton soit itérative, ce qui signifie qu'elle approche la solution par une suite de valeurs approchées de plus en plus précises, elle converge très rapidement. La vitesse de convergence est quadratique, ce qui signifie grossièrement que le nombre de chiffres significatifs corrects double à chaque itération asymptotiquement. Pour cette raison, cet algorithme est souvent employé dans des ordinateurs comme une méthode très rapide pour calculer les racines carrées.

Pour des grandes valeurs de n, l'algorithme de la racine n-ième est légèrement moins efficace puisqu'il exige le calcul de x_k^n à chaque étape, mais peut être efficacement mis en œuvre avec un bon algorithme d'élévation à une puissance.

Lien avec la méthode de Newton

La méthode de Newton est une méthode permettant de déterminer une valeur approchée d'un zéro d'une fonction f. Le schéma général de la méthode est le suivant:

  1. Considérer une valeur approchée de départ x0
  2. Poser x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)}
  3. Recommencer à l'étape 2 jusqu'à la précision voulue.

Le problème de la recherche d'une racine n-ième peut se ramener à celui de la recherche d'un zéro de la fonction f définie par

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

La fonction f est dérivable sur \mathbb{R}_+ et la dérivée est donnée par:

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

D'où la relation récurrente:

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]

qui mène à l'algorithme général de recherche d'une racine n-ième.


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Algorithme de calcul de la racine n-ième de Wikipédia en français (auteurs)

Игры ⚽ Нужно решить контрольную?

Regardez d'autres dictionnaires:

  • Algorithme De Calcul De La Racine N-ième — La racine n ième d un nombre réel positif A, notée , est le réel positif solution de l équation xn = A (Pour tout entier naturel non nul n, il existe n nombres complexes distincts solutions de cette équation si A > 0, mais une seule est… …   Wikipédia en Français

  • Algorithme de calcul de la racine n-ieme — Algorithme de calcul de la racine n ième La racine n ième d un nombre réel positif A, notée , est le réel positif solution de l équation xn = A (Pour tout entier naturel non nul n, il existe n nombres complexes distincts solutions de cette… …   Wikipédia en Français

  • Calcul de la racine n-ieme d'un nombre — Calcul de la racine n ième d un nombre La racine n ième (ou, rarement, racine énième) d un nombre réel positif A, se notant , est la solution positive de l équation xn = A avec . Pour un entier n, il y a n solutions complexes distinctes pour… …   Wikipédia en Français

  • Calcul de la racine n-ième d'un nombre — La racine n ième (ou, rarement, racine énième) d un nombre réel positif A, se notant , est la solution positive de l équation xn = A avec . Pour un entier n, il y a n solutions complexes distinctes pour cette équation si A > 0, mais une seule… …   Wikipédia en Français

  • Calcul De La Racine Énième D'un Nombre — Calcul de la racine n ième d un nombre La racine n ième (ou, rarement, racine énième) d un nombre réel positif A, se notant , est la solution positive de l équation xn = A avec . Pour un entier n, il y a n solutions complexes distinctes pour… …   Wikipédia en Français

  • Calcul de la racine cubique d'un nombre — Calcul de la racine n ième d un nombre La racine n ième (ou, rarement, racine énième) d un nombre réel positif A, se notant , est la solution positive de l équation xn = A avec . Pour un entier n, il y a n solutions complexes distinctes pour… …   Wikipédia en Français

  • Calcul de la racine enieme d'un nombre — Calcul de la racine n ième d un nombre La racine n ième (ou, rarement, racine énième) d un nombre réel positif A, se notant , est la solution positive de l équation xn = A avec . Pour un entier n, il y a n solutions complexes distinctes pour… …   Wikipédia en Français

  • Calcul de la racine nième d'un nombre — Calcul de la racine n ième d un nombre La racine n ième (ou, rarement, racine énième) d un nombre réel positif A, se notant , est la solution positive de l équation xn = A avec . Pour un entier n, il y a n solutions complexes distinctes pour… …   Wikipédia en Français

  • Calcul de la racine quatrième d'un nombre — Calcul de la racine n ième d un nombre La racine n ième (ou, rarement, racine énième) d un nombre réel positif A, se notant , est la solution positive de l équation xn = A avec . Pour un entier n, il y a n solutions complexes distinctes pour… …   Wikipédia en Français

  • Calcul de la racine énième d'un nombre — Calcul de la racine n ième d un nombre La racine n ième (ou, rarement, racine énième) d un nombre réel positif A, se notant , est la solution positive de l équation xn = A avec . Pour un entier n, il y a n solutions complexes distinctes pour… …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”