All Topics  
Linear interpolation

 

 
   Email Print
   Bookmark   Link
 

 

Linear interpolation
 
 
  Topics Linear interpolation Topic Home

Linear interpolation is a method of curve fitting
Curve fitting

Curve fitting is finding a curve which has the best fit to a series of data points and possibly other constraints. This section is an introduction to both interpolation and regression analysis....
 using linear polynomials. It is heavily employed in mathematics
Mathematics

Mathematics is the study of quantity, structure, space, change, and related topics of pattern and form. Mathematicians seek out patterns whether found in numbers, space, natural science, computers, imaginary abstractions, or elsewhere....
 (particularly numerical analysis
Numerical analysis

Numerical analysis is the study of algorithms for the problems of continuous mathematics .One of the earliest mathematical writings is the Babylonian tablet YBC 7289, which gives a sexagesimal numerical approximation of , the length of the diagonal in a unit square....
), and numerous applications including computer graphics
Computer graphics

Computer graphics are graphics created by computers and, more generally, the representation and manipulation of pictorial data by a computer....
. It is a simple form of interpolation
Interpolation

In the mathematics subfield of numerical analysis, interpolation is a method of constructing new data points within the range of a discrete set of known data points....
.

Lerp is a quasi-acronym for linear interpolation, which can also be used as a verb .

he two known points are given by the coordinates and , the linear interpolant is the straight line between these points.






Discussion
Ask a question about 'Linear interpolation'
Start a new discussion about 'Linear interpolation'
Answer questions from other users
Full Discussion Forum



Encyclopedia


Linear interpolation is a method of curve fitting
Curve fitting

Curve fitting is finding a curve which has the best fit to a series of data points and possibly other constraints. This section is an introduction to both interpolation and regression analysis....
 using linear polynomials. It is heavily employed in mathematics
Mathematics

Mathematics is the study of quantity, structure, space, change, and related topics of pattern and form. Mathematicians seek out patterns whether found in numbers, space, natural science, computers, imaginary abstractions, or elsewhere....
 (particularly numerical analysis
Numerical analysis

Numerical analysis is the study of algorithms for the problems of continuous mathematics .One of the earliest mathematical writings is the Babylonian tablet YBC 7289, which gives a sexagesimal numerical approximation of , the length of the diagonal in a unit square....
), and numerous applications including computer graphics
Computer graphics

Computer graphics are graphics created by computers and, more generally, the representation and manipulation of pictorial data by a computer....
. It is a simple form of interpolation
Interpolation

In the mathematics subfield of numerical analysis, interpolation is a method of constructing new data points within the range of a discrete set of known data points....
.

Lerp is a quasi-acronym for linear interpolation, which can also be used as a verb .

Linear interpolation between two known points

If the two known points are given by the coordinates and , the linear interpolant is the straight line between these points. For a value x in the interval , the value y along the straight line is given from the equation

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

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

which is the formula for linear interpolation in the interval . Outside this interval, the formula is identical to linear extrapolation.

Interpolation of a data set

Linear interpolation on a set of data points is defined as the concatenation of linear interpolants between each pair of data points. This results in a continuous curve
Continuous function

In mathematics, a continuous function is a function for which, intuitively, small changes in the input result in small changes in the output. Otherwise, a function is said to be discontinuous....
, with a discontinuous derivative, thus of differentiability class .

Linear interpolation as approximation


Linear interpolation is often used to approximate a value of some function
Function (mathematics)

The mathematical concept of a function expresses dependence between two quantities, one of which is known and the other which is produced. A function associates a single output to each input element drawn from a fixed Set , such as the real numbers , although different inputs may have the same output....
 f using two known values of that function at other points. The error of this approximation is defined as

where p denotes the linear interpolation polynomial
Polynomial

In mathematics, a polynomial is an expression constructed from variables and constants, using the operations of addition, subtraction, multiplication, and constant non-negative whole number exponents....
 defined above

It can be proven using Rolle's theorem
Rolle's theorem

In calculus, a branch of mathematics, Rolle's theorem essentially states that a differentiable function , which attains equal values at two points, must have a stationary point somewhere between them where the slope is zero....
 that if f has a continuous second derivative, 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 operation of linear interpolation between two values is so commonly used in computer graphics
Computer graphics

Computer graphics are graphics created by computers and, more generally, the representation and manipulation of pictorial data by a computer....
 that it is sometimes called a lerp in that field's jargon. The term can be used as a verb
Verb

In syntax, a verb is a word that usually denotes an action , an occurrence , or a state of being . Depending on the language, a verb may vary in form according to many factors, possibly including its grammatical tense, grammatical aspect, grammatical mood and grammatical voice....
 or noun
Noun

In linguistics, a noun is a member of a large, open class lexical category whose members can occur as the main word in the subject of a clause, the object of a verb, or the object of a preposition....
 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
Bilinear interpolation

In mathematics, bilinear interpolation is an extension of linear interpolation for interpolation functions of two variables on a regular grid. The key idea is to perform linear interpolation first in one direction, and then again in the other direction....
 can be accomplished in two lerps. Because this operation is cheap, it's also a good way to implement accurate lookup table
