Lagrange Interpolating Polynomial

The Lagrange interpolating polynomial is the Polynomial of degree $n-1$ which passes through the $n$ points $y_1=f(x_1)$, $y_2=f(x_2)$, ..., $y_n=f(x_n)$. It is given by

$$P(x)=\sum_{j=1}^n P_j(x),$$ (1)

where

$$P_j(x) = \prod_{\scriptstyle k=1 \atop \scriptstyle k\not = j}^n {x-x_k\over x_j-x_k}y_j.$$ (2)

Written explicitly,

$$P(x) = {(x-x_2)(x-x_3)\cdots(x-x_n)\over (x_1-x_2)(x_1-x_3)\cdots(x_1-x_n)}y_1$$

$$\phantom{=} \mathop{+}{(x-x_1)(x-x_3)\cdots(x-x_n)\over (x_2-x_1)(x_2-x_3)\cdots(x_2-x_n)}y_2 + \cdots$$

$$\phantom{=} \mathop{+}{(x-x_1)(x-x_2)\cdots(x-x_{n-1})\over (x_n-x_1)(x_n-x_2)\cdots(x_n-x_{n-1})}y_n.$$ (3)

For $n=3$ points,

$$P(x) = {(x-x_2)(x-x_3)\over(x_1-x_2)(x_1-x_3)}y_1+{(x-x_1)(x-x_3)\over (x_2-x_1)(x_2-x_3)}y_2+{(x-x_1)(x-x_2)\over (x_3-x_1)(x_3-x_2)}y_3$$ (4)

$$P'(x) = {2x-x_2-x_3\over (x_1-x_2)(x_1-x_3)}y_1+{2x-x_1-x_3\over (x_2-x_1)(x_2-x_3)}y_2+{2x-x_1-x_2\over (x_3-x_1)(x_3-x_2)}y_3.$$ (5)

Note that the function $P(x)$ passes through the points $(x_i,y_i)$, as can be seen for the case $n=3$,

$$P(x_1) = {(x_1-x_2)(x_1-x_3)\over(x_1-x_2)(x_1-x_3)}y_1+{(x_1-x_1)(x_1-x_3)\over(x_2-x_1)(x_2-x_3)}y_2+{(x_1-x_1)(x_1-x_2)\over(x_3-x_1)(x_3-x_2)}y_3 = y_1$$ (6)

$$P(x_2) = {(x_2-x_2)(x_2-x_3)\over(x_1-x_2)(x_1-x_3)}y_1+{(x_2-x_1)(x_2-x_3)\over(x_2-x_1)(x_2-x_3)}y_2+{(x_2-x_1)(x_2-x_2)\over(x_3-x_1)(x_3-x_2)}y_3 = y_2$$ (7)

$$P(x_3) = {(x_3-x_2)(x_3-x_3)\over(x_1-x_2)(x_1-x_3)}y_1+{(x_3-x_1)(x_3-x_3)\over(x_2-x_1)(x_2-x_3)}y_2+{(x_3-x_1)(x_3-x_2)\over(x_3-x_1)(x_3-x_2)}y_3 = y_3.$$ (8)

Generalizing to arbitrary $n$,

$$P(x_j)=\sum_{k=1}^n P_k(x_j) = \sum_{k=1}^n \delta_{jk}y_k = y_j.$$ (9)

The Lagrange interpolating polynomials can also be written using

$$\pi(x) \equiv \prod_{k=1}^n (x-x_k),$$ (10)

$$\pi(x_j) = \prod_{k=1}^n (x_j-x_k),$$ (11)

$$\pi'(x_j) = \left[{d\pi\over dx}\right]_{x=x_j} = \prod_{\scriptstyle k=1\atop\scriptstyle k\not= j}^n (x_j-x_k),$$ (12)

so

$$P(x)=\sum_{k=1}^n {\pi(x)\over (x-x_k)\pi'(x_k)}y_k.$$ (13)

Lagrange interpolating polynomials give no error estimate. A more conceptually straightforward method for calculating them is Neville's Algorithm.

See also Aitken Interpolation, Lebesgue Constants (Lagrange Interpolation), Neville's Algorithm, Newton's Divided Difference Interpolation Formula

References

Abramowitz, M. and Stegun, C. A. (Eds.). Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables, 9th printing. New York: Dover, pp. 878-879 and 883, 1972.

Beyer, W. H. (Ed.) CRC Standard Mathematical Tables, 28th ed. Boca Raton, FL: CRC Press, p. 439, 1987.

Press, W. H.; Flannery, B. P.; Teukolsky, S. A.; and Vetterling, W. T. ``Polynomial Interpolation and Extrapolation'' and ``Coefficients of the Interpolating Polynomial.'' §3.1 and 3.5 in Numerical Recipes in FORTRAN: The Art of Scientific Computing, 2nd ed. Cambridge, England: Cambridge University Press, pp. 102-104 and 113-116, 1992.