Extrapolació de Richardson

algorisme matemàtic

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'úsModifica

Suposem que volem aproximar   i disposem d'un mètode   que depèn d'un paràmetre   prou petit tal que

 

Definim un nou mètode

 

Així,

 

  s'anomena extrapolació de Richardson d'A(h) i té un error estimat d'ordre   respecte  .

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 generalModifica

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

 

on els ai són constants desconegudes i les ki són constants conegudes que compleixen hki > hki+1.

El valor exacte que busquem ve donat per

 

que pot simplificar-se en notació O gran com

 

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

 
 

Si multipliquem la segona equació per tk0 i li restem la segona equació obtenim

 

que aïllant A esdevé

 

Amb aquest procediment hem obtingut una millor aproximació d'A traeint-li el major terme en l'error, que era O(hk0). 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

 

de manera que

 

amb  .

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 k0 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

 

porti a una relació aproximada

 

que pot ser resolta numèricament per aproximar k0.

ExempleModifica

Aplicant el Teorema de Taylor per h=0,

 

la derivada de f(x) ve donada per

 

Si les aproximacions inicials de la derivada s'escullen

 

aleshores ki = i+1.

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

 

Per la nova aproximació

 

podem tornar a extrapolar per obtenir

 

ReferènciesModifica

  1. Richardson, Lewis Fry «The approximate arithmetical solution by finite differences of physical problems including differential equations, with an application to the stresses in a masonry dam» (en anglès). Philosophical Transactions of the Royal Society A, 210, 459-470, 1911, pàgs. 307–357. DOI: 10.1098/rsta.1911.0009.
  2. Richardson, Lewis Fry; Gaunt, John Arthur «The deferred approach to the limit» (en anglès). Philosophical Transactions of the Royal Society A, 226, 636-646, 1927, pàg. 299–349. DOI: 10.1098/rsta.1927.0008.
  3. Birkhoff, Garrett; Rota, Gian-Carlo. Ordinary differential equations (en anglès). 3a ed.. John Wiley and sons, 1978, p. 126. ISBN 0-471-07411-X. OCLC 4379402. 

BibliografiaModifica

  • Brezinski, C.; Redivo Zaglia, M. Extrapolation Methods. Theory and Practice (en anglès). Amsterdam: North Holland, 1991. ISBN 978-0444888143. 

Enllaços externsModifica