FACTOID # 6: Michigan is ranked 22nd in land area, but since 41.27% of the state is composed of water, it jumps to 11th place in total area.
 
 Home   Encyclopedia   Statistics   States A-Z   Flags   Maps   FAQ   About 
   
 
WHAT'S NEW
RELATED ARTICLES
People who viewed "Interpolation" also viewed:
 

SEARCH ALL

FACTS & STATISTICS    Advanced view

Search encyclopedia, statistics and forums:

 

 

(* = Graphable)

 

 


Encyclopedia > Interpolation

In the mathematical subfield of numerical analysis, interpolation is a method of constructing new data points within the range of a discrete set of known data points. For other meanings of mathematics or uses of math and maths, see Mathematics (disambiguation) and Math (disambiguation). ... Numerical analysis is the study of approximate methods for the problems of continuous mathematics (as distinguished from discrete mathematics). ... In topology, a point x of a set S is called an isolated point, if there exists a neighbourhood of x not containing other points of S. In particular, in an Euclidean space (or in a metric space), x is an isolated point of S, if one can find an...


In engineering and science one often has a number of data points, as obtained by sampling or experiment, and tries to construct a function which closely fits those data points. This is called curve fitting or regression analysis. Interpolation is a specific case of curve fitting, in which the function must go exactly through the data points. Engineering is the discipline and profession of applying scientific knowledge and utilizing natural laws and physical resources in order to design and implement materials, structures, machines, devices, systems, and processes that realize a desired objective and meet specified criteria. ... A magnet levitating above a high-temperature superconductor demonstrates the Meissner effect. ... Sampling is that part of statistical practice concerned with the selection of individual observations intended to yield some knowledge about a population of concern, especially for the purposes of statistical inference. ... In the scientific method, an experiment (Latin: ex- periri, of (or from) trying) is a set of observations performed in the context of solving a particular problem or question, to retain or falsify a hypothesis or research concerning phenomena. ... Curve fitting is finding a curve which matches a series of data points and possibly other constraints. ... In statistics, regression analysis examines the relation of a dependent variable (response variable) to specified independent variables (explanatory 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 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 table, and try to interpolate those data points to construct a simpler function. Of course, when using the simple function to calculate new data points we usually do not receive the same result as when using the original function, but depending on the problem domain and the interpolation method used the gain in simplicity might offset the error. In computer science, a lookup table is a data structure, usually an array or associative array, used to replace a runtime computation with a simpler lookup operation. ...


It should be mentioned that there is 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 theorem. There also are many other subsequent results. In mathematics, the Riesz-Thorin theorem, often referred to as the ``Riesz-Thorin Interpolation Theorem or the ``Riesz-Thorin Convexity Theorem is a result about ``interpolation of operators. This should not be confused with somewhat different mathematical procedure of interpolation of functions. ... In mathematics, the Marcinkiewicz theorem, discovered by Józef Marcinkiewicz, is a result about interpolation of operators acting on Lp spaces and related spaces. ...

Contents

Definition

An interpolation of a finite set of points on an epitrochoid. Points through which curve is splined are red; the blue curve connecting them is interpolation.
An interpolation of a finite set of points on an epitrochoid. Points through which curve is splined are red; the blue curve connecting them is interpolation.

From inter meaning between and pole, the points or nodes. Any means of calculating a new point between two existing data points is therefore interpolation. An epitrochoid is a roulette traced by a point attached to a circle of radius b rolling around the outside of a fixed circle of radius a, where the point is a distance h from the center of the exterior circle. ... One type of spline, a bézier curve In the mathematical subfield of numerical analysis, a spline is a special function defined piecewise by polynomials. ...


There are many methods for doing this, many of which involve fitting some sort of function to the data and evaluating that function at the desired point. This does not exclude other means such as statistical methods of calculating interpolated data.


The simplest form of interpolation is to take the mean average of x and y of two adjacent points to find the mid point. This will give the same result as linear interpolation evaluated at the midpoint.


Given a sequence of n distinct numbers xk called nodes and for each xk a second number yk, we are looking for a function f so that For other senses of this word, see sequence (disambiguation). ...

f(x_k) = y_k mbox{ , } k=1,ldots,n

A pair xk,yk is called a data point and f is called an interpolant for the data points.


When the numbers yk are given by a known function f, we sometimes write fk.


Example

For example, suppose we have a table like this, which gives some values of an unknown function f.

Plot of the data points as given in the table.
Plot of the data points as given in the table.
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 algorithm are: How accurate is the method? How expensive is it? How smooth is the interpolant? How many data points are needed?
Flowcharts are often used to graphically represent algorithms. ... In mathematical analysis, a differentiability class is a classification of functions according to the properties of their derivatives. ...


Piecewise constant interpolation

Piecewise constant interpolation, or nearest-neighbor interpolation.
Piecewise constant interpolation, or nearest-neighbor interpolation.
For more details on this topic, see Nearest-neighbor interpolation.

The simplest interpolation method is to locate the nearest data value, and assign the same value. In one dimension, there are seldom good reasons to choose this one over linear interpolation, which is almost as cheap, but in higher dimensions, in multivariate interpolation, this can be a favourable choice for its speed and simplicity.
In numerical analysis, multivariate interpolation or spatial interpolation is interpolation on functions of more than one variable. ...


Linear interpolation

Plot of the data with linear interpolation superimposed
Plot of the data with linear interpolation superimposed
Main article: Linear interpolation

One of the simplest methods is linear interpolation (sometimes known as lerp). Consider the above example of determining 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. Linear interpolation is a process employed in mathematics, and numerous applications including computer graphics. ... For other uses, see Linear (disambiguation). ...


Generally, linear interpolation takes two data points, say (xa,ya) and (xb,yb), and the interpolant is given by:

 y = y_a + frac{(x-x_a)(y_b-y_a)}{(x_b-x_a)} 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 differentiable at the point xk. This article is about derivatives and differentiation in mathematical calculus. ...


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 xa and xb and that g is twice continuously differentiable. Then the linear interpolation error is

 |f(x)-g(x)| le C(x_b-x_a)^2 quadmbox{where}quad C = frac18 max_{yin[x_a,x_b]} |g''(y)|.

In words, the error is proportional to the square of the distance between the data points. The error of 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

Plot of the data with polynomial interpolation applied
Plot of the data with polynomial interpolation applied

Polynomial interpolation is a generalization of linear interpolation. Note that the linear interpolant is a linear function. We now replace this interpolant by a polynomial of higher degree. In the mathematical subfield of numerical analysis, polynomial interpolation is the interpolation of a given data set by a polynomial. ... A linear function is a mathematical function term of the form: f(x) = m x + c where c is a constant. ... In mathematics, a polynomial is an expression that is constructed from one variable or more variables and constants, using only the operations of addition, subtraction, multiplication, and constant positive whole number exponents. ... This article is about the term degree as used in mathematics. ...


Consider again the problem given above. The following sixth degree polynomial goes through all the seven points:

f(x) = − 0.0001521x6 − 0.003130x5 + 0.07321x4 − 0.3577x3 + 0.2255x2 + 0.9038x.

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 solves all the problems of linear interpolation.


However, polynomial interpolation also has some disadvantages. Calculating the interpolating polynomial is relatively very computationally expensive (see computational complexity). Furthermore, polynomial interpolation may not be so exact after all, especially at the end points (see Runge's phenomenon). These disadvantages can be avoided by using spline interpolation.
Complexity theory is part of the theory of computation dealing with the resources required during computation to solve a given problem. ... The red curve is the Runge function, the blue curve is a 5th-degree polynomial, while the green curve is a 9th-degree polynomial. ...


Spline interpolation

Plot of the data with Spline interpolation applied
Plot of the data with Spline interpolation applied
Main article: spline interpolation

Remember that 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. 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. ... One type of spline, a bézier curve In the mathematical subfield of numerical analysis, a spline is a special function defined piecewise by polynomials. ...


For instance, the natural cubic spline is piecewise 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 the mathematical subfield of numerical analysis spline interpolation is a special form of interpolation where the interpolant is a piecewise polynomial called spline. ... In mathematics, a function f(x) of a real number variable x is defined piecewise, if f(x) is given by different expressions on various intervals. ...

 f(x) = left{ begin{matrix} -0.1522 x^3 + 0.9937 x, & mbox{if } x in [0,1],  -0.01258 x^3 - 0.4189 x^2 + 1.4126 x - 0.1396, & mbox{if } x in [1,2],  0.1403 x^3 - 1.3359 x^2 + 3.2467 x - 1.3623, & mbox{if } x in [2,3],  0.1579 x^3 - 1.4945 x^2 + 3.7225 x - 1.8381, & mbox{if } x in [3,4],  0.05375 x^3 -0.2450 x^2 - 1.2756 x + 4.8259, & mbox{if } x in [4,5],  -0.1871 x^3 + 3.3673 x^2 - 19.3370 x + 34.9282, & mbox{if } x in [5,6].  end{matrix} right.

In this case we get f(2.5)=0.597262.


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 high-degree polynomials used in polynomial interpolation. It also does not suffer from Runge's phenomenon.
The red curve is the Runge function, the blue curve is a 5th-degree polynomial, while the green curve is a 9th-degree polynomial. ...


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 functions, and trigonometric interpolation is interpolation by trigonometric polynomials. The discrete Fourier transform is a special case of trigonometric interpolation. Another possibility is to use wavelets. In mathematics, a rational function in algebra is a function defined as a ratio of polynomials. ... In the mathematical subfield of numerical analysis, trigonometric interpolation is a special form of interpolation on the unit circle in the complex plane using trigonometric polynomials. ... In the mathematical subfield of numerical analysis, a trigonometric polynomial is a finite linear linear combination of sin(nx) and cos(nx) with n a natural number. ... In mathematics, the discrete Fourier transform (DFT), occasionally called the finite Fourier transform, is a transform for Fourier analysis of finite-domain discrete-time signals. ... A wavelet is a kind of mathematical function used to divide a given function into different frequency components and study each component with a resolution that matches its scale. ...


The Whittaker–Shannon interpolation formula can be used if the number of data points is infinite. The Whittaker–Shannon interpolation formula dates back to works of E. Borel in 1898, and E. T. Whittaker in 1915, and was cited from works of J. M. Whittaker in 1935 in the formulation of the Nyquist–Shannon sampling theorem by C. E. Shannon in 1949. ...


Multivariate interpolation is the interpolation of functions of more than one variable. Methods include bilinear interpolation and bicubic interpolation in two dimensions, and trilinear interpolation in three dimensions. In numerical analysis, multivariate interpolation or spatial interpolation is interpolation on functions of more than one variable. ... In mathematics, bilinear interpolation is an extension of linear interpolation for interpolating functions of two variables. ... In numerical analysis, a branch of mathematics, bicubic interpolation is one of the most common interpolation methods in two dimensions. ... Trilinear interpolation is the process of taking a three-dimensional set of numbers and interpolating the values linearly, finding a point using a weighted average of eight values. ...


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 interpolation problems. Hermite interpolation is a method closely related to the Newton divided difference method of interpolation in numerical analysis, that allows us to consider given derivatives at data points, as well as the data points themselves. ...


Related concepts

The term extrapolation is used if we want to find data points outside the range of known data points. In mathematics, extrapolation is the process of constructing new data points outside a discrete set of known data points. ...


In curve 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. This requires parameterizing the potential interpolants and having some way of measuring the error. In the simplest case this leads to least squares approximation. Curve fitting is finding a curve which matches a series of data points and possibly other constraints. ... In regression analysis, least squares, also known as ordinary least squares analysis, is a method for linear regression that determines the values of unknown quantities in a statistical model by minimizing the sum of the residuals (the difference between the predicted and observed values) squared. ...


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. In mathematics, approximation theory is concerned with how functions can be approximated with other, simpler, functions, and with characterising in a quantitative way the errors introduced thereby. ...


References

  • David Kidner, Mark Dorey and Derek Smith (1999). What's the point? Interpolation and extrapolation with a regular grid DEM. IV International Conference on GeoComputation, Fredericksburg, VA, USA.
  • Kincaid, David; Ward Cheney (2002). Numerical Analysis (3rd edition). Brooks/Cole. ISBN 0-534-38905-8.  Chapter 6.
  • Schatzman, Michelle (2002). Numerical Analysis: A Mathematical Introduction. Clarendon Press, Oxford. ISBN 0-19-850279-6.  Chapters 4 and 6.

External links

Wikimedia Commons has media related to:
Interpolation
  • DotPlacer applet : Applet showing various interpolation methods, with movable points
Image File history File links Commons-logo. ...

  Results from FactBites:
 
Interpol - Wikipedia, the free encyclopedia (980 words)
Interpol, once merely the organization's telegraphic address, was officially incorporated into the organization's new name adopted in 1956, prior to which it was known as the International Criminal Police Commission.
Interpol was founded in Austria in 1923 as the International Criminal Police Commission.
Interpol maintains a large database charting unsolved crimes and both convicted and alleged criminals.
Interpol (band) - Wikipedia, the free encyclopedia (591 words)
Interpol is a New York City indie rock band, formed in 1998.
Sam Fogarino told a reporter from Pitchfork in an interview that Interpol is in the process of recording new material for their third album.
Another suggestion as to the reason the band is so called is because the word Interpol suggests order and efficiency, similar to the style in which the band plays.
  More results at FactBites »

 
 

COMMENTARY     


Share your thoughts, questions and commentary here
Your name
Your comments

Want to know more?
Search encyclopedia, statistics and forums:

 


Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 1022, m