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}
Bibliography
1. P. Moin, "Fundamentals of Engineering Numerical Analysis," Cambridge University Press, 2nd ed., 2011
page revision: 17, last edited: 19 Dec 2011 19:20