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

${\displaystyle S=\{s_{n}\}_{n\in \mathbb {N} }}$

de limite

${\displaystyle \lim _{n\to \infty }s_{n}=\ell ,}$

alors une suite accélérée est une deuxième suite

${\displaystyle S'=\{s'_{n}\}_{n\in \mathbb {N} }}$

qui converge plus vite vers ${\displaystyle \ell }$ que la première, ce qui se traduit par :

${\displaystyle \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 ${\displaystyle \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)^[1] et de Kummer (en)^[2], 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 XX^e siècle, dont l'extrapolation de Richardson, introduite par Lewis Fry Richardson au début du XX^e 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 XVIII^e siècle, l'epsilon algorithme de Peter Wynn en 1956, la transformation en u de Levin^[3] 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.^[4].

Exemple

Un exemple historique d'accélération de série a été appliquée au calcul de la constante d'Euler-Mascheroni :

${\displaystyle \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 000^e terme). La formule d'Euler-Maclaurin appliquée à la fonction logarithme permet d'obtenir l'égalité :

${\displaystyle \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 16^e 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

${\displaystyle 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 :

${\displaystyle \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 :

${\displaystyle \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)^[5].

Prolongements conformes

Une série

${\displaystyle S=\sum _{n=0}^{\infty }a_{n}}$

peut être vue comme l'évaluation en z = 1 d'une fonction f(z) définie par :

${\displaystyle 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

${\displaystyle 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^[6].

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 :

${\displaystyle \mathbb {A} :S\to S'=\mathbb {A} (S)={(s'_{n})}_{n\in \mathbb {N} }}$

définie par

${\displaystyle 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.

Notes et références

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Series acceleration » (voir la liste des auteurs).

1. (en) Milton Abramowitz et Irene Stegun, Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables [détail de l’édition] (lire en ligne), 3, eqn 3.6.27, 16
2. (en) Milton Abramowitz et Irene Stegun, Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables [détail de l’édition] (lire en ligne); 3, eqn 3.6.26, 16
3. (en) Ranjan Bhattacharya, Dhiranjan Roy et Siddhartha Bhowmick, « On the regularity of the levin U-transform », Computer Physics Communications, vol. 55, n^o 3,‎ octobre 1989, p. 297-301 (lire en ligne).
4. (en) Henri Cohen, Fernando Rodriguez Villegas et Don Zagier, « Convergence Acceleration of Alternating Series », Experimental Mathematics, vol. 9, n^o 1,‎ 2000, p. 3 (lire en ligne).
5. (en) William H. Press, et al., Numerical Recipes in C, Cambridge University Press, 1987 (ISBN 0-521-43108-5) (voir section 5.1).
6. (en) E.J. Weniger, « Mathematical properties of a new Levin-type sequence transformation introduced by Čı́žek, Zamastil, and Skála. I. Algebraic theory », Journal of Mathematical Physics, vol. 45, n^o 3,‎ 2004, p. 1209–1246

Voir aussi

Bibliographie

• C. Brezinski and M. Redivo Zaglia, Extrapolation Methods. Theory and Practice, North-Holland, 1991.
• G. A. Baker Jr. and P. Graves-Morris, Padé Approximants, Cambridge U.P., 1996.
• (en) Eric W. Weisstein, « Convergence Improvement », sur MathWorld
• H. H. H. Homeier, « Scalar Levin-type sequence transformations », Journal of Computational and Applied Mathematics, vol. 122,‎ 2000, p. 81 (DOI 10.1016/S0377-0427(00)00359-9, Bibcode 2000JCoAM.122...81H, arXiv math/0005209), « math/0005209 », texte en accès libre, sur arXiv..

Articles connexes

• Transformation de Shanks
• Extrapolation polynomiale minimale (en)
• Transformation de van Wijngaarden
• Sommation d'Ewald

Liens externes

• Convergence acceleration of series
• GNU Scientific Library, Series Acceleration
• Digital Library of Mathematical Functions

• Portail de l'analyse