This chapter describes functions for performing interpolation.  The library provides a variety of interpolation methods, including Cubic splines and Akima splines.  The interpolation types are interchangeable, allowing different methods to be used without recompiling. Interpolations can be defined for both normal and periodic boundary conditions.  Additional functions are available for computing derivatives and integrals of interpolating functions.

The functions described in this section are declared in the header files gsl_interp.h and gsl_spline.h.

Introduction
============

Given a set of data points (x_1, y_1) \dots (x_n, y_n) the routines described in this section compute a continuous interpolating function y(x) such that y(x_i) = y_i.  The interpolation is piecewise smooth, and its behavior at the end-points is determined by the type of interpolation used.

Interpolation Functions
=======================

The interpolation function for a given dataset is stored in a gsl_interp object.  These are created by the following functions.

 -- Function: gsl_interp * gsl_interp_alloc (const gsl_interp_type * T, size_t SIZE)
     This function returns a pointer to a newly allocated interpolation object of type T for SIZE data-points.

 -- Function: int gsl_interp_init (gsl_interp * INTERP, const double XA[], const double YA[], size_t SIZE)
     This function initializes the interpolation object INTERP for the data (XA,YA) where XA and YA are arrays of size SIZE.  The interpolation object (gsl_interp) does not save the data arrays XA and YA and only stores the static state computed from the data.  The XA data array is always assumed to be strictly ordered, with increasing x values; the behavior for other arrangements is not defined.

 -- Function: void gsl_interp_free (gsl_interp * INTERP)
     This function frees the interpolation object INTERP.

Interpolation Types
===================

The interpolation library provides five interpolation types:

 -- Interpolation Type: gsl_interp_linear
     Linear interpolation.  This interpolation method does not require any additional memory.

 -- Interpolation Type: gsl_interp_polynomial
     Polynomial interpolation.  This method should only be used for interpolating small numbers of points because polynomial interpolation introduces large oscillations, even for well-behaved datasets.  The number of terms in the interpolating polynomial is equal to the number of points.

 -- Interpolation Type: gsl_interp_cspline
     Cubic spline with natural boundary conditions.  The resulting curve is piecewise cubic on each interval, with matching first and second derivatives at the supplied data-points.  The second derivative is chosen to be zero at the first point and last point.

 -- Interpolation Type: gsl_interp_cspline_periodic
     Cubic spline with periodic boundary conditions.  The resulting curve is piecewise cubic on each interval, with matching first and second derivatives at the supplied data-points.  The derivatives at the first and last points are also matched.  Note that the last point in the data must have the same y-value as the first point, otherwise the resulting periodic interpolation will have a discontinuity at the boundary.

 -- Interpolation Type: gsl_interp_akima
     Non-rounded Akima spline with natural boundary conditions.  This method uses the non-rounded corner algorithm of Wodicka.

 -- Interpolation Type: gsl_interp_akima_periodic
     Non-rounded Akima spline with periodic boundary conditions.  This method uses the non-rounded corner algorithm of Wodicka.

The following related functions are available:

 -- Function: const char * gsl_interp_name (const gsl_interp * INTERP)
     This function returns the name of the interpolation type used by INTERP. For example,

          printf ("interp uses '%s' interpolation.\n",
                  gsl_interp_name (interp));

     would print something like,

          interp uses 'cspline' interpolation.

 -- Function: unsigned int gsl_interp_min_size (const gsl_interp * INTERP)
     This function returns the minimum number of points required by the interpolation type of INTERP.  For example, Akima spline interpolation requires a minimum of 5 points.

Index Look-up and Acceleration
==============================

The state of searches can be stored in a gsl_interp_accel object, which is a kind of iterator for interpolation lookups.  It caches the previous value of an index lookup.  When the subsequent interpolation point falls in the same interval its index value can be returned immediately.

 -- Function: size_t gsl_interp_bsearch (const double X_ARRAY[], double X, size_t INDEX_LO, size_t INDEX_HI)
     This function returns the index i of the array X_ARRAY such that x_array[i] <= x < x_array[i+1].  The index is searched for in the range [INDEX_LO,INDEX_HI].  inlinefn

 -- Function: gsl_interp_accel * gsl_interp_accel_alloc (void)
     This function returns a pointer to an accelerator object, which is a kind of iterator for interpolation lookups.  It tracks the state of lookups, thus allowing for application of various acceleration strategies.

 -- Function: size_t gsl_interp_accel_find (gsl_interp_accel * A, const double X_ARRAY[], size_t SIZE, double X)
     This function performs a lookup action on the data array X_ARRAY of size SIZE, using the given accelerator A.  This is how lookups are performed during evaluation of an interpolation.  The function returns an index i such that x_array[i] <= x < x_array[i+1].  inlinefn

 -- Function: void gsl_interp_accel_free (gsl_interp_accel* ACC)
     This function frees the accelerator object ACC.

