Crash Course in Scientific Computing

XVII. Interpolation

Interpolation describes the general problem of providing the value of a function, which is known only for a few points, at any point which lies between other known points (if the unknown point is not "surrounded" by known points, then the problem becomes that of "extrapolation", next lecture).

The simplest and also most natural method of interpolation is linear interpolation, which assumes that two neighbouring points are linked by a line. It has been used since immemorial times throughout history and remains a basic technique in the computer industry, which even formed a special name for it, "lerp" (also used as a verb).

The method simply consists in finding the equation for a line between two points, those which are known from the data, i.e.,

$$L(x)=f(a)+{f(b)-f(a)\over b-a}(x-a)$$

Let us assume that in the parametrization of our problem, the range of the function is the number of equally-spaced data points known and we wish to interpolate to real-valued functions. All variations of lerp will do something similar. We can then refer to the known data points $a$ and $b$ from $x$ as:

$$ \begin{align} a&=\lfloor x\rfloor\\ b&=\lceil x\rceil \end{align} $$

where the floor and ceil functions are defined as follows:

plot([floor, ceil], -3:.1:3, legend=false, lw=2)

In this case, our linear interpolation is easily implemented. Here is some sample data:

data = [sin(i) for i=0:2pi]

And here is the function to "lerp" it:

function lerpdata(x)
    a=floor(Int,x);
    b=ceil(Int,x);
    data[a]+((data[b]-data[a])/(b-a))*(x-a)
end

scatter(data)
plot!(lerpdata,1:.01:7, lw=3, ls=:dash, legend=false)

While it works well with enough points if the data has no noise, if it has, it gives disagreeable results:

data = [sin(i)+rand()/5 for i=0:.1:2pi]
scatter(data)
plot!(lerpdata,1:.0001:63, lw=3, legend=false)

In two dimensions, linear interpolation becomes bilinear interpolations (in 3D, trilinear, etc.)

Polynomial interpolation.

Spline interpolation.

Runge's phenomenon.