Analyse de convergence — Définitions et ordre de convergence

Objectifs d'apprentissage

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

• Définir l'ordre de convergence d'une méthode itérative
• Calculer la constante asymptotique pour différentes méthodes
• Comparer les vitesses de convergence des méthodes étudiées

Motivation

Nous avons vu plusieurs méthodes pour résoudre $F(x) = 0$. Dans nos exemples, nous avons observé que :

• La bissection converge en ~11 itérations
• L'interpolation linéaire converge en ~8 itérations
• La sécante converge en ~5 itérations
• Newton converge en ~3 itérations

Pourquoi ces différences ? Est-ce un hasard lié à notre exemple, ou y a-t-il une explication théorique ?

Pour répondre, nous devons étudier à quelle vitesse l'erreur diminue d'une itération à l'autre.

Rappel : suites convergentes

Une suite numérique $\{x_n\}$ est une séquence de nombres réels indexés par $n$ :

Une suite converge vers une limite $L$ si ses termes se rapprochent arbitrairement de $L$ quand $n$ devient grand. On note :

Formellement, cela signifie que pour tout $\varepsilon > 0$, il existe un rang $N$ tel que $|x_n - L| < \varepsilon$ pour tout $n \geq N$.

Dans nos méthodes itératives, nous générons une suite $\{x_n\}$ qui converge vers la racine $x^*$. La question est : à quelle vitesse ?

L'erreur signée

Supposons qu'une méthode itérative génère une suite $\{x_n\}$ convergeant vers $x^*$.

L'erreur signée à l'itération $n$ est la différence entre notre approximation et la vraie solution :

L'erreur peut être positive ou négative (d'où « signée »). En pratique, on ne connaît pas $x^*$ exactement, mais on peut étudier le comportement théorique de $e_n$.

La question fondamentale est : quelle est la relation entre $e_{n+1}$ et $e_n$ ?

Convergence linéaire

La forme la plus simple est celle où l'erreur est multipliée par un facteur constant à chaque itération :

où $0 < C < 1$ est une constante. On parle alors de convergence linéaire.

Exemple avec C = 0.5

Si l'erreur initiale est $e_0 = 1$ et $C = 0.5$ :

Par récurrence, on obtient $e_n = C^n \cdot e_0$. Puisque $0 < C < 1$, on a $C^n \to 0$, donc la méthode converge.

