Interpolation

According to the Oxford English Dictionary, to interpolate is

To alter or enlarge (a book or writing) by insertion of new matter; esp. to tamper with by making insertions which create false impressions as to the date or character of the work in question.

The use of the term interpolation in mathematics was inspired in an obvious way by that concept, but is different: it refers to the approximation of a value of a function for which we only know values for a discrete set of values of the independent variable. For example, suppose we have a table like this, which gives some values of an known function f.

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

What value does the function have at, say, x = 2.5? Interpolation answers questions like this.

More formally, interpolation solves the following problem: given a sequence x₁, ..., x_n of distinct points and a some numbers f₁, ..., f_n, find a function f such that f(x_k) = f_k for all k = 1, ..., n.

Table of contents

1 Introduction
2 Linear interpolation
3 Polynomial interpolation
4 Spline interpolation
5 Other forms of interpolation
6 Related concepts
7 Further reading
8 References

Introduction

Interpolation may be used if one does not know the function being interpolated at every point. The function values f_k may have come from an experiment. Interpolation can also be used if we do have a formula, but it takes very long to evaluate. In that case, it should be borne in mind that interpolation is not exact: one cannot hope to find the precise value of f(x) from incomplete information.

There are many different interpolation methods, some of which are described below. Some of the things 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?

Linear interpolation

right 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 (x_a,f_a) and (x_b,f_b), and the interpolant is given by

This formula can be interpreted as a weighted average.

Linear interpolation is quick and easy, but it is not very precise. Another disadvantage is that the interpolant is not differentiable 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 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:

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

right Remember that linear interpolation uses a linear function for each of intervals [x_k,x_k+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

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

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.

The Nyquist-Shannon interpolation formula can be used if the number of data points is infinite.

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.

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.

Related concepts

The term extrapolation is used if we want to find the value of f at a point x which is outside of the points x_k at which f is given.

In regression or curve fitting problems, the constraint that the interpolant has to go exactly through the data points is relaxed. We only require that it approaches the data points as closely as possible.

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.

References

David Kincaid and Ward Cheney (2002). Numerical Analysis (3rd ed.), Chapter 6. Brooks/Cole. ISBN 0-534-38905-8.
Michelle Schatzman (2002). Numerical Analysis: A Mathematical Introduction, Chapters 4 and 6. Clarendon Press, Oxford. ISBN 0-19-850279-6.

In music, interpolation is an abrupt change of elements, with (almost immediate) continuation of the first idea.