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

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

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

$u_{n}=L+\epsilon$, avec $\epsilon$ l'erreur d'approximation.

L'erreur d'approximation de l'équation précédente peut être aussi bien positive que négative. Par exemple, si j'ai $u_{n}=2.23$ et L = 2, l'erreur d'approximation est positive et égale à 0.23. Par contre, si j'ai $u_{n}=1.50$ et $L=2$, 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 :

$\epsilon _{a}=|a-b|$, avec a la valeur exacte 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 :

$\epsilon _{r}={\frac {|a-b|}{|a|}}$, avec a la valeur exacte et b une valeur approchée de a.

Appliqué à une suite $u_{n}$ qui converge vers L, on trouve alors :

$\epsilon _{a}=|u_{n}-L|$, avec L la limite.

$\epsilon _{r}={\frac {|u_{n}-L|}{|L|}}={\frac {|u_{n}|}{|L|}}-1$, 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.

La vitesse de convergence

L'erreur d'approximation absolue diminue avec le rang, ce qui fait que les deux erreurs d'approximation absolues $|u_{n}-L|$ et $|u_{n+1}-L|$ 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 $(u_{n})$ converge rapidement. L'idée est de comparer ces deux différences entre deux rangs, en utilisant leur rapport $|u_{n+1}-L| \over |u_{n}-L|$. La vitesse de convergence est définie par la limite de ce quotient quand n tend vers l’infini.

$Q=\lim _{n\to \infty }{\frac {|u_{n+1}-L|}{|u_{n}-L|}}$

