Extrapolació de Richardson

En el camp de l'anàlisi numèrica, lPlantilla:'extrapolació de Richardson és un mètode d'acceleració que es fa servir per augmentar el radi de convergència d'una successió, especialment d'un mètode iteratiu. Rep el seu nom del matemàtic Lewis Fry Richardson, que va definir aquest mètode a principis del Plantilla:Segle. En paraules de Birkhoff i Rota, Plantilla:Citació

Entre les aplicacions pràctiques del mètode d'extrapolació de Richardson hi ha la Integració de Romberg, que aplica l'extrapolació de Richardson al mètode del trapezi, i l'algorisme de Bulirsch–Stoer, que s'usa per resoldre equacions diferencials ordinàries.

Exemple d'ús

Suposem que volem aproximar $A^{*}$ i disposem d'un mètode $A(h)$ que depèn d'un paràmetre $h$ prou petit tal que

$A(h)=A^{\ast }+C{h}^n+o(h^{n+1})$

Definim un nou mètode

$R(h,k):=\frac{k^{n}A(h)-A(kh)}{k^n-1}$

Així,

$R(h,k)=\frac{k^n(A^{*}+C{h}^n+o(h^{n+1}))-(A^{*}+C{k}^n{h}^n+o(h^{n+1}))}{k^n-1}=A^{*}+o(h^{n+1}).$

$R(h,k)$ s'anomena extrapolació de Richardson dPlantilla:'A(h) i té un error estimat d'ordre $o(h^{n+1})$ respecte $A(h)$.

Sovint és més senzill obtenir una precisió donada fent servir R(h) en comptes dPlantilla:'A(h') amb una hPlantilla:' menor, que podria causar problemes deguts a limitacions en la precisió (per exemple errors d'arrodoniment) i/o deguts a l'increment en el nombre de càlculs necessaris (veure exemples següents).

Fórmula general

Sigui A(h) una aproximació dPlantilla:'A que depèn d'un pas positiu h amb una fórmula d'error

$A-A(h)=a_0{h}^{k_0}+a_1{h}^{k_1}+a_2{h}^{k_2}+\cdots$

on els a_i són constants desconegudes i les k_i són constants conegudes que compleixen h^k_i > h^k_i+1.

El valor exacte que busquem ve donat per

$A=A(h)+a_0{h}^{k_0}+a_1{h}^{k_1}+a_2{h}^{k_2}+\cdots$

que pot simplificar-se en notació O gran com

$A=A(h)+a_0{h}^{k_0}+O(h^{k_1}).$

Fent servir com a mides de pas h i h / t per algunes t, les dues fórumles per A esdevenen:

$A=A(h)+a_0{h}^{k_0}+O(h^{k_1})$

$A=A\left(\frac{h}{t}\right)+a_0{\left(\frac{h}{t}\right)}^{k_0}+O(h^{k_1}).$

Si multipliquem la segona equació per t^k₀ i li restem la segona equació obtenim

$(t^{k_0}-1)A=t^{k_0}A\left(\frac{h}{t}\right)-A(h)+O(h^{k_1})$

que aïllant A esdevé

$A=\frac{t^{k_0}A\left(\frac{h}{t}\right)-A(h)}{t^{k_0}-1}+O(h^{k_1}).$

Amb aquest procediment hem obtingut una millor aproximació dPlantilla:'A traeint-li el major terme en l'error, que era O(h^k₀). Aquest procediment pot repetir-se per eliminar els següients termes d'error i obtenir així millors aproximacions.

Pot definir-se una relació de recurrència per les aproximacions a partir de

$A_{i+1}(h)=\frac{t^{k_i}{A}_i\left(\frac{h}{t}\right)-A_i(h)}{t^{k_i}-1}$

de manera que

$A=A_{i+1}(h)+O(h^{k_{i+1}})$

amb $A_0=A(h)$.

L'extrapolació de Richardson pot considerar-se com una seqüència de transformacions lineals.

A més, la fórmula general pot fer-se servir per estimar k₀ quan ni el seu valor ni el dPlantilla:'A es coneixen a priori. Aquesta tècnica pot ser útil per quantificar un radi de convergència desconegut. Aproximacions dPlantilla:'A donades a partir de tres mides de pas diferents, h, h / t, and h / s, fan que la relació exacta

$A=\frac{t^{k_0}A\left(\frac{h}{t}\right)-A(h)}{t^{k_0}-1}+O(h^{k_1})=\frac{s^{k_0}A\left(\frac{h}{s}\right)-A(h)}{s^{k_0}-1}+O(h^{k_1})$

porti a una relació aproximada

$A\left(\frac{h}{t}\right)+\frac{A\left(\frac{h}{t}\right)-A(h)}{t^{k_0}-1}\approx A\left(\frac{h}{s}\right)+\frac{A\left(\frac{h}{s}\right)-A(h)}{s^{k_0}-1}$

que pot ser resolta numèricament per aproximar k₀.

Exemple

Aplicant el Teorema de Taylor per h=0,

$f(x+h)=f(x)+f^{\prime }(x)h+\frac{f^{″}(x)}{2}{h}^2+\cdots$

la derivada de f(x) ve donada per

$f^{\prime }(x)=\frac{f(x+h)-f(x)}{h}-\frac{f^{″}(x)}{2}h+\cdots .$

Si les aproximacions inicials de la derivada s'escullen

$A_0(h)=\frac{f(x+h)-f(x)}{h}$

aleshores k_i = i+1.

Per t = 2, per primera fórumla extrapolada per A hauria de ser

$A=2A_0\left(\frac{h}{2}\right)-A_0(h)+O(h^2).$

Per la nova aproximació

$A_1(h)=2A_0\left(\frac{h}{2}\right)-A_0(h)$

podem tornar a extrapolar per obtenir

$A=\frac{4A_1\left(\frac{h}{2}\right)-A_1(h)}{3}+O(h^3).$

Bibliografia

• Plantilla:Ref-llibre

Enllaços externs

• Module for Richardson's Extrapolation, fullerton.edu Plantilla:En
• Fundamental Methods of Numerical Extrapolation With Applications, mit.edu Plantilla:En
• Richardson-Extrapolation Plantilla:En
• Richardson extrapolation on a website of Robert Israel (University of British Columbia) Plantilla:En