Interpolacija

U matematičkoj podoblasti numerička analiza, **interpolacija** je metod konstruisanja novih tački na grafikonu unutar ranga diskretnog skupa poznatih tačaka na grafikonu.

U inženjerstvu i nauci, barata se mnoštvom brojeva i tačaka na grafikonima, koje su dobijene uzorkovanjem ili eksperimentisanjem, te se nastoji konstruisati funkcija koja približno pristaje svim tačkama na grafikonu. Ovo se naziva prilagođavanje krive ili regresiona analiza. Interpolacija je poseban slučaj prilagođavanja krive, u kojem funkcija mora tačno proći kroz zadane tačke na grafikonu.

Drugačiji problem, koji je usko vezan za interpolaciju, je aproksimacija komplikovane funkcije preko jednostavnije funkcije. Pretpostavimo da poznajemo funkciju, ali da je ona previše kompleksna kako bi je efikasno izračunali. Tada možemo izabrati nekoliko poznatih tačaka iz komplikovane funkcije, praveći preglednu tablicu, te pokušavamo interpolisati te tačke kako bi konstruisali jednostavniju funkciju. Naravno, kada koristimo jednostavniju funkciju kako bi izračunali nove tačke na grafikonu, obično ne dobijamo isti rezultat kao što bi dobili kod originalne funkcije, ali u zavisnosti od domena problema i metoda interpolacije kojeg smo koristili, dobijena jednostavnost može nadoknaditi grešku.

Potrebno je spomenuti da postoji i druga veoma različita vrsta interpolacije u matematici, naziva "interpolacija operatora". Kao klasične rezultate u interpolaciji operatora imamo Riesz-Thorinov teorem i Marcinkiewiczov teorem. Postoje i neki drugi rezultati, koje sada nećemo spominjati.

## Definicjja 
I riječi '**interpolacija**, *inter* znači "između", a *polacija* (pol) znači taćka ili čvor. Bilo koje sredstvo izračunavanja nove tačke između dvije ili više već postojećih tačaka, naziva se interpolacija.

Postoji mnogo načina d a se to uradi, od kojih mnogi uključuju  prilagođavanje neke vrste funkcije zadanim podacima i izračunavanje te funkcije u željenoj tački. Ovo ne isključuje druga sredstva, kao što su statističke metode izračunavanja interpolisanih podataka.

Jedan od najjednostavnijih oblika interpolacije je uzimanje aritmetičke sredine vrijednosti dvije susjedne tačke, kako bi našli vrijednost tačke između njih. Ovo daje isti rezultat kao i linerna funkcija izračunata u sredini te dvije zadane tačke.

Za dati niz *n* *različitih* brojeva *x**k*, koji se nazivaju **čvorovi** i za svaki *x**k* drugi broj *y**k*, tražimo funkciju *f* tako da je

:f(x_k) = y_k \mbox{ , } k=1,\ldots,n

Par *x**k*,*y**k* naziva se **tačka na grafikonu**, a *f* se naziva **interpolant** za te tačke na grafikonu.

Kada su brojevi *y**k* dati preko poznate funkcije *f*, ponekad to pišemo kao *f**k*.

## Primjer 
Na primjer, pretpostavimo da imamo slijedeću tabelu, koja daje neke vrijednosti funkcije *f*. 
desno|mini|230px|Raspored tačaka na grafikonu, kao što je zadato u tabeli desno.

Interpolacija nam daje mogućnost da procijenimo vrijednost funkcije u nekim srednjim tačkmama, kao što je *x*&nbsp;=&nbsp;2,5.

Postoji mnogo različitih metoda interpolacije, od kojih su neke opisane u tekstu ispod. Treba voditi računa, kada birate najprikladniji algoritam, na slijedeće: Kako je metod tačan? Koliko je težak? Koliko je gladak interpolant? Koliko je potrebno tačaka na grafikonu?

