AskDefine | Define interpolate

Dictionary Definition

interpolate

Verb

1 estimate the value of [syn: extrapolate]
2 insert words into texts, often falsifying it thereby [syn: alter, falsify]

User Contributed Dictionary

English

Verb

  1. To estimate the value of a function between two points between which it is tabulated.
  2. During the course of processing some data, and in response to a directive in that data, to fetch data from a different source and process it in-line along with the original data.
  3. To introduce material to change the meaning of or falsify a text.

Synonyms

Translations

to estimate the value of a function
to fetch data from a different source and process it in-line along with the original data
to introduce material to change the meaning of or falsify a text

Related terms

Quotations

  • A macro is invoked in the same way as a request; a control line beginning .xx will interpolate the contents of macro xx. —Joseph F. Ossanna, Nroff/Troff User's manual
  • In Perl, variable interpolation happens in double-quoted strings and patterns, and list interpolation occurs when constructing the list of values to pass to a list operator or other such construct that takes a LIST. —Wall, Christiansen, and Orwant, Programming Perl, 3rd Edition, 2000, p. 992.

Italian

Verb

interpolate
  1. Form of Second-person plural imperative, interpolare#Italian|interpolare

Extensive Definition

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

Definition

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.
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
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. 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?

Piecewise constant 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.

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.
Generally, linear interpolation takes two data points, say (xa,ya) and (xb,yb), and the interpolant is given by:
y = y_a + \frac 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.
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 \quad\mbox\quad C = \frac18 \max_ |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

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.
Consider again the problem given above. The following sixth degree polynomial goes through all the seven points:
f(x) = -0.0001521 x^6 - 0.003130 x^5 + 0.07321 x^4 - 0.3577 x^3 + 0.2255 x^2 + 0.9038 x.
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.

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.
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
f(x) = \left\

Synonyms, Antonyms and Related Words

add, admit, annex, append, drag in, edge in, enter, fill in, foist in, fudge in, implant in, inject in, insert, insert in, insinuate, insinuate in, intercalate, interjaculate, interject, interlope, interpose, intervene, introduce in, intrude, lug in, put between, run in, sandwich, smuggle in, squeeze in, superadd, throw in, thrust in, wedge in, work in, worm in
Privacy Policy, About Us, Terms and Conditions, Contact Us
Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2
Material from Wikipedia, Wiktionary, Dict
Valid HTML 4.01 Strict, Valid CSS Level 2.1