interpolation exercise

Exercise "Interpolation"

Objective:

Implement functions for interpolation of tabulated data.

Problems:

(6 points) Linear spline (linear interpolation)
1. Implement a function that 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);     /* C */ 
def linterp(x:list, y:list, z:float):                      # procedural python
```
2. Implement a function that calculates the intergral of the linear spline from the point x[0] to the given point z. The integral must be calculated analytically of course as it is an integral of a linear function. The signature could be something like
```
double linterp_integ(int n, double *x, double *y, double z);     /* C or procedural C++ */ 
def linterp_integ(x:list, y:list, z:float):                      # procedural python
```
3. Make some plots to prove that your linear spline and your integrator work as intended.
Hints:
1. To illustrate that your routines work as intended tabulate some known function and interpolate the table using your routines (including if implemented the integral and the derivative). Compare with the exact results.
2. Location of the index i of the interval containing z, x[i]<z<x[i+1], must(!) be done using the binary search.
3. The plot can be done using either Gnuplot or the "quick-and-dirty" plotter, the graph utility from plotutils. Install it with sudo apt-get install plotutils. It is a simple filter which takes data in the form of two columns, for x and y, from the standard input (or from a file) and sends a plot in the given format to the standard output, for example,
```
graph --output-format svg < data > plot.svg
```
  A blank line in the data-file separates different data sets. An example of graph usage can be found here and here.

(3 points) Quadratic spline

Implement quadratic spline with derivative and integral. Note that quadratic spline is only for learning, for practical applications always use cubic spline instead.

Hints:

You can test your quadratic-spline by considering the following {x_i, y_i} tables,
- {x_i=i, y_i=1} , i=1,...,5
- {x_i=i, y_i=i} , i=1,...,5
- {x_i=i, y_i=i²} , i=1,...,5
Calcullate manually the parameters {b_i, c_i} of the corresponding quadratic-splines, and compare the results with your quadratic-spline program.
In C-language a quadratic spline can be kept in a structure like the following,
```
typedef struct {int n; double *x, *y, *b, *c;} qspline;
```

Your functions for quadratic spline with derivative and integral may look like

C :

struct qspline * qspline_alloc(int n, double *x, double *y); /* allocates and builds the quadratic spline */
double qspline_evaluate(struct qspline *s, double z);        /* evaluates the prebuilt spline at point z */
double qspline_derivative(struct qspline *s, double z); /* evaluates the derivative of the prebuilt spline at point z */
double qspline_integral(struct qspline *s, double z);  /* evaluates the integral of the prebuilt spline from x[0] to z */
void qspline_free(struct qspline *s); /* free memory allocated in qspline_alloc */

Python :

def qspline(x:list,y:list) :
	# calculate b[i],c[i]
	def eval(z:float, deriv:int=0)
		if deriv==1 : # calculate and return derivative
		elif deriv==-1 : # calculate and return integral
		else : # calculate and return spline
	return eval # functional style

(1 points) Cubic spline
- Implement cubic spline with derivative and integral.
- For C,C++: check that the GSL cubic spline functions give similar results to your cubic spline.
- For languages with available libraries (like NumPy): check that the library implementation of cubic spline gives the same result as your spline.
- In case of no libraries: Check that the spline utility from plotutils produces a similar cubic spline to your implementation.