Extrapolació de Richardson

En el camp de l'anàlisi numèrica, l'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 segle xx.^[1][2] En paraules de Birkhoff i Rota,

«	...la seva utilitat per computacions pràctiques difícilment pot subestimar-se.	»
— Garrett Birkhoff i Gian-Carlo Rota, Ordinary differential equations

^[3]

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 ${\displaystyle A^{*}}$ i disposem d'un mètode ${\displaystyle A(h)}$ que depèn d'un paràmetre ${\displaystyle h}$ prou petit tal que

${\displaystyle A(h)=A^{\ast }+Ch^{n}+o(h^{n+1})\;}$

Definim un nou mètode

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

Així,

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

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

Sovint és més senzill obtenir una precisió donada fent servir R(h) en comptes d'A(h') amb una h' 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ó d'A que depèn d'un pas positiu h amb una fórmula d'error

${\displaystyle 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

${\displaystyle 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

${\displaystyle 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:

${\displaystyle A=A(h)+a_{0}h^{k_{0}}+O(h^{k_{1}})\,\!}$

${\displaystyle 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

${\displaystyle (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é

${\displaystyle 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ó d'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

${\displaystyle 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

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

amb ${\displaystyle 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 d'A es coneixen a priori. Aquesta tècnica pot ser útil per quantificar un radi de convergència desconegut. Aproximacions d'A donades a partir de tres mides de pas diferents, h, h / t, and h / s, fan que la relació exacta

${\displaystyle 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

${\displaystyle 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,

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

la derivada de f(x) ve donada per

${\displaystyle f'(x)={\frac {f(x+h)-f(x)}{h}}-{\frac {f''(x)}{2}}h+\cdots .}$

Si les aproximacions inicials de la derivada s'escullen

${\displaystyle 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

${\displaystyle A=2A_{0}\!\left({\frac {h}{2}}\right)-A_{0}(h)+O(h^{2}).}$

Per la nova aproximació

${\displaystyle A_{1}(h)=2A_{0}\!\left({\frac {h}{2}}\right)-A_{0}(h)}$

podem tornar a extrapolar per obtenir

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