Interpolacija

Za ostala značenja vidi Interpolacija (razdvojba).

Interpolacija u matematičkom polju numeričke matematike označava metodu konstrukcije novih točaka podataka unutar raspona diskretnog skupa poznatih točaka podataka.

U inženjerstvu i znanosti interpolacija često ima mnogo točaka podataka prikupljenih uzorkovanjem ili eksperimentiranjem, te se njome pokušava konstruirati funkcija koja približno odgovara tim točkama podataka. To se naziva prilagodba krivulje ili regresijska analiza. Interpolacija je specifični slučaj prilagodbe krivulje u kojem funkcija mora točno prolaziti točkama podataka.

Drugi problem koji je blisko povezan s interpolacijom je aproksimacija složene funkcije jednostavnom funkcijom. Ako pretpostavimo da znamo funkciju koja je previše složena za učinkovitu procjenu, onda bismo mogli izabrati nekoliko poznatih točaka podataka iz složene funkcije, zatim izraditi preglednu tablicu i pokušati interpolirati te točke podataka radi konstrukcije jednostavnije funkcije. Naravno, kada koristimo jednostavnu funkciju za izračun novih točaka podataka obično ne dobivamo isti rezultat kada bismo koristili originalnu funkciju, već se ovisno o problemskoj domeni i interpolacijskoj metodi korištenoj za dobivanje jednostavnosti pojavljuje pogreška.

Treba napomenuti kako postoji druga potpuno različita vrsta interpolacije u matematici koja se naziva "interpolacija operatora". Klasičan rezultat oko interpolacije operatora jesu Riesz-Thorinov teorem i Marcinkiewiczov teorem. Također postoje mnogi naknadni rezultati.

Definicija

Interpolacija dolazi od riječi inter između i polos os, osovina, odnosno točka, čvor. Svako izračunavanje nove točke između dviju ili više postojećih točaka podataka je interpolacija.

Postoje mnoge metode interpolacije od kojih mnoge uključuju prilagođavanje nekakve vrste funkcije podatcima i zatim procjenu vrijednosti te funkcije na željenoj točki. Ovo ne isključuje ostale načine poput statističkih metoda izračuna interpoliranih podataka.

Jedan od najjednostavnijih oblika interpolacije je izračun aritmetičke sredine iz vrijednosti dviju susjednih točaka kako bi se odredila točka u njihovoj sredini. Isti se rezultat dobiva određivanjem vrijednosti linearne funkcije u srednjoj točki.

Danom nizu od n različitih brojeva x_k koje nazivamo čvorovi tako da za svaki x_k postoji drugi broj y_k, naći ćemo funkciju f za koju vrijedi

$f(x_{k})=y_{k}{\mbox{ , }}k=1,\ldots ,n$

Par x_k,y_k naziva se točka podataka, a f se naziva interpolant za te točke podataka.

Kada su brojevi y_k dani poznatom funkcijom f, onda se ponekad piše f_k.

Primjer

Za primjer pretpostavimo da imamo tablicu nalik ovoj u kojoj su navedene vrijednosti nepoznate funkcije f.

Prikaz točaka podataka danih u tablici.

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

Interpolacija osigurava način procjenjivanja funkcije na međutočkama, npr. ako x = 2,5.

Postoji mnogo različitih interpolacijskih metoda od kojih su neke opisane ispod. Neka pitanja koja se javljaju kod izbora prikladnog algoritma jesu: Koliko je metoda pouzdana? Koliko je ona točna? Koliko je interpolant gladak? Koliko je potrebno točaka podataka?

Lokalna konstantna interpolacija

Lokalna konstantna interpolacija ili proksimalna interpolacija.

Za više detalja o ovoj temi vidi proksimalna interpolacija.

Najjednostavnija interpolacijska metoda je lociranje najbliže vrijednosti podataka i pridruživanje iste vrijednosti. Kod jedne dimenzije rijetki su dobri razlozi za izbor ove vrste interpolacije umjesto linearne koja je gotovo jeftina, no kod viših dimenzija, u multivarijatnoj interpolaciji, proksimalna interpolacija je prikladan izbor zbog svoje brzine i jednostavnosti.

Po dijelovima linearna interpolacija

