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

How to do linear interpolation

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₁. By inspecting the figure we see that:

$\backslash frac\{y\; -\; y\_0\}\{y\_1\; -\; y\_0\}\; =\; \backslash frac\{x\; -\; x\_0\}\{x\_1\; -\; x\_0\}.\; \backslash ,\backslash !$

Let us write $\backslash alpha$ for the value equal to both sides. This is the interpolation coefficient—the proportion of the distance from x₀ to x₁ you have traversed at the point when you encounter x. Since you know the required value of x, you can find $\backslash alpha$ from the formula

$\backslash alpha\; =\; \backslash frac\{x-x\_0\}\{x\_1-x\_0\}.\; \backslash ,\backslash !$

But it is also true that

$\backslash alpha\; =\; \backslash frac\{y-y\_0\}\{y\_1-y\_0\}\; \backslash ,\backslash !$

which can be manipulated algebraically into either the form:

$y\; =\; (1\; -\; \backslash alpha)\; y\_0\; +\; \backslash alpha\; y\_1\; \backslash ,\backslash !$

or if you prefer:

$y\; =\; y\_0\; +\; \backslash alpha\; (y\_1-y\_0)\backslash ,\backslash !$

from which you can find y directly using your computed value of $\backslash alpha$. This formula is in fact valid even when x is not between x₀ and x₁, although $\backslash alpha$ will then not be between 0 and 1 and therefore cannot be said to be a "proportion" in the usual sense of the word. In this case the method is called linear extrapolation—see extrapolation.

When y is known and x must be found, the procedure is identical with x and y interchanged.

Linear interpolation as approximation

Linear interpolation is often used to approximate a value of some function f using two known values of that function at other points. The error of this approximation is defined as

$R\_T\; =\; f(x)\; -\; p(x)\; \backslash ,\backslash !$

where p denotes the linear interpolation polynomial defined above

$p(x)\; =\; f(x\_0)\; +\; \backslash frac\{f(x\_1)-f(x\_0)\}\{x\_1-x\_0\}(x-x\_0).\; \backslash ,\backslash !$

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

$|R\_T|\; \backslash leq\; \backslash frac\{(x\_1-x\_0)^2\}\{8\}\; \backslash max\_\{x\_0\; \backslash leq\; x\; \backslash leq\; x\_1\}\; |f\text{'}\text{'}(x)|.\; \backslash ,\backslash !$

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 operation of linear interpolation between two values is so commonly used in computer graphics that it is sometimes called a lerp in the jargon of computer graphics. The term can be used as a verb or noun for the operation. e.g. "Bresenham's algorithm lerps incrementally between the two endpoints of the line."

Lerp operations are built into the hardware of all modern computer graphics processors. They are often used as building blocks for more complex operations: for example, a bilinear interpolation can be accomplished in three lerps. Because this operation is cheap, it's also a good way to implement accurate lookup tables with quick lookup for smooth functions without having too many table entries.

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 functions of three variables. Other extensions of linear interpolation can be applied to other kinds of mesh such as triangular and tetrahedral meshes.

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.

See also

• bilinear interpolation
• de Casteljau's algorithm

External links

• Equations of the Straight Line at cut-the-knot
• Lagrange Polynomials and Interpolation at cut-the-knot

Interpolation

Interpolation linéaire | Metodo dell'interpolazione lineare