Editing Linear interpolation

{{short description|Method of curve fitting to construct new data points within the range of known data points}}

[[Image:LinearInterpolation.svg|thumb|right|300px|Given the two red points, the blue line is the linear interpolant between the points, and the value {{mvar|y}} at {{mvar|x}} may be found by linear interpolation.]]
In mathematics, '''linear interpolation''' is a method of [[curve fitting]] using [[linear polynomial]]s to construct new data points within the range of a discrete set of known data points.

==Linear interpolation between two known points==
[[Image:Linear interpolation visualisation.svg|thumb|In this geometric visualisation, the value at the green circle multiplied by the horizontal distance between the red and blue circles is equal to the sum of the value at the red circle multiplied by the horizontal distance between the green and blue circles, and the value at the blue circle multiplied by the horizontal distance between the green and red circles.]]
If the two known points are given by the coordinates <math>(x_0,y_0)</math> and {{nowrap|<math>(x_1,y_1)</math>,}} the '''linear interpolant''' is the straight line between these points. For a value <math>x</math> in the interval {{nowrap|<math>(x_0, x_1)</math>,}} the value <math>y</math> along the straight line is given from the equation of slopes 
<math display="block">\frac{y - y_0}{x - x_0} = \frac{y_1 - y_0}{x_1 - x_0},</math>
which can be derived geometrically from the figure on the right. It is a special case of [[Polynomial interpolation#Constructing the interpolation polynomial|polynomial interpolation]] with {{nowrap|<math>n = 1</math>.}}

Solving this equation for <math>y</math>, which is the unknown value at <math>x</math>, gives
<math display="block">\begin{align} 
y &= y_0 + (x-x_0)\frac{y_1 - y_0}{x_1 - x_0} \\
&= \frac{y_0(x_1-x_0)}{x_1-x_0} + \frac{y_1(x - x_0)-y_0(x - x_0)}{x_1 - x_0}\\
&= \frac{y_1x - y_1x_0-y_0x + y_0x_0 + y_0x_1-y_0x_0}{x_1 - x_0} \\
&= \frac{y_0(x_1 - x)+y_1(x - x_0)}{x_1 - x_0},
\end{align}
</math>
which is the formula for linear interpolation in the interval {{nowrap|<math>(x_0,x_1)</math>.}} 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 <math display="inline">1 - (x-x_0)/(x_1-x_0)</math> and <math display="inline">1 - (x_1-x)/(x_1-x_0)</math>, which are normalized distances between the unknown point and each of the end points. Because these sum to 1, 
<math display="block">\begin{align}
y &= y_0 \left(1 - \frac{x - x_0}{x_1 - x_0}\right) + y_1 \left(1 - \frac{x_1 - x}{x_1 - x_0}\right) \\
  &= y_0 \left(1 - \frac{x - x_0}{x_1 - x_0}\right) + y_1 \left(\frac{x - x_0}{x_1 - x_0}\right) \\
  &= y_0 \left(\frac{x_1 - x}{x_1 - x_0}\right) + y_1 \left(\frac{x - x_0}{x_1 - x_0}\right)
\end{align}</math>
yielding the formula for linear interpolation given above.

==Interpolation of a data set==
[[Image:Interpolation example linear.svg|thumb|right|300px|Linear interpolation on a data set (red points) consists of pieces of linear interpolants (blue lines).]] 
Linear interpolation on a set of data points {{math|(''x''<sub>0</sub>, ''y''<sub>0</sub>), (''x''<sub>1</sub>, ''y''<sub>1</sub>), ..., (''x''<sub>n</sub>, ''y''<sub>n</sub>)}} is defined as [[piecewise linear curve|piecewise linear]], resulting from the concatenation of [[linear segment]] interpolants between each pair of data points. This results in a [[Continuous function|continuous curve]], with a discontinuous derivative (in general), thus of [[differentiability class]] {{nowrap|<math>C^0</math>.}}

==Linear interpolation as an approximation==

Linear interpolation is often used to approximate a value of some [[Function (mathematics)|function]] {{mvar|f}} using two known values of that function at other points. The ''error'' of this approximation is defined as
<math display="block">R_T = f(x) - p(x),</math>
where {{mvar|p}} denotes the linear interpolation [[polynomial]] defined above:
<math display="block">p(x) = f(x_0) + \frac{f(x_1) - f(x_0)}{x_1 - x_0}(x - x_0).</math>

It can be proven using [[Rolle's theorem]] that if {{mvar|f}} has a continuous second derivative, then the error is bounded by
<math display="block">|R_T| \leq \frac{(x_1 - x_0)^2}{8} \max_{x_0 \leq x \leq x_1} \left|f''(x)\right|.</math>

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]] (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 ancient [[Chinese mathematics|Chinese mathematical]] text called ''[[The Nine Chapters on the Mathematical Art]]'' ({{lang|zh|九章算術}}),<ref name="Needham1959">{{cite book|author=Joseph Needham|title=Science and Civilisation in China: Volume 3, Mathematics and the Sciences of the Heavens and the Earth|url=https://books.google.com/books?id=jfQ9E0u4pLAC&pg=PA147|date=1 January 1959|  publisher=Cambridge University Press| isbn=978-0-521-05801-8| pages=147–}}</ref> dated from 200 BC to AD 100 and the ''[[Almagest]]'' (2nd century AD) by [[Ptolemy]].

The basic operation of linear interpolation between two values is commonly used in [[computer graphics]]. In that field's jargon it is sometimes called a '''lerp''' (from '''l'''inear int'''erp'''olation). 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 table]]s with quick lookup for [[smooth function]]s without having too many table entries.

==Extensions==
{{comparison of 1D and 2D interpolation.svg|250px|linear and bilinear interpolation}}

===Accuracy===

If a [[differentiability class|{{math|''C''<sup>0</sup>}}]] function is insufficient, for example if the process that has produced the data points is known to be smoother than {{math|''C''<sup>0</sup>}}, it is common to replace linear interpolation with [[spline interpolation]] or, in some cases, [[polynomial interpolation]].

===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]]. Notice, though, that these interpolants are no longer [[linear functions]] of the spatial coordinates, rather products of linear functions; this is illustrated by the clearly non-linear example of [[bilinear interpolation]] in the figure below. Other extensions of linear interpolation can be applied to other kinds of [[polygon mesh|mesh]] such as triangular and tetrahedral meshes, including [[Bézier surface]]s. These may be defined as indeed higher-dimensional [[piecewise linear function|piecewise linear functions]] (see second figure below).

[[Image:Bilininterp.png|right|thumb|Example of [[bilinear interpolation]] on the unit square with the {{mvar|z}} values 0, 1, 1, and 0.5 as indicated. Interpolated values in between are represented by colour.]]
[[Image:Piecewise linear function2D.svg|right|thumbnail|A piecewise linear function in two dimensions (top) and the convex polytopes on which it is linear (bottom)]]

==Programming language support==
Many libraries and [[shading language]]s have a "lerp" helper-function (in [[GLSL]] known instead as '''mix'''), returning an interpolation between two inputs <code>(v0, v1)</code> for a parameter <code>t</code> in the closed unit interval [0, 1]. Signatures between lerp functions are variously implemented in both the forms <code>(v0, v1, t)</code> and <code>(t, v0, v1)</code>.
<syntaxhighlight lang="c" line>
// 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) {
  return v0 + t * (v1 - v0);
}

// 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) {
  return (1 - t) * v0 + t * v1;
}
</syntaxhighlight>
This lerp function is commonly used for [[alpha blending]] (the parameter "{{var|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]]
* [[Spline interpolation]]
* [[Polynomial interpolation]]
* [[de Casteljau's algorithm]]
* [[First-order hold]]
* [[Bézier curve]]

==References==
{{Reflist}}
{{refbegin}}
* {{Citation | last1=Meijering | first1=Erik | title=A chronology of interpolation: from ancient astronomy to modern signal and image processing | doi=10.1109/5.993400 | year=2002 | journal=Proceedings of the IEEE | volume=90 | issue=3 | pages=319–342| url=http://infoscience.epfl.ch/record/63085 }}.
{{refend}}

==External links==

* [http://www.cut-the-knot.org/Curriculum/Calculus/StraightLine.shtml Equations of the Straight Line] at [[cut-the-knot]]
* [http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2019/p0811r3.html Well-behaved interpolation for numbers and pointers]
* {{springer|title=Linear interpolation|id=p/l059330}}
* {{springer|title=Finite-increments formula|id=p/f040300}}
* [https://www.youtube.com/watch?v=LSNQuFEDOyQ Lerp smoothing is broken - a journey of decay and delta time]


{{DEFAULTSORT:Linear Interpolation}}
[[Category:Interpolation]]

[[de:Interpolation (Mathematik)#Lineare Interpolation]]