Prikaz podataka s nadodanom linearnom interpolacijom

Glavni članak: linearna interpolacija

Jedna od najjednostavnijih metoda je po dijelovima linearna interpolacija (ponekad se naziva lerp). Uzmimo u obzir gore spomenuti primjer određivanja f(2,5). Budući da je 2,5 sredina između 2 i 3, razumljivo je uzeti sredinu f(2,5) između f(2) = 0,9093 i f(3) = 0,1411, što daje rezultat od 0,5252.

Linearna interpolacija općenito uzima dvije točke podataka, recimo (x_a,y_a) i (x_b,y_b), pa je interpolant zadan:

$y=y_{a}+(x-x_{a}){\frac {(y_{b}-y_{a})}{(x_{b}-x_{a})}}$ na točki (x,y).

Linearna interpolacija je brza i lagana, no nije odveć precizna. Drugi nedostatak je nediferencijabilnost interpolanta na točki x_k.

Sljedeća procjena pogreške pokazuje da linearna interpolacija nije odveć precizna. Označimo funkciju koju želimo interpolirati za g, te pretpostavimo da x leži između x_a i x_b i da je g dvostruko kontinuirano diferencijabilan. Tada je pogreška linearne interpolacije

$|f(x)-g(x)|\leq C(x_{b}-x_{a})^{2}\quad {\mbox{gdje je}}\quad C={\frac {1}{8}}\max _{y\in [x_{a},x_{b}]}|g''(y)|.$

Zapisano riječima, pogreška je proporcionalna kvadratu udaljenosti između točaka podataka. Pogreška nekih drugih metoda, uključujući polinomnu interpolaciju i spline interpolaciju (opisanu dolje), proporcionalna je većim potencijama udaljenosti između točaka podataka. Ove metode također produciraju glađe interpolante.

Polinomna interpolacija

Prikaz podataka s primijenjenom polinomnom interpolacijom

Glavni članak: polinomna interpolacija

Polinomna interpolacija je generalizacija linearne interpolacije. Primijetite kako je linearni interpolant linearna funkcija. Sada ovaj interpolant zamjenjujemo polinomom višeg stupnja.

Polinom u općem obliku zapisujemo kao f(x)=a_nxⁿ+a_n-1x^n-1+...+a₁x+a₀, dakle kao izraz s n+1 nepoznanicom. Kako bi ih jednoznačno odredili potreban nam je n+1 podatak, odnosno točke interpolacije. Iz toga slijedi da s n točaka interpolacije (uz zadovoljavanje određenih uvjeta, poput onog da dvije točke koje želimo interpolirati ne smiju imati jednaku x-koordinatu) jednoznačno možemo odrediti polinom stupnja n-1 koji kroz njih prolazi.

Dva su osnovna oblika u kojima se taj intepolacijski polinom može zapisati. Prvi, Lagrangeov oblik interpolacijskog polinoma vrlo je jednostavno zapisati. No zbog njegovog nestandardnog zapisa, vrednovanje vrijednosti tog polinoma ima visoku složenost, pa se u pravilu ne upotrebljava u praksi. S druge strane, Newtonov oblik interpolacijskog polinoma zahtjeva više posla kod računanja njegovih koeficjenata (vrijednosti a_i), no standardni zapis omogućava brzo izvrednjavanje nekim od algoritama za izvrednjavanje polinoma, poput Hornerovog algoritma. Metoda računanja koeficijenata Newtonovog interpolacijskog polinoma naziva se računanjem podijeljenih razlika.

Uzmimo opet u obzir gore dan problem. Sljedeći polinom šestog stupnja prolazi kroz svih sedam točaka:

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

Zamjenivši x = 2,5, dobivamo da je f(2.5) = 0,5965.

Općenito govoreći, ako imamo n točaka podataka, onda postoji točno jedan polinom najviše n-1 stupnja koji prolazi kroz sve točke podataka. Interpolacijska pogreška je proporcionalna udaljenosti između točaka podataka s potencijom n. štoviše, interpolant je polinom i stoga beskonačno diferencijabilan (iako su sve derivacije nakon konačno mnogo njih identički jednake nuli). Stoga vidimo da polinomna interpolacija rješava sve probleme linearne interpolacije.

