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* &rarr; 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

:  A - A(h) = c_nh^n + c_mh^m + \ldots 

hvor *m > n* er begge hele tall, mens *c<sub>n</sub>* og *c<sub>m</sub>*&thinsp; er koeffisienter som man prinsipielt kan finne. Det er vanlig å si at på denne formen har det numeriske resultatet *A*(*h*)&thinsp; en nøyaktighet av orden  *h<sup>n</sup>*.

Hvis man hadde kjent koeffisienten  *c<sub>n</sub>*, kunne man ha korrigert denne approksimasjonen og dermed fått et resultat med større nøyaktighet av orden *h<sup>m</sup>*. 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

:  A - A(h/N) = c_n(h/N)^n + c_m(h/N)^m + \ldots 

Ved å kombinere disse to tilnærmete resultatene kan koeffisienten *c<sub>n</sub>* elimineres slik at man står igjen med

:  A(1 - N^n) + N^nA(h/N) - A(h) = c'_mh^m + \ldots 

hvor koeffisienten *c'<sub>m</sub>* i alminnelighet er forskjellig fra *c<sub>m</sub>*. Derfor har tilnærmelsen

:  A_1(h/N) = {N^nA(h/N) - A(h)\over N^n - 1} 

en nøyaktighet av orden *h<sup>m</sup>* 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*&thinsp;2. Dermed kan koeffisienten *c'<sub>m</sub>* elimineres slik at et resultat med nøyaktighet *h<sup>p</sup>* kan oppnås hvor *p > m*. Det er da gitt ved

:  A_2(h/N^2) = {N^mA_1(h/N^2) - A_1(h/N)\over N^m - 1} 

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

: \begin{array}{l | c | c | r}
h & O(h^n) & O(h^m) & O(h^p) \\
\hline
h & A(h) &  & \\
h/N & A(h/N) & A_1(h/N) & \\
h/N^2 & A(h/N^2) & A_1(h/N^2) & A_2(h/N^2) \\
\end{array}

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*&thinsp;(*x*) kan numerisk finnes fra definisjonen

: f\!\,'(x) = \frac{f(x +h) - f(x)}{h} 

i grensen *h* &rarr; 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*&thinsp;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<sup>&thinsp;x</sup>&thinsp;* i punktet *x* = 0. Da den deriverte av funksjonen i dette tilfellet er lik med samme funksjon, blir derfor det eksakte resultatet *A* = *e*&thinsp;0 = 1.

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

:  A(0.2) = {e^{0.2} - e^0\over 0.2} = {1.221403 - 1\over 0.2} = 1.107014 

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

:  A_1(0.1) = 2\cdot A(0.1) - A(0.2) = 1.051709 - 1.107014 = 0.996404 

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

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

: \begin{array}{l | c | c | r}
h & O(h) & O(h^2) & O(h^3) \\
\hline
0.2 & 1.107014 &  & \\
0.1 & 1.051709 & 0.996404 & \\
0.05 & 1.025422 & 0.999135 & 1.000045 \\
\end{array}

Til størrelsesorden *h*&thinsp;3 er derfor den deriverte lik med *A*2(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.