This wikilog article is a draft, it was not published yet.

Julia programming

⇠ Back to Blog:Sandbox

We could now study still other methods, such as the Backward Euler method, or Implicit Euler method. But we will instead turn to other numerical problems, namely, interpolation and extrapolation.

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").

The simplest and also most natural method of interpolation. 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)
Screenshot 26-03-2020 182425.jpg

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)
Screenshot 26-03-2020 202110.jpg

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)
Screenshot 26-03-2020 202640.jpg


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

Polynomial interpolation.

Spline interpolation.

Runge's phenomenon.