Interpolasjon

Fra Wikipedia, den frie encyklopedi
Gå til: navigasjon, søk

Interpolasjon er i matematikk en prosess for å tilnærme en funksjon i et punkt ved hjelp av kjente funksjonsverdier i nærliggende punkt. Begrepet er ofte knyttet til at punktet der funksjonen er ukjent ligger innenfor et intervall utspent av punktene der funksjonen er kjent, i motsetning til ekstrapolasjon, der punktet ligger utenfor intervallet.

I mange tilfeller vil en funksjonssammenheng kunne være kjent bare i et endelig antall punkt. Som ledd i et eksperiment kan en for eksempel ha utført målinger av fallhastigheten til en ball, slik at denne er kjent for et sett av tidspunkt etter at ballen er sluppet. For å estimere hastigheten i et vilkårlig tidspunkt kan en bruke en interpolasjonsteknikk.

En vanlig brukt teknikk er lineær interpolasjon, der en antar at funksjonssammenhengen er lineær mellom de kjente punktene. Det eksisterer imidlertid en lang rekke teknikker for interpolasjon, studert i den delen av matematikk som kalles numerisk analyse. Mange metoder i numerisk analyse bruker interpolasjon som en viktig byggestein, for eksempel metoder for numerisk integrasjon.

Også kurvetilpasning og regresjonsanalyse kan brukes for å estimere en funksjonssammenheng, men disse teknikkene skiller seg fra interpolasjon ved at de kjente funksjonsverdiene ikke nødvendigvis blir eksakt reprodusert.

Formell definisjon[rediger | rediger kilde]

La (xi, fi) være et endelig sett av ordnede par. Interpolasjonsproblemet kan formuleres som å finne en funksjon f(x) i en gitt klasse av funksjoner W som oppfyller


\begin{array}{llll}
&f &= f(x) \in W \quad &x \in V \\
&f(x_i) &= f_i \quad &x_i \in V \quad  i=1,...,N 
\end{array}

Klassen av funksjoner W kan være for eksempel være polynomfunksjoner eller trigonometriske funksjoner. Det er utviklet flere spesielle funksjonsklasser for interpolasjon.

Funksjonen f(x) som blir brukt som basis for interpolasjonen kan omtales som en interpolant eller en interpolasjonsfunksjon. Verdiene xi kalles (interpolasjons)noder eller (interpolasjons)punkt.

I noen tilfeller kan det også stilles krav til verdien av den deriverte av funksjonen i interpolasjonspunktene, tilsvarende som for verdien av funksjonen i disse punktene.

Invers interpolasjon[rediger | rediger kilde]

I invers interpolasjon blir en tabulert funksjon brukt til å bestemme verdien av x når funksjonsverdien f(x) er gitt. For lineær interpolasjon er interpolasjonsproblemet og den inverse interpolasjonsproblemet ekvivalente, men de vil ikke være det for andre valg av interpolasjonsfunksjoner.

Interpolasjonsbasis[rediger | rediger kilde]

Dersom den valget klassen av interpolasjonsfunksjoner W er et endeligdimensjonalt vektorrom, så eksisterer det et endelig sett av funksjoner {qj} som basis for dette. Funksjonen en søker som interpolant kan da uttrykkes som en sum av disse basisfunksjonene:

f(x) = \sum_j a_j q_j(x) \,

Fra formuleringen av interpolasjonsproblemet finner en da at koeffisientene aj må oppfylle ligningssettet

f(x_i) = \sum_j^M a_j q_j(x_i) = f_i  \quad i=1,...,N

Her er M dimensjonen til vektorrommet W. Dette ligningssettet vil kunne brukes til å bestemme koeffisientene og dermed interpolanten. Dersom det ikke stilles vilkår på den deriverte av funksjonen kan en velge et interpolasjonsrom W med dimensjon M = N. Ligningssettet gir da N lineære ligninger for å bestemme de N ukjente interpolasjonskoeffisientene.

Eksempel[rediger | rediger kilde]

Plott av tabelldata

Anta at vi kjenner en funksjon i datapunktene vist i tabellen under.

x f(x)
0 0
1 0,8415
2 0,9093
3 0,1411
4 −0,7568
5 −0,9589
6 −0,2794

