8
$\begingroup$

Can anybody explain to me what Lagrange Interpolating Polynomial is with examples? I know the formula but it doesn't seem intuitive to me.

$\endgroup$
  • 1
    $\begingroup$ The formula is constructed so that the polynomial necessarily goes through the points specified. Examples. $\endgroup$ – vadim123 Oct 12 '13 at 21:55
21
$\begingroup$

The Lagrange interpolating polynomial is a tool which helps us construct a polynomial which goes through any desired set of points.

Lets say we want a polynomial that goes through the points $(1,3) (3,4) (5,6) (7,-10)$.

First we define the polynomial $P(x)=(x-1)(x-3)(x-5)(x-7)$. This has roots at the x-coordinates of each of the points we want to interpolate. Then we construct the following polynomials from this,

$$f_1(x) = P(x)/(x-1)$$ $$f_2(x) = P(x)/(x-3)$$ $$f_3(x) = P(x)/(x-5)$$ $$f_4(x) = P(x)/(x-7)$$

Notice that in particular $f_1(x)=(x-3)(x-5)(x-7)$. This function has the following property: It is zero at $x=3,5,$ and $7$ and nonzero at $x=1$. This means that it is "on" when we are at the first x-coordinate and "off" at the others. Each of them are designed to work this way.

Now consider the following expression,

$$ L(x) = 3 \frac{f_1(x)}{f_1(1)} + 4 \frac{f_2(x)}{f_2(3)} + 6 \frac{f_3(x)}{f_3(5)} -10 \frac{f_4(x)}{f_4(7)} $$

Notice that this functions goes through all four designated points. When we plug in the desired value of $x$ only one of the four functions $f_j$ is turned on and the others are zero. The coefficients are designed to force the expression to equal the corresponding $y$-coordinates.

In particular consider $L(5)$,

$$ L(5) = 3 \frac{f_1(5)}{f_1(1)} + 4 \frac{f_2(5)}{f_2(3)} + 6 \frac{f_3(5)}{f_3(5)} -10 \frac{f_4(5)}{f_4(7)} $$

$$ L(5) = 0 + 0 + 6 \frac{f_3(5)}{f_3(5)} -0 $$

$$ L(5) = 6 \frac{f_3(5)}{f_3(5)} $$

$$ L(5) = 6 (1) $$

$$ L(5) = 6 $$

So we have the desired point $(5,6)$. Try explicitly writing out the polynomial and plugging in the other points to really see it work.

$\endgroup$
  • $\begingroup$ There is a sort of generalization of this idea in the form a something called a Lagrange mesh basis. These are used to quickly compute eigenfunction expansions and matrix elements in nuclear physics and other disciplines. Check out the following paper if you're interested " onlinelibrary.wiley.com/doi/10.1002/pssb.200541305/abstract " $\endgroup$ – Spencer Oct 12 '13 at 21:58
  • $\begingroup$ Wow! Thanks a lot for the explanation Sir! $\endgroup$ – user87274 Oct 12 '13 at 23:03
  • $\begingroup$ My pleasure, I remember these being really confusing when I was first introduced to them. $\endgroup$ – Spencer Oct 12 '13 at 23:21
  • $\begingroup$ This explanation makes a lot of sense. It's really unfortunate that it's the other answer here that both Wolfram Alpha and Wikipedia have. Wikipedia's at least I can fix. $\endgroup$ – Omnifarious Jun 19 '17 at 20:48
1
$\begingroup$

Linear interpolation consists of approximating a function $f(x)$ as

$$f(x)=\sum_{i=1}^{N}a_i \phi_i(x)\;\;\;\;\;\;\;\;\;\;\;(1)$$

where the $a_i$'s are the interpolation coefficients and the $\phi_i$'s are prefixed interpolation functions.

Lagrange interpolation, which is one of the simplest and mostly employed interpolation methods, consists of finding the interpolation coefficients as the solution of the linear system

$$f(x_j)=\sum_{i=1}^{N}a_i \phi_i(x_j), \;\;\;\;\;\; j=1,\ldots,N\;\;\;\;\;\;\;\;\;\;\;(2)$$

where the $x_j$'s are interpolation points.

A common case is when the interpolation functions are polynonials, say

$$f(x_j)=\sum_{i=1}^{N}\alpha_i x^{i-1}_j, \;\;\;\;\;\; j=1,\ldots,N.\;\;\;\;\;\;\;\;\;\;\;(3)$$

The determinant of such a system is a Vandermonde determinant which is always non-vanishing and therefore the system always admits a unique solution, provided that the interpolation points are all different. Accordingly, polynomial Lagrange interpolation is always unique.

Polynomial interpolation functions in eq. (1) can be found by assuming that $\phi_i(x)$ is a polynomial of degree $N-1$, that $\phi_i(x_j)=0$, $j=1,\ldots,N$ and $j\neq i$, and that $\phi_i(x_i)=1$. Accordingly,

$$\phi_i(x)=\prod_{j\neq i}\frac{x-x_j}{x_i-x_j}\;\;\;\;\;\;\;\;\;\;\;(4)$$

and

$$f(x)=\sum_{i=1}^{N}f(x_i)\prod_{j\neq i}\frac{x-x_j}{x_i-x_j}\;\;\;\;\;\;\;\;\;\;\;(5)$$

Reference: N.S. Bakhvalov, Numerical Methods, Mir Publishers Moscow, 1981.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy