Lagrange Interpolation

Lagrange interpolation is a well known, classical technique for interpolation [194]. It is also called Waring-Lagrange interpolation, since Waring actually published it 16 years before Lagrange [312, p. 323]. More generically, the term polynomial interpolation normally refers to Lagrange interpolation. In the first-order case, it reduces to linear interpolation.

Given a set of $N+1$ known samples $f(x_k)$ , $k=0,1,2,\ldots,N$ , the problem is to find the unique order $N$ polynomial $y(x)$ which interpolates the samples.^5.2The solution can be expressed as a linear combination of elementary $N$ th order polynomials:

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

where

$$l_k(x) \isdef \frac{(x - x_0) \cdots (x - x_{k-1}) (x - x_{k+1}) \cdots (x - x_N) }{(x_k - x_0) \cdots (x_k - x_{k-1}) (x_k - x_{k+1}) \cdots (x_k - x_N)}.$$

From the numerator of the above definition, we see that $l_k(x)$ is an order $N$ polynomial having zeros at all of the samples except the $k$ th. The denominator is simply the constant which normalizes to give $l_k(x_k)=1$ . Thus, we have

$$l_k(x_j) = \delta_{kj} \isdef \left\{\begin{array}{ll} 1, & j=k, \\ [5pt] 0, & j\neq k. \\ \end{array} \right.$$

The polynomial $l_k$ can be interpreted as the $k$ th basis polynomial for constructing a polynomial interpolation of order $N$ over the $N+1$ sample points $x_k$ . It is an order $N$ polynomial having zeros at all of the samples except the $k$ th, where it is 1. An example of a set of eight basis functions $l_k$ for randomly selected interpolation points $x_k$ is shown in Fig.4.10.

Figure 4.10: Example Lagrange basis functions in the eighth-order case for randomly selected interpolation points (marked by dotted lines). The unit-amplitude points are marked by dashed lines.