Vés al contingut

Extrapolació de Richardson

De la Viquipèdia, l'enciclopèdia lliure
(S'ha redirigit des de: Mètode d'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

[modifica]

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 general

[modifica]

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.

Exemple

[modifica]

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ències

[modifica]
  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. 

Bibliografia

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

Enllaços externs

[modifica]