In the
mathematical field of
numerical analysis
Numerical analysis is the study of algorithms that use numerical approximation (as opposed to symbolic computation, symbolic manipulations) for the problems of mathematical analysis (as distinguished from discrete mathematics). It is the study of ...
, interpolation is a type of
estimation, a method of constructing (finding) new
data points based on the range of a
discrete set
]
In mathematics, a point ''x'' is called an isolated point of a subset ''S'' (in a topological space ''X'') if ''x'' is an element of ''S'' and there exists a neighborhood of ''x'' which does not contain any other points of ''S''. This is equival ...
of known data points.
In
engineering
Engineering is the use of scientific method, scientific principles to design and build machines, structures, and other items, including bridges, tunnels, roads, vehicles, and buildings. The discipline of engineering encompasses a broad rang ...
and
science
Science is a systematic endeavor that builds and organizes knowledge in the form of testable explanations and predictions about the universe.
Science may be as old as the human species, and some of the earliest archeological evidence for ...
, one often has a number of data points, obtained by
sampling or
experimentation, which represent the values of a function for a limited number of values of the
independent variable
Dependent and independent variables are variables in mathematical modeling, statistical modeling and experimental sciences. Dependent variables receive this name because, in an experiment, their values are studied under the supposition or demand ...
. It is often required to interpolate; that is, estimate the value of that function for an intermediate value of the independent variable.
A closely related problem is the
approximation
An approximation is anything that is intentionally similar but not exactly equality (mathematics), equal to something else.
Etymology and usage
The word ''approximation'' is derived from Latin ''approximatus'', from ''proximus'' meaning ''very ...
of a complicated function by a simple function. Suppose the formula for some given function is known, but too complicated to evaluate efficiently. A few data points from the original function can be interpolated to produce a simpler function which is still fairly close to the original. The resulting gain in simplicity may outweigh the loss from interpolation error and give better performance in calculation process.
Example
This table gives some values of an unknown function
.
Interpolation provides a means of estimating the function at intermediate points, such as
We describe some
methods
Method ( grc, μέθοδος, methodos) literally means a pursuit of knowledge, investigation, mode of prosecuting such inquiry, or system. In recent centuries it more often means a prescribed process for completing a task. It may refer to:
*Scien ...
of interpolation, differing in such properties as: accuracy, cost, number of data points needed, and
smoothness
In mathematical analysis, the smoothness of a function is a property measured by the number of continuous derivatives it has over some domain, called ''differentiability class''. At the very minimum, a function could be considered smooth if it ...
of the resulting
interpolant function.
Piecewise constant interpolation
![Piecewise constant](https://upload.wikimedia.org/wikipedia/commons/4/47/Piecewise_constant.svg)
The simplest interpolation method is to locate the nearest data value, and assign the same value. In simple problems, this method is unlikely to be used, as
linear
Linearity is the property of a mathematical relationship (''function'') that can be graphically represented as a straight line. Linearity is closely related to '' proportionality''. Examples in physics include rectilinear motion, the linear r ...
interpolation (see below) is almost as easy, but in higher-dimensional
multivariate interpolation, this could be a favourable choice for its speed and simplicity.
Linear interpolation
![Interpolation example linear](https://upload.wikimedia.org/wikipedia/commons/6/67/Interpolation_example_linear.svg)
One of the simplest methods is linear interpolation (sometimes known as lerp). Consider the above example of estimating ''f''(2.5). Since 2.5 is midway between 2 and 3, it is reasonable to take ''f''(2.5) midway between ''f''(2) = 0.9093 and ''f''(3) = 0.1411, which yields 0.5252.
Generally, linear interpolation takes two data points, say (''x''
''a'',''y''
''a'') and (''x''
''b'',''y''
''b''), and the interpolant is given by:
:
:
:
This previous equation states that the slope of the new line between
and
is the same as the slope of the line between
and
Linear interpolation is quick and easy, but it is not very precise. Another disadvantage is that the interpolant is not
differentiable at the point ''x''
''k''.
The following error estimate shows that linear interpolation is not very precise. Denote the function which we want to interpolate by ''g'', and suppose that ''x'' lies between ''x''
''a'' and ''x''
''b'' and that ''g'' is twice continuously differentiable. Then the linear interpolation error is
:
In words, the error is proportional to the square of the distance between the data points. The error in some other methods, including
polynomial interpolation and spline interpolation (described below), is proportional to higher powers of the distance between the data points. These methods also produce smoother interpolants.
Polynomial interpolation
![Interpolation example polynomial](https://upload.wikimedia.org/wikipedia/commons/4/41/Interpolation_example_polynomial.svg)
Polynomial interpolation is a generalization of linear interpolation. Note that the linear interpolant is a
linear function. We now replace this interpolant with a
polynomial
In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An exa ...
of higher
degree
Degree may refer to:
As a unit of measurement
* Degree (angle), a unit of angle measurement
** Degree of geographical latitude
** Degree of geographical longitude
* Degree symbol (°), a notation used in science, engineering, and mathematics
...
.
Consider again the problem given above. The following sixth degree polynomial goes through all the seven points:
:
Substituting ''x'' = 2.5, we find that ''f''(2.5) = ~0.59678.
Generally, if we have ''n'' data points, there is exactly one polynomial of degree at most ''n''−1 going through all the data points. The interpolation error is proportional to the distance between the data points to the power ''n''. Furthermore, the interpolant is a polynomial and thus infinitely differentiable. So, we see that polynomial interpolation overcomes most of the problems of linear interpolation.
However, polynomial interpolation also has some disadvantages. Calculating the interpolating polynomial is computationally expensive (see
computational complexity
In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations) ...
) compared to linear interpolation. Furthermore, polynomial interpolation may exhibit oscillatory artifacts, especially at the end points (see
Runge's phenomenon).
Polynomial interpolation can estimate local maxima and minima that are outside the range of the samples, unlike linear interpolation. For example, the interpolant above has a local maximum at ''x'' ≈ 1.566, ''f''(''x'') ≈ 1.003 and a local minimum at ''x'' ≈ 4.708, ''f''(''x'') ≈ −1.003. However, these maxima and minima may exceed the theoretical range of the function; for example, a function that is always positive may have an interpolant with negative values, and whose inverse therefore contains false
vertical asymptotes.
More generally, the shape of the resulting curve, especially for very high or low values of the independent variable, may be contrary to commonsense; that is, to what is known about the experimental system which has generated the data points. These disadvantages can be reduced by using spline interpolation or restricting attention to
Chebyshev polynomials
The Chebyshev polynomials are two sequences of polynomials related to the cosine and sine functions, notated as T_n(x) and U_n(x). They can be defined in several equivalent ways, one of which starts with trigonometric functions:
The Chebyshe ...
.
Spline interpolation
![Interpolation example spline](https://upload.wikimedia.org/wikipedia/commons/5/53/Interpolation_example_spline.svg)
Remember that linear interpolation uses a linear function for each of intervals
''k'',''x''''k+1''">'x''''k'',''x''''k+1'' Spline interpolation uses low-degree polynomials in each of the intervals, and chooses the polynomial pieces such that they fit smoothly together. The resulting function is called a spline.
For instance, the
natural cubic spline
In the mathematical field of numerical analysis, spline interpolation is a form of interpolation where the interpolant is a special type of piecewise polynomial called a spline. That is, instead of fitting a single, high-degree polynomial to all ...
is
piecewise
In mathematics, a piecewise-defined function (also called a piecewise function, a hybrid function, or definition by cases) is a function defined by multiple sub-functions, where each sub-function applies to a different interval in the domain. Pi ...
cubic and twice continuously differentiable. Furthermore, its second derivative is zero at the end points. The natural cubic spline interpolating the points in the table above is given by
:
In this case we get ''f''(2.5) = 0.5972.
Like polynomial interpolation, spline interpolation incurs a smaller error than linear interpolation, while the interpolant is smoother and easier to evaluate than the high-degree polynomials used in polynomial interpolation. However, the global nature of the basis functions leads to ill-conditioning. This is completely mitigated by using splines of compact support, such as are implemented in Boost.Math and discussed in Kress.
Mimetic interpolation
Depending on the underlying discretisation of fields, different interpolants may be required. In contrast to other interpolation methods, which estimate functions on target points, mimetic interpolation evaluates the integral of fields on target lines, areas or volumes, depending on the type of field (scalar, vector, pseudo-vector or pseudo-scalar).
A key feature of mimetic interpolation is that
vector calculus identities
The following are important identities involving derivatives and integrals in vector calculus.
Operator notation
Gradient
For a function f(x, y, z) in three-dimensional Cartesian coordinate variables, the gradient is the vector field:
\o ...
are satisfied, including
Stokes' theorem
Stokes's theorem, also known as the Kelvin–Stokes theorem Nagayoshi Iwahori, et al.:"Bi-Bun-Seki-Bun-Gaku" Sho-Ka-Bou(jp) 1983/12Written in Japanese)Atsuo Fujimoto;"Vector-Kai-Seki Gendai su-gaku rekucha zu. C(1)" :ja:培風館, Bai-Fu-Kan( ...
and the
divergence theorem
In vector calculus, the divergence theorem, also known as Gauss's theorem or Ostrogradsky's theorem, reprinted in is a theorem which relates the ''flux'' of a vector field through a closed surface to the ''divergence'' of the field in the vol ...
. As a result, mimetic interpolation conserves line, area and volume integrals. Conservation of line integrals might be desirable when interpolating the
electric field
An electric field (sometimes E-field) is the physical field that surrounds electrically charged particles and exerts force on all other charged particles in the field, either attracting or repelling them. It also refers to the physical field fo ...
, for instance, since the line integral gives the
electric potential
The electric potential (also called the ''electric field potential'', potential drop, the electrostatic potential) is defined as the amount of work energy needed to move a unit of electric charge from a reference point to the specific point in ...
difference at the endpoints of the integration path. Mimetic interpolation ensures that the error of estimating the line integral of an electric field is the same as the error obtained by interpolating the potential at the end points of the integration path, regardless of the length of the integration path.
Linear
Linearity is the property of a mathematical relationship (''function'') that can be graphically represented as a straight line. Linearity is closely related to '' proportionality''. Examples in physics include rectilinear motion, the linear r ...
,
bilinear and
trilinear interpolation are also considered mimetic, even if it is the field values that are conserved (not the integral of the field). Apart from linear interpolation, area weighted interpolation can be considered as one of the first mimetic interpolation method to have been developed.
Function approximation
Interpolation is a common way to approximate functions. Given a function
with a set of points