Newton, Cauchy-Lipschitz et les autres

La méthode de Newton

Pour résoudre $g(x) = 0$, la méthode de Newton itère

$$f(x) = x - \frac{g(x)}{g'(x)}$$

Un point fixe de $f$ est exactement une racine de $g$. Au voisinage d'une racine simple $c$, on montre que $f'(c) = 0$, donc $f$ y est contractante d'un facteur aussi petit que l'on veut : la convergence est en fait quadratique, le nombre de décimales exactes doublant à chaque étape.

L'exemple canonique est le calcul de $\sqrt{2}$ avec $g(x) = x^2 - 2$, qui donne la formule de Héron :

$$f(x) = \frac{1}{2}\left(x + \frac{2}{x}\right)$$

$n$	$u_n$	Décimales exactes
$0$	$2$	$0$
$1$	$1{,}5$	$1$
$2$	$1{,}4166667$	$2$
$3$	$1{,}4142157$	$5$
$4$	$1{,}4142136$	$8$

Le théorème de Cauchy-Lipschitz

L'application la plus spectaculaire est l'existence et l'unicité des solutions d'une équation différentielle. Le problème

$$y'(t) = F\left(t, y(t)\right), \qquad y(t_0) = y_0$$

s'écrit sous forme intégrale $y(t) = y_0 + \displaystyle\int_{t_0}^{t} F\left(s, y(s)\right)\,\mathrm{d}s$, c'est-à-dire comme la recherche d'un point fixe de l'application qui, à une fonction $y$, associe le membre de droite.

Lorsque $F$ est lipschitzienne en sa seconde variable, cette application est contractante sur un espace de fonctions bien choisi, complet pour la norme de la convergence uniforme. Le théorème de Banach fournit alors la solution, et son unicité. La méthode des itérées de Picard n'est rien d'autre que la suite $u_{n+1} = f(u_n)$ dans ce cadre.

Un panorama des usages

Domaine	Ce que le théorème fournit
Analyse numérique	convergence de Newton, de la méthode de la sécante
Équations différentielles	théorème de Cauchy-Lipschitz
Algèbre linéaire	convergence des méthodes itératives de Jacobi et Gauss-Seidel
Géométrie fractale	attracteur d'un système de fonctions itérées
Informatique	sémantique des définitions récursives, plus petit point fixe

Piège classique

Croire que tout théorème de point fixe exige une contraction. Ce n'est pas le cas : le théorème du point fixe de Brouwer affirme que toute application continue d'une boule fermée de $\mathbb{R}^d$ dans elle-même admet un point fixe, sans aucune hypothèse de contraction. Dans le cas $d = 1$, il se démontre en deux lignes avec le théorème des valeurs intermédiaires appliqué à $x \mapsto f(x) - x$.

La différence est décisive en pratique : Brouwer donne l'existence, mais ni l'unicité, ni un algorithme. Banach donne les trois.