Lagrange Interpolation

• Lagrange interpolation is just polynomial interpolation
• $N$ th-order polynomial interpolates $N+1$ points
• First-order case = linear interpolation

Problem Formulation

Given a set of $N+1$ known samples $f(x_k)$ , $k=0,1,2,\ldots,N$ , find the unique order $N$ polynomial $y(x)$ which interpolates the samples

Solution (Waring, Lagrange):

$$y(x) = \sum_{k=0}^N l_k(x)f(x_k)$$

where $l_k(x)$ is the Lagrange polynomial corresponding to sample $x_k$ :

$$l_k(x) \mathrel{\stackrel{\mathrm{\Delta}}{=}}{ (x - x_0) \cdots (x - x_{k-1}) (x - x_{k+1}) \cdots (x - x_N) \over (x_k - x_0) \cdots (x_k - x_{k-1}) (x_k - x_{k+1}) \cdots (x_k - x_N) }$$

• Numerator gives a zero at all samples but the $k$ th
• Denominator simply normalizes $l_k(x)$ to $1$ at $x=x_k$
• As a result,
  $$l_k(x_j) = \delta_{kj} \mathrel{\stackrel{\mathrm{\Delta}}{=}}\left\{\begin{array}{ll} 1, & j=k \\ [5pt] 0, & j\neq k \\ \end{array} \right.$$

• Generalized bandlimited impulse = generalized sinc function:
  Each $l_k(x)$ goes through $1$ at $x=x_k$ and zero at all other sample points
  I.e., $l_k(x)$ is analogous to sinc$(x-x_k)$

• For uniformly spaced samples, Lagrange interpolaton converges to sinc interpolation as $N\to\infty$

• For uniformly spaced samples and finite $N$ , Lagrange interpolaton is equivalent to windowed sinc interpolation using a binomial window
  (see text for refs)

• Nonuniformly spaced sample locations, such as along the zeros of a Chebyshev polynomial, generally do better than uniform spacing, when applicable