methode de Newton.

Soit un nombre réel $p$, on cherche à trouver une méthode pour extraire la racine carrée de $p$ (notée $\sqrt{p}$) à la main, par la méthode de Newton, qui porte souvent le nom de méthode de Hénon pour ce cas (qui fût utilisée à Alexandrie). On trouve également le nom d'algorithme de Babylone.

On se donne une fonction $f$, $C^2$ sur un intervalle $\lbrack a,b \rbrack$, tel que $p$ soit une racine de $f$. Soit $z$ une approximation de $p$ tel que $f(z) \not= 0$ et que $\vert x-z\vert$ soit petit, alors on a, pour tout $x$ dans un bon intervalle,

$$f(x) = f(z) + (x-z) f'(z) + \frac{1}{2} (x-z)^2 f''(\zeta)$$

où $\zeta$ est entre $x$ et $z$.

On se place alors en $x=p$, donc $f(x)=f(p)=0$ et donc

$$0 \approx f(z) + (p-z) f'(z)$$

De là il vient que $p \approx z - \frac{f(z)}{f'(z)}$. Ce qui est une bonne approximation de $p$. On peut alors construire une suite définie par:

$$\left\{ \begin{array}{l} p_0 \text{, une aproximation de }p \ p_{n+1} = p_n - \frac{f(p_n)}{f'(p_n)}\ \end{array}\right.$$

Dans notre cas, on cherche la racine de $p$, donc on s'intéresse à la fonction $f(x) = x^2 - p$. On vérifie alors que: $f(\sqrt{p}) = 0$ et $f'(p) = 2x$. Donc $\frac{f(x)}{f'(x)} = (x^2-p) / (2x)$ De là, on se donne la suite définie par

$$\left\{ \begin{array}{l} p_0\ p_{n+1} = \frac{1}{2} (p_n + \frac{p}{p_n})\ \end{array}\right.$$

On montre aisement que cette suite converge vers $\sqrt{p}$. Cette méthode à une convergence quadratique, c'est à dire qu'à chaque itération on double le nombre de décimales valides.