Lookup table

In computer science, a lookup table is a data structure, usually an array or associative array, often used to replace a runtime computation with a simpler array indexing operation....
s with quick lookup for smooth function
Smooth function

In mathematical analysis, a differentiability class is a classification of function according to the properties of their derivatives. Higher order differentiability classes correspond to the existence of more derivatives....
s without having too many table entries.

Extensions


Accuracy


If a C0 function is insufficient, for example if the process that has produced the data points is known be smoother than C0, it is common to replace linear interpolation with spline interpolation
Spline interpolation

In the mathematics field of numerical analysis, spline interpolation is a form of interpolation where the interpolant is a special type of piecewise polynomial called a spline ....
, or even polynomial interpolation
Polynomial interpolation

In the mathematics subfield of numerical analysis, polynomial interpolation is the interpolation of a given data set by a polynomial. In other words, given some data points , the aim is to find a polynomial which goes exactly through these points....
 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
Bilinear interpolation

In mathematics, bilinear interpolation is an extension of linear interpolation for interpolation functions of two variables on a regular grid. The key idea is to perform linear interpolation first in one direction, and then again in the other direction....
, and in three dimensions, trilinear interpolation
Trilinear interpolation

Trilinear interpolation is a method of multivariate interpolation on a Three dimensional space regular grid. It approximates the value of an intermediate point within the local axial rectangular prism linearly, using data on the lattice points....
. Other extensions of linear interpolation can be applied to other kinds of mesh
Polygon mesh

File:Dolphin triangle mesh.pngA polygon mesh or unstructured grid is a collection of vertices, edges and faces that defines the shape of a polyhedron object in 3D computer graphics and solid modeling....
 such as triangular and tetrahedral meshes.

History


Linear interpolation has been used since antiquity for filling the gaps in tables, often with astronomical
Astronomy

Astronomy is the science of Astronomical object and Phenomenon that originate outside the Earth's atmosphere . It is concerned with the evolution, physics, chemistry, meteorology, and motion of celestial objects, as well as the physical cosmology....
 data. It is believed that it was used by Babylonian astronomers and mathematicians
Babylonian mathematics

Babylonian mathematics refers to any mathematics of the peoples of Mesopotamia , from the days of the early Sumerians to the fall of Babylon in 539 BC....
 in Seleucid
Seleucid Empire

The Seleucid Empire /s?'lus?d/ was a Hellenistic empire, i.e. a successor state of Alexander the Great's empire. The Seleucid Empire was centered in the near East and at the height of its power included central Anatolia, the Levant, Mesopotamia, Persia, today's Turkmenistan, Pamir Mountains and parts of Pakistan....
 Mesopotamia
Mesopotamia

Mesopotamia is the area of the Tigris-Euphrates river system, along the Tigris and Euphrates rivers, largely corresponding to modern Iraq, as well as some parts of northeastern Syria, some parts of southeastern Turkey, and some parts of the Khuzestan Province of southwestern Iran....
 (last three centuries BC), and by the Greek astronomer
Greek astronomy

Greek astronomy is the astronomy of those who wrote in the Greek language in classical antiquity i.e. see Aristarchus of Samos Greek astronomer/mathematician and his heliocentric model of the solar system....
 and mathematician
Greek mathematics

Greek mathematics, as that term is used in this article, is the mathematics written in Greek language, developed from the 6th century BC to the 5th century AD around the Eastern shores of the Mediterranean....
, Hipparchus
Hipparchus

Hipparchus, the common Latinization of the Greek Hipparkhos, can mean:* Hipparchus, the ancient Greek astronomer** Hipparchic cycle, an astronomical cycle he created...
 (second century BC). A description of linear interpolation can be found in the Almagest
Almagest

Almagest is the Latin form of the Arabic language name of a mathematical and astronomical treatise proposing the complex motions of the stars and planetary paths, originally written in Greek language as by Ptolemy of Alexandria, Egypt, written in the 2nd century....
 (second century AD) by Ptolemy
Ptolemy

Claudius Ptolemaeus , known in English as Ptolemy , was a Roman Greek mathematics, Greek astronomy, geographer and astrologer. He lived in History of Roman Egypt, and was probably born there in a town in the Thebaid called Ptolemais Hermiou; he died in Alexandria around 168 AD....
.

See also

  • Bilinear interpolation
    Bilinear interpolation

    In mathematics, bilinear interpolation is an extension of linear interpolation for interpolation functions of two variables on a regular grid. The key idea is to perform linear interpolation first in one direction, and then again in the other direction....
  • de Casteljau's algorithm
    De Casteljau's algorithm

    In the mathematics subfield of numerical analysis the de Casteljau's algorithm, named after its inventor Paul de Casteljau, is a Recursion method to evaluate polynomials in Bernstein form or B?zier curves....


External links

  • at cut-the-knot
    Cut-the-knot

    Cut-the-knot is an educational website maintained by Alexander Bogomolny and devoted to popular exposition of a great variety of topics in mathematics....