Interpolation

We present the formulae relating to different types of interpolation methodologies.

Cubic Spline Interpolation

This method again assumes that the interpolating function is cubic polynomial, but it imposes different conditions:

  • The function values at the given points \(t_0\) to \(t_n\) matches the given ordinates (n+1) conditions.
  • The function, and its first two derivatives are continuous, giving us \( 3(n-1) \) conditions. Continuity means that the left and right spline meet at each of the interior point, That is, at each of the interior points \(t_1 \) to \( t_{n-1}\), the following holds:

$$ P_{i}(t_i)= P_{i-1}(t_i) $$ $$ P_{i}^{\prime}(t_i)= P_{i-1}^{\prime}(t_i) $$ $$ P_{i}^{\prime \prime}(t_i)= P_{i-1}^{\prime \prime}(t_i) $$

As a cubic polynomial has 4 parameters, and we have n polynomials to fit, we need to determine 4n variables. However, we only have 4n-2 conditions: The first statement gives us \(n+1\) conditions, while the continuity requirements gives \( 3(n-1) \) conditions. We will therefore need to impose two more conditions. The most popular options are to assume that the second derivatives at the end are zero, or the first derivatives at the end are known.

The Cubic Spline Interpolating Polynomial

Whilst this method also assumes that the interpolating function is cubic polynomial, the polynomial is expressed in a different form: in terms of the second derivatives to be more precise. Let's pretend for a moment that we know the value of the second derivative in addition to the value of the function at each of the given data point. As the interpolating function is assumed to be cubic, its second derivative must be linear, and hence we can write the second derivative of the interpolating polynomial as a linear combination of the assumed values of the second derivatives at both ends of the interval, which we write as per the linear interpolation formula as:

$$ P_{i}^{\prime \prime}(t)= \frac{(t_{i+1}-t)}{(t_{i+1}-t_i)} c_i + \frac{(t-t_i)}{(t_{i+1}-t_i)} c_{i+1} $$

Integrating twice, we get:

$$ \int{P^{\prime \prime}_{i}(t) dt}= c_i \int{\frac{(t_{i+1}-t)}{(t_{i+1}-t_i)}dt} + c_{i+1} \int{\frac{(t-t_i)}{(t_{i+1}-t_i)}dt} $$ $$ P^{\prime}_{i}(t)= - c_i \frac{{(t_{i+1}-t)}^2}{2 (t_{i+1}-t_i)} + c_{i+1} \frac{{(t-t_i)}^2}{2(t_{i+1}-t_i)} + a_i $$ $$ \int{P^{\prime}_{i}(t) dt}= - c_i \int{\frac{{(t_{i+1}-t)}^2}{2 (t_{i+1}-t_i)} dt} + c_{i+1} \int{\frac{{(t-t_i)}^2}{2(t_{i+1}-t_i)}dt} + a_i \int{dt} $$ $$ P_{i} (t) = c_i \frac{{(t_{i+1}-t)}^3}{6(t_{i+1}-t_i)} + c_{i+1} \frac{{(t-t_i)}^3}{6(t_{i+1}-t_i)} + a_i t + b_i$$

Where \( a_i\) and \(b_i\) were introduced as constants of integration. Now we can recast \( a_i t + b_i \) in the Lagrange form, giving us:

$$ P_{i} (t) = c_i \frac{{(t_{i+1}-t)}^3}{6(t_{i+1}-t_i)} + c_{i+1} \frac{{(t-t_i)}^3}{6(t_{i+1}-t_i)} + a_i (t_{i+1}-t) + b_i (t-t_i)$$

We require that the value of the interpolating polynomial matches the value of the function at both ends of the interval:

$$ P_{i}(t_i)=f_i \quad \Rightarrow \quad c_i \frac{{(t_{i+1}-t_i)}^3}{6(t_{i+1}-t_i)} + a_i (t_{i+1}-t_i) = f_i \quad \Rightarrow \quad a_i = \left( f_i-c_i \frac{{(t_{i+1}-t_i)}^2}{6}\right) \frac{1}{t_{i+1}-t_i} $$ $$ P_{i}(t_{i+1})=f_{i+1} \quad \Rightarrow \quad c_{i+1} \frac{{(t_{i+1}-t_i)}^3}{6(t_{i+1}-t_i)} + b_i (t_{i+1}-t_i) =f_{i+1} \quad \Rightarrow \quad b_i =\left( f_{i+1} - c_{i+1} \frac{{(t_{i+1}-t_i)}^2}{6} \right) \frac{1}{t_{i+1}-t_i} $$

Hence our interpolating function becomes after substituting for \(a_i\) and \(b_i\):

$$ P_{i} (t) = c_i \frac{{(t_{i+1}-t)}^3}{6(t_{i+1}-t_i)} + c_{i+1} \frac{{(t-t_i)}^3}{6(t_{i+1}-t_i)} + \left( f_i-c_i \frac{{(t_{i+1}-t_i)}^2}{6}\right) \frac{t_{i+1}-t}{t_{i+1}-t_i} + \left( f_{i+1} - c_{i+1} \frac{{(t_{i+1}-t_i)}^2}{6} \right) \frac{t-t_i}{t_{i+1}-t_i} $$

We thus have our cubic spline interpolating polynomial, which is good, but the problem is we do not have the second derivatives values - we only pretended that we do. Now we must find a way to determine these, which is the objective of the next sub-section.

Determining the c's

