La méthode de Newton.

La méthode de Newton est une méthode de résolution de l'équation f (x) = 0, attention à la différence avec le théorème du point fixe qui permet de résoudre numériquement f (x) = x. Si x₀ est proche de la racine r on peut faire un développement de Taylor à l'ordre 1 de la fonction f en x₀ :

f (x) = f (x₀) + (x - x₀)f'(x₀) + O((x - x₀)²)

Pour trouver une valeur approchée de r, on ne garde que la partie linéaire du développement, on résout :

f (r) = 0 $$\approx$$ f (x₀) + (r - x₀)f'(x₀)

donc (si f'(x₀) $\neq$ 0) :

r $$\approx$$ x₀ - $${\frac{{f(x_0)}}{{f'(x_0)}}}$$

Graphiquement, cela revient à tracer la tangente à la courbe représentative de f et à chercher où elle coupe l'axe des x. On considère donc la suite récurrente définie par une valeur u₀ proche de la racine et par la relation :

u_n+1 = u_n - $${\frac{{f(u_n)}}{{f'(u_n)}}}$$

Il y a deux théorèmes importants, l'un d'eux prouve que si u₀ est ``assez proche'' de r alors la suite u<sub>n</sub> converge vers r, malheureusement il est difficile de savoir en pratique si on est ``assez proche'' de u₀ pour que ce théorème s'applique. Le second théorème donne un critère pratique facile à vérifier qui assure la convergence, il utilise les propriétés de convexité de la fonction.

Théorème 2   Soit f une fonction de classe C² (2 fois continument dérivable) sur un intervalle fermé I. Soit r une racine simple de f située à l'intérieur de I (telle que f (r) = 0 et f'(r) $\neq$ 0). Alors il existe $\varepsilon$ > 0 tel que la suite définie par

u_n+1 = u_n - $${\frac{{f(u_n)}}{{f'(u_n)}}}$$,    | u₀ - r| $$\leq$$ $$\varepsilon$$

converge vers r.

Si on a | f''| $\leq$ M et | 1/f'| $\leq$ m sur un intervalle [r - $\eta$, r + $\eta$] contenu dans I, alors on peut prendre tout réel $\varepsilon$ > 0 tel que $\varepsilon$ < 2/(mM) et $\varepsilon$ $\leq$ $\eta$.

Démonstration : on a

u_n+1 - r = u_n - r - $${\frac{{f(u_n)}}{{f'(u_n)}}}$$ = $${\frac{{(u_n-r)f'(u_n)-f(u_n)}}{{f'(u_n)}}}$$

En appliquant un développement de Taylor de f en u_n à l'ordre 2, on obtient pour un réel $\theta$ situé entre r et u_n :

0 = f (r) = f (u_n) + (r - u_n)f'(u_n) + (r - u_n)²$${\frac{{f'{'}(\theta)}}{{2}}}$$

donc :

(u_n - r)f'(u_n) - f (u_n) = (u_n - r)²$${\frac{{f'{'}(\theta)}}{{2}}}$$

d'où :

| u_n+1 - r| $$\leq$$ | u_n - r|²$${\frac{{1}}{{\vert f'(u_n)\vert}}}$$$${\frac{{\vert f'{'}(\theta)\vert}}{{2}}}$$

On commence par choisir un intervalle [r - $\varepsilon$, r + $\varepsilon$] contenant strictement r et tel que | f''| < M et | 1/f'| < m sur [r - $\varepsilon$, r + $\varepsilon$] (c'est toujours possible car f'' et 1/f' sont continues au voisinage de r puisque f'(r) $\neq$ 0). Si u_n est dans cet intervalle, alors $\theta$ aussi donc

| u_n+1 - r| $$\leq$$ | u_n - r|²$${\frac{{Mm}}{{2}}}$$ $$\leq$$ $${\frac{{\vert u_n-r\vert Mm}}{{2}}}$$| u_n - r|,

On a | u_n - r| $\leq$ $\varepsilon$, on diminue si nécessaire $\varepsilon$ pour avoir $\varepsilon$ < 2/(Mm), on a alors :

| u_n+1 - r| $$\leq$$ k| u_n - r|,    k = $${\frac{{\varepsilon Mm}}{{2}}}$$ < 1

donc d'une part u_n+1 est encore dans l'intervalle [r - $\varepsilon$, r + $\varepsilon$] ce qui permettra de refaire le même raisonnement au rang suivant, et d'autre part on a une convergence au moins géométrique vers r (en fait bien meilleure lorsqu'on est proche de r grace au carré dans | u_n - r|²).

Remarque : ce théorème se généralise sur $\mathbb {C}$ et même sur $\mathbb {R}$ⁿ.

Exemple : pour calculer $\sqrt{{2}}$, on écrit l'équation x² - 2 = 0 qui a $\sqrt{{2}}$ comme racine simple sur I = [1/2, 2], on obtient la suite récurrente

u_n+1 = u_n - $${\frac{{u_n^2-2}}{{2u_n}}}$$

Si on prend $\eta$ = 1/2, on a f' = 2x et f'' = 2 donc on peut prendre M = 2 et m = 1 car | 1/f'| $\leq$ 1 sur [$\sqrt{{2}}$ -1/2,$\sqrt{{2}}$ + 1/2]. On a 2/(mM) = 1, on peut donc prendre $\varepsilon$ = 1/2, la suite convergera pour tout u₀ $\in$ [$\sqrt{{2}}$ -1/2,$\sqrt{{2}}$ + 1/2].

Plus générallement, on peut calculer une racine k-ième d'un réel a en résolvant f (x) = x^k - a par la méthode de Newton.

L'inconvénient de ce théorème est qu'il est difficile de savoir si la valeur de départ qu'on a choisie se trouve suffisamment près d'une racine pour que la suite converge. Pour illustrer le phénomène, on peut par exemple colorer les points du plan complexe en n + 1 couleurs selon que la suite définie par la méthode de Newton converge vers l'une des n racines d'un polynôme de degré n fixé au bout de par exemple 50 itérations (la n + 1-ième couleur servant aux origines de suite qui ne semblent pas converger).

Passons maintenant à un critère très utile en pratique :

Définition 4 (convexité)  
Une fonction f continument dérivable sur un intervalle I de $\mathbb {R}$ est dite convexe si son graphe est au-dessus de la tangente en tout point de I.

Il existe un critère simple permettant de savoir si une fonction de classe C² est convexe :

Théorème 3   Si f est C² et f'' $\geq$ 0 sur I alors f est convexe.

Démonstration :
L'équation de la tangente au graphe en x₀ est

y = f (x₀) + f'(x₀)(x - x₀)

Soit

g(x) = f (x) - (f (x₀) + f'(x₀)(x - x₀))

on a :

g(x₀) = 0,    g'(x) = f'(x) - f'(x₀),    g'(x₀) = 0,    g'' = f'' $$\geq$$ 0

donc g' est croissante, comme g'(x₀) = 0, g' est négative pour x < x₀ et positive pour x > x₀, donc g est décroissante pour x < x₀ et croissante pour x > x₀. On conclut alors que g $\geq$ 0 puisque g(x₀) = 0. Donc f est bien au-dessus de sa tangente.

On arrive au deuxième théorème sur la méthode de Newton

Théorème 4   Si f (r) = 0, f'(r) > 0 et si f'' $\geq$ 0 sur [r, b] alors pour tout u₀ $\in$ [r, b] la suite de la méthode de Newton

u_n+1 = u_n - $${\frac{{f(u_n)}}{{f'(u_n)}}}$$,

est définie, décroissante, minorée par r et converge vers r. De plus

0 $$\leq$$ u_n - r $$\leq$$ $${\frac{{f(u_n)}}{{f'(r)}}}$$

Démonstration :
On a f'' $\geq$ 0 donc si f'(r) > 0 alors f' > 0 sur [r, b], f est donc strictement croissante sur [r, b] on en déduit que f > 0 sur ]r, b] donc u_n+1 $\leq$ u_n. Comme la courbe représentative de f est au-dessus de la tangente, on a u_n+1 $\geq$ r (car u_n+1 est l'abscisse du point d'intersection de la tangente avec l'axe des x). La suite u_n est donc décroissante minorée par r, donc convergente vers une limite l $\geq$ r. À la limite, on a

l = l - $${\frac{{f(l)}}{{f'(l)}}}$$ $$\Rightarrow$$ f (l )= 0

donc l = r car f > 0 sur ]r, b].

Comme (u_n) est décroissante, on a bien 0 $\leq$ u_n - r, pour montrer l'autre inégalité, on applique le théorème des accroissements finis, il existe $\theta$ $\in$ [r, u_n] tel que

f (u_n) - f (r) = (u_n - r)f'($$\theta$$)

comme f (r) = 0, on a

u_n - r = $${\frac{{f(u_n)}}{{f'(\theta)}}}$$

et la deuxième inégalité du théorème en découle parce que f' est croissante.

Variantes :
Il existe des variantes, par exemple si f'(r) < 0 et f'' $\geq$ 0 sur [a, r]. Si f'' $\leq$ 0, on considère g = - f.

Application :
On peut calculer la valeur approchée de la racine k-ième d'un réel a > 0 en appliquant ce deuxième théorème. En effet si a > 0, alors x^k - a est 2 fois continument dérivable et de dérivée première kx^k-1 et seconde k(k - 1)x^k-2 strictement positives sur $\mathbb {R}$^{+ *} (car k $\geq$ 2). Il suffit donc de prendre une valeur de départ u₀ plus grande que la racine k-ième, par exemple 1 + a/k (en effet (1 + a/k)^k $\geq$ 1 + ka/k = 1 + a). En appliquant l'inégalité du théorème, on a :

0 $$\leq$$ u_n - $$\sqrt[k]{{a}}$$ $$\leq$$ $${\frac{{u_n^k - a}}{{k\sqrt[k]{a}^{k-1} }}}$$ $$\leq$$ $${\frac{{u_n^k-a}}{{ka}}}$$$$\sqrt[k]{{a}}$$ $$\leq$$ $${\frac{{u_n^k-a}}{{ka}}}$$(1 + $${\frac{{a}}{{k}}}$$)

Pour avoir une valeur approchée de $\sqrt[k]{{a}}$ à $\varepsilon$ près, on peut donc choisir comme test d'arrêt

u_n^k - a $$\leq$$ $${\frac{{ka}}{{1+\frac{a}{k}}}}$$$$\varepsilon$$

Par exemple pour $\sqrt{{2}}$, le test d'arrêt serait u_n² -2 $\leq$ 2$\varepsilon$.