Voir la source de Delta-2

{{confusion|Delta II}}

'''Delta-2''' est un procédé d'[[accélération de suite|accélération de la convergence]] de suites en [[analyse numérique]], popularisé par le mathématicien [[Alexander Aitken]] en 1926<ref>Alexander Aitken, "On Bernoulli's numerical solution of algebraic equations", ''Proceedings of the Royal Society of Edinburgh'' (1926) '''46''' pp. 289-305.</ref>. 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 {{s-|XVII}}) pour calculer une approximation de {{math|π}} par la méthode des polygones d'[[Archimède]].

== Définition ==
Soit une suite <math>x={(x_n)}_{n\in\N}</math> 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 :

:<math> 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}}</math>

C'est de la première écriture que le procédé tire son nom.
Sous certaines conditions, la suite {{mvar|Ax<sub>n</sub>}} converge plus vite que la suite initiale {{mvar|x<sub>n</sub>}}, 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 {{mvar|x<sub>n</sub>}} ainsi que {{mvar|Ax<sub>n</sub>}} avec un nombre important de chiffres significatifs. Certaines écritures de l'algorithme propagent moins les [[Erreur d'arrondi|erreurs d'arrondi]], par exemple :

:<math> Ax_{n}=x_{n+1}+\frac{1}{\frac{1}{x_{n+2}-x_{n+1}}-\frac{1}{x_{n+1}-x_{n}}}   </math>

La suite {{mvar|Ax<sub>n</sub>}} é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é :
:<math> A(ax_{n} + b) = aA(x_{n}) + b</math>, {{mvar|a}} et {{mvar|b}} constantes réelles.

Le Delta-2 détermine une estimation de la limite de la suite {{mvar|x<sub>n</sub>}} en partant de l'hypothèse que celle-ci vérifie l'équation aux différences suivante :
:<math>a_0(x_n - x_\infty) + a_1(x_{n+1} - x_\infty) = 0,\, a_0 + a_1 \neq 0</math>

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 :

:<math>x_n = x_\infty + a\lambda^n,\, \lambda \neq 1</math>
 
Il est à noter que même si la suite {{mvar|x<sub>n</sub>}} diverge, c'est-à-dire si |λ| > 1, le Delta-2 converge vers « [[antilimite|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 {{mvar|x<sub>n</sub>}} converge vers {{math|''x''{{ind|∞}}}} et si :

:<math>\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</math>

alors {{mvar|Ax<sub>n</sub>}} converge vers {{math|''x''{{ind|∞}}}} plus vite que {{mvar|x<sub>n</sub>}}.
}}
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 {{sfrac|π|4}} peut être calculée d'après la série de [[Gottfried Wilhelm Leibniz|Leibniz]], connue pour sa convergence très lente :

:: <math>\frac{\pi}{4} = \sum_{n=0}^\infty \frac{(-1)^n}{2n+1} \approx 0{,}785\,398</math>

