# Accélération de suite

En mathématiques, l'accélération de suite est une méthode de transformation de suites ou de série numérique visant à améliorer la vitesse de convergence d'une série. Des techniques d'accélération sont souvent utilisées en analyse numérique, afin d'améliorer la rapidité de méthodes d'intégration numérique ou obtenir des identités sur des fonctions spéciales. Par exemple, la transformation d'Euler appliquée à la série hypergéométrique permet de retrouver plusieurs identités connues.

## Définition

On considère une suite
    $S=\{s_{n}\}_{n\in \mathbb {N} }$
de limite
    $\lim _{n\to \infty }s_{n}=\ell ,$
alors une suite accélérée est une deuxième suite
    $S'=\{s'_{n}\}_{n\in \mathbb {N} }$
qui converge plus vite vers $\ell$ que la première, ce qui se traduit par :
    $\lim _{n\to \infty }{\frac {s'_{n}-\ell }{s_{n}-\ell }}=0.$
Si la suite S diverge, la transformation agit comme une méthode d'extrapolation vers l'antilimite $\ell$.
Les prolongements de la série originale vers la transformée peuvent être linéaires ou non. En général, les transformations non linéaires ont tendance à être plus efficaces.

## Présentation générale

Les techniques classiques d'accélération de séries sont les transformations d'Euler (ou binomiale) et de Kummer (en), et les méthodes de sommation (Césàro, Hölder, Toeplitz...), qui ont pour avantage d'être linéaires.
Une variété de méthodes plus rapides et spéciales ont été développées au XXe siècle, dont l'extrapolation de Richardson, introduite par Lewis Fry Richardson au début du XXe siècle mais aussi connue et utilisée par Katahiro Takebe en 1722, la méthode delta-2 d'Aitken, introduite par Alexander Aitken en 1926 mais aussi connue de Takakazu Seki au XVIIIe siècle, l'epsilon algorithme de Peter Wynn en 1956, la transformation en u de Levin et la méthode de Wilf-Zeilberger-Ekhad utilisant des identités hypergéométriques.
Pour les séries alternées, plusieurs techniques puissantes, donnant des vitesses de convergence de 5,828$^{-n}$ jusqu'à 17,93$^{-n}$ pour une sommation de n termes, décrites par Cohen et al..

### Exemple

Un exemple historique d'accélération de série a été appliquée au calcul de la constante d'Euler-Mascheroni :
    $\gamma =\lim _{n\rightarrow \infty }\left(\sum _{k=1}^{n}{\frac {1}{k}}-\ln(n)\right)=\lim _{n\rightarrow \infty }\sum _{k=1}^{n}\left[{\frac {1}{k}}-\ln \left(1+{\frac {1}{k}}\right)\right].$
Ces séries convergent très lentement (seuls trois décimales exactes après calcul du 100 000e terme). La formule d'Euler-Maclaurin appliquée à la fonction logarithme permet d'obtenir l'égalité :
    $\sum _{k=1}^{n}{\frac {1}{k}}-\ln(n)\sim \gamma +{\frac {1}{2n}}-\sum _{j=1}^{+\infty }{\frac {b_{2j}}{2j\,n^{2j}}},$
avec b$_{2j}$, les nombres de Bernoulli. Par cette méthode, les calculs ont pu aller jusqu'à la 16e décimale.

## Transformations linéaires

Une méthode de transformation linéaire de suites consiste à associer à la suite (s$_n$) une suite de la forme
    $s_{n}\longrightarrow s_{n}'=\sum _{k=0}^{n}\omega _{k}s_{k},{\textrm {avec}}\sum _{k=0}^{n}\omega _{k}=1.$
Elles ont l'avantage d'être indépendantes de la suite d'origine : les poids dans la somme sont constants et indépendants des valeurs de (s$_n$).
Les suites transformées ont une convergence accélérée si la suites d'origine est déjà convergente ou si les derniers termes ont les poids les plus forts.

### Exemple

La transformation binomiale est plutôt bien adaptée pour les séries alternées, on applique :
    $\sum _{n=0}^{\infty }(-1)^{n}a_{n}=\sum _{n=0}^{\infty }(-1)^{n}{\frac {\Delta ^{n}a_{0}}{2^{n+1}}}$
où Δ est l'opérateur de différentiation amont :
    $\Delta ^{n}a_{0}=\sum _{k=0}^{n}(-1)^{k}{n \choose k}a_{n-k}.$
Si la première série converge lentement, la deuxième a une vitesse bien plus forte.
Une façon particulièrement efficace d'implémenter numériquement la transformation binomiale est la transformation de van Wijngaarden (en).

## Prolongements conformes

Une série
    $S=\sum _{n=0}^{\infty }a_{n}$
peut être vue comme l'évaluation en z = 1 d'une fonction f(z) définie par :
    $f(z)=\sum _{n=0}^{\infty }a_{n}z^{n}.$
La fonction f(z) peut avoir des singularités sur le plan complexe qui borne le rayon de convergence de la série. Si le point z = 1 est proche de la frontière du disque de convergence, la série S converge lentement. On peut alors améliorer la convergence de la série par un prolongement conforme qui déplace les singularités de sorte que le point z = 1 soit plus loin du nouveau disque de convergence.
Le prolongement conforme z = Φ(w) doit vérifier Φ(0) = 0, et on choisit de préférence une fonction de dérivée finie en w = 0. On peut aussi choisir Φ(1) = 1 sans perte de généralité, car on peut changer l'échelle de w pour redéfinir Φ. On considère alors la fonction
    $g(w)=f\left(\Phi (w)\right)$
L'égalité Φ(1) = 1 implique f(1) = g(1). Le développement en série de g(w) en fixant z = Φ(w) dans le développement en série de f(z) car Φ(0) = 0 ; les n premiers termes du développement en série de f(z) permettront d'obtenir les n premiers termes du développement en série de g(w) si Φ'(0) ≠ 0. Fixer w = 1 dans le développement en série permettra d'obtenir une nouvelle série qui, si elle converge, convergera vers la même valeur que la série originale.

## Transformations non linéaires de suites

Parmi les transformations non linéaires de suites, on trouve les approximants de Padé, la transformation de Shanks et les transformations de suites de Levin.
Les transformations non linéaires de suites donnent des méthodes numériques pour la sommation de séries divergentes ou asymptotiques telles qu'en apparaissent dans la théorie des perturbations, et peuvent servir de méthodes d'extrapolation très efficaces.

### Méthode d'Aitken

Une transformation non linéaire de suite est l'extrapolation d'Aitken ou la méthode Delta-2 :
    $\mathbb {A} :S\to S'=\mathbb {A} (S)={(s'_{n})}_{n\in \mathbb {N} }$
définie par
    $s'_{n}=s_{n+2}-{\frac {(s_{n+2}-s_{n+1})^{2}}{s_{n+2}-2s_{n+1}+s_{n}}}.$
Cette transformation est utilisée pour augmenter le taux de convergence d'une suite convergeant lentement ; heuristiquement, elle élimine la plus grande partie de l'erreur absolue.