 | This article includes a list ofgeneral references, butit lacks sufficient correspondinginline citations. Please help toimprove this article byintroducing more precise citations.(October 2016) (Learn how and when to remove this message) |
In themathematical field ofnumerical analysis,interpolation is a type ofestimation, a method of constructing (finding) newdata points based on the range of adiscrete set of known data points.[1][2]
Inengineering andscience, one often has a number of data points, obtained bysampling orexperimentation, which represent the values of a function for a limited number of values of theindependent variable. It is often required tointerpolate; that is, estimate the value of that function for an intermediate value of the independent variable.
A closely related problem is theapproximation 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.
This table gives some values of an unknown function.
| 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
We describe somemethods of interpolation, differing in such properties as: accuracy, cost, number of data points needed, andsmoothness of the resultinginterpolant function.
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, aslinear interpolation (see below) is almost as easy, but in higher-dimensionalmultivariate interpolation, this could be a favourable choice for its speed and simplicity.
One of the simplest methods is linear interpolation (sometimes known as lerp). Consider the above example of estimatingf(2.5). Since 2.5 is midway between 2 and 3, it is reasonable to takef(2.5) midway betweenf(2) = 0.9093 andf(3) = 0.1411, which yields 0.5252.
Generally, linear interpolation takes two data points, say (xa,ya) and (xb,yb), 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 notdifferentiable at the pointxk.
The following error estimate shows that linear interpolation is not very precise. Denote the function which we want to interpolate byg, and suppose thatx lies betweenxa andxb and thatg 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, includingpolynomial 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 is a generalization of linear interpolation. Note that the linear interpolant is alinear function. We now replace this interpolant with apolynomial of higherdegree.
Consider again the problem given above. The following sixth degree polynomial goes through all the seven points:
Substitutingx = 2.5, we find thatf(2.5) = ~0.59678.
Generally, if we haven data points, there is exactly one polynomial of degree at mostn−1 going through all the data points. The interpolation error is proportional to the distance between the data points to the powern. 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 (seecomputational complexity) compared to linear interpolation. Furthermore, polynomial interpolation may exhibit oscillatory artifacts, especially at the end points (seeRunge'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 atx ≈ 1.566,f(x) ≈ 1.003 and a local minimum atx ≈ 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 falsevertical 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 toChebyshev polynomials.
Linear interpolation uses a linear function for each of intervals [xk,xk+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, thenatural cubic spline ispiecewise 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 getf(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.[3]
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 thatvector calculus identities are satisfied, includingStokes' theorem and thedivergence theorem. As a result, mimetic interpolation conserves line, area and volume integrals.[4] Conservation of line integrals might be desirable when interpolating theelectric field, for instance, since the line integral gives theelectric potential difference at the endpoints of the integration path.[5] 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,bilinear andtrilinear 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 one of the first mimetic interpolation methods to have been developed.[6]
TheTheory of Functional Connections (TFC) is a mathematical framework specifically developed forfunctional interpolation. Given any interpolant that satisfies a set of constraints, TFC derives a functional that represents the entire family of interpolants satisfying those constraints, including those that are discontinuous or partially defined. These functionals identify the subspace of functions where the solution to a constrained optimization problem resides. Consequently, TFC transforms constrained optimization problems into equivalent unconstrained formulations. This transformation has proven highly effective in the solution ofdifferential equations. TFC achieves this by constructing a constrained functional (a function of a free function), that inherently satisfies given constraints regardless of the expression of the free function. This simplifies solving various types of equations and significantly improves the efficiency and accuracy of methods likePhysics-Informed Neural Networks (PINNs). TFC offers advantages over traditional methods likeLagrange multipliers andspectral methods by directly addressing constraints analytically and avoiding iterative procedures, although it cannot currently handle inequality constraints.
Interpolation is a common way to approximate functions. Given a function with a set of points one can form a function such that for (that is, that interpolates at these points). In general, an interpolant need not be a good approximation, but there are well known and often reasonable conditions where it will. For example, if (four times continuously differentiable) thencubic spline interpolation has an error bound given by where and is a constant.[7]
Gaussian process is a powerful non-linear 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; that is, for fitting a curve through noisy data. In the geostatistics community Gaussian process regression is also known asKriging.
Inverse Distance Weighting (IDW) is a spatial interpolation method that estimates values based on nearby data points, with closer points having more influence.[8] It uses an inverse power law for weighting, where higher power values emphasize local effects, while lower values create a smoother surface. IDW is widely used inGIS,meteorology, and environmental modeling for its simplicity but may produce artifacts in clustered or uneven data.[9]
Other forms of interpolation can be constructed by picking a different class of interpolants. For instance, rational interpolation isinterpolation byrational functions usingPadé approximant, andtrigonometric interpolation is interpolation bytrigonometric polynomials usingFourier series. Another possibility is to usewavelets.
TheWhittaker–Shannon interpolation formula can be used if the number of data points is infinite or if the function to be interpolated has compact support.
Sometimes, we know not only the value of the function that we want to interpolate, at some points, but also its derivative. This leads toHermite interpolation problems.
When each data point is itself a function, it can be useful to see the interpolation problem as a partialadvection problem between each data point. This idea leads to thedisplacement interpolation problem used intransportation theory.
Multivariate interpolation is the interpolation of functions of more than one variable. Methods includenearest-neighbor interpolation,bilinear interpolation andbicubic interpolation in two dimensions, andtrilinear interpolation in three dimensions.They can be applied to gridded or scattered data. Mimetic interpolation generalizes to dimensional spaces where.[10][11]
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 that of a higher sampling rate (Upsampling) using various digital filtering techniques (for example, convolution with a frequency-limited 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 originalNyquist limit of the signal (that is, 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 bookMultirate Digital Signal Processing.[12]
The termextrapolation is used to find data points outside the range of known data points.
Incurve fitting 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 toleast squares approximation.
Approximation theory 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.
If we consider as a variable in atopological space, and the function mapping to aBanach space, then the problem is treated as "interpolation of operators".[13] The classical results about interpolation of operators are theRiesz–Thorin theorem and theMarcinkiewicz theorem. There are also many other subsequent results.
{{cite book}}: CS1 maint: location missing publisher (link){{citation}}: CS1 maint: work parameter with ISBN (link){{cite book}}:ISBN / Date incompatibility (help)
