Extrapolation de Richardson

En analyse numérique, le procédé d'extrapolation de Richardson est une technique d'accélération de la convergence. Il est ainsi dénommé en l'honneur de Lewis Fry Richardson^[1]^,^[2], qui l'a introduit au début du XX^e siècle.

Ce procédé est notamment utilisé pour définir une méthode numérique d'intégration : la méthode de Romberg, accélération de la méthode des trapèzes.

Présentation du principe

On suppose que la quantité inconnue A peut être approchée par une fonction A(h) avec une convergence d'ordre n en h

$A-A(h) = a_n h^n+O(h^m),~a_n\ne0,~m>n,$

expression dans laquelle le coefficient a_n n'est pas connu. Le principe d'extrapolation consiste supprimer le terme en hⁿ par combinaison linéaire de deux valeurs de A(h), calculés avec des h différents : par exemple A(h) et A(h/2). On obtient :

$R(h) = A(h/2) + \frac{A(h/2)-A(h)}{2^n-1} = \frac{2^n\,A(h/2)-A(h)}{2^n-1}$

R(h) est l'extrapolé de Richardson qui approche A à l'ordre m>n en h. Le facteur 2 peut être remplacé par n'importe quel autre facteur. L'intérêt de la méthode est qu'il sera fréquemment plus aisé d'obtenir une précision donnée en calculant R(h) que A(h') avec un h' beaucoup plus petit (risque d'erreur d'arrondi, grande quantité de calcul...).

Formule générale

On suppose que l'on dispose d'une approximation de A avec une formule d'erreur de cette forme

$A = A(h) + a_0h^{k_0} + a_1h^{k_1} + a_2h^{k_2} + \cdots a_zh^{k_z}+O(h^{k_{z+1}}),$

les coefficients étant inconnus. On se fixe un paramètre réel r>1 et on forme une combinaison entre la relation précédente et cette même relation prise au point $h / r$

$(r^{k_0}-1)A = r^{k_0}A\left(\frac{h}{r}\right) - A(h) + 0+a_1\left(\frac{r^{k_0}}{r^{k_1}}-1\right)h^{k_1}+\dots+a_z\left(\frac{r^{k_0}}{r^{k_z}}-1\right)h^{k_z} +O(h^{k_{z+1}}).$

Le terme en h^k₀ a disparu. Cette formule peut être itérée pour augmenter l'ordre.

Pour les formules d'erreur pouvant être exprimé sous la forme:

$A = A(h) + a_1{\phi(h)} + a_2{\phi(h)}^2 + a_3{\phi(h)}^3 + \cdots a_z{\phi(h)}^z+O({\phi(h)}^{z+1}),$

avec une fonction $Φ(x)$ connue telle que $\lim_{x \to 0} \phi(x)=0$ , un algorithme d'interpolation polynomial (par exemple l'algorithme d'Aitken Neville) peut être utilisé.

Dans ce cas, le résultat de l'extrapolation de Richardson s'obtient en calculant la valeur en zéro du polynôme d'interpolation passant par les points $(Φ(h i), A (h i))$ , où les h_i forment une suite décroissant vers 0. Une variante consiste à utiliser une interpolation par fraction rationnelle au lieu d'une interpolation polynomiale (Bulirsch et Stoer^[3] ou le ρ-algorithme de P. Wynn).

Pour le cas encore plus général, où la formule d'erreur est de la forme:

$A = A(h) + a_1 \phi_1(h) + a_2 \phi_2(h) + a_3 \phi_3(h) + \cdots$

avec les fonction $Φ n (x)$ connues et telles que $\lim_{x \to 0} \phi_n(x)=0$ , l'algorithme d'interpolation linéaire généralisé de Mühlbach^[4] peut être utilisé: On obtient dans ce cas un algorithme d'accélération de la convergence appelé E-algorithme, de Håvie^[5] et Brezinski^[6] (à ne pas confondre avec l' ε-algorithme de P. Wynn).

Algorithme

L'algorithme présenté est celui associé à la méthode d'Aitken Neville, lorsque la formule d'erreur est de la forme:

$A = A(h) + a_1{\phi(h)} + a_2{\phi(h)}^2 + a_3{\phi(h)}^3 + \cdots a_z{\phi(h)}^z+O({\phi(h)}^{z+1}),$

Pour N valeurs différente calculés de A_n,avec la suite auxiliaire h_n correspondante, on initialise le tableau suivant:

$R^{(n)}_0=A_n \text{ } n=0,1...N$

Puis le reste du tableau (seulement la partie triangulaire supérieur) est calculé par les relations:

$R_{k+1}^{(n)}=R_{k}^{(n+1)}+ \frac{R_{k}^{(n+1)}-R_{k}^{(n)} }{ \frac{\phi(h_n)}{\phi(h_{n+k+1})}-1} \text{ } n=0,1...N,k=0,1...n$

Le résultat de l'extrapolation de Richardson est $R^{(0)}_N \text{ } n=0,1...$ (la pointe du triangle)

Le choix de la suite auxiliaire h_n est un compromis entre une suite décroissant suffisamment rapidement pour obtenir un algorithme numériquement stable, et une suite décroissant lentement évitant les difficultés de calcul des A_n. Pour des raisons de risque de divergence, on évitera d'utiliser une suite auxiliaire décroissant plus lentement que la suite harmonique (critère de Laurent).

D'autres algorithmes d'interpolation polynomiales peuvent être utilisés à la place de la méthode d'Aitken Neville, notamment la méthode de Lagrange (en particulier sa variante dite barycentrique). Dans ce cas précis, les polynômes formant la base de Lagrange peuvent être calculés une fois pour toutes (ceux-ci ne dépendant que de la suite h_n choisie) , ce qui rend l'algorithme compétitif. Ceci est d'autant plus vrai s'il y a à extrapoler à plusieurs reprises, par exemple pour la résolution des équations différentielles, ou l'extrapolation d'une suite vectorielle.

Les suites classiquement utilisés sont:

- la suite de Romberg $h_n= \frac {h_0}{2^n}$

- les suites de Bulirsch Stoer $h_1=h_0/2 ; h_2=h_0/3 ; h_{n+2}= \frac {h_n}{2}$ ou bien $h_1=h_0/2 ; h_2=h_0/4 ;h_3=h_0/6 ; h_{n+2}= \frac {h_n}{2}$

- la suite de Deuflhard $h_n= \frac {h_0}{2n}$

Exemples d'application

Approximation numérique de la dérivée d'une fonction

Le point de départ est le développement de Taylor de la fonction à dériver :

$f(x+h) = f(x) + f'(x)h + \frac{f''(x)}{2!}h^2 + \frac{f'''(x)}{3!}h^3 +\frac{f''''(x)}{4!}h^4 + \cdots$

la dérivée de f(x) est déduite

$f'(x) = \frac{f(x+h) - f(x)}{h} - \frac{f''(x)}{2}h - \frac{f'''(x)}{3!}h^2 - \frac{f''''(x)}{4!}h^3+ \cdots.$

en appelant $A(h) = \frac{f(x+h) - f(x)}{h}$ , le terme d'erreur se présente sous une forme :

$A(h) = f'(x) + a_1 h + a_2 h^2 + a_3 h^3 + \cdots$

forme idéale pour être accélérée à l'aide de l'extrapolation de Richardson. Il suffira de calculer A(h) pour différentes valeur de h (par exemple la suite de Romberg), et de s'en servir pour éliminer les termes en h, h² etc...

En soustrayant le développement de Taylor de f(x+h) à celui de f(x-h), on obtient :

$f(x+h)- f(x-h) = 2 f'(x)h + 2 \frac{f'''(x)}{3!}h^3 +2 \frac{f^{(5)}(x)}{5!}h^5 + \cdots$

on en tire une autre approximation de la dérivée :

$A(h)= \frac{f(x+h) - f(x-h)}{2h} = f'(x) + a_2 h^2 + a_4 h^4 + a_6 h^6+ \cdots.$

qui ne contient que des termes d'erreur de degré pair. L'utilisation de l'extrapolation de Richardson est dans ce cas beaucoup plus efficace, car à chaque étape, le degré d'approximation est augmenté de 2.

De la même manière, cette fois-ci en additionnant les développements de f(x+h) et f(x-h), on en tire une formule du même type servant à calculer la dérivée seconde :

$A(h) = \frac{f(x+h) - 2f(x) + f(x-h)}{h^2}= f''(x) + a_2 h^2 + a_4 h^4 +a_6 h^6+ \cdots.$

Dans les deux cas précédents, on pourra utiliser la méthode de Aitken Neville pour le calcul de l'extrapolation de Richardson, avec la fonction $Φ(h) = h 2$ .

Intégration numérique

La méthode des trapèzes possède un terme d'erreur n'ayant que des puissances paires de h, d'après la formule d'Euler-Maclaurin. Elle est donc très bien adaptée à l'utilisation de l'extrapolation de Richardson. La méthode résultante est appelé méthode de Romberg.

La méthode du point médian possède aussi ce type de développement, et peut donc fournir une variante de la méthode de Romberg. Les deux méthodes peuvent être utilisées de concert pour fournir une estimation de l'erreur de l'intégrale résultante.

Intégration numérique des équations différentielles

