# Dictionary Definition

interpolation

### Noun

1 a message (spoken or written) that is
introduced or inserted; "with the help of his friend's
interpolations his story was eventually told"; "with many
insertions in the margins" [syn: insertion]

2 (mathematics) calculation of the value of a
function between the values already known

3 the action of interjecting or interposing an
action or remark that interrupts [syn: interjection, interposition, interpellation]

# User Contributed Dictionary

see Interpolation

## English

### Pronunciation

- Rhymes: -eɪʃǝn

### Noun

- In music: an abrupt change of elements, with (almost immediate) continuation of the first idea. (DeLone et. al. (Eds.), 1975, chap. 1)
- In mathematics and science: the process of estimating the value of a function at a point from its values at nearby points.
- The process of including and processing externally-fetched data in a document or program; see interpolate.

#### Related terms

#### Synonyms

including and processing externally-fetched data#### Translations

- Dutch: interpolatie (2)
- Finnish: interpolointi
- German: Interpolation (2)
- Italian: interpolazione
- Swedish: interpolation (2)

### References

- DeLone et. al. (Eds.) (1975). Aspects of Twentieth-Century Music. Englewood Cliffs, New Jersey: Prentice-Hall. ISBN 0130493465.

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

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

addition, affix, allonge, appendix, approximation, aside, cadenza, coda, codicil, commentary, differentiation,
division, embedment, enclitic, entrance, envoi, epilogue, episode, equation, evolution, extempore, extrapolation, flourish, graft, grafting, hot lick, impaction, impactment, implantation, impromptu, improvisation, infix, infixion, infusion, injection, inoculation, insert, insertion, insinuation, integration, intercalation, interjection, interlineation, interlocution, introduction, intromission, inversion, involution, lick, marginalia, multiplication, notation, note, obiter dictum, parenthesis, penetration, perfusion, postscript, practice, prefix, proclitic, proportion, reduction, remark, rider, riff, scholia, side remark, subtraction, suffix, tail, tessellation, tossing-in,
transformation,
transplant, transplantation,
vamp