Lagrange Polynomial Interpolation

Suppose you want to compute the polynomial $P(x)$ of $deg(P) \leqslant n$ which passes through $n+1$ given points:

(1)
\begin{align} \left( {\begin{array}{*{20}{c}} {{x_0}} \\ {P({x_0})} \end{array}} \right),\left( {\begin{array}{*{20}{c}} {{x_1}} \\ {P({x_1})} \end{array}} \right),...,\left( {\begin{array}{*{20}{c}} {{x_n}} \\ {P({x_n})} \end{array}} \right) \end{align}

The appropriate Lagrange polynomial is:

(2)
\begin{gathered} P(x) = \sum\limits_{j = 0}^n {\left[ {\left( {\prod\limits_{k = 0,k \ne j}^n {\frac{{x - {x_k}}}{{{x_j} - {x_k}}}} } \right)P({x_j})} \right]} = \\ \,\,\,\,\,\,\,\,\,\,\,\, = \frac{{(x - {x_1})(x - {x_2}) \cdot \cdot \cdot (x - {x_n})}}{{({x_0} - {x_1})({x_0} - {x_2}) \cdot \cdot \cdot ({x_0} - {x_n})}}P({x_0}) + \frac{{(x - {x_0})(x - {x_2}) \cdot \cdot \cdot (x - {x_n})}}{{({x_1} - {x_0})({x_1} - {x_2}) \cdot \cdot \cdot ({x_1} - {x_n})}}P({x_1}) + ... \\ \,\,\,\,\,\,\,\,\,\,\,\, + \frac{{(x - {x_0})(x - {x_1}) \cdot \cdot \cdot (x - {x_{n - 1}})}}{{({x_n} - {x_0})({x_n} - {x_1}) \cdot \cdot \cdot ({x_n} - {x_{n - 1}})}}P({x_n}) \\ \end{gathered}

## Idea

We would like to write the polynomial as weighted sum of the values $P(x_j)$:

(3)
\begin{align} P(x) = \sum\limits_{j = 0}^n {{w_j(x)}P(x_j)} \end{align}

To pass through all the given points, the weight should be:

(4)
\begin{align} {w_j}(x) = \left\{ \begin{gathered} 0,if\,\,x = {x_i};i \ne j \\ 1,if\,\,x = {x_j} \\ anything,otherwise \\ \end{gathered} \right. \end{align}

Now, we have to find such polynomials $w_j(x)$.

The polynomial that has zeros at all $x_i, i=0,...,n$ points except the point $x_j$ can be written as:

(5)
\begin{align} \frac{\alpha_j(x-x_0)(x-x_1)\cdot \cdot \cdot (x-x_n)}{x-x_j} \end{align}

We would like to get 1 at the points $x_j$, but this polynomial at $x_j$ equals:

(6)
\begin{align} {\alpha _j}\prod\limits_{k = 0,k \ne j}^n {({x_j} - {x_k})} =1 \end{align}

From this equation, $\alpha_j$ can be computed.

Bibliography

1. P. Moin, "Fundamentals of Engineering Numerical Analysis," Cambridge University Press, 2nd ed., 2011