Analyse de convergence — Point fixe et Newton

Objectifs d'apprentissage

À la fin de cette leçon, vous serez en mesure de :

Appliquer le théorème de la moyenne pour analyser la convergence
Démontrer l'ordre de convergence de la méthode du point fixe
Démontrer l'ordre de convergence de la méthode de Newton
Comprendre l'impact des racines multiples sur la convergence

Rappel : le théorème de la moyenne

Le théorème de la moyenne (aussi appelé théorème des accroissements finis) est un outil fondamental pour analyser la convergence.

🚨

Théorème de la moyenne

Si $f(x)$ est continue sur $[a, b]$ et dérivable sur $]a, b[$ , alors il existe $\xi \in ]a, b[$ tel que :

f'(\xi) = \frac{f(b) - f(a)}{b - a}

Interprétation géométrique

Ce théorème dit qu'il existe au moins un point où la tangente à la courbe est parallèle à la sécante reliant les points $(a, f(a))$ et $(b, f(b))$ .

Forme utile pour notre analyse

On peut réécrire le théorème sous la forme :

f(b) - f(a) = f'(\xi) \cdot (b - a)

Cette forme sera utilisée pour relier l'erreur à l'itération $n+1$ à l'erreur à l'itération $n$ .

Convergence de la méthode du point fixe

Rappel de la méthode

La méthode du point fixe transforme $F(x) = 0$ en $x = g(x)$ et itère :

X_{n+1} = g(X_n)

La racine $r$ est un point fixe : $r = g(r)$ .

Analyse par le théorème de la moyenne

Calculons l'erreur $e_{n+1} = X_{n+1} - r$ :

e_{n+1} = X_{n+1} - r = g(X_n) - g(r)

En appliquant le théorème de la moyenne à $g$ entre $r$ et $X_n$ , il existe $\xi_n$ entre ces deux points tel que :

g(X_n) - g(r) = g'(\xi_n) \cdot (X_n - r)

Donc :

e_{n+1} = g'(\xi_n) \cdot e_n

Passage à la limite

Quand $n \to \infty$ , on a $X_n \to r$ , donc $\xi_n \to r$ (car $\xi_n$ est entre $X_n$ et $r$ ).

Si $g'(r) \neq 0$ :

\lim_{n \to \infty} \frac{|e_{n+1}|}{|e_n|} = \lim_{n \to \infty} |g'(\xi_n)| = |g'(r)|

En comparant avec la définition de l'ordre de convergence (avec $p = 1$ ), on identifie :

C = |g'(r)|

Condition de convergence

Pour avoir convergence, il faut $0 < C < 1$ , donc :

|g'(r)| < 1

💡

Condition suffisante de convergence

La méthode du point fixe converge si $|g'(r)| < 1$ et si le point de départ $X_0$ est suffisamment proche de $r$ .

Analyse par développement de Taylor

Le théorème de la moyenne nous dit que la convergence est linéaire quand $g'(r) \neq 0$ . Mais que se passe-t-il si $g'(r) = 0$ ?

Pour répondre, utilisons le développement de Taylor.

Développement de g(Xₙ)

On développe $g(X_n)$ autour du point fixe $r$ :

g(X_n) = g(r + e_n) = g(r) + g'(r) \cdot e_n + \frac{g''(r)}{2!} \cdot e_n^2 + \frac{g'''(r)}{3!} \cdot e_n^3 + \cdots

Comme $r = g(r)$ (point fixe) et $X_{n+1} = g(X_n)$ :

X_{n+1} = r + g'(r) \cdot e_n + \frac{g''(r)}{2!} \cdot e_n^2 + \frac{g'''(r)}{3!} \cdot e_n^3 + \cdots

En soustrayant $r$ des deux côtés :

e_{n+1} = g'(r) \cdot e_n + \frac{g''(r)}{2!} \cdot e_n^2 + \frac{g'''(r)}{3!} \cdot e_n^3 + \cdots

Cas 1 : g'(r) ≠ 0 — Convergence linéaire

Si $g'(r) \neq 0$ , le terme dominant est $g'(r) \cdot e_n$ :

\frac{e_{n+1}}{e_n} = g'(r) + \frac{g''(r)}{2!} \cdot e_n + \frac{g'''(r)}{3!} \cdot e_n^2 + \cdots

Quand $n \to \infty$ , $e_n \to 0$ , donc :

\lim_{n \to \infty} \frac{|e_{n+1}|}{|e_n|} = |g'(r)|

Conclusion : Convergence linéaire avec $C = |g'(r)|$ .

Cas 2 : g'(r) = 0, g''(r) ≠ 0 — Convergence quadratique

Si $g'(r) = 0$ , le développement devient :

e_{n+1} = \frac{g''(r)}{2!} \cdot e_n^2 + \frac{g'''(r)}{3!} \cdot e_n^3 + \cdots

Le terme dominant est maintenant $\frac{g''(r)}{2} \cdot e_n^2$ :

\frac{e_{n+1}}{e_n^2} = \frac{g''(r)}{2} + \frac{g'''(r)}{6} \cdot e_n + \cdots

Quand $n \to \infty$ :

\lim_{n \to \infty} \frac{|e_{n+1}|}{|e_n|^2} = \frac{|g''(r)|}{2}

Conclusion : Convergence quadratique avec $C = \frac{|g''(r)|}{2}$ .

Cas 3 : g'(r) = g''(r) = 0, g'''(r) ≠ 0 — Convergence cubique

Si les deux premières dérivées s'annulent :