Polinomna interpolacija ipak ima neke nedostatke. Računanje interpolirajućeg polinoma računski je zahtjevnije (vidi računska složenost) u usporedbi s linearnom interpolacijom. Štoviše, polinomna interpolacija ne mora uopće biti točna, posebice na krajnjim točkama (vidi Rungeov fenomen). Poznati su npr. primjeri velikih odstupanja polinomnih interpolacija kod interpoliranja sporo rastućih ili padajućih funkcija s velikim udaljenostima između čvorova interpolacije. Ovi nedostatci mogu se izbjeći uporabom spline interpolacije.

Spline interpolacija

Prikaz podataka s primijenjenom spline interpolacijom

Glavni članak: spline interpolacija

Sjetimo se kako po dijelovima linearna interpolacija koristi linearnu funkciju na svakom intervalu [x_k,x_k+1]. Spline interpolacija koristi polinome manjeg stupnja na svakom intervalu i odabire polinomne dijelove tako da skupa glatko pristaju. Rezultirajuća funkcija naziva se spline.

Primjerice, prirodni kubični spline je segmentno kubičan i dvostruko kontinuirano diferencijabilan. Štoviše, njegova druga derivacija je nula na krajnjim točkama. Prirodni kubični spline koji interpolira točke na gornjoj tablici dan je izrazom

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

U tom slučaju dobivamo f(2,5)=0,5972.

Poput polinomne interpolacije, spline interpolacijom nastaje manja pogreška nego kod linearne interpolacije, a interpolant je glađi. Interpolant je ipak lakši za procjenu od polinoma desetog stupnja korištenog u polinomnoj interpolaciji. Ona također ne pati od Rungeova fenomena.

Ostali oblici interpolacije

Ostali oblici interpolacije mogu se konstruirati odabirom različitog razreda interpolanata. Primjerice, racionalna interpolacija je interpolacija racionalnim funkcijama, a trigonometrijska interpolacija je interpolacija trigonometrijskim polinomima. Diskretna Fourierova transformacija poseban je slučaj trigonometrijske interpolacije. Druga mogućnost je upotreba waveleta.

Whittaker–Shannonova interpolacijska formula može se koristiti ako je broj točaka podataka beskonačan.

Multivarijatna interpolacija je interpolacija funkcija s više od jedne varijable. Metode uključuju bilinearnu interpolaciju i bikubičnu interpolaciju u dvije dimenzije, te trilinearnu interpolaciju u tri dimenzije.

Ponekad ne samo da znamo vrijednost funkcije koju želimo interpolirati na neke točke nego također i njezinu derivaciju. To dovodi do problema Hermiteove interpolacije.

Srodni koncepti

Termin ekstrapolacija se koristi kada želimo pronaći točke podataka izvan dometa poznatih točaka podataka.

U problemima prilagođavanja krivulja ublaženo je ograničenje da interpolant mora točno prolaziti kroz točke podataka. Jedini zahtjev odnosi se na što je moguće bliži pristup točkama podataka. To zahtijeva određivanje parametara potencijalnih interpolanata i postojanje načina za određivanje pogreške. U najjednostavnijem slučaju to vodi do aproksimacije najmanjih kvadrata.

Teorija aproksimacije istražuje način za pronalazak najbolje aproksimacije za danu funkciju drugom funkcijom iz predeterminiranih klasa, te određivanje prikladnosti te aproksimacije. Ovo jasno daje granicu za to koliko dobro interpolant može aproksimirati nepoznatu funkciju.

Referencije

• David Kidner, Mark Dorey and Derek Smith (1999). What's the point? Interpolation and extrapolation with a regular grid DEM. IV International Conference on GeoComputation, Fredericksburg, VA, USA.
• Kincaid, David; Ward Cheney (2002). Numerical Analysis (3rd edition). Brooks/Cole. ISBN 0-534-38905-8   Chapter 6.
• Schatzman, Michelle (2002). Numerical Analysis: A Mathematical Introduction. Clarendon Press, Oxford. ISBN 0-19-850279-6   Chapters 4 and 6.

Vanjske poveznice

• GaussianProcesses.com: Teorija i primjene Gaussovih procesa
• DotPlacer applet : Applet koji prikazuje različite interpolacijske metode s pomičnim točkama