Interpolacija

Sa Wikipedije, slobodne enciklopedije
Idi na: navigacija, traži
Question book-new.svg Ovaj članak ili neka od njegovih sekcija nije dovoljno potkrijepljena izvorima (literatura, web stranice ili drugi izvori).
Sporne rečenice i navodi bi mogli, ukoliko se pravilno ne označe validnim izvorima, biti obrisani i uklonjeni. Pomozite Wikipediji tako što ćete navesti validne izvore putem referenci, te nakon toga možete ukloniti ovaj šablon.
Bih-usa.svg Ovaj članak nije preveden ili je djelimično preveden.
Ako smatrate da ste sposobni da ga prevedete, kliknite na link uredi i prevedite ga vodeći računa o enciklopedijskom stilu pisanja i pravopisu bosanskog jezika.
Za druga značenja pojma Interpolacija pogledajte Interpolacija (čvor).

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[uredi | uredi izvor]

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 xk, koji se nazivaju čvorovi i za svaki xk drugi broj yk, tražimo funkciju f tako da je

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

Par xk,yk naziva se tačka na grafikonu, a f se naziva interpolant za te tačke na grafikonu.

Kada su brojevi yk dati preko poznate funkcije f, ponekad to pišemo kao fk.

Primjer[uredi | uredi izvor]

Na primjer, pretpostavimo da imamo slijedeću tabelu, koja daje neke vrijednosti funkcije f.

Raspored tačaka na grafikonu, kao što je zadato u tabeli desno.
x f(x)
0 0
1 0 , 8415
2 0 , 9093
3 0 , 1411
4 −0 , 7568
5 −0 , 9589
6 −0 , 2794

Interpolacija nam daje mogućnost da procijenimo vrijednost funkcije u nekim srednjim tačkmama, kao što je x = 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[uredi | uredi izvor]

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[uredi | uredi izvor]

Grafikon sa primjenom linearne interpolacije
Glavna stranica: Linearna interpolacija

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 (xa,ya) i (xb,yb), 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 xk.

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 xa i xb 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[uredi | uredi izvor]

Grafikon sa primjenom polinomske interpolacije
Glavna stranica: Polinomska interpolacija

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.

Zarmotrimo 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[uredi | uredi izvor]

Grafikon sa primjenom splajn interpolacije
Glavna stranica: Splajn interpolacija

Zapamtite da linearna interpolacija koristi linearne funkcije za svaki od intervala [xk,xk+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.

Like polynomial interpolation, spline interpolation incurs a smaller error than linear interpolation and the interpolant is smoother. However, the interpolant is easier to evaluate than the high-degree polynomials used in polynomial interpolation. It also does not suffer from Runge's phenomenon.

Interpolacija preko Gaussovih procesa[uredi | uredi izvor]

Gaussian process is a powerful non-linear interpolation tool. Many popular interpolation tools are actually equivalent to particular Gaussian processes. Gaussian processes can be used not only for fitting an interpolant that passes exactly through the given data points but also for regression, i.e. for fitting a curve through noisy data. In the geostatistics community Gaussian process regression is also known as Kriging.

Ostali oblici interpolacije[uredi | uredi izvor]

Other forms of interpolation can be constructed by picking a different class of interpolants. For instance, rational interpolation is interpolation by rational functions, and trigonometric interpolation is interpolation by trigonometric polynomials. The discrete Fourier transform is a special case of trigonometric interpolation. Another possibility is to use wavelets.

The Whittaker–Shannon interpolation formula can be used if the number of data points is infinite.

Multivariate interpolation is the interpolation of functions of more than one variable. Methods include bilinear interpolation and bicubic interpolation in two dimensions, and trilinear interpolation in three dimensions.

Sometimes, we know not only the value of the function that we want to interpolate, at some points, but also its derivative. This leads to Hermite interpolation problems.

Slični koncepti[uredi | uredi izvor]

Termin 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[uredi | uredi izvor]

Vanjski linkovi[uredi | uredi izvor]

Commons logo
U Wikimedijinom spremniku se nalazi još materijala vezanih uz: