Encyclopedia > Linear interpolation

  Article Content

Linear interpolation

Linear interpolation is a process employed in linear algebra, and numerous applications thereof including computer graphics and numerical analysis.

How to do linear interpolation

You know the coordinates <math>(x_0,y_0)</math> and <math>(x_1, y_1)</math>. You want to pick points on this line by knowing either an x or y in the interval <math>(x_0...x_1, y_0...y_1)</math>. For example you want to increase x by a constant factor from <math>x_0</math> up to <math>x_1</math> and get the corresponding y values. By inspecting the figure we see that:

<math>\frac{y - y_0}{y_1 - y_0} = \frac{x - x_0}{x_1 - x_0}.</math>

By manipulating this algebraically, and writing

<math>\alpha = \frac{x-x_0}{x_1-x_0}</math>

you get:

<math>y = (1 - \alpha) y_0 + \alpha y_1 </math>

or if you prefer:

<math>y = y_0 + \frac{y_1-y_0}{x_1-x_0}(x-x_0)</math>

The same formula can easily be derived for x when y is known.

Linear Interpolation as Approximation

In numerical analysis a linear interpolation of certain points that are in reality values of some function <math>f</math> is typically used to approximate the function <math>f</math>. In this case the <math>y</math> in the formulas above is substituted for the linear interpolation polynomial of degree one, <math>p(x)</math> over the two known function values <math>f(x_0)</math> and <math>f(x_1)</math> thusly:

<math>p(x) = f(x_0) + \frac{f(x_1)-f(x_0)}{x_1-x_0}(x-x_0)</math>

The truncation error of this approximation is defined as

<math>R_T = f(x) - p(x)</math>

and this error can for a function with 2 continuous derivatives be proven to be:

<math>|R_T| \leq \frac{(x_1-x_0)^2}{8} \max_{x_0 \leq x \leq x_1} |f(x)|</math>

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. The proof for this error can be performed using Rolle's theorem.

Other Uses of Linear Interpolation

The basic linear interpolation operation is so commonly used in computer graphics that it is known as a lerp[?]. Lerp operations are built into the hardware of all modern computer graphics processors.

In more demanding approximation you will typically use polynomial interpolation see:

Linear interpolatiom can also be extended to Bilinear interpolation[?], for example to interpolate a function z(x, y) where z can be written in terms of an α factor for the x-direction and a β factor for the y-direction. Bilinear interpolation is often used as a crude anti-aliasing filter.



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
Bullying

...   Contents TyrantRedirected from Bullying Tyrant is a term for someone with absolute governmental power, from the Greek language turannos. In Classical ...

 
 
 
This page was created in 25.6 ms