Les suites et séries/Annexe : la vitesse de convergence d'une suite

Un livre de Wikilivres.
Sauter à la navigation Sauter à la recherche

Si toutes les suites convergent, certaines le font plus rapidement que d'autres. Les termes des suites rapides arrivent rapidement à des valeurs proches de leur limite, alors que ce n'est pas le cas pour les suites lentes. Cette description intuitive n'est cependant pas facile à formaliser. Mais sa formalisation est particulièrement utile quand on doit analyser la convergence de certaines suites. C'est notamment le cas en analyse numérique, un domaine des mathématique assez complexe. C'est aussi utilisé dans le domaine du calcul numérique (à savoir le calcul sur ordinateur), qui fait un grand usage de suites pour calculer certains nombres. Par exemple, il existe des suites qui permettent de calculer certaines constantes mathématiques , comme pi, e, ou bien d'autres constantes utiles. Pour donner un autre exemple, la constante de Majorana, une constante de la physique des particules, se calcule avec une suite de ce genre. Il est préférable d'utiliser des suites qui convergent rapidement pour faire les calculs et c'est là que l'analyse de la vitesse de convergence devient utile.

L'erreur d'approximation[modifier | modifier le wikicode]

La définition formelle de la vitesse de convergence fait intervenir la différence entre un terme et la limite . Si est assez grand, est assez proche de la limite . On peut alors considérer que . Il est alors intéressant d'étudier l'erreur d'approximation, à savoir de combien le terme approximé se trompe par rapport à la valeur exacte de L. Intuitivement, on devine que :

, avec l'erreur d'approximation.

L'erreur d'approximation de l'équation précédente eut être aussi bien positive que négative. Par exemple, si j'ai et L = 2, l'erreur d'approximation est positive et égale à 0.23. Par contre, si j'ai et , l'erreur d'approximation est négative et égale à -0.5. Ce qui nous intéresse dans la suite du cours est la valeur absolue de l'erreur d'approximation. Celle-ci porte le nom d'erreur absolue.

L'erreur absolue est la valeur absolue de l'erreur d'approximation, comme mentionnée plus haut. Dans le cas général, elle vaut :

, avec a la valeur exacte a et b une valeur approchée de a.

L'erreur relative est l'erreur absolue, mais rapportée en valeur de a. Dans le cas général, elle vaut :

, avec a la valeur exacte a et b une valeur approchée de a.

Appliqué à une suite qui converge vers L, on trouve alors :

, avec L la limite.
, avec L la limite.

C'est l'erreur d'approximation absolue qui est utilisée pour définir la convergence de la suite. Cependant, l'erreur relative n'est pas inutile et nous servira quand on parlera du nombre de chiffres significatifs de l'approximation.

Vitesse de convergence[modifier | modifier le wikicode]

L'erreur d'approximation absolue diminue avec le rang, ce qui fait que les deux erreurs d'approximation absolues et seront différentes. Plus l'erreur d'approximation diminue d'un rang au suivant, plus l'erreur d'approximation diminue rapidement avec le rang n et plus la suite converge rapidement. L'idée est de comparer ces deux différences entre deux rangs, en utilisant leur rapport . La vitesse de convergence est définie par la limite de ce quotient quand n tend vers l’infini.

