Сплајн интерполација

У математичкој области нумеричке анализе, сплајн интерполација је врста интерполације где је интерполент специјалан полином познат као сплајн. Сплајн интерполација се чешће користи од полиномијалне интерполације јер је њена грешка често доста мања, чак и са малим степенима сплајн полинома. Сплајн интерполација заобилази проблем Рунгеовог феномена, у коме се јављају осцилације између тачака када се интерполира полиномом високог степена.

Увод

Сплајн је раније био еластични лењир направљен да се савија и прође између различитих фиксираних тачака. Користили су се за техничке цртеже, углавном у бродоградњи, када се цртало руком.

Figure 1: Интерполација кубним сплајном између осам тачака

Математички модел еластичног лењира фиксираног између n+1 чворова $(x_{i},y_{i})\quad i=0,1,\dotsc ,n$ је интерполација између свака два пара чворова $(x_{i-1}\ ,\ y_{i-1})$ и $(x_{i}\ ,\ y_{i})$ са полиномима $y=q_{i}(x),\quad i=1,2,\dotsc ,n$.

Кривина криве

$y=f(x)$

је

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

Пошто сплајн тежи да минимизује кривину, $y'$ и $y''$ ће бити непрекидне свуда, па и у самим чворовима. Да би ово било постигнуто, мора

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

и да

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

за све i, $1\leq i\leq n-1$. Ово се може постићи само ако се користе полиноми степена 3 или већи. Углавном се користи степен 3, то јест кубни сплајн.

Алгоритам за налажење кубног сплајна

Полином трећег степена $q(x)$ за који важи

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

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

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

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

може се написати као

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

(1)

где

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

(2)

и

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

(3)

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

(4)

Како је $q'={\tfrac {dq}{dx}}={\tfrac {dq}{dt}}\ {\tfrac {dt}{dx}}={\tfrac {dq}{dt}}\ {\tfrac {1}{x_{2}-x_{1}}}$ добијамо:

$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)

Постављањем x = x₁ и x = x₂ у једначинама (5) и (6) добијамо (2) што јесу први изводи q'(x₁) = k₁ и q'(x₂) = k₂ као и други изводи

$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)

Ако сада (x_i, y_i) где i = 0, 1, ... , n are n+1 тачке и

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

(9)

где i = 1, 2, ..., n и $t={\tfrac {x-x_{i-1}}{x_{i}-x_{i-1}}}$ are n полиноми трећег степена интерполирају y у интервалу x _i-1 ≤ x ≤ x_i за i = 1,... , n тако да q'_i (x_i) = q' _i+1 (x_i) за i = 1, ... , n-1 онда n полинома заједно дефинише диференцијабилну функцију на интервалу x₀ ≤ x ≤ x_n и

$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)

за i = 1, ..., n где

$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)

Ако је низ k₀, k₁, ..., k_n такав да додавањем q"_i(x_i) = q"_i+1(x_i) за i = 1, ..., n-1 резултујућа функција ће имати и непрекидан други извод.

Из (7), (8), (10) and (11) следи да је ово случак ако и само ако

${\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)

за i = 1, ..., n-1. Релације (15) су n-1 линеарне једначине за n+1 вредност k₀, k₁, ..., k_n.

За еластичне лењире треба да важи да лево од најлевљег и десно од најдешњег чвора лењир треба да се слободно креће и заууеће облик праве линије са q" = 0 . Како q" треба да је непрекидна функција по x за „природне сплајнове“ и поред n-1 линеарних једначина (15) треба да важи

$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,$

то јест да

${\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)

Дакле, (15) заједно са (16) и (17) дају n+1 линеарних једначина које једнозначно одређују n+1 параметара k₀, k₁, ..., k_n.

Пример

Figure 2: Интерполација са „природним“ кубним сплајном са три чвора.

У случају три чвора, вредности за $k_{0},k_{1},k_{2}$ се добијају решавањем система

${\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}}$

са

$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}}}$

За три чвора

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

добија се

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

а из (10) и (11) добија се

$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$