Delta-2

Delta-2
Page d'aide sur l'homonymie Ne doit pas être confondu avec Delta II.

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 populaire du fait de sa simplicité et de son efficacité. Une première forme de cet algorithme a été utilisé par Kowa Seki (fin du XVII siècle) pour calculer une approximation de π par la méthode des polygones d'Archimède.

Sommaire

Definition

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

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 Axn converge plus vite que la suite initiale xn, ce qui permet d'estimer la limite de xn 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 xn ainsi que Axn avec un nombre important de chiffres significatifs. Certaines écritures de l'algorithme propagent moins les erreurs d'arrondi, par exemple :

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

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

A(axn + b) = aA(xn) + b, a et b constantes réelles.

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

a_0(x_n - x_\infty) + a_1(x_{n+1} - x_\infty) = 0, a0 + a1 ≠ 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 :

x_n = x_\infty + a\lambda^n, λ ≠ 1

Il est à noter que même si la suite xn 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é de Aitken est :

Si la suite xn converge vers x_\infty et si :

\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 Axn converge vers x_\infty plus vite que xn.

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 :

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 \frac{\pi}{4} peut être calculé d'après la série de Leibniz, réputée pour sa convergence très lente :
\frac{\pi}{4} = \sum_{n=0}^\infty \frac{(-1)^n}{2n+1} \approx 0,785398
n terme xn = somme partielle Axn−2
0 1 1 —
1 -0,33333333 0,66666667 —
2 0,2 0,86666667 0,78630952
3 -0,14285714 0,72380952 0,79166667
4 0,11111111 0,83492063 0,78333333
5 -9,0909091×10-2 0,74401154 0,78492063
6 7,6923077×10-2 0,82093462 0,78567821
7 -6,6666667×10-2 0,75426795 0,78522034
8 5,8823529×10-2 0,81309148 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

La convergence d'un procédé itératif de point fixe du type xn + 1 = f(xn) peut être accéléré de plusieurs manière :

  • 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é procédé de Aitken-Steffensen. Il permet 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é de Aitken-Steffensen remplace l'itération d'origine xn + 1 = f(xn) par

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é équation de Kepler, lié au calcul d'orbites en astronomie)

x − asin x = M

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

x0 = M

xn + 1 = M + asin(xn)

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,0985644...), on obtient :

n xn = valeur itérée Axn-2 A²xn-4 A3xn-6 Steffensen
0 0,0100000 0,0100000
1 0,0189999 0,0189999
2 0,0270988 0,0999107 0,0270988
3 0,0343860 0,0997946 0,0999107
4 0,0409413 0,0996601 0,1006471 0,0997701
5 0,0468369 0,0995222 0,1050054 0,0996442
6 0,0521378 0,0993898 0,0961648 0,1020862 0,0985651
7 0,0569027 0,0992677 0,0978300 0,0975661 0,0985650
8 0,0611848 0,0991582 0,0982150 0,0983308 0,0985649
9 0,0650320 0,0990622 0,0983714 0,0984784 0,0985644
10 0,0684875 0,0989792 0,0984494 0,0985271 0,0985644
11 0,0715906 0,0989082 0,0984927 0,0985467 0,0985644
12 0,0743765 0,0988482 0,0985183 0,0985555 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 \sqrt{2} \approx 1,4142136 peut être calculé par la Méthode de Héron, en partant d'une valeur initiale x0 et la suite récurrente (à convergence quadratique) :

x_{n+1} = \frac{x_n + \frac{2}{x_n}}{2}.


En partant de x0 = 1 :

n xn = valeur itérée Axn−2
0 1
1 1,5
2 1,4166667 1,4285714
3 1,4142157 1,4141414
4 1,4142136 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 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, éditions Technip, 1978, ISBN 2-7108-0341-0

Voir aussi

Articles connexes


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Delta-2 de Wikipédia en français (auteurs)

Игры ⚽ Поможем написать курсовую

Regardez d'autres dictionnaires:

  • delta — delta …   Dictionnaire des rimes

  • Delta — commonly refers to: Delta (letter), Δ or δ in the Greek alphabet, also used as a mathematical symbol River delta, a landform at the mouth of a river Delta Air Lines, a major U.S. airline Delta may also refer to: Contents 1 Places …   Wikipedia

  • Delta 2 — Delta II  Ne doit pas être confondu avec Delta 2. Une Delta II 7925 s’apprete à lancer la sonde De …   Wikipédia en Français

  • Delta IV — Medium Données générales Mission Lanceur Commercial Orbite LEO et GTO Période des lancements …   Wikipédia en Français

  • delta — [ dɛlta ] n. m. • delta du Nil XIIIe; de delta « lettre grecque » I ♦ Quatrième lettre de l alphabet grec (Δ, δ), correspondant au d. En forme de delta. ⇒ deltoïde, triangulaire. Aile (en) delta. ⇒ deltaplane. ♢ Adj. inv. Phys. Rayon delta :… …   Encyclopédie Universelle

  • Delta A — launching Explorer 14 Function Expendable launch system Country of origin …   Wikipedia

  • Delta B — prior to the launch of TIROS 8 Function Expendable launch system Country of origin …   Wikipedia

  • Delta C — The first Delta C launches with Explorer 18 Function Expendable launch system Country of origin …   Wikipedia

  • Delta D — Launch of a Delta D with Intelsat I Function Expendable launch system Country of origin …   Wikipedia

  • Delta J — Launch of the Delta J with Explorer 38 Function Expendable launch system Country of origin   …   Wikipedia

  • Delta M — Launch of the first Delta M with Intelsat 301 Function Expendable launch system Country of origin …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”