Editing Spline interpolation (section)

==Algorithm to find the interpolating cubic spline==
We wish to find each polynomial <math>q_i(x)</math> given the points <math>(x_0, y_0)</math> through <math>(x_n, y_n)</math>. To do this, we will consider just a single piece of the curve, <math>q(x)</math>, which will interpolate from <math>(x_1, y_1)</math> to <math>(x_2, y_2)</math>. This piece will have slopes <math>k_1</math> and <math>k_2</math> at its endpoints. Or, more precisely,

:<math>q(x_1)  = y_1,</math>
:<math>q(x_2)  = y_2,</math>
:<math>q'(x_1) = k_1,</math>
:<math>q'(x_2) = k_2.</math>

The full equation <math>q(x)</math> can be written in the symmetrical form
{{NumBlk|:|<math>q(x) = \big(1 - t(x)\big)\,y_1 + t(x)\,y_2 + t(x)\big(1 - t(x)\big)\Big(\big(1 - t(x)\big)\,a + t(x)\,b\Big),</math>|{{EquationRef|1}}}}
where
{{NumBlk|:|<math>t(x) = \frac{x - x_1}{x_2 - x_1},</math>|{{EquationRef|2}}}}
{{NumBlk|:|<math>a = k_1 (x_2 - x_1) - (y_2 - y_1),</math>|{{EquationRef|3}}}}
{{NumBlk|:|<math>b = -k_2 (x_2 - x_1) + (y_2 - y_1).</math>|{{EquationRef|4}}}}

But what are <math>k_1</math> and <math>k_2</math>? To derive these critical values, we must consider that

