Vitesse de convergence des suites

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En analyse numérique, qui est 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 ; plus précisément, tous ses éléments sont 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.

Vitesse de convergence en quotient[modifier | modifier le code]

Cette section décrit quelques notions de vitesse de convergence d'une suite \{x_k\}_{k\geqslant 1} d'un espace normé \mathbb{E}, vers sa limite x_*, fondées sur la comparaison de la norme de l'erreur x_k-x_* de deux éléments successifs. La norme de \mathbb{E} est notée \|\cdot\|. L'erreur est toujours supposée non nulle : x_k\ne x_*, pour tout indice k. Cette hypothèse est raisonnable lorsque la suite est générée par un algorithme bien conçu, car dès que x_k=x_*, la suite devient stationnaire après x_k (tous les itérés suivants sont égaux à x_*) et il n'y a plus de sens à parler de vitesse de convergence. On s'intéresse donc au quotient


\frac{\|x_{k+1}-x_*\|}{\|x_k-x_*\|^\alpha},

\alpha 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 x_* des fonctions définissant le problème que l'on cherche à résoudre et dont x_* est solution. Évidemment, plus \alpha est grand, plus la vitesse de convergence est rapide (car asymptotiquement \|x_k-x_*\|<1).

Brièvement, on dit que le q-ordre de convergence est \alpha>1 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 \|\cdot\|, un réel \tau\in{[0,1[} et un indice k_1\geqslant 1, tels que pour tout k\geqslant k_1, on a \|x_{k+1}-x_*\|\leqslant \tau\|x_k-x_*\|,
  • superlinéaire si \|x_{k+1}-x_*\|/\|x_k-x_*\|\to0,
  • quadratique (q-ordre 2) s'il existe une constante C>0, tels que pour tout k\geqslant 1, on a \|x_{k+1}-x_*\|\leqslant C\|x_k-x_*\|^2,
  • cubique (q-ordre 3) s'il existe une constante C>0, tels que pour tout k\geqslant 1, on a \|x_{k+1}-x_*\|\leqslant C\|x_k-x_*\|^3,
  • quartique (q-ordre 4) s'il existe une constante C>0, tels que pour tout k\geqslant 1, on a \|x_{k+1}-x_*\|\leqslant C\|x_k-x_*\|^4, etc.

Numériquement, plus la convergence est rapide, plus le nombre de chiffres significatifs corrects de x_k (ceux identiques à ceux de x_*) augmente vite. Donnons une définition plus précise de cette notion. Si x_k 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 \mathbb{E}. On suppose que x_*\ne0 car on ne peut définir ce que sont les chiffres significatifs de zéro. Si \|x_k-x_*\|/\|x_*\| vaut 10^{-4}, on dira que x_k a 4 chiffres significatifs corrects (ce serait effectivement le cas si x_k et x_* étaient des scalaires). Ceci conduit à la définition suivante.

Nombre de chiffres significatifs corrects — Le nombre de chiffres significatifs corrects de x_k par rapport à x_*\ne0 est le nombre réel défini par


\sigma_k:=-\log_{10}\,\frac{\|x_k-x_*\|}{\|x_*\|}.

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

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 q-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 q-quadratique est alors une indication sur la correction du calcul des dérivées. Comme on ne connaît pas la solution, on ne peut vérifier la vitesse de convergence en quotient attendue par l'examen du quotient de la norme des erreurs successives, qu'en résolvant deux fois le problème ; la première fois pour calculer une approximation précise de la solution x_*, la seconde pour faire l'examen des quotients sus-mentionnés ; c'est dommage. 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


F:\mathbb{E}\to\mathbb{E},

pourvu que


F(x) \sim (x-x_*).

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

Les trois principales vitesses de convergence en quotient sont les vitesses de convergence q-linéaire, q-superlinéaire et q-quadratique.

Convergence q-linéaire[modifier | modifier le code]

Cette vitesse de convergence est parfois appelée convergence géométrique, car la norme de l'erreur \|x_k-x_*\| est majorée asymptotiquement par une suite géométrique de raison \tau.

Convergence q-linéaire — On dit qu'une suite \{x_k\}_{k\geqslant 1} converge q-linéairement vers x_* s'il existe une norme \|\cdot\|, un scalaire \tau\in[0,1[ et un indice k_1\geqslant 1 tels que pour tout k\geqslant k_1 on ait


\|x_{k+1}-x_*\|\leqslant \tau\|x_k-x_*\|.

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 \tau strictement plus petit que 1. Le scalaire \tau 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 \tau<1 pour une autre norme.

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

Convergence q-linéaire en termes de \sigma_k — La suite \{x_k\}_{k\geqslant 1} converge q-linéairement vers x_*\ne0 pour la norme \|\cdot\| si, et seulement si, il existe une constante \sigma>0 et un indice k_1\geqslant 1 tels que pour tout k\geqslant k_1 on ait


\sigma_{k+1} \geqslant \sigma_k + \sigma,

\sigma_k est défini avec la norme \|\cdot\|.

Exemples d'algorithmes générant des suites q-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 q-superlinéaire[modifier | modifier le code]

Convergence q-superlinéaire — On dit qu'une suite \{x_k\}_{k\geqslant 1} converge q-superlinéairement vers x_* si pour tout \tau>0, il existe un indice k_r\geqslant 1 tels que pour tout k\geqslant k_r on ait


\|x_{k+1}-x_*\|\leqslant \tau\|x_k-x_*\|.

Il revient au même de dire que le quotient


\frac{\|x_{k+1}-x_*\|}{\|x_k-x_*\|}\to 0.

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

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

Convergence q-superlinéaire en termes de \sigma_k — La suite \{x_k\}_{k\geqslant 1} converge q-superlinéairement vers x_*\ne0 pour la norme \|\cdot\| si, et seulement si,


\sigma_{k+1} - \sigma_k \to \infty,

\sigma_k est défini avec la norme \|\cdot\|.

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

Convergence q-superlinéaire en termes d'une fonction s'annulant au point limite — Soient x_*\in\mathbb{E} un point et F:\mathbb{E}\to\mathbb{E} une fonction telle que F(x_*)=0 et telle que F(x)\,\sim\,(x-x_*) pour x proche de x_*. Alors la suite \{x_k\} converge q-superlinéairement vers x_* pour la norme \|\cdot\| si, et seulement si,


\log\|F(x_{k+1})\|-\log\|F(x_k)\|\to-\infty.

On peut le dire autrement : la suite \{x_k\} converge q-superlinéairement si, et seulement si, le tracé k\mapsto\log\|F(x_k)\| a une majorante affine de pente négative arbitraire.

Exemples d'algorithmes générant des suites q-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 q-ordre de convergence est de 1,84.

Convergence q-quadratique[modifier | modifier le code]

Convergence q-quadratique — On dit qu'une suite \{x_k\}_{k\geqslant 1} converge q-quadratiquement vers x_* s'il existe une constant C\geqslant 0 telle que pour tout k\geqslant 1 on ait


\|x_{k+1}-x_*\|\leqslant C\|x_k-x_*\|^2.

Pour une suite q-quadratiquement convergente, le quotient


\frac{\|x_{k+1}-x_*\|}{\|x_k-x_*\|}\leqslant C\|x_k-x_*\|\to 0,

si bien qu'une suite convergeant q-quadratiquement converge q-superlinéairement.

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

Convergence q-quadratique en termes de \sigma_k — La suite \{x_k\}_{k\geqslant 1} converge q-quadratiquement vers x_*\ne0 pour la norme \|\cdot\| si, et seulement si, il existe une constante C\in\mathbb{R} telle que


\sigma_{k+1}\geqslant 2\sigma_k + C,

\sigma_k est défini avec la norme \|\cdot\|. Dans ce cas


\liminf_{k\to\infty}\;\frac{\sigma_{k+1}}{\sigma_k} \geqslant 2.

De manière imagée, on peut exprimer verbalement la dernière inégalité en disant qu'une suite \{x_k\} convergeant q-quadratiquement a des éléments x_k 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 q-quadratique d'une suite par l'intermédiaire d'une fonction s'annulant au point limite.

Convergence q-quadratique en termes d'une fonction s'annulant au point limite — Soient x_*\in\mathbb{E} un point et F:\mathbb{E}\to\mathbb{E} une fonction telle que F(x_*)=0 et telle que F(x)\,\sim\,(x-x_*) pour x proche de x_*. Alors la suite \{x_k\} converge q-quadratiquement vers x_* si, et seulement si, il existe une constante C\in\mathbb{R} telle que


\log\|F(x_{k+1})\|\leqslant 2\log\|F(x_k)\| + C.

Dans ce cas


\liminf_{k\to\infty}\,\frac{\log\|F(x_{k+1})\|}{\log\|F(x_k)\|}\geqslant 2.

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

Typiquement, ce sont donc les algorithmes qui procèdent par linéarisation des équations à résoudre qui génèrent des suites convergeant q-quadratiquement.

Annexes[modifier | modifier le code]

Article connexe[modifier | modifier le code]

Lien externe[modifier | modifier le code]

Ouvrage général[modifier | modifier le code]

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