Vitesse de convergence des suites

En analyse numérique — une branche des mathématiques — on peut classer les suites convergentes en fonction de leur vitesse de convergence vers leur point limite. C'est une manière d'apprécier l'efficacité des algorithmes qui les génèrent.

Les suites considérées ici sont convergentes sans être stationnaires (tous leurs termes sont même supposés différents du point limite). Si une suite est stationnaire, tous ses éléments sont égaux à partir d'un certain rang et il est alors normal de s'intéresser au nombre d'éléments différents du point limite. C'est ce que l'on fait lorsqu'on étudie la complexité des algorithmes trouvant ce qu'ils cherchent en un nombre fini d'étapes.

Vue d'ensembleModifier

DéfinitionsModifier

Cette section décrit quelques notions de vitesse de convergence d'une suite   d'un espace vectoriel normé  , vers sa limite  , fondées sur la comparaison de la norme de l'erreur   de deux éléments successifs. L'erreur est toujours supposée non nulle :  , pour tout indice  . Cette hypothèse est raisonnable lorsque la suite est générée par un algorithme « bien conçu », c'est-à-dire pour lequel dès que  , la suite devient stationnaire après   (tous les itérés suivants sont égaux à   et il n'y a plus de sens à parler de vitesse de convergence). On s'intéresse donc au quotient

 ,

  est un nombre réel strictement positif. L'intérêt pour ce quotient provient du fait qu'on peut souvent l'estimer en faisant un développement de Taylor autour de   des fonctions définissant le problème que l'on cherche à résoudre et dont   est solution. Évidemment, plus   est grand, plus la vitesse de convergence est rapide (car asymptotiquement  ).

Brièvement, on dit que le q-ordre de convergence est   si le quotient ci-dessus est borné. Le préfixe q-, qui rappelle le mot quotient, est souvent omis. On dit aussi que la convergence est :

  • linéaire s'il existe une norme  , un réel   et un indice   tels que pour tout  ,   ;
  • superlinéaire si   ;
  • quadratique (ordre 2) s'il existe une constante   telle que pour tout indice  ,   ;
  • cubique (ordre 3) s'il existe une constante   telle que pour tout indice  ,   ;
  • quartique (ordre 4) s'il existe une constante   telle que pour tout indice  ,  etc.

Les trois principales vitesses de convergence en quotient sont les vitesses de convergence linéaire, superlinéaire et quadratique. Elles sont davantage discutées ci-dessous.

Incidence sur le nombre de chiffres significatifs correctsModifier

Numériquement, plus la convergence est rapide, plus le nombre de chiffres significatifs corrects de   (ceux identiques à ceux de  ) augmente vite. Donnons une définition plus précise de cette notion. Si   est un vecteur, on ne peut pas définir par un scalaire la correction des chiffres significatifs de toutes ses composantes, mais on peut le faire en moyenne au sens de la norme sur  . On suppose que   car on ne peut définir ce que sont les chiffres significatifs de zéro. Si   vaut  , on dira que   a 4 chiffres significatifs corrects (ce serait effectivement le cas si   et   étaient des scalaires). Ceci conduit à la définition suivante.

Nombre de chiffres significatifs corrects — Le nombre de chiffres significatifs corrects de   par rapport à   est le nombre réel défini par

 .

Lorsque  , on peut exprimer les vitesses de convergence en quotient en utilisant   plutôt que le quotient ci-dessus, ce que nous ferons.

Estimation sans connaissance de la limiteModifier

Il est parfois intéressant de vérifier numériquement que les suites générées par un algorithme ont bien la vitesse de convergence attendue. Bien sûr, c'est une manière de vérifier que l'algorithme est bien implémenté, mais il y a une autre motivation. Par exemple, sous certaines hypothèses de régularité, on sait que l'algorithme de Newton converge quadratiquement ; cet algorithme procède par linéarisation de la fonction qu'il cherche à annuler ; vérifier que la convergence des suites générées est bien quadratique est alors une indication sur la correction du calcul des dérivées.

En général on ne connaît pas la solution, si bien que la vérification de la vitesse de convergence en quotient attendue par l'examen du quotient de la norme des erreurs successives requiert une double résolution du problème. La première résolution sert à calculer une approximation précise de la solution   ; la seconde résolution examine les quotients sus-mentionnés. On peut éviter cette double résolution si l'on arrive à exprimer la vitesse de convergence en termes d'une quantité dont la limite est connue, typiquement nulle.

Il en est ainsi si l'on cherche à annuler une fonction  , c'est-à-dire à trouver un point   tel que

 ,

pourvu que

 .

Cette écriture signifie qu'il existe des constantes   et   telles que pour tout   voisin de  , on a  . Une telle équivalence de comportement asymptotique est vérifiée si   est différentiable en   et si   est inversible. Les vitesses de convergence d'une suite   présentées ci-dessous seront également exprimées en termes du logarithme de la norme de  , de manière à permettre une vérification numérique de cette convergence.

