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

$A-A(h)=c_{n}h^{n}+c_{m}h^{m}+\ldots$

hvor m > n er begge hele tall, mens c_n og c_m  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 hⁿ.

Hvis man hadde kjent koeffisienten c_n, kunne man ha korrigert denne approksimasjonen og dermed fått et resultat med større nøyaktighet av orden h^m. 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_n elimineres slik at man står igjen med

$A(1-N^{n})+N^{n}A(h/N)-A(h)=c'_{m}h^{m}+\ldots$

hvor koeffisienten c'_m i alminnelighet er forskjellig fra c_m. Derfor har tilnærmelsen

$A_{1}(h/N)={N^{n}A(h/N)-A(h) \over N^{n}-1}$

en nøyaktighet av orden h^m 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². Dermed kan koeffisienten c'_m elimineres slik at et resultat med nøyaktighet h^p kan oppnås hvor p > m. Det er da gitt ved

$A_{2}(h/N^{2})={N^{m}A_{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 (x) kan numerisk finnes fra definisjonen

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

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² 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⁰ = 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².

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³ er derfor den deriverte lik med A₂(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.