Vitesse de convergence

En analyse numérique, la vitesse de convergence d'une suite représente la vitesse à laquelle les termes de la suite se rapprochent de sa limite. Bien que cet ordre de grandeur de vitesse de convergence ne fournisse pas d'information sur toute partie finie de l'ensemble des termes de la suite, ce concept a une grande importance pratique lorsque nous travaillons avec une suite d'approximations successives obtenue à partir d'une méthode itérative, car en général peu d'itérations sont nécessaires pour donner une valeur approchée intéressante lorsque la vitesse de convergence est grande.

Définition de la vitesse de convergence

Supposons que la suite (x_k) converge vers le nombre ξ.

On dit que cette suite converge linéairement vers ξ, s'il existe μ, 0 < μ < 1, tel que

$\lim_{k\to \infty} \frac{|x_{k+1}-\xi|}{|x_k-\xi|} = \mu \quad\quad (1)$

Le nombre μ est appelé vitesse de convergence.

Si (1) est vérifiée pour μ = 0, alors la convergence de la suite est dite super-linéaire. On dit aussi que la suite converge super-linéairement. Au contraire, on dit que la vitesse de convergence de la suite est sous-linéaire lorsque (1) n'est vérifiée pour aucun μ < 1.

La définition suivante sert à distinguer les différentes vitesses de convergence super-linéaires.

On dit que la suite de limite ξ est convergente d'ordre q pour q > 1 s'il existe μ > 0 tel que

$\lim_{k\to \infty} \frac{|x_{k+1}-\xi|}{|x_k-\xi|^q} = \mu \quad\quad (2)$

En particulier :

• la convergence d'ordre 2 est dite quadratique,
• la convergence d'ordre 3 est dite cubique,
• la convergence d'ordre 4 est dite quartique.

Commentaires

Dans la pratique, on espère rarement obtenir une convergence plus que quadratique, qui est déjà très satisfaisante. Une telle vitesse de convergence correspond à un doublement du nombre de chiffres précis à chaque étape, et donc typiquement une approximation de la limite à 30 décimales correctes après seulement 5 pas, si la valeur initiale est convenablement choisie. Un exemple célèbre de méthode qui converge quadratiquement est celui de la méthode de Newton.

Articles connexes

• Comparaison asymptotique
• Vitesse de convergence des suites