e_{n+1} = \frac{g'''(r)}{3!} \cdot e_n^3 + \cdots

\lim_{n \to \infty} \frac{|e_{n+1}|}{|e_n|^3} = \frac{|g'''(r)|}{6}

Conclusion : Convergence cubique avec $C = \frac{|g'''(r)|}{6}$ .

Résumé pour le point fixe

Condition	Ordre p	Constante C
$g'(r) \neq 0$	1 (linéaire)	$\|g'(r)\|$
$g'(r) = 0$ , $g''(r) \neq 0$	2 (quadratique)	$\frac{\|g''(r)\|}{2}$
$g'(r) = g''(r) = 0$ , $g'''(r) \neq 0$	3 (cubique)	$\frac{\|g'''(r)\|}{6}$

Observation clé : Plus de dérivées s'annulent au point fixe, plus la convergence est rapide !

Convergence de la méthode de Newton

Newton comme méthode de point fixe

La méthode de Newton peut s'écrire comme une méthode de point fixe avec :

G(X) = X - \frac{F(X)}{F'(X)}

Pour déterminer l'ordre de convergence, nous devons calculer $G'(r)$ .

Calcul de G'(X)

En utilisant la règle du quotient :

G'(X) = 1 - \frac{F'(X) \cdot F'(X) - F(X) \cdot F''(X)}{[F'(X)]^2}

G'(X) = 1 - \frac{[F'(X)]^2 - F(X) \cdot F''(X)}{[F'(X)]^2}

G'(X) = \frac{[F'(X)]^2 - [F'(X)]^2 + F(X) \cdot F''(X)}{[F'(X)]^2}

G'(X) = \frac{F(X) \cdot F''(X)}{[F'(X)]^2}

Évaluation en X = r (racine simple)

Au point $r$ , on a $F(r) = 0$ . Donc :

G'(r) = \frac{F(r) \cdot F''(r)}{[F'(r)]^2} = \frac{0 \cdot F''(r)}{[F'(r)]^2} = 0

Conclusion pour une racine simple

Puisque $G'(r) = 0$ , d'après notre analyse du point fixe (cas 2), la méthode de Newton a une convergence quadratique !

\lim_{n \to \infty} \frac{|e_{n+1}|}{|e_n|^2} = \frac{|G''(r)|}{2}

C'est ce qui explique pourquoi Newton converge si rapidement : le nombre de décimales correctes double à chaque itération.

Racines multiples

Définition

Une racine $r$ est de multiplicité m si :

F(X) = (X - r)^m \cdot H(X)

où $H(r) \neq 0$ .

Exemples :

$F(X) = X - 3$ : racine simple ( $m = 1$ ) en $r = 3$
$F(X) = (X - 3)^2$ : racine double ( $m = 2$ ) en $r = 3$
$F(X) = (X - 3)^3$ : racine triple ( $m = 3$ ) en $r = 3$

Caractérisation par les dérivées

Pour une racine de multiplicité $m$ :

$F(r) = F'(r) = F''(r) = \cdots = F^{(m-1)}(r) = 0$
$F^{(m)}(r) \neq 0$

Impact sur Newton

Pour une racine de multiplicité $m \geq 2$ , calculons $G'(r)$ .

Avec $F(X) = (X-r)^m H(X)$ , les dérivées sont :

F'(X) = (X-r)^{m-1} \left[ mH(X) + (X-r)H'(X) \right]

F''(X) = (X-r)^{m-2} \left[ m(m-1)H(X) + 2m(X-r)H'(X) + (X-r)^2 H''(X) \right]

En évaluant $G'(X) = \frac{F(X) \cdot F''(X)}{[F'(X)]^2}$ en $X = r$ et en simplifiant (les puissances de $(X-r)$ se simplifient), on obtient :

|G'(r)| = \frac{m - 1}{m}

Conséquence

Pour une racine de multiplicité $m \geq 2$ :

$G'(r) \neq 0$
La convergence est linéaire avec $C = \frac{m-1}{m}$

Multiplicité m	\|G'(r)\|	Type de convergence
1 (simple)	0	Quadratique
2 (double)	1/2	Linéaire
3 (triple)	2/3	Linéaire
m	(m-1)/m	Linéaire

⚠️

Attention aux racines multiples

La méthode de Newton perd sa convergence quadratique pour les racines multiples. Plus la multiplicité est élevée, plus la constante $C = \frac{m-1}{m}$ est proche de 1, et plus la convergence est lente.

Modification de Newton pour les racines multiples

Si on connaît la multiplicité $m$ , on peut modifier la formule de Newton :

X_{n+1} = X_n - m \cdot \frac{F(X_n)}{F'(X_n)}

Cette modification restaure la convergence quadratique.

Résumé général

Méthode	Condition	Ordre p	Constante C
Point fixe	$g'(r) \neq 0$	1	$\|g'(r)\|$
Point fixe	$g'(r) = 0$	2	$\frac{\|g''(r)\|}{2}$
Newton	Racine simple	2	$\frac{\|G''(r)\|}{2}$
Newton	Racine de multiplicité m	1	$\frac{m-1}{m}$

Points clés

Théorème de la moyenne : permet de relier $e_{n+1}$ à $e_n$ via $g'(\xi_n)$
Point fixe : l'ordre de convergence dépend de combien de dérivées de $g$ s'annulent en $r$
Newton = point fixe avec $G(X) = X - \frac{F(X)}{F'(X)}$
Newton et racine simple : $G'(r) = 0$ → convergence quadratique
Newton et racine multiple : $|G'(r)| = \frac{m-1}{m}$ → convergence linéaire
Condition de convergence : $|g'(r)| < 1$ est une condition suffisante