Observation : Pour gagner une décimale de précision (diviser l'erreur par 10), il faut environ 3-4 itérations.

Convergence quadratique

Une convergence plus rapide se produit quand l'erreur est élevée au carré :

On parle alors de convergence quadratique.

Exemple avec C = 1

Si l'erreur initiale est $e_0 = 0.1$ :

Avec la convergence quadratique, le nombre de décimales correctes double à chaque itération. C'est pour cela que Newton converge si vite : 4 itérations suffisent pour atteindre la précision machine.

Formule générale

Par récurrence, on peut montrer que :

Forme générale de la décroissance de l'erreur

Comparons les deux types de convergence en regardant comment $\log|e_n|$ évolue.

Convergence linéaire

On a $|e_n| = C^n \cdot |e_0|$, donc :

Le logarithme de l'erreur décroît linéairement en $n$.

Convergence quadratique

On a $|e_n| \approx |e_0|^{2^n}$, donc :

Le logarithme de l'erreur décroît exponentiellement en $n$, comme $2^n$.

Généralisation pour p > 1

Pour une convergence d'ordre $p > 1$, on observe que $\log|e_n|$ décroît comme $p^n$.

Cela signifie que l'erreur a la forme :

où $\varepsilon$ est une petite constante (liée à l'erreur initiale).

Définition formelle

Nous pouvons maintenant généraliser avec une définition formelle.

Cette définition formalise l'idée que $e_{n+1} \approx C \cdot e_n^p$.

Nomenclature

Comment déterminer l'ordre ?

En pratique, on procède par essais :

1. Essayer p = 1 : calculer $\displaystyle\lim_{n \to \infty} \frac{|e_{n+1}|}{|e_n|}$

   • Si on obtient $0 < C < 1$ → convergence linéaire
   • Si on obtient $C = 0$ → essayer p = 2

2. Essayer p = 2 : calculer $\displaystyle\lim_{n \to \infty} \frac{|e_{n+1}|}{|e_n|^2}$

   • Si on obtient $C \neq 0$ → convergence quadratique

Application : méthode de bissection

Rappelons que l'intervalle de confiance se réduit de moitié à chaque itération :

L'erreur est bornée par $|e_n| \leq \Delta X^{(n)}$.

Calcul de l'ordre

Avec $p = 1$, calculons le rapport des erreurs successives :

Conclusion : La bissection a une convergence linéaire ($p = 1$) avec $C = 1/2$.

À chaque itération, l'erreur est divisée par 2. Pour réduire l'erreur d'un facteur 1000 (≈ 3 décimales), il faut environ 10 itérations car $2^{10} = 1024 > 1000$.

Application : méthode d'interpolation linéaire

La méthode d'interpolation linéaire (Regula Falsi) a également une convergence linéaire ($p = 1$), mais avec une constante $C$ qui dépend de la fonction.

Le phénomène de la borne bloquée

Rappelons que Regula Falsi garde toujours deux points de signes opposés. Quand la fonction est convexe (ou concave) au voisinage de la racine, une des deux bornes reste souvent « bloquée » pendant plusieurs itérations tandis que l'autre se déplace.

Par exemple, si $F$ est convexe et croissante, la borne inférieure reste fixe et seule la borne supérieure converge vers la racine.

Analyse de l'erreur

Pour déterminer la constante $C$, on analyse l'erreur sur la borne mobile. Notons :

• $a$ : la borne fixe (bloquée)
• $x_n$ : la borne mobile à l'itération $n$
• $e_n = x_n - x^*$ : l'erreur de la borne mobile
• $e_a = a - x^*$ : l'erreur de la borne fixe (constante !)

Point de départ : On développe $F(x_n)$ et $F(a)$ en série de Taylor autour de la racine $x^*$. Comme $F(x^*) = 0$ :

Pour $F(x_n)$, on néglige le terme en $e_n^2$ car $e_n \to 0$. Mais pour $F(a)$, on garde le terme en $e_a^2$ car $e_a$ reste constant (la borne est bloquée).

La formule de Regula Falsi donne :

Calcul de l'erreur $e_{n+1} = x_{n+1} - x^*$ : En substituant les développements de Taylor et en simplifiant (exercice !), on obtient :

Cette formule montre que $e_{n+1}$ dépend de :

• $e_n$ : l'erreur actuelle de la borne mobile
• $e_a$ : l'erreur de la borne fixe (qui reste constante)
• Le rapport $\frac{F''(x^*)}{F'(x^*)}$ : la courbure relative de $F$

Résultat

La constante asymptotique est donc :

Cette constante dépend de deux facteurs :

• $|e_a|$ : la distance entre la borne bloquée et la racine
• $\frac{|F''(x^*)|}{|F'(x^*)|}$ : la courbure relative de $F$ à la racine

Interprétation :

• Plus $e_a$ est petit (borne fixe proche de la racine) → $C$ petit → convergence rapide
• Si $F'' \approx 0$ (fonction presque linéaire) → $C \approx 0$ → convergence rapide
• Si $F''$ est grand et $e_a$ grand → $C$ proche de 1 → convergence lente

Comparaison avec la bissection

Application : méthode de la sécante

La sécante utilise la même formule que Regula Falsi, mais garde les deux points avec $|F(X)|$ le plus petit (au lieu des signes opposés). Cette différence change radicalement l'ordre de convergence.

Pourquoi un ordre différent de Regula Falsi ?

Dans Regula Falsi, une borne reste bloquée → l'erreur diminue d'un seul côté → convergence linéaire.

Dans la sécante, les deux points se rapprochent de la racine à chaque itération. L'information des deux dernières approximations est utilisée, ce qui accélère la convergence.

Une récurrence à deux termes

Pour Newton, l'erreur $e_{n+1}$ ne dépend que de $e_n$ :

Pour la sécante, la formule utilise $X_n$ et $X_{n-1}$. On peut montrer (par développement de Taylor) que l'erreur satisfait une récurrence faisant intervenir les deux dernières erreurs :

C'est un produit, pas une puissance ! Cette structure particulière va donner un ordre de convergence inhabituel.

Résolution de la récurrence

Pour trouver l'ordre de convergence $p$, on utilise la forme générale vue précédemment.

Rappel : Pour une convergence d'ordre $p$, l'erreur décroît comme :

Ici, on ne connaît pas $p$, c'est ce qu'on cherche ! Posons $p = \alpha$ (inconnue).

Substitution : En remplaçant dans $e_{n+1} \approx C \cdot e_n \cdot e_{n-1}$ :

En comparant les exposants de $\varepsilon$ (et en ignorant la constante $C$ pour l'analyse asymptotique) :

Simplification : En divisant par $\alpha^{n-1}$ :

Le nombre d'or apparaît

L'équation $\alpha^2 = \alpha + 1$ est l'équation caractéristique de la suite de Fibonacci !

Ses solutions sont :

La solution positive est le nombre d'or :

Puisque $\alpha$ correspond à l'ordre de convergence $p$, on a :

Interprétation

L'ordre de convergence de la sécante est $p \approx 1.618$, ce qui en fait une méthode superlinéaire :

• Plus rapide que la bissection et Regula Falsi ($p = 1$)
• Moins rapide que Newton ($p = 2$)

Mais attention : chaque itération de la sécante ne nécessite qu'une seule évaluation de $F$, contre deux pour Newton ($F$ et $F'$). Cette économie compense partiellement l'ordre inférieur.

Comparaison des méthodes

Coût par itération

Efficacité (ordre / coût)

En termes d'efficacité pure, la sécante est la meilleure ! Cependant, Newton reste souvent préféré car sa convergence quadratique est plus prévisible.

Les quatre récurrences tracées ci-dessus sont celles établies dans cette leçon : $e_{n+1} = 0{,}5\,e_n$ pour la bissection, $e_{n+1} = C e_n$ pour l'interpolation linéaire, $e_{n+1} \approx C e_n^{1{,}618}$ pour la sécante et $e_{n+1} = C e_n^2$ pour Newton. En échelle logarithmique, l'ordre se lit directement dans la forme de la courbe : une droite signale un ordre 1, une courbe qui s'incurve vers le bas un ordre supérieur à 1.

L'ordre domine la constante

Une question naturelle : vaut-il mieux un grand ordre $p$ ou une petite constante $C$ ?

Réponse : L'ordre est beaucoup plus important.

Exemple

Comparons deux méthodes avec $e_0 = 0.01$ :

• Méthode A : linéaire ($p = 1$) avec $C = 0.1$ (excellente constante)
• Méthode B : quadratique ($p = 2$) avec $C = 10$ (mauvaise constante)

Une fois l'erreur suffisamment petite, la méthode d'ordre supérieur écrase l'autre, quelle que soit la constante.

Résumé

Points clés

1. Erreur signée : $e_n = x_n - x^*$

2. Convergence linéaire ($p = 1$) : $e_{n+1} \approx C \cdot e_n$

3. Convergence quadratique ($p = 2$) : $e_{n+1} \approx C \cdot e_n^2$ — les décimales correctes doublent

4. L'ordre p est plus important que la constante C

5. La sécante a l'ordre du nombre d'or (≈ 1.618)