Vitesse de convergence des suites

Cette section décrit quelques notions de vitesse de convergence d'une suite ${\displaystyle \left(x_{k}\right)}$ d'un espace vectoriel normé ${\displaystyle \left(E,\|\cdot \|\right)}$, vers sa limite ${\displaystyle x_{*}}$, fondées sur la comparaison de la norme de l'erreur ${\displaystyle x_{k}-x_{*}}$ de deux éléments successifs. L'erreur est toujours supposée non nulle : ${\displaystyle x_{k}\neq x_{*}}$, pour tout indice ${\displaystyle k}$. 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 ${\displaystyle x_{k}=x_{*}}$, la suite devient stationnaire après ${\displaystyle x_{k}}$ (tous les itérés suivants sont égaux à ${\displaystyle x_{*}}$ et il n'y a plus de sens à parler de vitesse de convergence). On s'intéresse donc au quotient

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

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

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

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

Nombre de chiffres significatifs corrects — Le nombre de chiffres significatifs corrects de ${\displaystyle x_{k}}$ par rapport à ${\displaystyle x_{*}\neq 0}$ est le nombre réel défini par

${\displaystyle \sigma _{k}:=-\log _{10}\,{\frac {\|x_{k}-x_{*}\|}{\|x_{*}\|}}}$.

Lorsque ${\displaystyle x_{*}\neq 0}$, on peut exprimer les vitesses de convergence en quotient en utilisant ${\displaystyle \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 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 ${\displaystyle x_{*}}$ ; 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 ${\displaystyle f:E\to F}$, c'est-à-dire à trouver un point ${\displaystyle x_{*}}$ tel que

${\displaystyle f(x_{*})=0}$,

pourvu que

${\displaystyle f(x)\sim (x-x_{*})}$.

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