Delta-2

Delta-2 est un procédé d'accélération de la convergence de suites en analyse numérique, popularisé par le mathématicien Alexander Aitken en 1926^[1]. C'est l'un des algorithmes d'accélération de la convergence les plus populaires du fait de sa simplicité et de son efficacité. Une première forme de cet algorithme a été utilisée par Seki Kōwa (fin du XVII^e siècle) pour calculer une approximation de π par la méthode des polygones d'Archimède.

Définition

Soit une suite ${\displaystyle x={(x_{n})}_{n\in \mathbb {N} }}$ convergente vers une limite que l'on souhaite déterminer, le procédé Delta-2 d'Aitken associe à cette suite une autre suite définie par :

${\displaystyle Ax_{n}=x_{n}-{\frac {(\Delta x_{n})^{2}}{\Delta ^{2}x_{n}}}=x_{n}-{\frac {(x_{n+1}-x_{n})^{2}}{x_{n}-2x_{n+1}+x_{n+2}}}}$

C'est de la première écriture que le procédé tire son nom. Sous certaines conditions, la suite Ax_n converge plus vite que la suite initiale x_n, ce qui permet d'estimer la limite de la suite avec une meilleure précision et/ou en effectuant moins de calculs.

C'est un algorithme numériquement peu stable : il convient de calculer la suite x_n ainsi que Ax_n avec un nombre important de chiffres significatifs. Certaines écritures de l'algorithme propagent moins les erreurs d'arrondi, par exemple :

${\displaystyle Ax_{n}=x_{n+1}+{\frac {1}{{\frac {1}{x_{n+2}-x_{n+1}}}-{\frac {1}{x_{n+1}-x_{n}}}}}}$

La suite Ax_n étant elle-même une suite numérique, il est possible de lui appliquer le Delta-2, et ainsi de suite : c'est ce qu'on appelle une application itérée du Delta-2.

Propriétés

Le Delta-2 est un algorithme non linéaire d'accélération de la convergence. Mais il vérifie la propriété :

${\displaystyle A(ax_{n}+b)=aA(x_{n})+b}$, a et b constantes réelles.

Le Delta-2 détermine une estimation de la limite de la suite x_n en partant de l'hypothèse que celle-ci vérifie l'équation aux différences suivante :

${\displaystyle a_{0}(x_{n}-x_{\infty })+a_{1}(x_{n+1}-x_{\infty })=0,\,a_{0}+a_{1}\neq 0}$

En résolvant cette équation aux différences, les suites (dont le Delta-2 détermine de manière immédiate la limite) sont de la forme :

${\displaystyle x_{n}=x_{\infty }+a\lambda ^{n},\,\lambda \neq 1}$

Il est à noter que même si la suite x_n diverge, c'est-à-dire si |λ| > 1, le Delta-2 converge vers « l'anti-limite » de la suite.

Le théorème de convergence pour le procédé d'Aitken est :

Théorème —  Si la suite x_n converge vers x_∞ et si :

${\displaystyle \lim _{n\to \infty }{\frac {x_{n+1}-x_{\infty }}{x_{n}-x_{\infty }}}={\frac {x_{n+2}-x_{n+1}}{x_{n+1}-x_{n}}}=\lambda \neq 1}$

alors Ax_n converge vers x_∞ plus vite que x_n.

Le Delta-2 est donc particulièrement bien adapté aux suites à convergence linéaires (dont l'écart avec leur limite se comporte à l'infini comme une suite géométrique).

Le Delta-2 est un cas particulier de certaines transformations plus générales :

• la transformation de Shanks ;
• le procédé d'Overholt.

Exemples d'application

Accélération de la convergence d'une série

Le Delta-2 peut être utilisé pour accélérer la convergence des séries en extrayant une suite numérique d'après leur somme partielle.

Par exemple, la valeur de π/4 peut être calculée d'après la série de Leibniz, connue pour sa convergence très lente :

${\displaystyle {\frac {\pi }{4}}=\sum _{n=0}^{\infty }{\frac {(-1)^{n}}{2n+1}}\approx 0{,}785\,398}$

n	Terme	Somme partielle xn	A xn−2
0	1	1	—
1	−0,333 333 33	0,666 666 67	—
2	0,2	0,866 666 67	0,791 666 67
3	−0,142 857 14	0,723 809 52	0,783 333 33
4	0,111 111 11	0,834 920 63	0,786 309 52
5	−9,090 909 1 × 10^−2	0,744 011 54	0,784 920 63
6	7,692 307 7 × 10^−2	0,820 934 62	0,785 678 21
7	−6,666 666 7 × 10^−2	0,754 267 95	0,785 220 34
8	5,882 352 9 × 10^−2	0,813 091 48	0,785 517 95

La précision obtenue par le Delta-2 avec seulement 9 termes, serait obtenue en sommant plus de 4000 termes de la suite non accélérée.

Accélération de la convergence des procédés itératifs

La convergence d'un procédé itératif de point fixe du type ${\displaystyle x_{n+1}=f(x_{n})}$ peut être accélérée de plusieurs manières :

• classiquement en calculant le Delta-2 de la suite récurrente ;
• en réinjectant périodiquement le résultat du Delta-2 dans la suite d'origine, afin de « l'aider » à converger.