## Interpolacija izlomljene konstante 
[mini|desno|Interpolacija izlomljene konstante, ili [interpolacija najbližeg susjeda.]]
Najjednostavniji metod interpolacije da da se locira najbliža tačka na grafikonu, te da joj se pridruži neka vrijednost. U jednoj dimenziji, rijetko postoje dobri razlozi da se koristi ovaj tip nad linearnom interpolacijom, koja je skoro uvijek jednoako teška, ali u više dimenzija, kod multivarijatne interpolacije, interpolacija izlomljene konstantethis može imati prednost zbog svoje brzine i jednostavnosti.

## Linearna interpolacija 
desno|mini|230px|Grafikon sa primjenom linearne interpolacije

Jedan od najjednostavnijih metoda je linearna interpolacija. Razmotrimo gornji primjer pronalaženja vrijednosi *f*(2,5). Pošto je 2,5 srednja vrijednost između 2 i 3, opravdano, za vrijednost *f*(2,5), možemo uzeti srednju vrijednost između *f*(2) = 0,9093 i *f*(3) = 0,1411, iz čega dobijamo vrijednost 0,5252.

Općenito, linearna interpolacija uzima dvije tačke na grafikonu, recimo (*x**a*,*y**a*) i (*x**b*,*y**b*), a interpolant je dat kao:

: y = y_a + \frac{(x-x_a)(y_b-y_a)}{(x_b-x_a)}  u tački (*x*,*y*).

Linearna interpolacija je brza i lagana, ali nije precizna. Još jedna nepovoljnost je ta što interpolant nije diferencijabilan u tački *x**k*.

Slijedeća procjena greške pokazuje da   linerana interpolacija nije preciznat. Označimo funkciju koju želimo interpolisati sa *g*, te pretpostavimo da *x* leži između *x**a* i *x**b* i da je *g* dva puta neprekidno diferencijabilna. Tada greška pri linearnoj interpolaciji iznosi

: |f(x)-g(x)| \le C(x_b-x_a)^2 \quad\mbox{gdje je}\quad C = \frac18 \max_{y\in[x_a,x_b]} |g*(y)|. 

Riječima, greška je proporcionalna kvadratu udaljenosti između tačaka na grafikonu. Greška kod nekih drugih metoda, uključujući polinomsku i splajn interpolaciju (opisane u tekstu ispod), je proporcionalna višim stepenima udaljenosti između tačaka na grafikonu. Ovi metodi, također, daje "glađe" interpolante.

## Polinomska interpolacija 
desno|mini|230px|Grafikon sa primjenom polinomske interpolacije

Polinomska interpolacija je generalizacija linearne interpolacije. Prethodno smo vidjeli da je linerani interpolant linearna funkcija. U ovom slučaju, zamijenimo taj interpolant sa polinomom višeg stepena.

Razmotrimo ponovo prethodni problem. Slijedeći polinom šestog stepena prolazi kroz svih sedam tačaka:
: 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. 

Zamjenom *x* = 2,5, dobijamo da je *f*(2,5) = 0,5965.

Općenito, ako imamo *n* tačaka na grafikonu, postoji tačno jedan polinom najvišeg stepna *n*−1 koji prolazi kroz sve tačke na grafikonu. Interpolacijska greška proporcionalna je udaljenosti između tačaka na stepen od *n*. Dalje, interpolant je polinom, te je zbog toga beskonačno puta diferencijabilan. Tako vidimo da polinomska interplacija rješava sve probleme linearne interpolacije.

Međutim, polinomska interpolacija, također, ima  i nedostatke. Izračunavanje interpolacionog polinoma prilično je teško (pogledajte teorija kompleksnosti izračunavanja) u poređenju sa linearnom interpolacijom. Dalje, polinomska interpolacija i nije tako tačna, posebno na krajnjim tačkama (pogledajte Rungeov fenomen). Ovi nedostaci mogu se izbjeći korištenjem splajn interpolacije.

