Splajn interpolacija

U matematičkoj oblasti numeričke analize, splajn interpolacija je vrsta interpolacije gde je interpolent specijalan polinom poznat kao splajn. Splajn interpolacija se češće koristi od polinomijalne interpolacije jer je njena greška često dosta manja, čak i sa malim stepenima splajn polinoma. Splajn interpolacija zaobilazi problem Rungeovog fenomena, u kome se javljaju oscilacije između tačaka kada se interpolira polinomom visokog stepena.

Uvod

Splajn je ranije bio elastični lenjir napravljen da se savija i prođe između različitih fiksiranih tačaka. Koristili su se za tehničke crteže, uglavnom u brodogradnji, kada se crtalo rukom.

Figure 1: Interpolacija kubnim splajnom između osam tačaka

Matematički model elastičnog lenjira fiksiranog između n+1 čvorova $(x_{i},y_{i})\quad i=0,1,\dotsc ,n$ je interpolacija između svaka dva para čvorova $(x_{i-1}\ ,\ y_{i-1})$ i $(x_{i}\ ,\ y_{i})$ sa polinomima $y=q_{i}(x),\quad i=1,2,\dotsc ,n$.

Krivina krive

$y=f(x)$

je

$\kappa ={\frac {y''}{(1+y'^{2})^{3/2}}}$

Pošto splajn teži da minimizuje krivinu, $y'$ i $y''$ će biti neprekidne svuda, pa i u samim čvorovima. Da bi ovo bilo postignuto, mora

$q'_{i}(x_{i})=q'_{i+1}(x_{i})$

i da

$q''_{i}(x_{i})=q''_{i+1}(x_{i})$

za sve i, $1\leq i\leq n-1$. Ovo se može postići samo ako se koriste polinomi stepena 3 ili veći. Uglavnom se koristi stepen 3, to jest kubni splajn.

Algoritam za nalaženje kubnog splajna

Polinom trećeg stepena $q(x)$ za koji važi

$q(x_{1})=y_{1}$

$q(x_{2})=y_{2}$

$q'(x_{1})=k_{1}$

$q'(x_{2})=k_{2}$

može se napisati kao

$q\ =\ (1-t)\ y_{1}+\ t\ y_{2}\ +\ t\ (1-t)\ (a\ (1-t)+b\ t)$

(1)

gde

$t={\tfrac {x-x_{1}}{x_{2}-x_{1}}}$

(2)

i

$a=\ k_{1}(x_{2}-x_{1})-(y_{2}-y_{1}),$

(3)

$b=-k_{2}(x_{2}-x_{1})+(y_{2}-y_{1}).$

(4)

Kako je $q'={\tfrac {dq}{dx}}={\tfrac {dq}{dt}}\ {\tfrac {dt}{dx}}={\tfrac {dq}{dt}}\ {\tfrac {1}{x_{2}-x_{1}}}$ dobijamo:

$q'\ ={\frac {y_{2}-y_{1}}{x_{2}-x_{1}}}+(1-2t)\ {\frac {a\ (1-t)+b\ t}{x_{2}-x_{1}}}\ +\ \ t\ (1-t)\ {\frac {b-a}{x_{2}-x_{1}}},$

(5)

$q''=2{\frac {b-2a+(a-b)3t}{{(x_{2}-x_{1})}^{2}}}.$

(6)

Postavljanjem x = x₁ i x = x₂ u jednačinama (5) i (6) dobijamo (2) što jesu prvi izvodi q'(x₁) = k₁ i q'(x₂) = k₂ kao i drugi izvodi

$q''(x_{1})=2{\frac {b-2a}{{(x_{2}-x_{1})}^{2}}}$

(7)

$q''(x_{2})=2{\frac {a-2b}{{(x_{2}-x_{1})}^{2}}}$

(8)

Ako sada (x_i, y_i) gde i = 0, 1, ... , n are n+1 tačke i

$q_{i}\ =\ (1-t)\ y_{i-1}+\ t\ y_{i}\ +\ t\ (1-t)\ (a_{i}\ (1-t)+b_{i}\ t)$

(9)

gde i = 1, 2, ..., n i $t={\tfrac {x-x_{i-1}}{x_{i}-x_{i-1}}}$ are n polinomi trećeg stepena interpoliraju y u intervalu x _i-1 ≤ x ≤ x_i za i = 1,... , n tako da q'_i (x_i) = q' _i+1 (x_i) za i = 1, ... , n-1 onda n polinoma zajedno definiše diferencijabilnu funkciju na intervalu x₀ ≤ x ≤ x_n i

$a_{i}=k_{i-1}(x_{i}-x_{i-1})-(y_{i}-y_{i-1})$

(10)

$b_{i}=-k_{i}(x_{i}-x_{i-1})+(y_{i}-y_{i-1})$

(11)

za i = 1, ..., n gde

$k_{0}=q_{1}'(x_{0})$

(12)

$k_{i}=q_{i}'(x_{i})=q_{i+1}'(x_{i})\quad i=1,\dotsc ,n-1$

(13)

$k_{n}=q_{n}'(x_{n})$

(14)

Ako je niz k₀, k₁, ..., k_n takav da dodavanjem q"_i(x_i) = q"_i+1(x_i) za i = 1, ..., n-1 rezultujuća funkcija će imati i neprekidan drugi izvod.

Iz (7), (8), (10) and (11) sledi da je ovo slučak ako i samo ako

${\frac {k_{i-1}}{x_{i}-x_{i-1}}}+\left({\frac {1}{x_{i}-x_{i-1}}}+{\frac {1}{x_{i+1}-x_{i}}}\right)\ 2k_{i}+{\frac {k_{i+1}}{x_{i+1}-x_{i}}}=3\ \left({\frac {y_{i}-y_{i-1}}{{(x_{i}-x_{i-1})}^{2}}}+{\frac {y_{i+1}-y_{i}}{{(x_{i+1}-x_{i})}^{2}}}\right)$

(15)

za i = 1, ..., n-1. Relacije (15) su n-1 linearne jednačine za n+1 vrednost k₀, k₁, ..., k_n.

Za elastične lenjire treba da važi da levo od najlevljeg i desno od najdešnjeg čvora lenjir treba da se slobodno kreće i zauueće oblik prave linije sa q" = 0 . Kako q" treba da je neprekidna funkcija po x za „prirodne splajnove“ i pored n-1 linearnih jednačina (15) treba da važi

$q''_{1}(x_{0})\ =2\ {\frac {3(y_{1}-y_{0})-(k_{1}+2k_{0})(x_{1}-x_{0})}{{(x_{1}-x_{0})}^{2}}}=0,$

$q''_{n}(x_{n})\ =-2\ {\frac {3(y_{n}-y_{n-1})-(2k_{n}+k_{n-1})(x_{n}-x_{n-1})}{{(x_{n}-x_{n-1})}^{2}}}=0,$

to jest da

${\frac {2}{x_{1}-x_{0}}}k_{0}\ +{\frac {1}{x_{1}-x_{0}}}k_{1}=3\ {\frac {y_{1}-y_{0}}{(x_{1}-x_{0})^{2}}},$

(16)

${\frac {1}{x_{n}-x_{n-1}}}k_{n-1}\ +{\frac {2}{x_{n}-x_{n-1}}}k_{n}=3\ {\frac {y_{n}-y_{n-1}}{(x_{n}-x_{n-1})^{2}}}.$

(17)

Dakle, (15) zajedno sa (16) i (17) daju n+1 linearnih jednačina koje jednoznačno određuju n+1 parametara k₀, k₁, ..., k_n.

Primer

Figure 2: Interpolacija sa „prirodnim“ kubnim splajnom sa tri čvora.

U slučaju tri čvora, vrednosti za $k_{0},k_{1},k_{2}$ se dobijaju rešavanjem sistema

${\begin{bmatrix}a_{11}&a_{12}&0\\a_{21}&a_{22}&a_{23}\\0&a_{32}&a_{33}\\\end{bmatrix}}{\begin{bmatrix}k_{0}\\k_{1}\\k_{2}\\\end{bmatrix}}={\begin{bmatrix}b_{1}\\b_{2}\\b_{3}\\\end{bmatrix}}$

sa

$a_{11}={\frac {2}{x_{1}-x_{0}}}$

$a_{12}={\frac {1}{x_{1}-x_{0}}}$

$a_{21}={\frac {1}{x_{1}-x_{0}}}$

$a_{22}=2\ \left({\frac {1}{x_{1}-x_{0}}}+{\frac {1}{x_{2}-x_{1}}}\right)$

$a_{23}={\frac {1}{x_{2}-x_{1}}}$

$a_{32}={\frac {1}{x_{2}-x_{1}}}$

$a_{33}={\frac {2}{x_{2}-x_{1}}}$

$b_{1}=3\ {\frac {y_{1}-y_{0}}{(x_{1}-x_{0})^{2}}}$

$b_{2}=3\ \left({\frac {y_{1}-y_{0}}{{(x_{1}-x_{0})}^{2}}}+{\frac {y_{2}-y_{1}}{{(x_{2}-x_{1})}^{2}}}\right)$

$b_{3}=3\ {\frac {y_{2}-y_{1}}{(x_{2}-x_{1})^{2}}}$

Za tri čvora

$(-1,0.5)\ ,\ (0,0)\ ,\ (3,3)$

dobija se

$k_{0}=-0.6875\ ,\ k_{1}=-0.1250\ ,\ k_{2}=1.5625$

a iz (10) i (11) dobija se

$a_{1}=k_{0}(x_{1}-x_{0})-(y_{1}-y_{0})=-0.1875$

$b_{1}=-k_{1}(x_{1}-x_{0})+(y_{1}-y_{0})=-0.3750$

$a_{2}=k_{1}(x_{2}-x_{1})-(y_{2}-y_{1})=-3.3750$

$b_{2}=-k_{2}(x_{2}-x_{1})+(y_{2}-y_{1})=-1.6875$