Cette deuxième stratégie, appliquée systématiquement toutes les 3 itérations, est appelée procédé d'Aitken-Steffensen. Il permet dans la plupart des cas de transformer une convergence (ou divergence) linéaire en convergence quadratique, et une convergence quadratique en super-quadratique. Le procédé d'Aitken-Steffensen remplace l'itération d'origine ${\displaystyle x_{n+1}=f(x_{n})}$ par

${\displaystyle x_{n+1}=f(x_{n})+{\frac {1}{{\frac {1}{f(f(x_{n}))-f(x_{n})}}-{\frac {1}{f(x_{n})-x_{n}}}}}}$

Exemple

L'équation (appelée équation de Kepler, liée au calcul d'orbites en astronomie)

${\displaystyle x-a\sin x=M}$

où x est l'inconnue (M et a étant connus), peut être résolue par exemple par l'itération :

${\displaystyle x_{0}=M,\,x_{n+1}=M+a\sin(x_{n})}$.

D'après le théorème du point fixe, cette suite converge vers la solution de l'équation de départ, si a < 1. Mais cette suite sera d'autant plus lente à converger que a sera proche de 1 (cas fréquemment rencontré en pratique, car typique des orbites des comètes). Il sera intéressant dans ce cas d'accélérer la convergence avec le Delta-2 ou le procédé d'Aitken-Steffensen.

Par exemple, pour a = 0,9 et M = 0,01 (solution x = 0,098 564 4...), on obtient :

n	xn valeur itérée	Axn-2	A^2xn-4	A^3xn-6	Steffensen
0	0,010 000 0				0,010 000 0
1	0,018 999 9				0,018 999 9
2	0,027 098 8	0,099 910 7			0,027 098 8
3	0,034 386 0	0,099 794 6			0,099 910 7
4	0,040 941 3	0,099 660 1	0,100 647 1		0,099 770 1
5	0,046 836 9	0,099 522 2	0,105 005 4		0,099 644 2
6	0,052 137 8	0,099 389 8	0,096 164 8	0,102 086 2	0,098 565 1
7	0,056 902 7	0,099 267 7	0,097 830 0	0,097 566 1	0,098 565 0
8	0,061 184 8	0,099 158 2	0,098 215 0	0,098 330 8	0,098 564 9
9	0,065 032 0	0,099 062 2	0,098 371 4	0,098 478 4	0,098 564 4
10	0,068 487 5	0,098 979 2	0,098 449 4	0,098 527 1	0,098 564 4
11	0,071 590 6	0,098 908 2	0,098 492 7	0,098 546 7	0,098 564 4
12	0,074 376 5	0,098 848 2	0,098 518 3	0,098 555 5	0,098 564 4

Les colonnes des Delta-2 ont été décalés vers le bas pour mettre sur une même ligne les itérés de base nécessaires à leur calcul, et ainsi mieux visualiser le gain apporté par l'accélération de la convergence vis-à-vis des itérations de base. On constate une nette accélération de la convergence de la suite initiale par le Delta-2. Les applications itérées du Delta-2 l'accélèrent encore davantage, mais le résultat le plus spectaculaire est obtenu par la méthode de Steffensen (les nombres en gras montrent l'application du Delta-2 toutes les 3 itérations). Pour obtenir la même précision que le Delta-2 après 12 itérations, il aurait fallu itérer 50 fois la formule de base, et l'itérer 300 fois pour être équivalent à la méthode de Steffensen.

Exemple 2

Lorsque l'itération de base a une convergence quadratique (par exemple avec la méthode de Newton), le Delta-2 ou la méthode de Steffensen, quoique accélérant la convergence, présente moins d'intérêt pratique. Le calcul d'une itération de base supplémentaire permet souvent d'obtenir le même résultat que la valeur accélérée.

La valeur de ${\displaystyle {\sqrt {2}}\approx 1,4142136}$ peut être calculé par la méthode de Héron, en partant d'une valeur initiale x₀ et la suite récurrente (à convergence quadratique) :

${\displaystyle x_{n+1}={\frac {x_{n}+{\frac {2}{x_{n}}}}{2}}.}$

En partant de x₀ = 1 :

n	Valeur itérée xn	Axn−2
0	1
1	1,5
2	1,416 666 7	1,428 571 4
3	1,414 215 7	1,414 141 4
4	1,414 213 6	1,414 213 6

On constate certes un gain en précision en accélérant la convergence, mais l'itérée de base suivante est du même ordre de précision, pour un moindre coût en calcul.

Autres applications

Ce procédé est notamment utilisé pour accélérer l'algorithme de décomposition de domaine de type Schwarz (additifs et multiplicatifs). En effet, on peut remarquer que sous certaines conditions, les coefficients de Fourier liés aux solutions itérées obtenus ont une convergence purement linéaire. Par ce principe, on peut réduire le nombre total d'itérations de l'algorithme à 3 ou 5 itérations pour des problèmes 1D ou 2D (respectivement).

Notes

1. Alexander Aitken, "On Bernoulli's numerical solution of algebraic equations", Proceedings of the Royal Society of Edinburgh (1926) 46 pp. 289-305.

Bibliographie

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

Voir aussi

Articles connexes

• ε-algorithme
• Transformation de Shanks
• Procédé d'Overholt
• Extrapolation de Richardson