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^[1], bien qu'elle ait été étudiée et publiée par R. Schmidt en 1941^[2].C'est une généralisation de l'algorithme Delta-2 d'Aitken.

Présentation

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

$e_k(A_n) = \frac{ \begin{vmatrix} A_{n} & \cdots & A_{n+k-1} & A_{n+k} \\ \Delta A_{n} & \cdots & \Delta A_{n+k-1} & \Delta A_{n+k} \\ \Delta A_{n+1} & \cdots & \Delta A_{n+k} & \Delta A_{n+k+1} \\ \vdots & & \vdots & \vdots \\ \Delta A_{n+k-1} & \cdots & \Delta A_{n+2k-2} & \Delta A_{n+2k-1} \\ \end{vmatrix} }{ \begin{vmatrix} 1 & \cdots & 1 & 1 \\ \Delta A_{n} & \cdots & \Delta A_{n+k-1} & \Delta A_{n+k} \\ \Delta A_{n+1} & \cdots & \Delta A_{n+k} & \Delta A_{n+k+1} \\ \vdots & & \vdots & \vdots \\ \Delta A_{n+k-1} & \cdots & \Delta A_{n+2k-2} & \Delta A_{n+2k-1} \\ \end{vmatrix} } = \frac{ \begin{vmatrix} A_{n} & \cdots & A_{n+k-1} & A_{n+k} \\ A_{n+1} & \cdots & A_{n+k} & A_{n+k+1} \\ A_{n+2} & \cdots & A_{n+k+1} & A_{n+k+2} \\ \vdots & & \vdots & \vdots \\ A_{n+k} & \cdots & A_{n+2k-1} & A_{n+2k} \\ \end{vmatrix} }{ \begin{vmatrix} \Delta^2 A_{n} & \cdots & \Delta^2 A_{n+k-2} & \Delta^2 A_{n+k-1} \\ \Delta^2 A_{n+1} & \cdots & \Delta^2 A_{n+k-1} & \Delta^2 A_{n+k} \\ \Delta^2 A_{n+2} & \cdots & \Delta^2 A_{n+k} & \Delta^2 A_{n+k+1} \\ \vdots & & \vdots & \vdots \\ \Delta^2 A_{n+k-1} & \cdots & \Delta^2 A_{n+2k-3} & \Delta^2 A_{n+2k-2}\\ \end{vmatrix} },$

avec ΔA_p = A_{p + 1} − A_p et Δ²A_p = ΔA_{p + 1} − ΔA_p.

Propriétés

• Modèle de convergence

La transformée de Shanks d'ordre k donne exactement la limite de la suite d'origine A_n si celle-ci vérifie l'équation aux différences linéaire à coefficient constant d'ordre k du type :

$\sum_{p=0}^k a_p (A_{n+p}-A)=0 \text{ }\forall n \text{ }$ avec les constantes arbitraires a_p telles que $\sum_{p=0}^k a_p \neq 0.$

Ce modèle de comportement de convergence possède 2k + 1 inconnus. En évaluant l'équation ci-dessus pour $A_{n}, A_{n+1}, \cdots, A_{n+2k}$, on obtient l'expression de la transformée de Shanks e_k(A_n) en résolvant l'inconnue A, dans le système obtenu.

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

$A_n = A + \sum_{p=1}^k \alpha_p q_p^n.$

Les q_p étant les k racines du polynôme $P(q)=\sum_{p=0}^k a_p q^p$. Certaines racines pouvant être complexes, le comportement de A_n englobe de nombreuses formes: combinaisons linéaires d'exponentielles décroissantes ou croissantes avec des sinusoïdes amorties ou amplifiées. Le cas où certaines racines du polynôme sont multiples génère d'autres formes non couvertes par la formule précédente, et élargit encore le nombre de formes où la transformation de Shanks fournie la limite de la suite A_n en un nombre fini d'étapes.

• Lien avec la table de Padé

Lorsque la suite à accélérer est la somme partielle d'un développement limité d'une fonction:

$A_n = \sum_{k=1}^n c_k x^k \text{ } f(x) = \sum_{k=1}^{\infty} c_k x^k.$

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

e_k(A_n) = [n + k / k]_f(x) k = 0,1... n = − k, − k + 1...

avec [n + k / k]_f(x) l'approximant de Padé d'indice k+n,k de f(x) (la fraction rationnelle de degré n+k au numérateur et k au dénominateur dont le développement limité coïncide avec celui de f(x) jusqu'au degré 2k+n). La transformée de Shanks fournit donc un moyen de calculer les différents approximants de Padé d'une fonction dont on connait sont 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 monotone (A_n est totalement monotone si $(-1)^n \Delta ^k A_n \geqslant 0\text{ }n,k= 0,1...$), et les suites totalement oscillantes (A_n est totalement oscillante si ( − 1)ⁿA_n est totalement monotone).

S'il existe des constantes a et b telles que la suite a.A_n+b soit totalement monotone ou oscillante, et si $\lim_{n \to \infty} \frac{A_{n+1}-A}{A_{n}-A}\neq 1$ (la convergence n'est pas de type logarithmique)

alors les lignes, colonnes et diagonales du tableau des transformés 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 "k", notamment pour k=1 où l'on obtient le Δ² de Aitken. En effet: $e_1(A_n) = \frac{ \begin{vmatrix} A_{n} & A_{n+1} \\ \Delta A_{n} & \Delta A_{n+1} \\ \end{vmatrix} }{ \begin{vmatrix} 1 & 1 \\ \Delta A_{n} & \Delta A_{n+1} \\ \end{vmatrix} }=\frac{A_n A_{n+2}-A^2_{n+1}}{A_{n+2}-2 A_{n+1}+A_n}$

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 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:

$\epsilon^{(n)}_{-1}=0 \text{ }\epsilon^{(-n-1)}_{2n}=0 \text{ } \epsilon^{(n)}_{0}=A_n \text{ }\forall n$

$\epsilon^{(n)}_{k+1}= \epsilon^{(n+1)}_{k-1} + \frac{1}{\epsilon^{(n+1)}_{k} - \epsilon^{(n)}_{k}} \text{ }\forall n,k$

$e_k(A_n)= \epsilon^{(n)}_{2k} \text{ }\forall k,n.$

L'ε-algorithme se prête particulièrement bien au calcul dans un tableur. Dans l'ε-algorithme, seules les indices k paires 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 :

$e_{-1}(A_n)=\infty \text{ }e_n(A_{-n-1})=0 \text{ } e_0(A_n)=A_n \text{ }\forall n$

$\frac{1}{e_{k+1}(A_{n-1}) - e_{k}(A_{n})} + \frac{1}{e_{k-1}(A_{n+1})- e_{k}(A_{n})} = \frac{1}{e_{k}(A_{n+1}) - e_{k}(A_{n})} + \frac{1}{e_{k}(A_{n-1})- e_{k}(A_{n})} \text{ }\forall n,k$

Exemples

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

Cette section est vide, insuffisamment détaillée ou incomplète. Votre aide est la bienvenue !

• Extension du domaine de convergence d'un développement limité

Le développement limité de la fonction Arc-tangente

$\arctan{x} = \sum_{n=0}^\infty \frac{(-1)^n x^{2n+1}}{2n+1}$

a un rayon de convergence égal à 1. Le calcul des transformées de Shanks de ce développement limité va fournir le tableau de Padé de la fonction Arc-tangente, dont certains éléments peuvent converger au delà de 1. Par exemple, pour x=2, on a:

Application de la transformée de Shanks à Arctan(2)=1,10714871...

n	An	e1(An)	e2(An)	e3(An)	e4(An)	e5(An)
0	2,000000	1,215686	1,122699	1,109420	1,107481	1,107197
1	-0,666667	0,992593	1,095083	1,105663	1,106953
2	5,733333	1,285457	1,120862	1,108523	1,107305
3	-12,552381	0,762040	1,087293	1,105534
4	44,336508	1,873988	1,141097	1,109410
5	-141,845310	-0,766091	1,041663
6	488,308536	6,008969	1,245533
7	-1696,224797	-12,406001
8	6013,892850	39,911298
9	-21580,212414
10	78284,168539

