In the
mathematicalMathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
field of
numerical analysisNumerical analysis is the study of algorithms that use numerical approximation for the problems of mathematical analysis ....
,
interpolation is a method of constructing new data points within the range of a discrete set of known data points.
In
engineeringEngineering is the discipline, art, skill and profession of acquiring and applying scientific, mathematical, economic, social, and practical knowledge, in order to design and build structures, machines, devices, systems, materials and processes that safely realize improvements to the lives of...
and
scienceScience is a systematic enterprise that builds and organizes knowledge in the form of testable explanations and predictions about the universe...
, one often has a number of data points, obtained by
samplingIn statistics and survey methodology, sampling is concerned with the selection of a subset of individuals from within a population to estimate characteristics of the whole population....
or experimentation, which represent the values of a function for a limited number of values of the independent variable. It is often required to
interpolate (i.e. estimate) the value of that function for an intermediate value of the independent variable. This may be achieved by
curve fittingCurve fitting is the process of constructing a curve, or mathematical function, that has the best fit to a series of data points, possibly subject to constraints. Curve fitting can involve either interpolation, where an exact fit to the data is required, or smoothing, in which a "smooth" function...
or
regression analysisIn statistics, regression analysis includes many techniques for modeling and analyzing several variables, when the focus is on the relationship between a dependent variable and one or more independent variables...
.
A different problem which is closely related to interpolation is the approximation of a complicated function by a simple function. Suppose we know the formula for the function but it is too complex to evaluate efficiently. Then we could pick a few known data points from the complicated function, creating a
lookup tableIn computer science, a lookup table is a data structure, usually an array or associative array, often used to replace a runtime computation with a simpler array indexing operation. The savings in terms of processing time can be significant, since retrieving a value from memory is often faster than...
, and try to interpolate those data points by constructing a simpler function. Of course, when using the simple function to estimate new data points we usually do not receive the same result as we would if we had used the original function, but depending on the problem domain and the interpolation method used the gain in simplicity might offset the error.
There is also another very different kind of interpolation in mathematics, namely the "interpolation of operators". The classical results about interpolation of operators are the Riesz–Thorin theorem and the
Marcinkiewicz theoremIn mathematics, the Marcinkiewicz interpolation theorem, discovered by , is a result bounding the norms of nonlinear operators acting on Lp spaces....
. There are also many other subsequent results.
Example
For example, suppose we have a table like this, which gives some values of an unknown function f.

x 

f(x) 


0 

0 

1 

0 
. 
8415 

2 

0 
. 
9093 

3 

0 
. 
1411 

4 

−0 
. 
7568 

5 

−0 
. 
9589 

6 