La méthode d'intégration de base qui se prête le mieux à l'extrapolation de Richardson est la méthode du point milieu (où du point milieu modifié) de Gragg. Elle possède aussi un terme d'erreur où n'apparait que les puissances paires de h (lorsque les subdivisions sont paires). La méthode résultante est connue sous le nom de Gragg - Bulirsch - Stoer (GBS). Il existe plusieurs variantes, dépendant du choix de la séquence des h_i, du type d'extrapolation (polynomiale ou rationnelle), et du calcul de la taille du pas global.

Notes

↑ L. F. Richardson, « The approximate arithmetical solution by finite differences of physical problems including differential equations, with an application to the stresses in a masonry dam », dans Philosophical Transactions of the Royal Society of London, Series A, vol. 210, 1911, p. 307–357 [lien DOI]
↑ L. F. Richardson, « The deferred approach to the limit », dans Philosophical Transactions of the Royal Society of London, Series A, vol. 226, 1927, p. 299–349 [lien DOI]
↑ Bulirsch, R. and Stoer, J. §2.2 in Introduction to Numerical Analysis. New York: Springer-Verlag, 1991
↑ Mühlbach, G., The general Neville-Aitken algorithm and some applications. Numer. Math. v31. 97-110
↑ Håvie, T., Generalized Neville type extrapolation schemes. BIT. v19. 204-213
↑ Brezinski, C., A general extrapolation algorithm. Numer. Math. v25. 175-187

Bibliographie

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

Voir aussi

Regardez d'autres dictionnaires:

Extrapolation De Richardson — En analyse numérique, le procédé d extrapolation de Richardson est une technique d accélération de la convergence. Il est ainsi dénommé en l honneur de Lewis Fry Richardson, qui l a introduit au début du XXe siècle. Ce procédé est notamment… … Wikipédia en Français
Extrapolation de richardson — En analyse numérique, le procédé d extrapolation de Richardson est une technique d accélération de la convergence. Il est ainsi dénommé en l honneur de Lewis Fry Richardson, qui l a introduit au début du XXe siècle. Ce procédé est notamment… … Wikipédia en Français
Richardson — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Sommaire 1 Patronyme 2 Toponyme 3 … Wikipédia en Français
Richardson extrapolation — In numerical analysis, Richardson extrapolation is a sequence acceleration method, used to improve the rate of convergence of a sequence. It is named after Lewis Fry Richardson, who introduced the technique in the early 20th century. [cite… … Wikipedia
Richardson-Extrapolation — Das Verfahren der Richardson Extrapolation wurde von Lewis Fry Richardson (1881–1953) entwickelt. Es kann angewendet werden, wenn man bei der numerischen Lösung eines Problems aufgrund zweier verschiedener Diskretisierungen (mit den Schrittweiten … Deutsch Wikipedia
Extrapolation — In mathematics, extrapolation is the process of constructing new data points outside a discrete set of known data points. It is similar to the process of interpolation, which constructs new points between known points, but the results of… … Wikipedia
Extrapolation — Unter Extrapolation wird die Bestimmung eines (oft mathematischen) Verhaltens über den gesicherten Bereich hinaus verstanden. Eine statistische Extrapolation bezeichnet man auch als Hochrechnung. Eine andere Herangehensweise ist die Interpolation … Deutsch Wikipedia
Lewis Fry Richardson — Pour les articles homonymes, voir Richardson. Lewis Fry Richardson est un mathématicien, météorologiste et psychologue britannique (1881 1953). Au cours des années 1916 1918, il imagina de prévoir le temps … Wikipédia en Français
Romberg-Extrapolation — Die Romberg Integration ist ein Verfahren zur numerischen Bestimmung von Integralen und wurde von Werner Romberg entwickelt. Sie ist eine Verbesserung der (Sehnen) Trapezregel durch Extrapolation. Inhaltsverzeichnis 1 Grundgedanke 2… … Deutsch Wikipedia
Lewis Fry Richardson — (* 11. Oktober 1881 in Newcastle upon Tyne; † 30. September 1953 in Kilmun, Argyll) war ein britischer Meteorologe und Friedensforscher. Er berechnete die erste Wettervorhersage, und auch wen … Deutsch Wikipedia

Dictionnaires et Encyclopédies sur 'Academic'

Extrapolation de Richardson

Sommaire

Présentation du principe

Formule générale

Algorithme

Exemples d'application

Approximation numérique de la dérivée d'une fonction

Intégration numérique

Intégration numérique des équations différentielles

Notes

Bibliographie

Voir aussi

Articles connexes

Regardez d'autres dictionnaires:

Share the article and excerpts

Dictionnaires et Encyclopédies sur 'Academic'

Wikipédia en Français

Extrapolation de Richardson

Sommaire

Présentation du principe

Formule générale

Algorithme

Exemples d'application

Approximation numérique de la dérivée d'une fonction

Intégration numérique

Intégration numérique des équations différentielles

Notes

Bibliographie

Voir aussi

Articles connexes

Regardez d'autres dictionnaires:

Share the article and excerpts

Direct link