To determine the c's, we use the above cubic polynomial equation and one of the conditions which says that the derivative of the left and the right polynomials at their intersection points meet. The derivative of the interpolating polynomial is

$$ P_{i}^{\prime} (t) = - c_i \frac{{(t_{i+1}-t)}^2}{2(t_{i+1}-t_i)} + c_{i+1} \frac{{(t-t_i)}^2}{2(t_{i+1}-t_i)} - \left( f_i-c_i \frac{{(t_{i+1}-t_i)}^2}{6}\right) \frac{1}{t_{i+1}-t_i} + \left( f_{i+1} - c_{i+1} \frac{{(t_{i+1}-t_i)}^2}{6} \right) \frac{1}{t_{i+1}-t_i} $$

The derivative of the ith interpolating polynomial takes the following value at the left end of the interval \( (t_i, t_{i+1})\):

$$ P_{i}^{\prime} (t_i) = - c_i \frac{{(t_{i+1}-t_i)}}{2} - \left( f_i-c_i \frac{{(t_{i+1}-t_i)}^2}{6}\right) \frac{1}{t_{i+1}-t_i} + \left( f_{i+1} - c_{i+1} \frac{{(t_{i+1}-t_i)}^2}{6} \right) \frac{1}{t_{i+1}-t_i} $$

And the derivative of the (i-1)th interpolating polynomial takes the following value at the right end of the interval \( (t_{i-1}, t_i)\):

$$ P_{i-1}^{\prime} (t_{i}) = c_{i} \frac{{(t_{i}-t_{i-1})}}{2} - \left( f_{i-1}-c_{i-1} \frac{{(t_{i}-t_{i-1})}^2}{6}\right) \frac{1}{t_{i}-t_{i-1}} + \left( f_{i} - c_{i} \frac{{(t_{i}-t_{i-1})}^2}{6} \right) \frac{1}{t_{i}-t_{i-1}} $$

Equating the derivatives of the ith and the (i-1)th polynomials at their intersection point \(t_i\), making the substitutions, simplifying, and collecting the unknowns and knowns on the left and right hand sides, respectively:

$$ P_{i-1}^{\prime} (t_{i})= P_{i}^{\prime} (t_i) $$ $$ c_{i-1} \frac{{(t_{i}-t_{i-1})}}{6} + c_i \frac{{(t_{i+1}-t_i)}+(t_{i}-t_{i-1})}{3} + c_{i+1} \frac{{(t_{i+1}-t_i)}}{6} = \frac{f_{i+1}-f_{i}}{t_{i+1}-t_i}-\frac{f_{i}-f_{i-1}}{t_{i}-t_{i-1}} $$

Multiplying both sides by \(\frac{6}{(t_{i+1}-t_i)+(t_{i}-t_{i-1})}\), we get:

$$ c_{i-1} \frac{{(t_{i}-t_{i-1})}}{(t_{i+1}-t_i)+(t_{i}-t_{i-1})} + 2 c_i + c_{i+1} \frac{{(t_{i+1}-t_i)}}{(t_{i+1}-t_i)+(t_{i}-t_{i-1})} = \frac{6}{(t_{i+1}-t_i)+(t_{i}-t_{i-1})} \left( \frac{f_{i+1}-f_{i}}{t_{i+1}-t_i}-\frac{f_{i}-f_{i-1}}{t_{i}-t_{i-1}} \right) $$

Which we write as:

$$ \alpha_i c_{i-1} + 2 c_i + \beta_i c_{i+1} = d_i $$

Where:

$$ \alpha_i = \frac{{(t_{i}-t_{i-1})}}{(t_{i+1}-t_i)+(t_{i}-t_{i-1})} $$ $$ \beta_i=\frac{{(t_{i+1}-t_i)}}{(t_{i+1}-t_i)+(t_{i}-t_{i-1})} = 1- \alpha_i$$ $$ d_i = \frac{6}{(t_{i+1}-t_i)+(t_{i}-t_{i-1})} \left( \frac{f_{i+1}-f_{i}}{t_{i+1}-t_i}-\frac{f_{i}-f_{i-1}}{t_{i}-t_{i-1}} \right) $$

The above equation holds for all i's from 1 to n-1, and we can thus write the problem as the system:

$$ \left[ \begin{matrix} 2 & \beta_0 & & & & \\ \alpha_1 & 2 & \beta_1 & & & \\ & \alpha_2 & 2 & \beta_2 & & \\ & & \ddots & \ddots & \ddots & \\ & & & \alpha_{n-1} & 2 & \beta_{n-1} \\ & & & & \alpha_{n} & 2 \\ \end{matrix} \right] \left[ \begin{matrix} c_0 \\ c_1 \\ c_2 \\ \vdots \\ c_{n-1} \\ c_{n} \\ \end{matrix} \right] =\left[ \begin{matrix} d_0 \\ d_1 \\ d_2 \\ \vdots \\ d_{n-1} \\ d_{n} \\ \end{matrix} \right] $$

Where we added two more equations, at the top and the bottom in line with the pattern:

$$ 2 c_0 + \beta_0 c_1=d_0 $$ $$ \alpha_{n} c_{n-1} + 2 c_n =d_n $$

As mentioned before, two additional conditions are required, and there are alternative ways to specify these. The so called natural spline amount to setting \(\beta_0=0\), \(d_0=0\), \( \alpha_{n}=0\), and \(d_n=0\), which gives \(c_0=0\) and \(c_n=0\)- i.e., the second derivatives at both ends of the input data are zero.

Solving the above tridiagonal system gives us c's, which is what we needed.