On distingue plusieurs vitesses de convergences, selon que la limite , , (le cas où implique une suite divergente).

  • Si la limite est égale à 1, alors la suite a une convergence infra-linéaire, aussi appelée convergence lente.
  • Si la limite est une constante K telle que , la suite a une convergence linéaire, aussi appelée convergence géométrique (on verra qu'il y a un lien avec les suites géométriques dans ce qui suit).
  • Si la limite est égale à 0, alors la suite a une convergence supra-linéaire, aussi appelée convergence rapide.
Convergence infralinéaire
Convergence linéaire
Convergence supralinéaire

Convergence linéaire[modifier | modifier le wikicode]

Pour le dire autrement, une suite a une convergence linéaire si, au-delà d'un certain rang, il existe tel que :

Cette équation nous dit qu'une suite est linéairement convergente si est bornée par une suite géométrique. Pour le dire en français, l'erreur d'approximation (sa valeur absolue, pour être précis) est bornée par une suite géométrique. L'erreur d'approximation diminue donc en passant au rang suivant, avec un taux de décroissance plus petit que 1, mais positif. Le coefficient est appelé le taux de convergence de la suite.

Convergence supra-linéaire[modifier | modifier le wikicode]

Il est possible de classer les convergences supra-linéaires en modifiant quelque peu l'équation. Il suffit d'élever le dénominateur de l'expression précédente à une certaine puissance , qui dépend de la suite.

On peut reformuler cette équation de la même manière que pour les suites linéairement convergentes, ce qui donne :

Suivant la valeur du coefficient , on distingue

  • les suites à convergence quadratique, pour lesquelles  ;
  • les suites à convergence cubique, pour lesquelles  ;
  • les suites à convergence quartique, pour lesquelles  ;
  • etc.
Convergence quadratique
Convergence cubique
Convergence quartique

Comparer la vitesse de convergence de deux suites[modifier | modifier le wikicode]

Il est parfois intéressant de comparer la vitesse de convergence de deux suites, pour savoir laquelle converge le plus vite. Les informaticiens font cela souvent, sans même le savoir, en comparant le comportement asymptotique de deux algorithmes (leur complexité algorithmique, pour être précis). Dans ce qui va suivre, nous allons comparer une suite à une suite de référence . Les suites de références auxquelles on compare les suites sont les suivantes :

Convergence lente Convergence géométrique Convergence rapide
, avec , avec

Chaque suite converge plus rapidement que les précédentes. On peut déterminer si une suite converge lentement, rapidement ou de manière géométrique en la comparant aux suites du tableau. Par exemple, on sait qu'une suite en (dominée par la suite définie par ) converge lentement.

Suites dominées, équivalentes et négligeables[modifier | modifier le wikicode]

Nous allons maintenant introduire les notions qui permettent de comparer les vitesses de convergence de deux suites. Prenons deux suites et , avec la suite de référence, à laquelle on compare . Les relations de dominance, négligeabilité et d'équivalence sont déterminée par la valeur de la limite : . Tout dépend si elle est finie, nulle ou égale à 1.

Notation Première définition Seconde définition Troisième définition
est dominée par , avec K un réel quelconque. Au-delà d'un certain rang , il existe une constante M telle que :
Il existe une suite bornée telle que :
est négligeable devant Il existe un rang au-delà duquel on a, pour tout  :
Il existe une suite qui converge vers zéro telle que :
est équivalente à Il existe une suite qui converge vers 1 telle que :

A partir de la définition de l'équivalence, on peut démontrer que deux suites équivalentes ont la même limite. Ainsi, si et que , alors on sait que .

Les relations entre dominance, négligeabilité et équivalence[modifier | modifier le wikicode]

Vous remarquerez que la négligeabilité et l'équivalence sont deux cas particuliers de dominance. Ce qui est à l'origine des deux propriétés suivantes :

  • Si une suite est négligeable devant , alors elle est aussi dominée par .
  • Si deux suites sont équivalentes, alors l'une domine l'autre et réciproquement.
Attention : la réciproque est fausse. Il existe des suites qui se dominent mutuellement, sans pour autant être équivalentes.

On peut démontrer que la négligeabilité est transitive :

L'équivalence de deux suites est, quant à elle, une relation transitive, réflexive (une suite est équivalente à elle-même) et symétrique (c'est donc une relation dite d'équivalence, d'où son nom).

Transitivité :
Réflexivité :
Symétrie :

Opérations avec l'équivalence, la négligeabilité et la dominance[modifier | modifier le wikicode]

Négligeabilité :

On peut démontrer qu'une combinaison linéaires de suites négligeables devant est aussi négligeable devant  :

, sous condition que .

Il en est de même pour le produit d'une suite par une suite négligeable devant  :

, sous condition que (mais on n'a pas besoin que ).

Equivalence :

On peut noter que les relations suivantes sont équivalentes :

Les relations au-delà de la première sont appelées des développements asymptotiques de l'équivalence. On voit avec ces relations que l'on ne peut pas additionner ou soustraire des suites équivalentes. Par exemple, si et , on ne peut PAS en déduire que . Les seules opérations que l'on peut faire dans ce genre de situation sont les multiplications, les quotients et les élévations à la puissance. Ainsi, si on a : et  :

Les chiffres significatifs de l'approximation[modifier | modifier le wikicode]

Si l'approximation est suffisante, et L ont des chiffres en communs et ne différent que par des chiffres les plus à droite. Pour rappel, les chiffres communs entre l'approximation et la cible (la limite L) sont appelés des chiffres significatifs. Plus le rang augmente, plus le nombre de chiffres significatifs augmente : des chiffres qui étaient erronés aux rangs précédents vont devenir corrects. L'approximation s'affinera progressivement, d'un rang à l'autre. Par exemple, prenons une suite qui me permet de calculer . Si j'ai , je n'ai que 8 chiffres significatifs corrects. En augmentant le rang, je vais avoir de plus en plus de chiffres qui vont devenir significatifs. Par exemple, je vais avoir , puis , etc.

Si on connait l'erreur d'approximation et la limite, on peut calculer le nombre de chiffres significatifs de après la virgule.

Celui-ci est définit par le logarithme de l'erreur relative (en fait, son opposé) :

Attention : cette formule ne vaut que si la limite est non-nulle, sans quoi on obtient une division par zéro.

Le lien avec la vitesse de convergence[modifier | modifier le wikicode]

Il existe un lien entre le nombre de chiffres significatifs et la vitesse de convergence.

Pour une convergence linéaire, au-delà d'un certain rang :

, avec k une constante positive non-nulle (k > 0).

Pour une convergence supra-linéaire :

Pour une convergence infra-linéaire, au-delà d'un certain rang :

, avec l'ordre de convergence.


Démonstration

Pour le démontrer, partons de l'équation :

Divisons des deux côtés par L :

En prenant l'opposé du logarithme, on a :

On utilise la formule  :

Simplifions :

On applique la formule  :

Divisons maintenant par  :

Prenons la limite.

La limite du terme : tend vers zéro, ce qui donne :

, ce qu'il fallait démontrer.