## Splajn interpolacija 
desno|mini|230px|Grafikon sa primjenom splajn interpolacije

Zapamtite da linearna interpolacija koristi linearne funkcije za svaki od intervala [*x**k*,*x**k+1*]. Splajn interpolacija koristi polinome nižeg stepena u svakom od intervala, te bira dijelove polinoma tako da je oni međusobno glatko uklapaju. Rezultirajuća funkcija naziva se splajn.

Na primjer, prirodni kubni splajn je izlomljena kubna funkcija koja je dva puta neprekidno diferencijabilna. Dalje, njena druga derivacija je nula u krajnjim tačkama. Prirodni kubni splajn koji interpoliše tačke u tabeli ispod dat je sa

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

U ovom slučaju dobijamo *f*(2,5)=0,5972.

Kao i polinomna interpolacija, splin interpolacija izaziva manju grešku od linearne interpolacije i interpolant je glađa. Međutim, interpolant je lakše procijeniti nego polinome visokog stupnja koji se koriste u polinomnoj interpolaciji. Interpolant također ne pati od Rungeovog fenomena.

## Interpolacija preko Gaussovih procesa 
Gaussov proces je moćan alat za nelinearnu interpolaciju. Mnogi popularni interpolacijski alati su zapravo ekvivalentni određenim Gausovim procesima. Gausovi procesi se mogu koristiti ne samo za postavljanje interpolanta koji prolazi upravo kroz date tačke podataka, već i za regresiju, tj. za uklapanje krivulje kroz mnogobrojne podatke. U geostatističkoj zajednici Gaussova regresija procesa je poznata  i pod nazivom Kriging.

## Ostali oblici interpolacije 
Ostali oblici interpolacije mogu se konstruisati odabirom različite klase interpolanata. Naprimjer, racionalna interpolacija je  **interpolacija** pomoću racionalne funkcije s, a trigonometrijska interpolacija je interpolacija pomoću trigonometrijskog polinoma s. Diskretna Fourierova transformacija je poseban slučaj trigonometrijske interpolacije. Druga mogućnost je da se koriste wavelet.

Whittaker-Shannonova formula za interpolaciju može se koristiti ako je broj točaka podataka beskonačan.
Višerazmjerna interpolacija je interpolacija funkcije više promjenljivih. Metode uključuju dvolinearnu interpolaciju i dvokubičnu interpolaciju u dvije dimenzije, i trilinearnu interpolaciju u tri dimenzije.
Ponekad ne znamo samo vrijednost funkcije koju želimo da interpoliramo u nekim tačkama, već i njen derivat. To dovodi do Hermitove interpolacije problema.

## Slični koncepti 
Naziv *ekstrapolacija* se koristi ako želimo pronaći dodatne tačke na grafikonu izvan okvira poznatih tačaka na tom grafikonu.
U promjemima prilagođavanja krive, ograničenje da interpolant mora proći tačno kroz tačke na grafikonu je ublaženo. Jedini zahtijev je da se tim tačkama priđe što je bliže moguće. To zahtijeva parametrizaciju potencijalnih interpolanata, te postojanja sredstva za mjerenje greške koju pri tome pravimo. U najjednostavnijem slučaju, to vodi do aproksimacije najmanjeg kvadrata.

Teorija aproksimacije proučava kako pronaći najbolju aproksimaciju za datu funkciju preko druge funkcije iz predodređene klase, te koliko je valjana ta aproksimacija. Iz ovoga dobijamo granicu kako dobro interpolant može aproksimovati nepoznatu funkciju.

## Reference 
* 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. 
*  Chapter 6.
*  Chapters 4 and 6.

## Vanjski linkovi 
* GaussianProcesses.com: Teorija i primjene Gaussovog procesa
* DotPlacer applet : Animacija koja pokazuje razne metode ainterpolacije

Kategorija:Interpolacija