Convergence linéaireModifier

Cette vitesse de convergence est parfois appelée convergence géométrique, car la norme de l'erreur   est majorée asymptotiquement par une suite géométrique de raison  .

Convergence linéaire — On dit qu'une suite   converge linéairement vers   s'il existe une norme  , un scalaire   et un indice   tels que

 .

Il faut donc que la norme de l'erreur décroisse strictement à chaque itération à partir d'une certaine itération, avec un taux de décroissance   strictement plus petit que 1. Le scalaire   est appelé le taux de convergence de la suite. Cette propriété dépend du choix de la norme que l'on utilise pour mesurer l'erreur, car l'estimation ci-dessus peut être vraie pour une norme et (malgré l'équivalence des normes en dimension finie) peut ne plus être vérifiée avec une constante   pour une autre norme.

Le résultat suivant fait le lien entre la convergence linéaire et le nombre   de chiffres significatifs corrects des itérés.

Convergence linéaire en termes de   — La suite   converge linéairement vers   pour la norme   si, et seulement si, il existe une constante   et un indice   tels que

 ,

  est défini avec la norme  .

Exemples d'algorithmes générant des suites linéairement convergentes
  • l'algorithme du gradient pour minimiser une fonction quadratique strictement convexe. Ceci n'est pas une bonne vitesse de convergence pour un algorithme d'optimisation différentiable ;
  • la méthode de dichotomie ou de la bissection pour rechercher un zéro d'une fonction réelle d'une variable réelle.

Convergence superlinéaireModifier

Convergence superlinéaire — On dit qu'une suite   converge superlinéairement vers   si

la suite   tend vers  .

Cette propriété est indépendante du choix de la norme. Clairement, toute suite convergeant superlinéairement converge linéairement.

Le résultat suivant fait le lien entre la convergence superlinéaire et le nombre   de chiffres significatifs corrects des itérés.

Convergence superlinéaire en termes de   — La suite   converge superlinéairement vers   pour la norme   si, et seulement si,

 ,

  est défini avec la norme  .

Voici une manière de vérifier numériquement la convergence superlinéaire d'une suite par l'intermédiaire d'une fonction s'annulant au point limite.

Convergence superlinéaire en termes d'une fonction s'annulant au point limite — Soient   un point et   une fonction telle que   et telle que   pour   proche de  . Alors la suite   converge superlinéairement vers   pour la norme   si, et seulement si,

 .

On peut le dire autrement : la suite   converge superlinéairement si, et seulement si, le tracé   a une majorante affine de pente négative arbitraire.

Exemples d'algorithmes générant des suites superlinéairement convergentes
  • les algorithmes de quasi-Newton en optimisation ou pour résoudre un système d'équations non linéaires ;
  • la méthode de Müller pour rechercher un zéro d'une fonction réelle d'une variable réelle. Plus précisément, son ordre de convergence est de 1,84.

Convergence quadratiqueModifier

Convergence quadratique — On dit qu'une suite   converge quadratiquement vers   si

la suite   est majorée

Clairement, toute suite convergeant quadratiquement converge superlinéairement.

Le résultat suivant fait le lien entre la convergence quadratique et le nombre   de chiffres significatifs corrects des itérés.

Convergence quadratique en termes de   — La suite   converge quadratiquement vers   pour la norme   si, et seulement si, il existe une constante   telle que

 ,

  est défini avec la norme  . Dans ce cas,

 .

De manière imagée, on peut exprimer verbalement la dernière inégalité en disant qu'une suite   convergeant quadratiquement a des éléments   dont le nombre de chiffres significatifs corrects double à chaque itération asymptotiquement. C'est une convergence très rapide puisque l'on atteint alors très vite le nombre maximal de chiffres significatifs qu'un ordinateur donné peut représenter (15..16 pour des nombres en double précision). Il est dès lors rarement utile d'avoir des suites convergeant plus rapidement.

Voici une manière de vérifier numériquement la convergence quadratique d'une suite par l'intermédiaire d'une fonction s'annulant au point limite.

Convergence quadratique en termes d'une fonction s'annulant au point limite — Soient   un point de   et   une fonction telle que   et telle que   pour   proche de  . Alors la suite   converge quadratiquement vers   si, et seulement si, il existe une constante   telle que

 .

Dans ce cas,

 .
Exemples d'algorithmes générant des suites quadratiquement convergentes

Typiquement, ce sont donc les algorithmes qui procèdent par linéarisation totale ou partielle des équations/inclusions à résoudre qui génèrent des suites convergeant quadratiquement.

BibliographieModifier

(en) J. M. Ortega et W. C. Rheinboldt, Iterative Solution of Nonlinear Equations in Several Variables, New York, Academic Press, (lire en ligne)