Transformation de Shanks

En analyse numérique, la transformation de Shanks est une méthode non linéaire d'accélération de la convergence de suites numériques. Cette méthode est nommée d'après Daniel Shanks, qui l'exposa en 1955, bien qu'elle ait été étudiée et publiée par R. J. Schmidt dès 1941. C'est une généralisation de l'algorithme Delta-2 d'Aitken.

Présentation 

Soit une suite numérique () dont on cherche à connaitre la limite . 
La transformée de Shanks d'ordre  de cette suite est donnée par le rapport de deux déterminants :

avec  et

Propriétés

Modèle de convergence 
La transformée de Shanks d'ordre  donne exactement la limite de la suite d'origine  si celle-ci vérifie l'équation aux différences linéaire à coefficients constants d'ordre  du type :
 avec les constantes arbitraires  telles que   
 
Ce modèle de comportement de convergence possède  inconnues. En évaluant l'équation ci-dessus pour , on obtient l'expression de la transformée de Shanks  en résolvant l'inconnue  dans le système obtenu.

En résolvant l'équation aux différences linéaire, on peut expliciter la forme de  pour laquelle la transformée de Shanks d'ordre  fournit la limite exacte :

Les  étant les  racines du polynôme ,  étant un polynôme arbitraire en , dont le degré  est la multiplicité de la racine . Les racines pouvant être complexes, le comportement de  englobe de nombreuses formes : combinaisons linéaires d'exponentielles décroissantes ou croissantes avec des sinusoïdes amorties ou amplifiées.

Lien avec la table de Padé 
Lorsque la suite à accélérer est la somme partielle d'un développement en série entière d'une fonction :

alors, les différentes transformées de Shanks de la suite constituent le tableau de Padé de la série :

avec  l'approximant de Padé d'indice  de  (la fraction rationnelle de degré  au numérateur et  au dénominateur dont le développement limité coïncide avec celui de  jusqu'au degré ). La transformation de Shanks fournit donc un moyen de calculer les différents approximants de Padé d'une fonction dont on connait le développement limité.

Cas de convergence démontrée 

L'accélération de la convergence de la transformation de Shanks a été démontrée pour certains types de suite, notamment les suites totalement monotones ( est totalement monotone si ) et les suites totalement oscillantes ( est totalement oscillante si  est totalement monotone).

S'il existe des constantes  et  telles que la suite  soit totalement monotone ou oscillante, et si

(la convergence n'est pas de type logarithmique) alors les lignes, colonnes et diagonales du tableau des transformées de Shanks convergent vers la limite de la suite d'origine, et cela plus vite que, respectivement, les lignes, colonnes et diagonales précédentes.

Algorithmes de calcul 

En pratique, le calcul des déterminants étant assez gourmand, la transformée de Shanks n'est effectivement calculée de cette manière que pour de faibles valeurs de , notamment pour  où l'on obtient le Δ d'Aitken. En effet :

La deuxième expression donnée plus haut de la transformée est un rapport de deux déterminants possédant une structure particulière, et qui entrent dans la catégorie des déterminants de Hankel. Il existe une relation de récurrence entre les déterminants de Hankel qui permet ainsi de calculer la transformée de Shanks plus économiquement.

Mais surtout, la méthode la plus utilisée pour calculer la transformée de Shanks est l'ε-algorithme de Peter Wynn :

L'ε-algorithme se prête particulièrement bien au calcul dans un tableur. Dans l'ε-algorithme, seuls les indices  pairs fournissent des résultats intéressants, les autres servant d'intermédiaires de calcul.  

Plusieurs autres algorithmes peuvent servir à calculer les transformées de Shanks (q-d algorithme de Rutishauser, η-algorithme de Bauer...). La règle de la croix peut être aussi utilisée :

.

Exemples

Accélération de la convergence d'une suite

Extension du domaine de convergence d'un développement en série entière 
Le développement en série entière de la fonction arc tangente
 
a un rayon de convergence égal à . Le calcul des transformées de Shanks de ce développement va fournir le tableau de Padé de la fonction arc tangente, dont certains éléments peuvent converger au-delà de . Par exemple, pour , on a :

Malgré la divergence manifeste de la série à accélérer, on constate que sa transformée de Shanks converge vers la valeur de . On obtient ainsi une partie de la table de Padé de la fonction arc tangente (l'autre partie peut être calculée en continuant l'ε-algorithme pour les  négatifs). Dans cet exemple, la meilleure estimation étant obtenue pour , correspondant à la diagonale du tableau de Padé. Il est important de calculer la suite  ainsi que les transformées successives en double précision (ou plus) afin de minimiser les propagations d'erreur d'arrondi dont l'algorithme a tendance à amplifier.

Application répétée et itérée 
La transformation de Shanks est une transformation de suite à suite : le résultat est donc une suite (qui contient moins de terme que la suite originale). Il peut venir à l'idée de refaire subir à la suite résultante une nouvelle transformation de Shanks : on appelle ceci une application répétée de la transformation de Shanks.

En reprenant la première ligne  du tableau précédent comme nouvelle suite initiale, on obtient : 

On constate une amélioration du résultat, ceci sans calculer de nouveaux termes de la série d'arc tangente (les calculs ont été effectués avec plus de chiffres significatifs que ceux affichés).

Une autre possibilité consiste à limiter l'ordre  des transformées. La dernière colonne calculée  servira alors de suite initiale pour une nouvelle transformation, poussée jusqu'à l'ordre , et ainsi de suite. On appelle ceci une application itérée de la transformée de Shanks d'ordre . On prend le plus souvent , c'est-à-dire que l'on itère le Δ d'Aitken.

En reprenant l'exemple de , on trouve :

Dans ce cas précis, l'application itérée du Δ d'Aitken donne de meilleurs résultats que la transformée de Shanks équivalente. 
Les applications répétées et itérées sont particulièrement sensibles à la propagation d'erreurs d'arrondi.

Accélération de la convergence d'une série de Fourier 
Les sommes partielles d'une série de Fourier peuvent fournir une suite qui peut être accélérée par la transformée de Shanks. Cependant, une manière plus logique de procéder est de transformer, par un changement de variable, la série de Fourier en une série entière. Les transformées de Shanks de cette série entière en fourniront sa table de Padé.

La série de Fourier :
 

se transforme en une série entière

 
dont la partie réelle est la valeur cherchée.

Par exemple, la fonction en dents de scie sur , dont la série de Fourier vaut :

devient après changement de variable la série entière :

dont on pourra accélérer la convergence en utilisant la transformation de Shanks (avec des nombres complexes).

Avec les six premiers termes de la série de Fourier :

on trouve, en explicitant la transformée de Shanks :

 

dont la partie réelle, en revenant à la variable , forme une fraction rationnelle trigonométrique :

.

On constate sur le graphique ci-contre une nette accélération de la convergence de la transformée de Shanks par rapport à la série initiale.

Notes

Référence

Articles connexes 
 ε-algorithme
 Delta-2
 Extrapolation de Richardson
 Approximant de Padé

Analyse numérique
Shanks