In mathematics, linear interpolation is a method of
curve fitting
Curve fitting is the process of constructing a curve, or mathematical function, that has the best fit to a series of data points, possibly subject to constraints. Curve fitting can involve either interpolation, where an exact fit to the data is ...
using
linear polynomial
In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An exampl ...
s to construct new data points within the range of a discrete set of known data points.
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 in the interval
, the value along the straight line is given from the equation of slopes
which can be derived geometrically from the figure on the right. It is a special case of
polynomial interpolation
In numerical analysis, polynomial interpolation is the interpolation of a given data set by the polynomial of lowest possible degree that passes through the points of the dataset.
Given a set of data points (x_0,y_0), \ldots, (x_n,y_n), with no ...
with .
Solving this equation for , which is the unknown value at , gives
which is the formula for linear interpolation in the interval
. Outside this interval, the formula is identical to
linear extrapolation.
This formula can also be understood as a weighted average. The weights are inversely related to the distance from the end points to the unknown point; the closer point has more influence than the farther point. Thus, the weights are
and
, which are normalized distances between the unknown point and each of the end points. Because these sum to 1,
yielding the formula for linear interpolation given above.
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, with a discontinuous derivative (in general), thus of
differentiability class
In mathematical analysis, the smoothness of a function is a property measured by the number of continuous derivatives it has over some domain, called ''differentiability class''. At the very minimum, a function could be considered smooth if ...
Linear interpolation as approximation
Linear interpolation is often used to approximate a value of some
function
Function or functionality may refer to:
Computing
* Function key, a type of key on computer keyboards
* Function model, a structured representation of processes in a system
* Function object or functor or functionoid, a concept of object-oriente ...
using two known values of that function at other points. The ''error'' of this approximation is defined as
where denotes the linear interpolation
polynomial
In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An exa ...
defined above:
:
It can be proven using
Rolle's theorem that if has a continuous second derivative, then the error is bounded by
That is, 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 the approximations made with simple linear interpolation become.
History and applications
Linear interpolation has been used since antiquity for filling the gaps in tables. Suppose that one has a table listing the population of some country in 1970, 1980, 1990 and 2000, and that one wanted to estimate the population in 1994. Linear interpolation is an easy way to do this. It is believed that it was used in the
Seleucid Empire
The Seleucid Empire (; grc, Βασιλεία τῶν Σελευκιδῶν, ''Basileía tōn Seleukidōn'') was a Greek state in West Asia that existed during the Hellenistic period from 312 BC to 63 BC. The Seleucid Empire was founded by the ...
(last three centuries BC) and by the Greek astronomer and mathematician
Hipparchus
Hipparchus (; el, Ἵππαρχος, ''Hipparkhos''; BC) was a Greek astronomer, geographer, and mathematician. He is considered the founder of trigonometry, but is most famous for his incidental discovery of the precession of the equi ...
(second century BC). A description of linear interpolation can be found in the ancient
Chinese mathematical text called ''
The Nine Chapters on the Mathematical Art
''The Nine Chapters on the Mathematical Art'' () is a Chinese mathematics book, composed by several generations of scholars from the 10th–2nd century BCE, its latest stage being from the 2nd century CE. This book is one of the earliest sur ...
'' (九章算術),
dated from 200 BC to AD 100 and the ''
Almagest
The ''Almagest'' is a 2nd-century Greek-language mathematical and astronomical treatise on the apparent motions of the stars and planetary paths, written by Claudius Ptolemy ( ). One of the most influential scientific texts in history, it canoni ...
'' (2nd century AD) by
Ptolemy
Claudius Ptolemy (; grc-gre, Πτολεμαῖος, ; la, Claudius Ptolemaeus; AD) was a mathematician, astronomer, astrologer, geographer, and music theorist, who wrote about a dozen scientific treatises, three of which were of importanc ...
.
The basic operation of linear interpolation between two values is commonly used in
computer graphics
Computer graphics deals with generating images with the aid of computers. Today, computer graphics is a core technology in digital photography, film, video games, cell phone and computer displays, and many specialized applications. A great de ...
. In that field's jargon it is sometimes called a lerp (from linear interpolation). The term can be used as a
verb
A verb () is a word (part of speech) that in syntax generally conveys an action (''bring'', ''read'', ''walk'', ''run'', ''learn''), an occurrence (''happen'', ''become''), or a state of being (''be'', ''exist'', ''stand''). In the usual descri ...
or
noun
A noun () is a word that generally functions as the name of a specific object or set of objects, such as living creatures, places, actions, qualities, states of existence, or ideas.Example nouns for:
* Living creatures (including people, alive, d ...
for the operation. e.g. "
Bresenham's algorithm
Bresenham's line algorithm is a line drawing algorithm that determines the points of an ''n''-dimensional raster graphics, raster that should be selected in order to form a close approximation to a straight line between two points. It is commonly u ...
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
In mathematics, bilinear interpolation is a method for interpolating functions of two variables (e.g., ''x'' and ''y'') using repeated linear interpolation. It is usually applied to functions sampled on a 2D rectilinear grid, though it can be ...
can be accomplished in three lerps. Because this operation is cheap, it's also a good way to implement accurate
lookup table
In computer science, a lookup table (LUT) is an array that replaces runtime computation with a simpler array indexing operation. The process is termed as "direct addressing" and LUTs differ from hash tables in a way that, to retrieve a value v wi ...
s with quick lookup for
smooth function
In mathematical analysis, the smoothness of a function (mathematics), function is a property measured by the number of Continuous function, continuous Derivative (mathematics), derivatives it has over some domain, called ''differentiability cl ...
s without having too many table entries.
Extensions
Accuracy
If a
function is insufficient, for example if the process that has produced the data points is known to be smoother than , it is common to replace linear interpolation with
spline interpolation
In the mathematical field of numerical analysis, spline interpolation is a form of interpolation where the interpolant is a special type of piecewise polynomial called a spline. That is, instead of fitting a single, high-degree polynomial to all ...
or, in some cases,
polynomial interpolation
In numerical analysis, polynomial interpolation is the interpolation of a given data set by the polynomial of lowest possible degree that passes through the points of the dataset.
Given a set of data points (x_0,y_0), \ldots, (x_n,y_n), with no ...
.
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
In mathematics, bilinear interpolation is a method for interpolating functions of two variables (e.g., ''x'' and ''y'') using repeated linear interpolation. It is usually applied to functions sampled on a 2D rectilinear grid, though it can be ...
, and in three dimensions,
trilinear interpolation
Trilinear interpolation is a method of multivariate interpolation on a 3-dimensional regular grid. It approximates the value of a function at an intermediate point (x, y, z) within the local axial rectangular prism linearly, using function data ...
. Notice, though, that these interpolants are no longer
linear functions
Linearity is the property of a mathematical relationship ('' function'') that can be graphically represented as a straight line. Linearity is closely related to '' proportionality''. Examples in physics include rectilinear motion, the linear ...
of the spatial coordinates, rather products of linear functions; this is illustrated by the clearly non-linear example of
bilinear interpolation
In mathematics, bilinear interpolation is a method for interpolating functions of two variables (e.g., ''x'' and ''y'') using repeated linear interpolation. It is usually applied to functions sampled on a 2D rectilinear grid, though it can be ...
in the figure below. Other extensions of linear interpolation can be applied to other kinds of
mesh
A mesh is a barrier made of connected strands of metal, fiber, or other flexible or ductile materials. A mesh is similar to a web or a net in that it has many attached or woven strands.
Types
* A plastic mesh may be extruded, oriented, ex ...
such as triangular and tetrahedral meshes, including
Bézier surface
Bézier surfaces are a species of mathematical spline used in computer graphics, computer-aided design, and finite element modeling.
As with Bézier curves, a Bézier surface is defined by a set of control points. Similar to interpolation in man ...
s. These may be defined as indeed higher-dimensional
piecewise linear function (see second figure below).
Programming language support
Many libraries and
shading language
A shading language is a graphics programming language adapted to programming shader effects (characterizing surfaces, volumes, and objects). Such language forms usually consist of special data types, like "vector", "matrix", "color" and " normal". ...
s have a "lerp" helper-function (in
GLSL
OpenGL Shading Language (GLSL) is a high-level shading language with a syntax based on the C programming language. It was created by the OpenGL ARB (OpenGL Architecture Review Board) to give developers more direct control of the graphics pipelin ...
known instead as mix), returning an interpolation between two inputs (v0, v1) for a parameter (t) in the closed unit interval
, 1 Signatures between lerp functions are variously implemented in both the forms (v0, v1, t) and (t, v0, v1).
// Imprecise method, which does not guarantee v = v1 when t = 1, due to floating-point arithmetic error.
// This method is monotonic. This form may be used when the hardware has a native fused multiply-add instruction.
float lerp(float v0, float v1, float t)
// Precise method, which guarantees v = v1 when t = 1. This method is monotonic only when v0 * v1 < 0.
// Lerping between same values might not produce the same value
float lerp(float v0, float v1, float t)
This lerp function is commonly used for
alpha blending
In computer graphics, alpha compositing or alpha blending is the process of combining one image with a background to create the appearance of partial or full transparency. It is often useful to render picture elements (pixels) in separate pas ...
(the parameter "t" is the "alpha value"), and the formula may be extended to blend multiple components of a vector (such as spatial ''x'', ''y'', ''z'' axes or ''r'', ''g'', ''b'' colour components) in parallel.
See also
*
Bilinear interpolation
In mathematics, bilinear interpolation is a method for interpolating functions of two variables (e.g., ''x'' and ''y'') using repeated linear interpolation. It is usually applied to functions sampled on a 2D rectilinear grid, though it can be ...
*
Spline interpolation
In the mathematical field of numerical analysis, spline interpolation is a form of interpolation where the interpolant is a special type of piecewise polynomial called a spline. That is, instead of fitting a single, high-degree polynomial to all ...
*
Polynomial interpolation
In numerical analysis, polynomial interpolation is the interpolation of a given data set by the polynomial of lowest possible degree that passes through the points of the dataset.
Given a set of data points (x_0,y_0), \ldots, (x_n,y_n), with no ...
*
de Casteljau's algorithm In the mathematical field of numerical analysis, De Casteljau's algorithm is a recursive method to evaluate polynomials in Bernstein form or Bézier curves, named after its inventor Paul de Casteljau. De Casteljau's algorithm can also be used to ...
*
First-order hold First-order hold (FOH) is a mathematical model of the practical reconstruction of sampled signals that could be done by a conventional digital-to-analog converter (DAC) and an analog circuit called an integrator. For FOH, the signal is reconstruct ...
*
Bézier curve
A Bézier curve ( ) is a parametric curve used in computer graphics and related fields. A set of discrete "control points" defines a smooth, continuous curve by means of a formula. Usually the curve is intended to approximate a real-world shape t ...
References
* .
External links
Equations of the Straight Lineat
cut-the-knot
Alexander Bogomolny (January 4, 1948 July 7, 2018) was a Soviet-born Israeli-American mathematician. He was Professor Emeritus of Mathematics at the University of Iowa, and formerly research fellow at the Moscow Institute of Electronics and Math ...
Well-behaved interpolation for numbers and pointers*
*
{{DEFAULTSORT:Linear Interpolation
Interpolation
de:Interpolation (Mathematik)#Lineare Interpolation