Exercise "Interpolation"

Using different styles of programming the exercise can be solved as follows,

1. Procedural programming (C,Pascal,Fortran-77,...):

   1. Define a structure which holds all the needed information about the quadratic spline:

      struct qspline {int n; double *x,*y,*b,*c};
      

      Alternatively, you can define a new type qspline

      typedef struct {int n; double *x, *y, *b, *c;} qspline;
      

      and then in the following instead of struct qspline simply use qspline.

   2. Implement a routine which allocates the necessary memory, calculates the spline coefficients c and returns the (pointer to the) properly filled qspline structure:

      struct qspline* qspline_construct(int n, double* x,double* y);
      

   3. Implement a routine which—given the precalculated qspline structure—computes the spline interpolation function at a given point z:

      double qspline_evaluate(struct qslpine* my_qspline, double z);
      

   4. Define a function, qspline_free, which frees the memory occupied by structure qspline.

      void qspline_free(struct qslpine* my_qspline);
      

2. Object oriented programming (C++, Java, Python, C#, ...): the structure (or class) holds not only data but also all the appropriate functions (called member functions) which have direct access to the data in the structure:

   1. Define a structure qspline which holds all the data for spline; the construction function becomes the constructor method; the evaluation function becomes the member function; the qspline_free function becomes the destructor method which is defined automatically (I think):

      struct qspline {
      vector<double> x,y,c; // the data for the spline
      qspline(vector<double> x, vector<double> y); // constructor
      double evaluate(double z); // evaluates the interpolation function
      };
      

   The std::vector<double> is a useful container in C++.

3. Functional programming (C++11, Lisp, Haskell, Python, JavaScript, ...): only the function for spline-evaluation is created and returned. This function captures all the needed information in itself (in its environment, to be precise):

   1. Define a function which calculates the spline coefficients and returns a function which evaluates the spline interpolation function using the captured coefficients (and other data):

      function<double(double)> construct_qspline_evaluation_function(vector<double> x, vector<double> y);
      

4. Template meta-programming(C++): we shall not use that until, perhaps, later.

1. (6 points) Linear and quadratic splines
   1. Implement a function which makes linear spline interpolation from a table {x[i], y[i]} at a given point z. Here you don't need to precalculate anything or use any structs. The signature of your function should be something like

      double linterp(int n, double *x, double *y, double z);

   2. Implement the following routines for quadratic spline interpolation,

      struct qspline *qspline_construct(int n, double *x, double *y);
      double qspline_evaluate(struct qspline *S, double z);
      void qspline_free(struct qspline *S);

   3. Perform linear spline and quadratic spline of the follolwing data,

      for(int i = 0; i < 10; i++) { x[i] = i + 0.5 * sin (i); y[i] = i + cos (i * i); }

      and plot the two interpolating functions (together with the data points).

   Hints:

   1. Location of the index i: x[i]<z<x[i+1] must be done using the binary search.
   2. The plot can be done using the graph utility from plotutils; an example of using it can be found here.

2. (3 points) Derivatives and integrals with quadratic spline

   Implement a function which estimates the derivative and the anti-derivative (indefinite integral) of a tabulated function by building a quadratic spline and then differentiating and integrating the spline (analytically!).

   Check your implementation e.g. on the following data (or better some other indicative data of your choice):

   for(int i = 0;i<10;i++) { x[i] = i*M_PI/9; y[i] = sin (x[i]); }

   Hint: for the integral the routine should return ∫x0z S(x) dx

3. (1 point) Cubic spline with derivative and anti-derivative

   Implement cubic spline with derivative and anti-derivative. Compare with quadratic spline.

4. (0 point) Comparison with library routines

   For C,C++: check that the GSL cubic spline functions give the same result as your cubic spline.

   For C++: make a C++ wrapper for the GSL cubic spline functions and check that they give the same result as your cubic spline.

   For languages with available libraries: check that library implementation of cubic spline gives the same result as your spline.

   For languages without good libraries: check that Octave cubic spline routine gives the same result as your implementation. On molveno Octave is simple octave, on lifa Octave is /usr/users/fedorov/bin/octave.