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 . 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 est une séquence de nombres réels indexés par :

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

Formellement, cela signifie que pour tout , il existe un rang tel que pour tout .

Dans nos méthodes itératives, nous générons une suite qui converge vers la racine . La question est : à quelle vitesse ?

L'erreur signée

Supposons qu'une méthode itérative génère une suite convergeant vers .

L'erreur signée à l'itération 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 exactement, mais on peut étudier le comportement théorique de .

La question fondamentale est : quelle est la relation entre et ?

Convergence linéaire

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

où est une constante. On parle alors de convergence linéaire.

Exemple avec C = 0.5

Si l'erreur initiale est et :

Par récurrence, on obtient . Puisque , on a , 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 :

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 évolue.

Convergence linéaire

On a , donc :

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

Convergence quadratique

On a , donc :

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

Généralisation pour p > 1

Pour une convergence d'ordre , on observe que décroît comme .

Cela signifie que l'erreur a la forme :

où 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 .

Nomenclature

Comment déterminer l'ordre ?

En pratique, on procède par essais :

1. Essayer p = 1 : calculer

   • Si on obtient → convergence linéaire
   • Si on obtient → essayer p = 2

2. Essayer p = 2 : calculer

   • Si on obtient → 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 .

Calcul de l'ordre

Avec , calculons le rapport des erreurs successives :

Conclusion : La bissection a une convergence linéaire () avec .

À 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 .

Application : méthode d'interpolation linéaire

La méthode d'interpolation linéaire (Regula Falsi) a également une convergence linéaire (), mais avec une constante 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 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 , on analyse l'erreur sur la borne mobile. Notons :

• : la borne fixe (bloquée)
• : la borne mobile à l'itération
• : l'erreur de la borne mobile
• : l'erreur de la borne fixe (constante !)

Point de départ : On développe et en série de Taylor autour de la racine . Comme :

Pour , on néglige le terme en car . Mais pour , on garde le terme en car reste constant (la borne est bloquée).

La formule de Regula Falsi donne :

Calcul de l'erreur : En substituant les développements de Taylor et en simplifiant (exercice !), on obtient :

Cette formule montre que dépend de :

• : l'erreur actuelle de la borne mobile
• : l'erreur de la borne fixe (qui reste constante)
• Le rapport : la courbure relative de

Résultat

La constante asymptotique est donc :

Cette constante dépend de deux facteurs :

• : la distance entre la borne bloquée et la racine
• : la courbure relative de à la racine

Interprétation :

• Plus est petit (borne fixe proche de la racine) → petit → convergence rapide
• Si (fonction presque linéaire) → → convergence rapide
• Si est grand et grand → 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 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 ne dépend que de :

Pour la sécante, la formule utilise et . 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 , on utilise la forme générale vue précédemment.

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

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

Substitution : En remplaçant dans :

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

Simplification : En divisant par :

Le nombre d'or apparaît

L'équation est l'équation caractéristique de la suite de Fibonacci !

Ses solutions sont :

La solution positive est le nombre d'or :

Puisque correspond à l'ordre de convergence , on a :

Interprétation

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

• Plus rapide que la bissection et Regula Falsi ()
• Moins rapide que Newton ()

Mais attention : chaque itération de la sécante ne nécessite qu'une seule évaluation de , contre deux pour Newton ( et ). 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.

L'ordre domine la constante

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

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

Exemple

Comparons deux méthodes avec :

• Méthode A : linéaire () avec (excellente constante)
• Méthode B : quadratique () avec (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 :

2. Convergence linéaire () :

3. Convergence quadratique () : — 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)