# Linear interpolation

**Linear interpolation**is a method ofcurve fitting using linear polynomials. It is heavily employed inmathematics (particularlynumerical analysis ), and numerous applications includingcomputer graphics . It is a simple form ofinterpolation .**Lerp**is a quasi-acronym for "linear interpolation", which can also be used as a verb harv|Raymond|2003.**Linear interpolation between two known points**If the two known points are given by the coordinates $scriptstyle(x\_0,y\_0)$ and $scriptstyle(x\_1,y\_1)$, the

**linear interpolant**is the straight line between these points. For a value "x" in the interval $scriptstyle(x\_0,\; x\_1)$, the value "y" along the straight line is given from the equation:$frac\{y\; -\; y\_0\}\{y\_1\; -\; y\_0\}\; =\; frac\{x\; -\; x\_0\}\{x\_1\; -\; x\_0\}$

which can be derived geometrically from the figure on the right.

Solving this equation for "y", which is the unknown value at "x", gives

:$y\; =\; y\_0\; +\; (x-x\_0)frac\{y\_1\; -\; y\_0\}\{x\_1-x\_0\}$

which is the formula for linear interpolation in the interval $scriptstyle(x\_0,x\_1)$. Outside this interval, the formula is identical to

linear extrapolation .**Interpolation of a data set**Linear interpolation on a set of data points $scriptstyle(x\_0,\; y\_0),,\; (x\_1,\; y\_1),,dots,,(x\_n,\; y\_n)$ is defined as the concatenation of linear interpolants between each pair of data points. This results in a continuous curve, with a discontinuous derivative, thus of

differentiability class $C^0$.**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)\; ,!$

where "p" denotes the linear interpolation

polynomial defined above:$p(x)\; =\; f(x\_0)\; +\; frac\{f(x\_1)-f(x\_0)\}\{x\_1-x\_0\}(x-x\_0).\; ,!$

It can be proven using

Rolle's theorem that if "f" has a continuous second derivative, the error is bounded by:$|R\_T|\; leq\; frac\{(x\_1-x\_0)^2\}\{8\}\; max\_\{x\_0\; leq\; x\; leq\; x\_1\}\; |f"(x)|.\; ,!$

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 that field's jargon. The term can be used as averb ornoun 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 two lerps. Because this operation is cheap, it's also a good way to implement accuratelookup table s with quick lookup forsmooth function s without having too many table entries.**Extensions****Accuracy**If a "C

^{0}" function is insufficient, for example if the process that has produced the data points is known be smoother than "C^{0}", it is common to replace linear interpolation withspline interpolation , or evenpolynomial interpolation in some cases.**Multivariate**Linear interpolation as described here is for data points in one spatial dimension. For two spatial dimensions, the extension of linear interpolation is called

bilinear interpolation , and in three dimensions,trilinear interpolation . Other extensions of linear interpolation can be applied to other kinds of mesh such as triangular and tetrahedral meshes.**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 by Babylonian astronomers and mathematicians in Seleucid

Mesopotamia (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) byPtolemy .**References***.

*.**ee also***

Bilinear interpolation

*de Casteljau's algorithm **External links*** [

*http://www.cut-the-knot.org/Curriculum/Calculus/StraightLine.shtml Equations of the Straight Line*] atcut-the-knot

*Wikimedia Foundation.
2010.*

### Look at other dictionaries:

**linear interpolation**— tiesinė interpoliacija statusas T sritis fizika atitikmenys: angl. linear interpolation vok. lineare Interpolation, f rus. линейная интерполяция, f pranc. interpolation linéaire, f … Fizikos terminų žodynas**linear interpolation**— A technique used in discounted cash flow for calculating the approximate internal rate of return of a project. The cash flows for the project are discounted at two discount rates to obtain a small positive and a small negative net present value.… … Accounting dictionary**linear interpolation**— noun Date: 1965 estimation of a function (as a logarithm) by assuming that it is a straight line between known values … New Collegiate Dictionary**linear interpolation method**— tiesinės interpoliacijos metodas statusas T sritis fizika atitikmenys: angl. linear interpolation method; method of proportional parts vok. lineare Interpolationsmethode, f rus. метод линейной интерполяции, m pranc. méthode d’interpolation… … Fizikos terminų žodynas**Interpolation search**— is an algorithm for searching for a given key value in an indexed array that has been ordered by the values of the key. It parallels how humans search through a telephone book for a particular name, the key value by which the book s entries are… … Wikipedia**Interpolation**— 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… … Wikipedia**Linear**— The word linear comes from the Latin word linearis , which means created by lines .In advanced mathematics, a linear map or function f ( x ) is a function which satisfies the following two properties:* Additivity (also called the superposition… … Wikipedia**Interpolation**— A method of estimating an unknown price or yield of a security. This is achieved by using other related known values that are located in sequence with the unknown value. Interpolation is most often used in situations where a table of values is… … Investment dictionary**interpolation linéaire**— tiesinė interpoliacija statusas T sritis fizika atitikmenys: angl. linear interpolation vok. lineare Interpolation, f rus. линейная интерполяция, f pranc. interpolation linéaire, f … Fizikos terminų žodynas**Linear programming**— (LP, or linear optimization) is a mathematical method for determining a way to achieve the best outcome (such as maximum profit or lowest cost) in a given mathematical model for some list of requirements represented as linear relationships.… … Wikipedia