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

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

Увод

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

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

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

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

$y=f(x)$

је

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

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

$q{\text{'}}_i(x_i)=q{\text{'}}_{i+1}(x_i)$

и да

$q^{\prime }{\text{'}}_i(x_i)=q^{\prime }{\text{'}}_{i+1}(x_i)$

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

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

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

$q(x_1)=y_1$

$q(x_2)=y_2$

$q^{\prime }(x_1)=k_1$

$q^{\prime }(x_2)=k_2$

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

1. Шаблон:NumBlk

где Шаблон:NumBlk и

1. Шаблон:NumBlk
2. Шаблон:NumBlk

Како је $q^{\prime }=\frac{dq}{dx}=\frac{dq}{dt}\frac{dt}{dx}=\frac{dq}{dt}\frac{1}{x_2-x_1}$ добијамо:

1. Шаблон:NumBlk
2. Шаблон:NumBlk

Постављањем Шаблон:Math и Шаблон:Math у једначинама (5) и (6) добијамо (2) што јесу први изводи Шаблон:Math и Шаблон:Math као и други изводи

1. Шаблон:NumBlk
2. Шаблон:NumBlk

Ако сада Шаблон:Math где Шаблон:Math = 0, 1, ... , n are n+1 тачке и

1. Шаблон:NumBlk

где i = 1, 2, ..., n и $t=\frac{x-x_{i-1}}{x_i-x_{i-1}}$ are n полиноми трећег степена интерполирају Шаблон:Math у интервалу Шаблон:Math за i = 1,... , n тако да Шаблон:Math за i = 1, ... , n-1 онда n полинома заједно дефинише диференцијабилну функцију на интервалу Шаблон:Math и

1. Шаблон:NumBlk
2. Шаблон:NumBlk

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

1. Шаблон:NumBlk
2. Шаблон:NumBlk
3. Шаблон:NumBlk

Ако је низ Шаблон:Math такав да додавањем Шаблон:Math за i = 1, ..., n-1 резултујућа функција ће имати и непрекидан други извод.

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

1. Шаблон:NumBlk

за i = 1, ..., n-1. Релације (15) су n-1 линеарне једначине за n+1 вредност Шаблон:Math.

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

$q^{\prime }{\text{'}}_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^{\prime }{\text{'}}_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,$

то јест да

1. Шаблон:NumBlk
2. Шаблон:NumBlk

Дакле, (15) заједно са (16) и (17) дају n+1 линеарних једначина које једнозначно одређују n+1 параметара Шаблон:Math.

Пример

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

У случају три чвора, вредности за $k_0,k_1,k_2$ се добијају решавањем система

$\left[\begin{array}{ccc}{a}_{11}& a_{12}& 0\\ a_{21}& a_{22}& a_{23}\\ 0& a_{32}& a_{33}\end{array}\right]\left[\begin{array}{c}{k}_0\\ k_1\\ k_2\end{array}\right]=\left[\begin{array}{c}{b}_1\\ b_2\\ b_3\end{array}\right]$

са

$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(\frac{1}{x_1-x_0}+\frac{1}{x_2-x_1})$

$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(\frac{y_1-y_0}{{(x_1-x_0)}^2}+\frac{y_2-y_1}{{(x_2-x_1)}^2})$

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