Malgré la série à accélérer manifestement divergente, on constate que sa transformée de Shanks converge vers la valeur de Arctan(2). 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 négatifs). Dans cet exemple, la meilleur estimation étant obtenue pour e_k(A₀), correspondant à la diagonale du tableau de Padé. Il est important de calculer la suite A_n 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 e_k(A₀) du tableau précédent comme nouvelle suite initiale, on obtient:

Application répétée de la transformée de Shanks à Arctan(2)=1,10714871...

ek(A0)	e1(ek(A0))	e2(ek(A0))
2,000000	1,11019129	1,10714844
1,215686	1,10720759	1,10714867
1,122699	1,10714937
1,109420	1,10714868
1,107481
1,107197

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 k des transformées. La dernière colonne calculée e_k(A_n) servira alors de suite initiale pour une nouvelle transformation, poussée jusqu'à l'ordre k, et ainsi de suite. On appelle ceci une application itérée de la transformée de Shanks d'ordre k. On prend le plus souvent k=1, c'est-à-dire que l'on itère le Δ² d'Aitken. En reprenant l'exemple de Arctan(2), on trouve:

Application itérée de e₁(A_n) (Δ² d'Aitken) à Arctan(2)=1,10714871...

n	An	e1(An)	e12(An)	e13(An)	e14(An)	e15(An)
0	2,000000	1,215686	1,119223	1,108112	1,107203	1,107151
1	-0,666667	0,992593	1,097666	1,106475	1,107111
2	5,733333	1,285457	1,117931	1,107786	1,107181
3	-12,552381	0,762040	1,091576	1,106394
4	44,336508	1,873988	1,133689	1,108205
5	-141,845310	-0,766091	1,056116
6	488,308536	6,008969	1,214677
7	-1696,224797	-12,406001
8	6013,892850	39,911298
9	-21580,212414
10	78284,168539

Dans ce cas précis, l'application itérée du Δ² d'Aitken compare favorablement avec 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 : $f(\theta) = \frac {a_0} {2} +\sum_{n=1}^\infty (a_n \cos{n \theta} + b_n \sin{n \theta})$

se transforme en une série entière

$f(z) = \frac {a_0} {2} +\sum_{n=1}^\infty (a_n- i b_n )z^n \text{ avec }z=e^{i \theta}$

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

Par exemple, la fonction en dent de scie sur [-π,+π], dont la série de Fourier vaut :

$f(\theta) = \sum_{n=1}^\infty (-1)^{n+1} \frac{2}{n} \sin{n \theta}$ devient après changement de variable la série entière:

$f(z) = \sum_{n=1}^\infty (-1)^{n} \frac{2i}{n} z^n \text{ avec }z=e^{i \theta}$

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

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

Accélération de la convergence de la série de Fourier de la fonction en dent de scie, avec la transformation de Shanks

$S_k = \sum_{n=1}^k (-1)^{n+1} \frac{2}{n} \sin{n \theta}$

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

$e_3(S_k)=\frac{22 z^3+120z^2+120z}{3i z^3 +36i z^2+90i z +60i}$

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

$\frac{440 \sin{3 \theta}+ 2940 \sin{2 \theta}+ 4704 \sin{\theta}}{120 \cos{3 \theta}+ 1620 \cos{2 \theta}+ 5832 \cos{ \theta}+4335}$

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

1. ↑ Daniel Shanks, Non-linear transformation of divergent and slowly convergent sequences, Journal of Mathematics and Physics vol 34 p 1–42, 1955.
2. ↑ R. Schmidt, On the numerical solution of linear simultaneous equations by an iterative method, Philosophical Magazine vol 32, p 369–383, 1941.

Références

• Claude Brezinski, Algorithmes d'accélération de la convergence: étude numérique, éditions Technip, 1978, (ISBN 2-7108-0341-0)

Voir aussi

Articles connexes

• ε-algorithme
• Delta-2
• Extrapolation de Richardson
• Approximant de Padé