Explanation of Lagrange Interpolating Polynomial Can anybody explain to me what Lagrange Interpolating Polynomial is with examples? I know the formula but it doesn't seem intuitive to me. 
 A: 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)$ and $(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.
A: 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.