Evaluation of Interpolating Functions
=====================================

 -- Function: double gsl_interp_eval (const gsl_interp * INTERP, const double XA[], const double YA[], double X, gsl_interp_accel * ACC)
 -- Function: int gsl_interp_eval_e (const gsl_interp * INTERP, const double XA[], const double YA[], double X, gsl_interp_accel * ACC, double * Y)
     These functions return the interpolated value of Y for a given point X, using the interpolation object INTERP, data arrays XA and YA and the accelerator ACC.

 -- Function: double gsl_interp_eval_deriv (const gsl_interp * INTERP, const double XA[], const double YA[], double X, gsl_interp_accel * ACC)
 -- Function: int gsl_interp_eval_deriv_e (const gsl_interp * INTERP, const double XA[], const double YA[], double X, gsl_interp_accel * ACC, double * D)
     These functions return the derivative D of an interpolated function for a given point X, using the interpolation object INTERP, data arrays XA and YA and the accelerator ACC.

 -- Function: double gsl_interp_eval_deriv2 (const gsl_interp * INTERP, const double XA[], const double YA[], double X, gsl_interp_accel * ACC)
 -- Function: int gsl_interp_eval_deriv2_e (const gsl_interp * INTERP, const double XA[], const double YA[], double X, gsl_interp_accel * ACC, double * D2)
     These functions return the second derivative D2 of an interpolated function for a given point X, using the interpolation object INTERP, data arrays XA and YA and the accelerator ACC.

 -- Function: double gsl_interp_eval_integ (const gsl_interp * INTERP, const double XA[], const double YA[], double A, double B, gsl_interp_accel * ACC)
 -- Function: int gsl_interp_eval_integ_e (const gsl_interp * INTERP, const double XA[], const double YA[], double A, double B, gsl_interp_accel * ACC, double * RESULT)
     These functions return the numerical integral RESULT of an interpolated function over the range [A, B], using the interpolation object INTERP, data arrays XA and YA and the accelerator ACC.

Higher-level Interface
======================

The functions described in the previous sections required the user to supply pointers to the x and y arrays on each call.  The following functions are equivalent to the corresponding gsl_interp functions but maintain a copy of this data in the gsl_spline object.  This removes the need to pass both XA and YA as arguments on each evaluation. These functions are defined in the header file gsl_spline.h.

 -- Function: gsl_spline * gsl_spline_alloc (const gsl_interp_type * T, size_t SIZE)

 -- Function: int gsl_spline_init (gsl_spline * SPLINE, const double XA[], const double YA[], size_t SIZE)

 -- Function: void gsl_spline_free (gsl_spline * SPLINE)

 -- Function: const char * gsl_spline_name (const gsl_spline * SPLINE)

 -- Function: unsigned int gsl_spline_min_size (const gsl_spline * SPLINE)

 -- Function: double gsl_spline_eval (const gsl_spline * SPLINE, double X, gsl_interp_accel * ACC)
 -- Function: int gsl_spline_eval_e (const gsl_spline * SPLINE, double X, gsl_interp_accel * ACC, double * Y)

 -- Function: double gsl_spline_eval_deriv (const gsl_spline * SPLINE, double X, gsl_interp_accel * ACC)
 -- Function: int gsl_spline_eval_deriv_e (const gsl_spline * SPLINE, double X, gsl_interp_accel * ACC, double * D)

 -- Function: double gsl_spline_eval_deriv2 (const gsl_spline * SPLINE, double X, gsl_interp_accel * ACC)
 -- Function: int gsl_spline_eval_deriv2_e (const gsl_spline * SPLINE, double X, gsl_interp_accel * ACC, double * D2)

 -- Function: double gsl_spline_eval_integ (const gsl_spline * SPLINE, double A, double B, gsl_interp_accel * ACC)
 -- Function: int gsl_spline_eval_integ_e (const gsl_spline * SPLINE, double A, double B, gsl_interp_accel * ACC, double * RESULT)

Examples
========

The following program demonstrates the use of the interpolation and spline functions.  It computes a cubic spline interpolation of the 10-point dataset (x_i, y_i) where x_i = i + \sin(i)/2 and y_i = i + \cos(i^2) for i = 0 \dots 9.

          [file interp.c not included]

The output is designed to be used with the GNU plotutils graph program,

     $ ./a.out > interp.dat
     $ graph -T ps < interp.dat > interp.ps

The result shows a smooth interpolation of the original points.  The interpolation method can changed simply by varying the first argument of gsl_spline_alloc.

The next program demonstrates a periodic cubic spline with 4 data points.  Note that the first and last points must be supplied with the same y-value for a periodic spline.

          [file interpp.c not included]

The output can be plotted with GNU graph.

     $ ./a.out > interp.dat
     $ graph -T ps < interp.dat > interp.ps

The result shows a periodic interpolation of the original points. The slope of the fitted curve is the same at the beginning and end of the data, and the second derivative is also.

References and Further Reading
==============================

Descriptions of the interpolation algorithms and further references can be found in the following books:

  C.W. Ueberhuber, Numerical Computation (Volume 1), Chapter 9 ``Interpolation'', Springer (1997), ISBN 3-540-62058-3.

  D.M. Young, R.T. Gregory A Survey of Numerical Mathematics (Volume 1), Chapter 6.8, Dover (1988), ISBN 0-486-65691-8.