Linear interpolation

Sponsor with the world's largest charity for orphans

Linear interpolation is a process employed in mathematics, and numerous applications thereof including computer graphics. It is a very simple form of interpolation.

Table of contents

1 How to do linear interpolation
2 Linear interpolation as approximation
3 Applications
4 History
5 Extensions
6 References

How to do linear interpolation

Image:Linear_interpolation.png

You know the coordinates (x₀, y₀) and (x₁, y₁). You want to pick points on this line with a given x in the interval [x₀, x₁]. By inspecting the figure we see that:

By manipulating this algebraically, and writing

for the slope, you get:

or if you prefer:

A similar formula can easily be derived for x when y is known.

Linear interpolation as approximation

In numerical analysis a linear interpolation of certain points that are in reality values of some function f is typically used to approximate the function f. The error of this approximation is defined as

where p denotes the linear interpolation polynomial defined above

It can be proven using Rolle's theorem that if f has two continuous derivatives, the error is bounded by

As you see, the approximation between two points on a given function gets worse with the second derivative of the function that is approximated. This is intuitively correct as well: the "curvier" the function is, the worse is the approximations made with simple linear interpolation.

Applications

Linear interpolation is often used to fill the gaps in a table. Suppose you have a table listing the population of some country in 1970, 1980, 1990 and 2000, and that you want to estimate the population in 1994. Linear interpolation gives you an easy way to do this.

The basic linear interpolation operation is so commonly used in computer graphics that it is known as a lerp. Lerp operations are built into the hardware of all modern computer graphics processors.

History

Linear interpolation has been used since antiquity for filling the gaps in tables, often with astronomical data. It is believed that it was used in the Seleucid Empire (last three centuries BC) and by the Greek astronomer and mathematician Hipparchus (second century BC). A description of linear interpolation can be found in the Almagest (second century AD) of Ptolemy.

Extensions

In demanding situations, linear interpolation is often not accurate enough. In that case, it can be replaced by polynomial interpolation or spline interpolation.

Linear interpolation can also be extended to bilinear interpolation for interpolating functions of two variables. Bilinear interpolation is often used as a crude anti-aliasing filter. Similarly, trilinear interpolation is used to interpolate function of three variables

References

E. Meijering (2002). A Chronology of Interpolation. From Ancient Astronomy to Modern Signal and Image Processing. Proceedings of the IEEE 9 (3), 319–342.