Algorithm and Example: Cubic Splines

🔹 Algorithm for computing a cubic spline

Given the points \((x_i,f(x_i))\), \(i=0,1,\dots,n\), the general algorithm to compute a cubic spline is as follows:

1. Construct the table of finite differences \(f[x_i,x_{i+1},x_{i+2}]\).
2. Compute the interval lengths \(h_i = x_{i+1} - x_i\).
3. Compute the second derivatives \(f''_i\) by solving the linear system consisting of:
   • Equations for interior nodes (continuity of first and second derivatives).
   • Additional equations depending on the spline type:
     • Natural spline: \(f''_0=f''_n=0\)
     • Spline with constant curvature at endpoints
     • Spline with specified first derivatives at endpoints
     • "Not-a-knot" spline
     • Periodic spline
4. Compute the coefficients of each interval polynomial \(p_i(x)\):

   f_i = f(x_i),
   f'_i = f[x_i,x_i+1] - h_i f''_i /3 - h_i f''_{i+1}/6,
   f'''_i = (f''_{i+1} - f''_i) / h_i

5. The spline over the interval \([x_i,x_{i+1}]\) is:

   p_i(x) = f_i + f'_i (x-x_i) + f''_i/2! (x-x_i)^2 + f'''_i/3! (x-x_i)^3

🔹 Numerical Example

Consider the 4 points: (1,1), (2,9), (4,2), (5,11). We calculate the finite differences, interval lengths, and second derivatives:

For the natural spline (\(f''_0=f''_3=0\)), the linear system for second derivatives is:

f''_0 = 0, f''_1 = -141/8, f''_2 = 147/8, f''_3 = 0

For the first interval [1,2]:

f0 = 1,
f'_0 = 175/16,
f'''_0 = -47/16

p0(x) = 1 + 175/16 (x-1) - 47/16 (x-1)³

Spline value at x = 1.5: 6.1015625

For the second interval [2,4]:

f1 = 9,
f'_1 = 17/8,
f'''_1 = 3

p1(x) = 9 + 17/8 (x-2) + 16 (x-2)² + 3 (x-2)³

Spline value at x = 3: 5.3125. The complete spline is shown in the corresponding figure.