AnalyseNotion · Glossaire
Vitesse de convergence
La vitesse de convergence d'une suite vers sa limite mesure à quelle rapidité les termes de la suite s'approchent de cette limite. On parle de convergence linéaire si l'erreur est réduite d'un facteur constant à chaque étape, de convergence quadratique si l'erreur au carré est réduite proportionnellement, et de convergence superlinéaire lorsque le rapport entre deux erreurs successives tend vers zéro, ce qui inclut notamment les convergences d'ordre strictement supérieur à 1. En analyse numérique, la vitesse de convergence détermine l'efficacité pratique des algorithmes itératifs.
Sommaire
Ce que vous allez apprendre
- Définir l'erreur et l'ordre de convergence d'une suite.
- Distinguer convergence linéaire, superlinéaire et quadratique.
- Vérifier une convergence quadratique sur les itérations de Newton pour √2.
- Repérer les effets du régime asymptotique et des arrondis.
En clair
Une calculatrice cherche √2 par approximations successives : 1,5, puis 1,4167, puis 1,414216. Chaque valeur se rapproche de 1,414214 environ, mais le nombre de décimales justes n'augmente pas toujours au même rythme.
La vitesse de convergence décrit précisément ce rythme. Si chaque étape divise à peu près l'erreur par une même constante, la convergence est linéaire. Si elle transforme une petite erreur en une erreur comparable à son carré, elle est quadratique et les chiffres exacts s'accumulent beaucoup plus vite.
Définition
Soit une suite de valeurs xn qui converge vers une limite ℓ. À l'étape n, son erreur absolue est le nombre en = |xn − ℓ|. La vitesse de convergence décrit le comportement de cette erreur lorsque n devient grand ; elle ne dit pas seulement que l'erreur tend vers zéro, mais à quel rythme elle le fait.
On dit que la convergence est d'ordre p, avec p ≥ 1, s'il existe une constante C strictement positive et finie telle que . Cette définition suppose que les erreurs considérées ne sont pas nulles à partir d'un certain rang. Pour p = 1, la convergence est linéaire lorsque 0 < C < 1. Pour p = 2, elle est quadratique.
La convergence est superlinéaire lorsque le rapport en+1/en tend vers zéro. Les ordres strictement supérieurs à 1, notamment l'ordre quadratique, sont donc superlinéaires. Selon les suites, un ordre au sens précédent peut ne pas exister ; on compare alors les erreurs avec des équivalents ou des majorations asymptotiques.
Un exemple, pas à pas
On approche √2 par la méthode de Newton. La limite visée est ℓ = √2 ≈ 1,4142135623730951, et la valeur initiale est x0 = 1,5. À chaque étape, on calcule la moyenne de xn et de 2/xn.
La règle d'itération est .
1. On obtient x1 = 17/12 ≈ 1,4166666667. L'erreur passe d'environ 0,0857864 à 0,00245310.
2. On obtient ensuite x2 = 577/408 ≈ 1,4142156863. L'erreur n'est plus que d'environ 0,00000212390.
3. Une troisième itération donne x3 ≈ 1,4142135623746899, avec une erreur d'environ 1,59 × 10−12. Le contrôle consiste à recalculer |xn − √2| : une fois l'approximation proche de √2, le rapport en+1/en2 se rapproche de 1/(2√2) ≈ 0,3536. La représentation logarithmique des quatre erreurs rend visible cette chute accélérée.
En pratique
Pour choisir entre deux algorithmes itératifs qui calculent la même grandeur, on observe l'erreur ou un résidu après chaque étape. À coût comparable, une décroissance superlinéaire fait préférer la méthode qui atteint la précision voulue en moins d'itérations.
Dans un calcul numérique, on fixe une tolérance puis on arrête les itérations lorsque l'erreur estimée devient assez petite. Si la limite exacte est inconnue, on suit plutôt un résidu calculable ou l'écart entre deux itérés, à condition qu'il contrôle réellement l'erreur.
Une méthode d'ordre élevé n'est pas automatiquement la plus rapide. On compare aussi le coût d'une itération, la précision des calculs et la taille de la zone où le régime annoncé apparaît. Une méthode linéaire robuste peut être préférable loin de la solution, avant de passer à Newton près de celle-ci.
À ne pas confondre
Convergence et vitesse de convergence. La convergence répond à la question « la suite atteint-elle une limite ? » ; la vitesse n'est étudiée qu'une fois cette limite identifiée. Une suite divergente n'a donc pas de vitesse de convergence vers une limite finie.
Convergence quadratique et convergence en moyenne quadratique. La première décrit une erreur d'itération qui se comporte comme le carré de l'erreur précédente. La seconde est un mode de convergence de variables aléatoires fondé sur l'espérance du carré de leur différence ; le contexte probabiliste tranche.
Ordre de convergence et complexité. L'ordre décrit la réduction asymptotique de l'erreur par itération. La complexité compte des ressources, comme le temps ou le nombre d'opérations. Deux méthodes de même ordre peuvent avoir des coûts très différents par étape.
Limites et pièges
Le régime asymptotique peut commencer tard. Les premiers rapports d'erreurs fluctuent souvent. Il faut examiner plusieurs itérations proches de la limite avant d'attribuer un ordre à partir de données numériques.
Le seuil C = 1 ne donne pas une contraction linéaire. Dans le critère d'ordre 1, il faut 0 < C < 1 pour que le modèle garantisse une réduction géométrique de l'erreur. Si le rapport tend vers 1, la suite peut converger, mais plus lentement que linéairement.
Une erreur nulle arrête la comparaison. Si un itéré atteint exactement la limite, les rapports suivants comportent une division par zéro. Le calcul a déjà convergé en un nombre fini d'étapes ; on le signale au lieu de lui attribuer artificiellement un ordre.
Les arrondis finissent par dominer. Près de la limite, une précision machine finie peut faire stagner ou osciller les erreurs mesurées. On estime l'ordre avant ce plateau et on contrôle le résultat avec un résidu adapté au problème.
Pour aller plus loin
La méthode de Newton montre comment une règle d'itération peut produire une convergence quadratique au voisinage d'une racine, sous des hypothèses adaptées.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres