*yi = f(xi)*, for

*i = 1…n*. To approximate the function at a new point

*x’*, we find the closest known points below and above, say

*xbelow < x’*and

*xabove > x’*, draw a straight line between

*(xbelow, ybelow)*and

*(xabove, yabove)*, and take the value

*y’*where this line is at

*x’*. The general form of the straight line is

*a * x + b*, where

*a = (yabove - ybelow) / (xabove - xbelow)*and

*b = ybelow - a * xbelow*. Using this, we can calculate

*y’ = a * x’ + b*

**Your task is to implement a function**

*Task:**interpolate(x, y, x_test)*that computes the linear interpolation of the unknown function f at a new point x_test. The sample is given in the form of two sequences x and y. Both sequences have the same length, and their elements are numbers. The x sequence contains the points where the function has been sampled, and the y sequence contains the function value at the corresponding point. In other words, y[i] = f(x[i]).

**Assumptions and restrictions:**You can assume that the arguments are as described: that is, x and y are sequences, both have the same length, and their elements are numbers. You should NOT make any assumption about what type of sequence the x and y arguments are. You can assume that the values in x are ordered in increasing order, and that they are unique (that is, there are no repeated x-values). You can assume that x_test is a number, and it is between two values in the x sequence, or possibly equal to a value in the sequence. If x_test is equal to a sample value (a value in the input xsequence), your function should simply return the corresponding function value from y. Your function must return a number. The scipy library has a whole module, scipy.interpolate which performs various kinds of interpolation, including linear interpolation as described above. Obviously,

**you may not use this module, or any other module that provides a ready-made solution to the problem**, since the goal of the assignment is for you to demonstrate that you can implement the function yourself. You can of course use the scipy interpolation function as a reference to test your implementation. NOTE: must be done on python 3, using only function definitions