1.4 Lagrange interpolation

Lagrange's interpolation method is a simple and clever way of finding the unique $L$ th-order polynomial that exactly passes through $L+1$ distinct samples of a signal. Once the polynomial is known, its value can easily be interpolated at any pointusing the polynomial equation. Lagrange interpolation is useful in many applications, including Parks-McClellan FIR Filter Design .

Lagrange interpolation formula

Given an $L$ th-order polynomial $$P(x)=a_0+a_{1}x+\mathrm{...}+a_{L}x^L=\sum_{k=0}^L a_{k}x^k$$ and $L+1$ values of $P(x_k)$ at different $x_k$ , $k\in \{0, 1, \mathrm{...}, L\}$ , $x_i\neq x_j$ , $i\neq j$ , the polynomial can be written as $$P(x)=\sum_{k=0}^L P(x_k)\frac{(x-x_1)(x-x_2)\mathrm{...}(x-x_{k-1})(x-x_{k+1})\mathrm{...}(x-x_L)}{(x_k-x_1)(x_k-x_2)\mathrm{...}(x_k-x_{k-1})(x_k-x_{k+1})\mathrm{...}(x_k-x_L)}$$ The value of this polynomial at other $x$ can be computed via substitution into this formula, or by expanding this formula to determine the polynomial coefficients $a_k$ in standard form.

Proof

Note that for each term in the Lagrange interpolation formula above, $$\prod_{i=0,i\neq k}^L \frac{x-x_i}{x_k-x_i}=\begin{cases}1 & \text{if $x=x_k$}\\ 0 & \text{if $(x=x_j)\land (j\neq k)$}\end{cases}$$ and that it is an $L$ th-order polynomial in $x$ . The Lagrange interpolation formula is thus exactly equal to $P(x_k)$ at all $x_k$ , and as a sum of $L$ th-order polynomials is itself an $L$ th-order polynomial.

It can be shown that the Vandermonde matrix $$\begin{pmatrix}1 & x_0 & x_0^2 & \mathrm{...} & x_0^L\\ 1 & x_1 & x_1^2 & \mathrm{...} & x_1^L\\ 1 & x_2 & x_2^2 & \mathrm{...} & x_2^L\\ ⋮ & ⋮ & ⋮ & \ddots & ⋮\\ 1 & x_L & x_L^2 & \mathrm{...} & x_L^L\\ \end{pmatrix}\left(\begin{array}{c}{a}_0\\ a_1\\ a_2\\ ⋮\\ a_L\end{array}\right)=\left(\begin{array}{c}P(x_0)\\ P(x_1)\\ P(x_2)\\ ⋮\\ P(x_L)\end{array}\right)$$ has a non-zero determinant and is thus invertible, so the $L$ th-order polynomial passing through all $L+1$ sample points $x_j$ is unique. Thus the Lagrange polynomial expressions, as an $L$ th-order polynomial passing through the $L+1$ sample points, must be the unique $P(x)$ .