−0 
. 
2794 
Interpolation provides a means of estimating the function at intermediate points, such as x = 2.5.
There are many different interpolation methods, some of which are described below. Some of the concerns to take into account when choosing an appropriate
algorithmIn mathematics and computer science, an algorithm is an effective method expressed as a finite list of welldefined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
are: How accurate is the method? How expensive is it? How
smoothIn mathematical analysis, a differentiability class is a classification of functions according to the properties of their derivatives. Higher order differentiability classes correspond to the existence of more derivatives. Functions that have derivatives of all orders are called smooth.Most of...
is the interpolant? How many data points are needed?
Piecewise constant interpolation
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 interpolation (see below) is almost as easy, but in higher dimensional
multivariate interpolationIn numerical analysis, multivariate interpolation or spatial interpolation is interpolation on functions of more than one variable.The function to be interpolated is known at given points and the interpolation problem consist of yielding values at arbitrary points .Regular grid:For function...
, this could be a favourable choice for its speed and simplicity.
Linear interpolation
One of the simplest methods is
linearIn mathematics, a linear map or function f is a function which satisfies the following two properties:* Additivity : f = f + f...
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:
at the point (x,y)
Linear interpolation is quick and easy, but it is not very precise. Another disadvantage is that the interpolant is not
differentiableIn calculus, a branch of mathematics, the derivative is a measure of how a function changes as its input changes. Loosely speaking, a derivative can be thought of as how much one quantity is changing in response to changes in some other quantity; for example, the derivative of the position of a...
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
Polynomial interpolation is a generalization of linear interpolation. Note that the linear interpolant is a
linear functionIn mathematics, the term linear function can refer to either of two different but related concepts:* a firstdegree polynomial function of one variable;* a map between two vector spaces that preserves vector addition and scalar multiplication....
. We now replace this interpolant by a
polynomialIn mathematics, a polynomial is an expression of finite length constructed from variables and constants, using only the operations of addition, subtraction, multiplication, and nonnegative integer exponents...
of higher
degreeIn mathematics, there are several meanings of degree depending on the subject. Unit of angle :A degree , usually denoted by ° , is a measurement of a plane angle, representing 1⁄360 of a turn...
.
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.5965.
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 complexityComputational Complexity may refer to:*Computational complexity theory*Computational Complexity...
) compared to linear interpolation. Furthermore, polynomial interpolation may exhibit oscillatory artifacts, especially at the end points (see
Runge's phenomenonIn the mathematical field of numerical analysis, Runge's phenomenon is a problem of oscillation at the edges of an interval that occurs when using polynomial interpolation with polynomials of high degree...
). More generally, the shape of the resulting curve, especially for very high or low values of the independent variable, may be contrary to commonsense, i.e. 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 polynomialsIn mathematics the Chebyshev polynomials, named after Pafnuty Chebyshev, are a sequence of orthogonal polynomials which are related to de Moivre's formula and which can be defined recursively. One usually distinguishes between Chebyshev polynomials of the first kind which are denoted Tn and...
.
Spline interpolation
Remember that linear interpolation uses a linear function for each of intervals [x
_{k},x
_{k+1}]. Spline interpolation uses lowdegree polynomials in each of the intervals, and chooses the polynomial pieces such that they fit smoothly together. The resulting function is called a
splineIn mathematics, a spline is a sufficiently smooth piecewisepolynomial function. In interpolating problems, spline interpolation is often preferred to polynomial interpolation because it yields similar results, even when using lowdegree polynomials, while avoiding Runge's phenomenon for higher...
.
For instance, the natural cubic spline is
piecewiseOn mathematics, a piecewisedefined function is a function whose definition changes depending on the value of the independent variable...
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 and the interpolant is smoother. However, the interpolant is easier to evaluate than the highdegree polynomials used in polynomial interpolation. It also does not suffer from Runge's phenomenonIn the mathematical field of numerical analysis, Runge's phenomenon is a problem of oscillation at the edges of an interval that occurs when using polynomial interpolation with polynomials of high degree...
.
Interpolation via Gaussian processes
Gaussian processIn probability theory and statistics, a Gaussian process is a stochastic process whose realisations consist of random values associated with every point in a range of times such that each such random variable has a normal distribution...
is a powerful nonlinear interpolation tool. Many popular interpolation tools are actually equivalent to particular Gaussian processes. Gaussian processes can be used not only for fitting an interpolant that passes exactly through the given data points but also for regression, i.e., for fitting a curve through noisy data. In the geostatistics community Gaussian process regression is also known as KrigingKriging is a group of geostatistical techniques to interpolate the value of a random field at an unobserved location from observations of its value at nearby locations....
.
Other forms of interpolation
Other forms of interpolation can be constructed by picking a different class of interpolants. For instance, rational interpolation is interpolation by rational functionIn mathematics, a rational function is any function which can be written as the ratio of two polynomial functions. Neither the coefficients of the polynomials nor the values taken by the function are necessarily rational.Definitions:...
s, and trigonometric interpolationIn mathematics, trigonometric interpolation is interpolation with trigonometric polynomials. Interpolation is the process of finding a function which goes through some given data points. For trigonometric interpolation, this function has to be a trigonometric polynomial, that is, a sum of sines and...
is interpolation by trigonometric polynomialIn the mathematical subfields of numerical analysis and mathematical analysis, a trigonometric polynomial is a finite linear combination of functions sin and cos with n a natural number. The coefficients may be taken as real numbers, for realvalued functions...
s. Another possibility is to use waveletA wavelet is a wavelike oscillation with an amplitude that starts out at zero, increases, and then decreases back to zero. It can typically be visualized as a "brief oscillation" like one might see recorded by a seismograph or heart monitor. Generally, wavelets are purposefully crafted to have...
s.
The Whittaker–Shannon interpolation formulaThe Whittaker–Shannon interpolation formula or sinc interpolation is a method to reconstruct a continuoustime bandlimited signal from a set of equally spaced samples.Definition:...
can be used if the number of data points is infinite.
Multivariate interpolationIn numerical analysis, multivariate interpolation or spatial interpolation is interpolation on functions of more than one variable.The function to be interpolated is known at given points and the interpolation problem consist of yielding values at arbitrary points .Regular grid:For function...
is the interpolation of functions of more than one variable. Methods include bilinear interpolationIn mathematics, bilinear interpolation is an extension of linear interpolation for interpolating functions of two variables on a regular grid. The interpolated function should not use the term of x^2 or y^2, but x y, which is the bilinear form of x and y.The key idea is to perform linear...
and bicubic interpolationIn mathematics, bicubic interpolation is an extension of cubic interpolation for interpolating data points on a two dimensional regular grid. The interpolated surface is smoother than corresponding surfaces obtained by bilinear interpolation or nearestneighbor interpolation...
in two dimensions, and trilinear interpolationTrilinear interpolation is a method of multivariate interpolation on a 3dimensional regular grid. It approximates the value of an intermediate point within the local axial rectangular prism linearly, using data on the lattice points...
in three dimensions.
Sometimes, we know not only the value of the function that we want to interpolate, at some points, but also its derivative. This leads to Hermite interpolationIn numerical analysis, Hermite interpolation, named after Charles Hermite, is a method of interpolating data points as a polynomial function. The generated Hermite polynomial is closely related to the Newton polynomial, in that both are derived from the calculation of divided differences.Unlike...
problems.
Interpolation in digital signal processing
In the domain of digital signal processing, the term interpolation refers to the process of converting a sampled digital signal (such as a sampled audio signal) to a higher sampling rate using various digital filtering techniques (e.g., convolution with a frequencylimited impulse signal). In this application there is a specific requirement that the harmonic content of the original signal be preserved without creating aliased harmonic content of the original signal above the original Nyquist limit of the signal (i.e., above fs/2 of the original signal sample rate). An early and fairly elementary discussion on this subject can be found in Rabiner and Crochiere's book Multirate Digital Signal Processing.
Related concepts
The term extrapolationIn mathematics, extrapolation is the process of constructing new data points. It is similar to the process of interpolation, which constructs new points between known points, but the results of extrapolations are often less meaningful, and are subject to greater uncertainty. It may also mean...
is used if we want to find data points outside the range of known data points.
In curve fittingCurve fitting is the process of constructing a curve, or mathematical function, that has the best fit to a series of data points, possibly subject to constraints. Curve fitting can involve either interpolation, where an exact fit to the data is required, or smoothing, in which a "smooth" function...
problems, the constraint that the interpolant has to go exactly through the data points is relaxed. It is only required to approach the data points as closely as possible (within some other constraints). This requires parameterizing the potential interpolants and having some way of measuring the error. In the simplest case this leads to least squaresThe method of least squares is a standard approach to the approximate solution of overdetermined systems, i.e., sets of equations in which there are more equations than unknowns. "Least squares" means that the overall solution minimizes the sum of the squares of the errors made in solving every...
approximation.
Approximation theoryIn mathematics, approximation theory is concerned with how functions can best be approximated with simpler functions, and with quantitatively characterizing the errors introduced thereby...
studies how to find the best approximation to a given function by another function from some predetermined class, and how good this approximation is. This clearly yields a bound on how well the interpolant can approximate the unknown function.
See also
 Simple rational approximation
Simple rational approximation is a subset of interpolating methods using rational functions. Especially, SRA interpolates a given function with a specific rational function whose poles and zeros are simple, which means that there is no multiplicity in poles and zeros. Sometimes, it only implies...
 Multivariate interpolation
In numerical analysis, multivariate interpolation or spatial interpolation is interpolation on functions of more than one variable.The function to be interpolated is known at given points and the interpolation problem consist of yielding values at arbitrary points .Regular grid:For function...
 Newton–Cotes formulas