Homework "Splines"

1. (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 either pre-calculate anything or use any structs. The signature of your function should be something like

      public static double linterp(double[] x, double[] y, double z){
              int i=binsearch(x,z);
              double dx=x[i+1]-x[i]; if(!(dx>0)) throw new Exception("uups...");
              double dy=y[i+1]-y[i];
              return y[i]+dy/dx*(z-x[i]);
              }
      

      Location of the index i of the interval containing z, x[i]<z<x[i+1], must(!) be done using binary search, like this:

      public static int binsearch(double[] x, double z)
      	{/* locates the interval for z by bisection */ 
      	if(!(x[0]<=z && z<=x[x.Length-1])) throw new Exception("binsearch: bad z");
      	int i=0, j=x.Length-1;
      	while(j-i>1){
      		int mid=(i+j)/2;
      		if(z>x[mid]) i=mid; else j=mid;
      		}
      	return i;
      	}
      

   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 as it is an integral of a linear function. The signature could be something like

      double linterpInteg(double[] x, double[] y, double z)
      

   3. Make some indicative plots to prove that your linear spline and your integrator work as intended.

2. (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=x_i} , i=1,...,5
     • {x_i=i, y_i=x_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-sharp a quadratic spline can be kept in a class like the following,

     class qspline {
     	double[] x,y,b,c;
     	public qspline(double[] xs,double[] ys){
     		/* store xs and ys; calculate b and c */
     		}
     	public double spline(double z){/* evaluate the spline */}
     	public double derivative(double z){/* evaluate the derivative */}
     	public double integral(double z){/* evaluate the integral */}
     	}
     

   • Functional programming style :

     Fun<double[],double[],int,Fun<double,double> >
     qspline=delegate(double[] x,double[] y,int deriv=0){
     	/* calculate b and c */
     	Fun<double,double> spline
     		=delegate(double z){
     		if(deriv==1) /* return derivative */
     		if(deriv==-1) /* return integral */
     		else /* return spline */
     		}
     	return spline;
     }
     

3. (1 points) Cubic spline

   • Implement cubic spline with derivative and integral.

   • Check that the built-in cubic splines in pyxplot/gnuplot (or the spline utility from plotutils) produces a similar cubic spline to your implementation.

Hints:

1. You can use either our vector class or double[] to keep the data.

2. Programming styles:

   The exercise can be solved using different styles of programming:

   1. Object oriented programming: The structure (or class) holds both the data and the appropriate functions (called member functions) which have direct access to the data in the structure.

   2. Functional programming: The function for spline-evaluation is created and returned. This function captures all the needed information in itself (in its environment, to be precise).

3. The plots can be done using either Pyxplot/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.