Interpolasjon vil være en teknikk for å finne et estimat av funksjonen i et mellomliggende punkt, som for eksempel x = 2,5. Datasettet er brukt i den følgende omtalen av interpolasjonsteknikker.

Interpolasjonsteknikker[rediger | rediger kilde]

Det eksisterer en lang rekke interpolasjonsteknikker, og noen av disse er omtalt i det følgende. Når en vurderer eller velger en interpolasjonsteknikk vil en ofte ta hensyn til følgende faktorer:

  • Hvor nøyaktig er metoden?
  • Hvor kostbar er metoden, i form av beregningsoperasjoner?
  • Hvor glatt er interpolanten?
  • Hvor mange interpolasjonspunkt trengs?
  • Hvor bør en definere interpolasjonspunktene?

Interpolasjonsteknikker vil kunne brukes for mange typer funksjoner, men for å forenkle presentasjonen er det i det følgende antatt at (xi,fi) er ordene par av reelle tall.

Stykkevis konstant interpolasjon[rediger | rediger kilde]

Dataeksempelet med stykkevis konstant interpolasjon

En enkel form for interpolasjon er å la den ukjente funksjonsverdien være lik verdien i det nærmeste kjente datapunktet. Interpolanten er da en stykkevis konstant funksjon. Metoden kalles også «nærmeste-nabo-interpolasjon».

I eksempelet gitt innledningsvis kan en velge f(2,5) = f(2) = 0,9093.

Lineær interpolasjon[rediger | rediger kilde]

Dataeksempelet med lineær interpolasjon

I lineær interpolasjon antar en at funksjonen er lineær mellom datapunktene. Dette er en svært vanlig form for interpolasjon. Ved hjelp av to nærliggende datapunkt 1 og 2 kan en vilkårlig funksjonsverdi regnes ut fra formelen

 f(x) = f_1 + (f_2 - f_1)\frac{(x-x_1)}{(x_2-x_1)}

I det innledede eksempelet ligger x=2,5 funksjonsverdien midtveis mellom f(2) = 0,9093 and f(3) = 0,1411, og lineær interpolasjon gir f(2,5) = 0,5252.

Lineær interpolasjon er enkel i bruk, men vil ofte være lite nøyaktig. Intuitivt kan en tenke seg at feilen vil vokse dess større krumning funksjonen har mellom interpolasjonspunktene, og dette kan også vises teoretisk. Det kan også være en ulempe at interpolanten ikke er deriverbar i datapunktene xi.

I datagrafikk brukes lineær interpolasjon så ofte at ordet «lerp» er etablert som en enkel forkortelse for «lineær interpolasjon». Forkortelsen har opphav i engelsk, men den har også etablert seg på norsk.[1]


Polynominterpolasjon[rediger | rediger kilde]

Dataeksempelet med 6.grads polynominterpolasjon

I polynominterpolasjon velger en et polynom som interpolant. Med (N+1) datapunkt vil det være mulig å tilpasse et polynom av grad minst lik N gjennom disse. For dataeksempelet kan en bruke en polynomtilnærming av skjette grad:

 f(x) = -0{,}0001521 x^6 - 0{,}003130 x^5 + 0{,}07321 x^4 - 0{,}3577 x^3 + 0{,}2255 x^2 + 0{,}9038 x.

Fra denne formelen finner en at f(2,5) = 0,5965.

For et stort antall datapunkt vil det beregnede polynomet kunne variere svært dramatisk i funksjonsverdi. Variasjonen er spesielt stor nær endene på dataintervallet når interpolasjonspunktene er ekvidistante, en oppførsel kjent som Runges fenomen. Variasjonen kan reduseres ved spesielle valg av interpolasjonspunktene, i såkalt Chebyshevinterpolasjon.

Når interpolasjonspolynomet er bestemt vil beregninger kunne utføres effektivt ved hjelp av Horners metode.

Splineinterpolasjon[rediger | rediger kilde]

Dataeksempelet med spline-interpolasjon

