Linear Interpolation

Interpolation involves finding an estimate for a function value between known values of the function.  Lets say someone has recorded the temperature every hour of the day and you need to know the temperature at 4:30 PM.  A reasonable approach would be to look up the temperature at 4:00 and 5:00 and take the average.  This is interpolation.  However, interpolation can be significantly improved but gets more complicated.  Interpolation is the backbone behind almost all numerical methods.

Sine function example

To start with we will examine the Sine function because it is smooth and we can find intermediate values by other means to check our results.  You may not know the function but we will use this as an example.  The Sine function also has a few well known values listed below:

• $ \sin(0)=0 $
• $ \sin(30^\circ)=\sin(\frac{\pi}{6})=\frac{1}{2} $
• $ \sin(45^\circ)=\sin(\frac{\pi}{4})=\frac{1}{\sqrt{2}} \approx 0.707107 $
• $ \sin(90^\circ)=\sin(\frac{\pi}{2})=1 $
• $ \sin(180^\circ)=\sin(\pi)=0 $
• $ \sin(270^\circ)=\sin(\frac{3}{2\pi})= -1 $
• $ \sin(360^\circ)=\sin(2\pi)=0 $

These values are shown below along with a Sine function.

Linear Interpolation

The simplest way to interpolate is to use a line between points. This results in a function approximation as shown below in red.

To look closer we will look between the third and fourth points, Point 2 and Point 3 since Point 0 is the first point.  The plot below shows only the segment between these points along with point location labels.

We want a line that goes from Point 2 to Point 3.  In this case n = 2 . One way to do this is to define two functions of x, the first is 1.0 at Point 2 and 0.0 at Point 3 while the second is 0.0 at Point 2 and 1.0 at Point 3.  For notation a plain x will be the variable x, while an x with a subscript will will be the x value at a point.  To make a function zero at a point multiply by $ ( x -x_n ) $

and to make it 1.0 at a point divide by this value evaluated at that point. This gives the two functions as

$ f_0 (x) = \frac{x_{n+1}-x}{x_{n+1}-x_n} \quad and \quad f_1 (x) = \frac{ x - x_n }{x_{n+1} - x_n }\qquad. $

Multiplying these functions by the value of y at the appropriate points and adding the functions together then gives

$ f(x) \;=\;y_n f_0 (x) + y_{n+1} f_1 (x) \;=\; \frac{x_{n+1}-x}{x_{n+1}-x_n}\, y_n + \frac{ x - x_n }{x_{n+1} - x_n }\, y_{n+1}$

$ f(x)\;=\;\frac{ (x_{n+1}-x)\,y_n + (x - x_n)\,y_{n+1} }{x_{n+1}-x_n}$

The estimate of the function between the points can be found by evaluating the function defined between those points.

Error Analysis

There is an error in this approximation because the straight line does not follow the curve resulting in a gap between the curves. If we know the real function has a continuous derivative between the points we can bound the error. By bounding the error we can determine how accurate our estimate of the function must be. The accuracy could be better but we would know it is at least as good as the bound. A continuous derivative means that there are no jumps or gaps in the derivative. The derivative is the slope of the curve at a location.
The key to this analysis is that given a continuous first derivative and the value at a point, the exact value at another point can be represented as

$y_{exact}(x) \;=\; y_n + (x-x_n) \; \frac{dy}{dx} \bigg\vert_{\;x=\xi} \quad \quad \quad (1)$

where $x_n \le \xi \le x\quad \quad \quad.$

To illustrate this, if the function has a continuous, defined derivative in the interval then the function is within a parallelogram bounded by the maximum and minimum derivatives within the interval as shown by the yellow polygon below

Note that in general the maximum and minimum derivatives are not known and may be unbounded (infinite). Since the derivative is continuous it contains all values between the minimum and maximum derivatives. Then any point within the parallelogram at an x value will be defined as in equation 1 above. This results in an error at x of

$ error = (x - x_{n} ) \left\vert \frac{y_{n+1}-y_n}{x_{n+1} - x_n} - \,\frac{dy}{dx} \big\vert_{x=\xi}\; \right \vert $

and a maximum error of

$ error_{max} = (x_{n+1} - x_{n} ) \left\vert \frac{y_{n+1}-y_n}{x_{n+1} - x_n} - \,\frac{dy}{dx} \big\vert_{\;x=\xi}\; \right\vert $

which decreases as the x interval gets smaller.

Quadratic Interpolation

Page under construction
Posting required for codecog to show equations.
Also, use "html" editor only since "Compose" eliminates paragraph tags causing troubles.