Richardson-ekstrapolasjon

Richardson-ektrapolasjon er en metode for å oppnå større nøyaktighet ved beregninger i numerisk analyse. Den ble foreslått av Lewis Fry Richardson i 1927 og danner grunnlaget for Romberg-integrasjon.

Ved de fleste numeriske beregninger må en kontinuerlig variabel erstattes med en som tar diskrete verdier. Er dette en uavhengig variabel, kan den angis ved verdier som skilles ved en liten størrelse som typisk betegnes ved h. I grensen h → 0 kan det eksakte resultatet av beregningen finnes. Så lenge h er liten, vil resultatet være tilnærmet og vanligvis mer nøyaktig desto mindre h er. Richardson-ekstrapolasjonen kan oppnå en forbedret nøyaktighet uten å måtte benytte så små verdier av h at avrundingsfeil ved beregningen begynner å påvirke resultatet.

Matematisk formulering

Betegner man størrelsen som skal beregnes med A, kan man finne det tilnærmete resultatet A(h) ved å benytte en slik diskretisering. Sammenhengen mellom disse vil da ha den generelle formen

 

hvor m > n er begge hele tall, mens cn og cm  er koeffisienter som man prinsipielt kan finne. Det er vanlig å si at på denne formen har det numeriske resultatet A(h)  en nøyaktighet av orden  hn.

Hvis man hadde kjent koeffisienten  cn, kunne man ha korrigert denne approksimasjonen og dermed fått et resultat med større nøyaktighet av orden hm. Det kan gjøres ved å gjenta beregningen med en mindre diskretisering h/N hvor tallet N > 1. Ofte velges for eksempel N = 2 som betyr at de diskretiserte punktene har halvparten av den opprinnelige avstanden. Et mer nøyaktig resultat A(h/N) oppnås dermed fra

 

Ved å kombinere disse to tilnærmete resultatene kan koeffisienten cn elimineres slik at man står igjen med

 

hvor koeffisienten c'm i alminnelighet er forskjellig fra cm. Derfor har tilnærmelsen

 

en nøyaktighet av orden hm og er derfor mer presis enn den underliggende forbedringen  A(h/N). Dette er essensen av Richardson-ekstrapolasjonen.

Richardson-tabell

Enda mer nøyaktigere resultat kan finnes ved å ta utgangspunkt i dene første Richardson-tilnærmelsen og så gjenta beregningen ved å redusere diskretiseringen med enda en faktor N slik at den effektivt blir h/N 2. Dermed kan koeffisienten c'm elimineres slik at et resultat med nøyaktighet hp kan oppnås hvor p > m. Det er da gitt ved

 

På denne måten kan Richardson-ekstrapolasjonen gjøres iterative med stadig økende nøyaktighet bare begrenset av avrundingsfeil i selve beregningsprosessen.

Man kan fremstille de forskjellige delresultatene i denne prosessen på tabellform. De tre første steppene gir på den måten

 

hvor hver horisontal linje gir en ny ekstrapolasjon. Elementene beregnes fra venstre mot høyre hvor resultatet til hver orden kan avleses på enden av linjen.

Eksempel

Den deriverte av en funksjon f (x) kan numerisk finnes fra definisjonen

 

i grensen h → 0. Resultatet vil da ha en nøyaktighet som er av størrelsesorden h. Man kan så bruke Richard-ekstrapolasjonen til å beregne den deriverte med nøyaktighet h 2 eller høyere. Det tilsvarer at potensene n = 1, m = 2 etc.

Som et enkelt eksempel kan man beregne den deriverte av eksponentialfunksjonen e x  i punktet x = 0. Da den deriverte av funksjonen i dette tilfellet er lik med samme funksjon, blir derfor det eksakte resultatet A = e 0 = 1.

Velger man en diskretisering h = 0.2, blir laveste approksimasjon til den deriverte

 

Feilen i dette resultatet er omtrent en tiendedel som tilsvarer størrelsen til h = 0.2.

Første Richardson-tilnærmelse kan nå finnes ved å betrakte den halverte diskretiseringen h = 0.1 som tilsvarer å ta N = 2. Da finnes på samme måte A(0.1) = 1.051709 som gir

 

Her er nå feilen mindre enn en hundredel som tilsvarer størrelsesorden h 2.

Man kan gjenta denne prosessen enda en gang for potensen m = 2 og samle resultatene i Richardson-tabellen:

 

Til størrelsesorden h 3 er derfor den deriverte lik med A2(0.05) = 1.000045 som er meget tett opp til det eksakte svaret.

Litteratur
 M.L. Boas, Mathematical Methods in the Physical Sciences, John Wiley & Sons, New York (1983). ISBN 0-471-04409-1.
 M.J. Maron, Numerical Analysis: A Practical Approach, Macmillan Publishing Company, ISBN 0-02-376210-1.

Numerisk analyse
Matematisk fysikk