SplineAlgorithm.txt

Given n points (x1, y1) ... (xn, yn)
We consider this a tabulation of function values yi = f(xi)

Compute coefficients ai, bi, ci, di  i=1..n such that
the function  y = ai x^3 + bi x^2 + ci x + di
is a cubic spline fit in the interval xi to xi+1.

The constraints are:
  The first and second derivatives must be equal on
  each side of every point (xi, yi) i=2..n-1.
  
The algorithm for computing the coefficients is:

Sort (xi, yi) increasing order by  xi

S1 = 0
Sn = 0  for "natural spline"

Solve the tridiagonal system of equations

|2(h1+h2)    h2                                     | |S1  | |y''1  |
|   h2    2(h2+h3)   h3                             | |S2  | |y''2  |
|            h3   2(h3+h4)  h4                      |*|S3  |=|y''3  |
| ...                                               | | ...| | ...  |
|                                hn-2 2(hn-2 + hn-1)| |Sn-1| |y''n-1|

   where y''i = numerical second derivative computed by
   divided differences on (xi-1, yi-1) (xi, yi) (xi+1, yi+1)
   
for i=1..n-1

h = xi+1 - xi

di = f(xi) = yi

ci = (yi+1 - yi)/h - (2 h Si + h Si+1)/6

bi = Si /2

ai = (Si+1 - Si)/6 h

note that an, bn, cn, dn are neither computer nor used

See "Evaluate" and "Integrate" for the uses of the coefficients.