On distingue plusieurs vitesses de convergences, selon que la limite $0=Q$, $0<Q<1$, $Q=1$ (le cas où $Q>1$ 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 $K\in {]0,1[}$, 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	$\lim _{n\to \infty }{\frac {|u_{n+1}-L|}{|u_{n}-L|}}=1$
Convergence linéaire	$0<\lim _{n\to \infty }{\frac {|u_{n+1}-L|}{|u_{n}-L|}}<1$
Convergence supralinéaire	$\lim _{n\to \infty }{\frac {|u_{n+1}-L|}{|u_{n}-L|}}=0$

Convergence linéaire

Pour le dire autrement, une suite a une convergence linéaire si, au-delà d'un certain rang, il existe $k\in {]0,1[}$ tel que :

$|u_{n+1}-L|\leq k\cdot |u_{n}-L|$

Cette équation nous dit qu'une suite $(u_{n})$ est linéairement convergente si $(|u_{n}-L|)$ 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 $k$ plus petit que 1, mais positif. Le coefficient $k$ est appelé le taux de convergence de la suite.

Convergence supra-linéaire

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 $\alpha$, qui dépend de la suite.

$\lim _{n\to \infty }{\frac {|u_{n+1}-L|}{|u_{n}-L|^{\alpha }}}=k$

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

$|u_{n+1}-L|\leq k\cdot |u_{n}-L|^{\alpha }$

Suivant la valeur du coefficient $\alpha$, on distingue

• les suites à convergence quadratique, pour lesquelles $\alpha =2$ ;
• les suites à convergence cubique, pour lesquelles $\alpha =3$ ;
• les suites à convergence quartique, pour lesquelles $\alpha =4$ ;
• etc.

Convergence quadratique	$\lim _{n\to \infty }{\frac {|u_{n+1}-L|}{|u_{n}-L|^{2}}}=K$	$|u_{n+1}-L|\leq k\cdot |u_{n}-L|^{2}$
Convergence cubique	$\lim _{n\to \infty }{\frac {|u_{n+1}-L|}{|u_{n}-L|^{3}}}=K$	$|u_{n+1}-L|\leq k\cdot |u_{n}-L|^{3}$
Convergence quartique	$\lim _{n\to \infty }{\frac {|u_{n+1}-L|}{|u_{n}-L|^{4}}}=K$	$|u_{n+1}-L|\leq k\cdot |u_{n}-L|^{4}$

Comparer la vitesse de convergence de deux suites

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 $(u_{n})$ à une suite de référence $(v_{n})$. Les suites de références auxquelles on compare les suites sont les suivantes :

Convergence lente		Convergence géométrique	Convergence rapide
$u_{n}={\frac {1}{(\ln n)^{a}}}$	$u_{n}={\frac {1}{n^{a}}}$	$u_{n}=k^{n}$, avec $0<k<1$	$u_{n}={\frac {1}{n!}}$	$u_{n}={\frac {1}{n^{n}}}$	$u_{n}=k^{2^{n}}$, avec $0<k<1$

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 $O\left({\frac {1}{n^{a}}}\right)$ (dominée par la suite définie par $u_{n}={\frac {1}{n^{a}}}$) converge lentement.

Suites dominées, équivalentes et négligeables

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

	Notation	Première définition	Seconde définition	Troisième définition
$(u_{n})$ est dominée par $(v_{n})$	$u_{n}=O(v_{n})$	$\lim _{n\to \infty }{\frac {u_{n}}{v_{n}}}\rightarrow K$, avec K un réel quelconque.	Au-delà d'un certain rang $N$, il existe une constante M telle que : $u_{n}<M\cdot v_{n}$	Il existe une suite $a_{n}$ bornée telle que : $u_{n}=a_{n}\cdot v_{n}$
$(u_{n})$ est négligeable devant $(v_{n})$	$u_{n}=o(v_{n})$	$\lim _{n\to \infty }{\frac {u_{n}}{v_{n}}}\rightarrow 0$	Il existe un rang au-delà duquel on a, pour tout $\epsilon >0$ : $u_{n}<\epsilon \cdot v_{n}$	Il existe une suite $\epsilon _{n}$ qui converge vers zéro telle que : $u_{n}=\epsilon _{n}\cdot v_{n}$
$(u_{n})$ est équivalente à $(v_{n})$	$u_{n}\sim v_{n}$	$\lim _{n\to \infty }{\frac {u_{n}}{v_{n}}}\rightarrow 1$		Il existe une suite $\nu _{n}$ qui converge vers 1 telle que : $u_{n}=\nu _{n}\cdot v_{n}$

À partir de la définition de l'équivalence, on peut démontrer que deux suites équivalentes ont la même limite. Ainsi, si $\lim _{n\rightarrow \infty }u_{n}=L$ et que $u_{n}\sim v_{n}$, alors on sait que $\lim _{n\rightarrow \infty }v_{n}=L$.

Les relations entre dominance, négligeabilité et équivalence

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 $(u_{n})$ est négligeable devant $(v_{n})$, alors elle est aussi dominée par $(v_{n})$.

$u_{n}=o(v_{n})\implies u_{n}=O(v_{n})$

• Si deux suites sont équivalentes, alors l'une domine l'autre et réciproquement.

$u_{n}\sim v_{n}\implies u_{n}=O(v_{n}),v_{n}=O(u_{n})$

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 :

$a_{n}=o(b_{n}),b_{n}=o(c_{n})\implies a_{n}=o(c_{n})$

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é : $a_{n}\sim b_{n},b_{n}\sim c_{n}\implies a_{n}\sim c_{n}$

Réflexivité : $a_{n}\sim a_{n}$

Symétrie : $a_{n}\sim b_{n}\equiv b_{n}\sim a_{n}$

Opérations avec l'équivalence, la négligeabilité et la dominance

Négligeabilité :

On peut démontrer qu'une combinaison linéaires de suites négligeables devant $(u_{n})$ est aussi négligeable devant $(u_{n})$ :

$a\times (a_{n})+\times (b_{n})=o(u_{n})$, sous condition que $a_{n}=o(u_{n})/math>et<math>b_{n}=o(u_{n})$.

Il en est de même pour le produit d'une suite $(a_{n})$ par une suite négligeable devant $(u_{n})$ :

$b_{n}\times (a_{n})=o(u_{n})$, sous condition que $a_{n}=o(u_{n})$ (mais on n'a pas besoin que $b_{n}=o(u_{n})$).

Équivalence :

On peut noter que les relations suivantes sont équivalentes :

• $u_{n}\sim v_{n}$
• $u_{n}=v_{n}+o(v_{n})$
• $v_{n}=u_{n}+o(u_{n})$
• $u_{n}-v_{n}=o(v_{n})$
• $v_{n}-u_{n}=o(u_{n})$

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 $u_{n}\sim w_{n}$ et $v_{n}\sim w_{n}$, on ne peut PAS en déduire que $u_{n}+v_{n}\sim 2\cdot w_{n}$. 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 : $u_{n}\sim a_{n}$ et $v_{n}\sim b_{n}$ :

• $u_{n}\cdot v_{n}\sim a_{n}\cdot b_{n}$
• ${\frac {u_{n}}{a_{n}}}\sim {\frac {v_{n}}{b_{n}}}$
• $u_{n}^{a}\sim v_{n}^{a}$

Les chiffres significatifs de l'approximation

Si l'approximation est suffisante, $u_{n}$ 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 $u_{n}$ 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 $\pi =3.141592653589793238462643383279502884...$. Si j'ai $u_{7}=3.1415926719457$, 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 $u_{1}0=3.14159265357817$, puis $u_{1}5=3.141592653589793235$, etc.

Si on connaît l'erreur d'approximation et la limite, on peut calculer le nombre de chiffres significatifs de $u_{n}$ après la virgule.

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

$\sigma _{n}=-\log {\epsilon _{r}}=-\log _{10}{\frac {|u_{n}-L|}{|L|}}$

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

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 :

$\sigma _{n+1}=\sigma _{n}+k$, avec k une constante positive non-nulle (k > 0).

Pour une convergence supra-linéaire :

$\lim _{n\to \infty }\sigma _{n+1}-\sigma _{n}=0$

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

$\lim _{n\to \infty }{\frac {\sigma _{n+1}}{\sigma _{n}}}\geq \alpha$, avec $\alpha$ l'ordre de convergence.

Démonstration

Pour le démontrer, partons de l'équation : $|u_{n+1}-L|\leq k\cdot |u_{n}-L|^{\alpha }$ Divisons des deux côtés par L : ${\frac {|u_{n+1}-L|}{L}}\leq k\cdot {\frac {|u_{n}-L|^{\alpha }}{L}}$ En prenant l'opposé du logarithme, on a : $-\log _{10}{\frac {|u_{n+1}-L|}{L}}\geq -\log _{10}\left(k\cdot {\frac {|u_{n}-L|^{\alpha }}{L}}\right)$ On utilise la formule $\log {(x\cdot y)}=\log {x}+\log {y}$ : $-\log _{10}{\frac {|u_{n+1}-L|}{L}}\geq -\left(\log _{10}{\frac {|u_{n}-L|^{\alpha }}{L}}+\log _{10}k\right)$ Simplifions : $-\log _{10}{\frac {|u_{n+1}-L|}{L}}\geq -\left(\alpha \cdot \log _{10}{\frac {|u_{n}-L|}{L}}+\log _{10}[L^{\alpha -1}k]\right)$ On applique la formule $\sigma _{n}=-\log _{10}{\frac {|u_{n}-L|}{L}}$ : $\sigma _{n+1}\geq \alpha \cdot \sigma _{n}-\log _{10}[L^{\alpha -1}k]$ Divisons maintenant par $\sigma _{n}$ : ${\frac {\sigma _{n+1}}{\sigma _{n}}}\geq \alpha -{\frac {\log _{10}[L^{\alpha -1}k]}{\sigma _{n}}}$ Puisque $\sigma _{n}$ tend vers l'infini par hypothèse, on déduit en passant à la limite que: $\lim _{n\to \infty }{\frac {\sigma _{n+1}}{\sigma _{n}}}\geq \alpha$, ce qu'il fallait démontrer.