Interpolacija

Interpolácija je v matematiki približna vrednost funkcije znotraj obsega znanih nepovezanih vrednosti neodvisne spremenljivke. Imejmo na primer naslednjo tabelo vrednosti fukcije

{\begin{matrix}\mathbf {x} &\mathbf {f(x)} \\&\\1&1\\2&4\\3&9\\\vdots &\vdots \\4&16\\5&25\\\end{matrix}}

Vidimo, da lahko odvisnost f(x) prilegamo s funkcijo x². V splošnem pri interpolaciji ni tako. Radi bi vedeli vrednost funkcije f(x), ki odgovarja x = 1,7. Najenostavnejša je linearna interpolacija med vrednostmima za x = 1 in x = 2:

f(1,7)\approx f(1)+{\frac {1,7-1}{2-1}}(f(2)-f(1))=1+0,7(4-1)=1+0,7\cdot 3=3,1\;.

Če je osnovna funkcija res $x^{2}$ , je prava rešitev seveda

f(1,7)=1,7^{2}=2,89

Na ta način po navadi interpolacija ni natančna. Zaradi tega lahko interpolacijo uporabimo kot učinkovit algoritmski postopek za 'ugibanje' številskih vrednosti, ki manjkajo, za spajanje točk v grafičnem prikazu, iskanje najboljšega prilega premic njihovim nagibom. V bistvu jo lahko uporabimo vsakokrat kadar želimo pretvoriti nezvezen niz podatkov v zvezno funkcijo.

Pri ekstrapolaciji za razliko iščemo vrednosti funkcije zunaj danega obsega znanih vrednosti. Moramo biti pazljivi, ker tukaj rezultati niso vedno smiselni.

Interpolacijski algoritmi

Pri iskanju ustreznega algoritma za interpolacijo vrednosti je potrebno upoštevati več stvari. Na primer kako dobro želimo prilagoditi funkcijo, koliko vrednosti želimo uporabiti za prilagajanje.

Interpolacijski postopki

Primerjajmo nekaj splošno uporabljanih interpolacijskih algoritmov, da dobimo vpogled kdaj je kakšen uporaben. V primerih bomo označili zaporedne vrednosti v ciljnem podatkovnem nizu kot $v_{0},v_{1},v_{2},v_{3}$ in vrednost, ki jo interpoliramo kot $x$ . Tako je naša funkcija

${\begin{matrix}\mathbf {x} &\mathbf {f(x)} \\&\\\lfloor x\rfloor -1&v_{0}\\\lfloor x\rfloor &v_{1}\\\vdots &\vdots \\\lfloor x\rfloor +1&v_{2}\\\lfloor x\rfloor +2&v_{3}\\\end{matrix}}$

$x_{f}=x-\lfloor x\rfloor$

Primer linearne interpolacije

Najpreprostejši postopek je linearna interpolacija, v angleških virih tudi označen z navideznim akronimom lerp.

Imamo dve vrednosti v točkah $v_{1}$ in $v_{2}$ . Potem določimo približni vrednosti z uteženo srednjo vrednostjo med dvema točkama, ki sta odvisni od vrednosti $x$ . To nam da:

$IV=v_{1}(1-x_{f})+v_{2}(x_{f})$

Ta algoritem je hiter in enostaven. Težava je, ker dobljena funkcija ni zvezno odvedljiva (oziroma ni odvedljiva pri $\lfloor x\rfloor$ ).

Primer interpolacije s kosinusom

Ta algoritem je malo obsežnejši od linearne interpolacije, vendar ne preveč.

Tukaj vzamemo dve vrednosti in z vrednostjo za $x$ izračunamo kosinus na intervalu $[0\ldots \pi ]$ , preslikamo v $[\lfloor x\rfloor \ldots \lceil x_{i}\rceil ]$ , kar se na koncu preslika v točki $v_{1}$ in $v_{2}$ .

$F={\frac {1-\cos(x_{f}\pi )}{2}}$

$IV=v_{1}(1-F)+v_{2}F$

To je le malo boljše od linearne interpolacije. Dobljena funkcija je sicer zvezno odvedljiva, toda odvedljivost je napovedljiva, ker je interpolacija še vedno linearna (odvod je v $\lfloor x\rfloor$ zmeraj enak nič).

Primer kubične interpolacije

Kubični algoritem je primer polinomske interpolacije. Ker je število potrebnih koeficientov za izračun kubične funkcije le štiri, je to število členov v večini primerov dovolj.

Aproksimacijski polinom lahko zapišemo v obliki:

$f(t)=at^{3}+bt^{2}+ct+d$

kjer se $f(t)$ preslika na točke

$f(-1)=v_{0}=-a+b-c+d$

$f(0)=v_{1}=d$

$f(1)=v_{2}=a+b+c+d$

$f(2)=v_{3}=8a+4b+2c+d$

Sedaj enačbe rešimo za $a,b,c$ in $d$ , da dobimo:

$a={\begin{matrix}{1 \over 6}\end{matrix}}(-v_{0}+3v_{1}-3v_{2}+v_{3})$

$b={\begin{matrix}{1 \over 2}\end{matrix}}(v_{0}-2v_{1}+v_{2})$

$c={\begin{matrix}{1 \over 6}\end{matrix}}(-2v_{0}-3v_{1}+6v_{2}-v_{3})$

$d=v_{1}$

Z zgornjimi koeficienti tvorimo polinom in ga izračunamo za izbrani $x$ .

$IV=ax_{f}^{3}+bx_{f}^{2}+cx_{f}+d$

Čeprav moramo tukaj najprej izračunati koeficiente krivulje, je ta postopek veliko natančnejši od linearne interpolacije.

Interpolacija v višjih razsežnostih

Primerjava različnih postopkov interpolacije v eni (zgoraj) in dveh razsežnostih (spodaj): po metodi najbližjega soseda (levo), linearna (v sredini) in kubična (desno)

Večrazsežni interpolacijski postopki so posebej prilagojeni od interpolacije vzdolž številskih premic do interpolacije vzdolž ravnin, prostornin ali celo višjih razsežnosti polj numeričnih podatkov.

Dve razsežnosti

Zgodovina

Guo Šoudžing