:<math>q' = \frac{dq}{dx} = \frac{dq}{dt} \frac{dt}{dx} = \frac{dq}{dt} \frac{1}{x_2 - x_1}.</math>
It then follows that
{{NumBlk|:|<math>q' = \frac{y_2 - y_1}{x_2 - x_1} + (1 - 2t) \frac {a(1 - t) + bt}{x_2 - x_1} + t(1 - t) \frac{b - a}{x_2 - x_1},</math>|{{EquationRef|5}}}}
{{NumBlk|:|<math>q'' = 2 \frac{b - 2a + (a - b)3t}{{(x_2 - x_1)}^2}.</math>|{{EquationRef|6}}}}

Setting {{math|''t'' {{=}} ''0''}} and {{math|''t'' {{=}} ''1''}} respectively in equations ({{EquationNote|5}}) and ({{EquationNote|6}}), one gets from ({{EquationNote|2}}) that indeed first derivatives {{math|''q′''(''x''<sub>1</sub>) {{=}} ''k''<sub>1</sub>}} and {{math|''q′''(''x''<sub>2</sub>) {{=}} ''k''<sub>2</sub>}}, and also second derivatives

{{NumBlk|:|<math>q''(x_1) = 2 \frac{b - 2a}{{(x_2 - x_1)}^2},</math>|{{EquationRef|7}}}}
{{NumBlk|:|<math>q''(x_2) = 2 \frac{a - 2b}{{(x_2 - x_1)}^2}.</math>|{{EquationRef|8}}}}

If now {{math|(''x<sub>i</sub>'', ''y<sub>i</sub>''), ''i'' {{=}} 0, 1, ..., ''n''}} are {{math|''n'' + 1}} points, and

{{NumBlk|:|<math>q_i = (1 - t)\,y_{i-1} + t\,y_i + t(1 - t)\big((1 - t)\,a_i + t\,b_i\big),</math>|{{EquationRef|9}}}}

where ''i'' = 1, 2, ..., ''n'', and <math>t = \tfrac{x - x_{i-1}}{x_i - x_{i-1}}</math> are ''n'' third-degree polynomials interpolating {{mvar|y}} in the interval {{math|''x''<sub>''i''−1</sub> ≤ ''x'' ≤ ''x<sub>i</sub>''}} for ''i'' = 1, ..., ''n'' such that {{math|''q′<sub>i</sub>'' (''x<sub>i</sub>'') {{=}} ''q′''<sub>''i''+1</sub>(''x<sub>i</sub>'')}} for ''i'' = 1, ..., ''n''&nbsp;−&nbsp;1, then the ''n'' polynomials together define a differentiable function in the interval {{math|''x''<sub>0</sub> ≤ ''x'' ≤ ''x<sub>n</sub>''}}, and

{{NumBlk|:|<math>a_i = k_{i-1}(x_i - x_{i-1}) - (y_i - y_{i-1}),</math>|{{EquationRef|10}}}}
{{NumBlk|:|<math>b_i = -k_i(x_i - x_{i-1}) + (y_i - y_{i-1})</math>|{{EquationRef|11}}}}
for ''i'' = 1, ..., ''n'', where
{{NumBlk|:|<math>k_0 = q_1'(x_0),</math>|{{EquationRef|12}}}}
{{NumBlk|:|<math>k_i = q_i'(x_i) = q_{i+1}'(x_i), \qquad i = 1, \dots, n - 1,</math>|{{EquationRef|13}}}}
{{NumBlk|:|<math>k_n = q_n'(x_n).</math>|{{EquationRef|14}}}}

If the sequence {{math|''k''<sub>0</sub>, ''k''<sub>1</sub>, ..., ''k<sub>n</sub>''}} is such that, in addition, {{math|''q′′<sub>i</sub>''(''x<sub>i</sub>'') {{=}} ''q′′''<sub>''i''+1</sub>(''x<sub>i</sub>'')}} holds for ''i'' = 1, ..., ''n''&nbsp;−&nbsp;1, then the resulting function will even have a continuous second derivative.

From ({{EquationNote|7}}), ({{EquationNote|8}}), ({{EquationNote|10}}) and ({{EquationNote|11}}) follows that this is the case if and only if

{{NumBlk|:|<math>\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)</math>|{{EquationRef|15}}}}

for ''i'' = 1, ..., ''n''&nbsp;−&nbsp;1. The relations ({{EquationNote|15}}) are {{math|''n'' − 1}} linear equations for the {{math|''n'' + 1}} values {{math|''k''<sub>0</sub>, ''k''<sub>1</sub>, ..., ''k<sub>n</sub>''}}.

For the elastic rulers being the model for the spline interpolation, one has that to the left of the left-most "knot" and to the right of the right-most "knot" the ruler can move freely and will therefore take the form of a straight line with {{math|''q′′'' {{=}} 0}}. As {{mvar|q′′}} should be a continuous function of {{mvar|x}}, "natural splines" in addition to the {{math|''n'' − 1}} linear equations ({{EquationNote|15}}) should have
:<math>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,</math>
:<math>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,</math>
i.e. that
{{NumBlk|:|<math>\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},</math>|{{EquationRef|16}}}}
{{NumBlk|:|<math>\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}.</math>|{{EquationRef|17}}}}

Eventually, ({{EquationNote|15}}) together with ({{EquationNote|16}}) and ({{EquationNote|17}}) constitute {{math|''n'' + 1}} linear equations that uniquely define the {{math|''n'' + 1}} parameters {{math|''k''<sub>0</sub>, ''k''<sub>1</sub>, ..., ''k<sub>n</sub>''}}.

There exist other end conditions, "clamped spline", which specifies the slope at the ends of the spline, and the popular "not-a-knot spline", which requires that the third derivative is also continuous at the {{math|''x''<sub>1</sub>}} and {{math|''x''<sub>''n''−1</sub>}} points.
For the "not-a-knot" spline, the additional equations will read:

:<math>q'''_1(x_1) = q'''_2(x_1) \Rightarrow \frac{1}{\Delta x_1^2} k_0 + \left( \frac{1}{\Delta x_1^2} - \frac{1}{\Delta x_2^2} \right) k_1 - \frac{1}{\Delta x_2^2} k_2 = 2 \left( \frac{\Delta y_1}{\Delta x_1^3} - \frac{\Delta y_2}{\Delta x_2^3} \right),</math>
:<math>q'''_{n-1}(x_{n-1}) = q'''_n(x_{n-1}) \Rightarrow \frac{1}{\Delta x_{n-1}^2} k_{n-2} + \left( \frac{1}{\Delta x_{n-1}^2} - \frac{1}{\Delta x_n^2} \right) k_{n-1} - \frac{1}{\Delta x_n^2} k_n = 2\left( \frac{\Delta y_{n-1} }{\Delta x_{n-1}^3 }- \frac{ \Delta y_n}{ \Delta x_n^3 } \right),</math>

where <math>\Delta x_i = x_i - x_{i-1},\ \Delta y_i = y_i - y_{i-1}</math>.