Spline-interpolasjon er en generalisering av lineær interpolasjon, der en bruker polynom med lav grad mellom datapunktene. Istedenfor å bruke et fast polynom til å interpolere alle verdier av x velger en i steden å la definisjonen av polynomet variere fra dataintervall til dataintervall. Polynomene som brukes konstrueres på en slik måte at en oppnår en viss grad av glatthet i interpolanten, for alle verdier av argumentet x.

For dataeksempelet i innledningen kan en bruke kubiske splines, dvs stykkevis tredjegradspolynom:

 f(x) = \begin{cases}
-0{,}1522 x^3 + 0{,}9937 x, &x \in [0,1], \\
-0{,}01258 x^3 - 0{,}4189 x^2 + 1{,}4126 x - 0{,}1396, &x \in [1,2], \\
0{,}1403 x^3 - 1{,}3359 x^2 + 3{,}2467 x - 1{,}3623, &x \in [2,3], \\
0{,}1579 x^3 - 1{,}4945 x^2 + 3{,}7225 x - 1{,}8381, &x \in [3,4], \\
0{,}05375 x^3 -0{,}2450 x^2 - 1{,}2756 x + 4{,}8259, &x \in [4,5], \\
-0{,}1871 x^3 + 3{,}3673 x^2 - 19{,}3370 x + 34{,}9282, &x \in [5,6]. \\
\end{cases}

Denne forma for interpolasjon gir f(2,5) = 0,5972.

Statistisk interpolasjon[rediger | rediger kilde]

Statistiske interpolasjonsmetoder er basert på teori og metoder fra statistikk. En viktig klasse av metoder er kriging, oppkalt etter den sørafrikanske gruveingeniøren Daniel Gerhardus Krige. Dette er romlige interpolasjonsteknikker, basert på at en kjenner en observert størrelse i gitte punkt i rommet, og at en så ønsker å bestemme størrelsen i et vilkårlig romlig punkt. Metoden forutsetter at størrelsen som interpoleres er romlig korrelert.[2]

Interpolasjon med kriging gir under visse vilkår en såkalt «best linear unbiased estimator», ofte forkortet «BLUE».

Etymologi[rediger | rediger kilde]

Ordet «interpolasjon» har opphav i latin, fra sammensetningen av «inter» = «mellom» og «polire» = «å glatte». Tilsvarende er «ekstrapolasjon» laget ved hjelp av forstavelsen «extra» = «utenfor».[3]

For å lette beregninger hadde man tabeller av spesielle funksjoner, som trigonometriske funksjoner og logaritmer. Dersom en hadde behov for en funksjonsverdi som ikke fantes i tabellen, måtte en «glatte over» gapet i tabellen ved å beregne den ukjente funksjonsverdien fra de gitte tabellverdiene.

Historie[rediger | rediger kilde]

Over tusen år før Kristus hadde en i Babylonia tabeller for ulike funksjoner, tabeller som ble brukt til å løse spesielle matematiske problem. Dette var tabeller for multiplikasjon, resiproke tall, kvadrattall og også logaritme-lignende tabeller. Babylonierene brukte lineær interpolasjon når de hadde behov for funksjonsverdier som ikke var tabulert. En tabell over (n3 + n2), samt lineær interpolasjon i denne, ble brukt til å løse visse typer kubiske ligninger.

Referanser[rediger | rediger kilde]

  1. ^ Obligatorisk oppgave i informatikk. Universitetet i Oslo (2003). Besøkt 22. juli 2012.
  2. ^ Jean-Paul Gilès, Pierre Delfiner (1999). Geostatistics: Modelling spatial uncertainty. John Wiley & Sons, Inc, Hoboken, New Jersey. ISBN 978-0-470-18315-1.
  3. ^ Steven Schwartzman (1994). The words of mathematics. An etymological dictionary of mathematical terms used in English. The Mathematical Association of America, Washington, DC. ISBN 0-88385-511-9.

Litteratur[rediger | rediger kilde]

  • Germund Dahlquist, Åke Björck (1974). Numerical methods. Prentice-Hall Inc, New Jersey. ISBN 0-13-627315-7.
  • M.J.D.Powell (1981). Approximation theory and methods. Cambridge University Press, Cambridge. ISBN 0-521-22472-1.
  • C.B.Boyer (1968). A history of mathematics. John Wiley & Sons, Inc, Princeton, USA. ISBN 0-691-02391-3.