{| class="wikitable"
|-
| {{mvar|n}}
| Terme
| Somme partielle {{mvar|x<sub>n</sub>}}
| {{math|''A x''<sub>''n''−2</sub>}}
|-
| 0
| 1
| 1
| —
|-
| 1
| {{Unité|-0.33333333}}
| {{Unité|0.66666667}}
| —
|-
| 2
| {{Unité|0.2}}
| {{Unité|0.86666667}}
| {{Unité|0.79166667}}
|-
| 3
| {{Unité|-0.14285714}}
| {{Unité|0.72380952}}
| {{Unité|0.78333333}}
|-
| 4
| {{Unité|0.11111111}}
| {{Unité|0.83492063}}
| {{Unité|0.78630952}}
|-
| 5
| {{Unité|-9.0909091|e=-2}}
| {{Unité|0.74401154}}
| {{Unité|0.78492063}}
|-
| 6
| {{Unité|7.6923077|e=-2}}
| {{Unité|0.82093462}}
| {{Unité|0.78567821}}
|-
| 7
| {{Unité|-6.6666667|e=-2}}
| {{Unité|0.75426795}}
| {{Unité|0.78522034}}
|-
| 8
| {{Unité|5.8823529|e=-2}}
| {{Unité|0.81309148}}
| {{Unité|0.78551795}}
|}

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 ===
{{Ancre|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 <math>x_{n+1}=f(x_n)</math> 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 <math>x_{n+1}=f(x_n)</math> par
:<math>x_{n+1} = f(x_{n}) + \frac{1}{\frac{1}{f(f(x_{n})) - f(x_{n})} - \frac{1}{f(x_{n}) - x_{n}}}</math>

;Exemple :
L'équation (appelée [[équation de Kepler]], liée au calcul d'orbites en [[astronomie]])
:<math>x - a\sin x = M</math>

où ''x'' est l'inconnue (''M'' et ''a'' étant connus), peut être résolue par exemple par l'itération :
:<math>x_0 = M,\,x_{n+1} = M + a\sin(x_n)</math>.

D'après le [[Application contractante|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'' = {{Unité|0.0985644}}...), on obtient :
{| class="wikitable"
|-
| ''n''
| ''x<sub>n</sub>'' valeur itérée
| ''Ax''<sub>''n''-2</sub>
| ''A''{{2}}''x''<sub>''n''-4</sub>
| ''A''{{3}}''x''<sub>''n''-6</sub>
| Steffensen
|-
|0
| {{Unité|0.0100000}}
|
|
|
| {{Unité|0.0100000}}
|-
|1
| {{Unité|0.0189999}}
|
|
|
| {{Unité|0.0189999}}
|-
|2
| {{Unité|0.0270988}}
| {{Unité|0.0999107}}
|
|
| {{Unité|0.0270988}}
|-
|3
| {{Unité|0.0343860}}
| {{Unité|0.0997946}}
|
|
| '''{{Unité|0.0999107}}'''
|-
|4
| {{Unité|0.0409413}}
| {{Unité|0.0996601}}
| {{Unité|0.1006471}}
|
| {{Unité|0.0997701}}
|-
|5
| {{Unité|0.0468369}}
| {{Unité|0.0995222}}
| {{Unité|0.1050054}}
|
| {{Unité|0.0996442}}
|-
|6
| {{Unité|0.0521378}}
| {{Unité|0.0993898}}
| {{Unité|0.0961648}}	
| {{Unité|0.1020862}}
| '''{{Unité|0.0985651}}'''
|-
|7
| {{Unité|0.0569027}}
| {{Unité|0.0992677}}
| {{Unité|0.0978300}}
| {{Unité|0.0975661}}
| {{Unité|0.0985650}}
|-
|8
| {{Unité|0.0611848}}
| {{Unité|0.0991582}}
| {{Unité|0.0982150}}
| {{Unité|0.0983308}}
| {{Unité|0.0985649}}
|-
|9
| {{Unité|0.0650320}}
| {{Unité|0.0990622}}
| {{Unité|0.0983714}}
| {{Unité|0.0984784}}
| '''{{Unité|0.0985644}}'''
|-
|10
| {{Unité|0.0684875}}
| {{Unité|0.0989792}}
| {{Unité|0.0984494}}
| {{Unité|0.0985271}}
| {{Unité|0.0985644}}
|-
|11
| {{Unité|0.0715906}}
| {{Unité|0.0989082}}
| {{Unité|0.0984927}}
| {{Unité|0.0985467}}
| {{Unité|0.0985644}}
|-
|12
| {{Unité|0.0743765}}
| {{Unité|0.0988482}}
| {{Unité|0.0985183}}
| {{Unité|0.0985555}}
| '''{{Unité|0.0985644}}'''
|}

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 <math>\sqrt{2} \approx 1,4142136</math> peut être calculé par la [[méthode de Héron]], en partant d'une valeur initiale {{math|''x''<sub>0</sub>}} et la suite récurrente (à convergence quadratique) :
:<math>x_{n+1} = \frac{x_n + \frac{2}{x_n}}{2}. </math>

En partant de ''x''<sub>0</sub> = 1 :
{| class="wikitable"
|-
| ''n''
| Valeur itérée <br/>''x<sub>n</sub>''
| ''Ax''<sub>''n''−2</sub>
|-
| 0
| 1
| 
|-
| 1
| {{Unité|1.5}}
| 
|-
| 2
| {{Unité|1.4166667}}
| {{Unité|1.4285714}}
|-
| 3
| {{Unité|1.4142157}}
| {{Unité|1.4141414}}
|-
| 4
| {{Unité|1.4142136}}
| {{Unité|1.4142136}}
|}
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 [[Série de Fourier#Coefficients_de_Fourier|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 ==
{{Références}}

== Bibliographie ==

* {{Ouvrage|langue=fr|auteur1=Claude Brezinski|titre=Algorithmes d'accélération de la convergence|sous-titre=étude numérique|éditeur=éditions Technip|lieu=Paris|année=1978|pages totales=392|isbn=2-7108-0341-0|lire en ligne=https://books.google.com/books?id=TxDghaunVjkC&printsec=frontcover}}

== Voir aussi ==
=== Articles connexes ===
* [[epsilon algorithme|ε-algorithme]]
* [[Transformation de Shanks]]
* [[Procédé d'Overholt]]
* [[Extrapolation de Richardson]]

{{Portail|analyse}}

[[Catégorie:Transformation de suite]]
[[Catégorie:Analyse numérique]]