Exercise "Interpolation"

1. Procedurial programming (C,Fortran,...):
   1. Define a structure which holds all the information about the quadratic spline:

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

   2. Define a function which allocates the necessary memory, calculates the spline coefficients c and returns the properly filled qspline structure.

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

   3. Define a function which computes the spline interpolation function given the precalculated qspline structure and the interpolation 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,...): the structure (or class) holds not only data but also all the appropriate functions (called member functions) which have direct acces 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++0x,Lisp,Haskell,...): only the function for spline-evaluation is created and returned. This function captures all the needed information in itself:
   1. Define a function which calculates the spline coefficients and returns a function which evaluates the spline interpolaion function using the captured coefficients (and other data):

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

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

1. (6 points) Linear and quadratic spline
   1. Implement a function which makes linear spline interpolation from a table {x[i],y[i]} at a given point z.
   2. Implement quadratic spline interpolation.
   3. Build interpolating functions—linear spline and quadratic spline—for the table

      
      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 table 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 antiderivative (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:

   
   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 ∫x1z S(x) dx

3. (1 point) Qubic spline with derivative and integral

   Implement qubic spline with derivative and antiderivative. 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 other languages with good libraries (Python): check that library implementation of cubic spline gives the same result as your spline.

   For other languages without good libraries: check that Octave cubic spline routine gives the same result as your implementation.