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 [318, 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 known samples , $k=0,1,2,\ldots,N$ , the problem is to find the unique order polynomial which interpolates the samples.^K.1The solution can be expressed as a linear combination of elementary th order polynomials:

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

where

$\displaystyle l_k(x) \isdef \frac{(x - x_0) \cdots (x - x_{k-1}) (x - x_{k+1}) ... ...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

is an order

polynomial having zeros at all of the samples except the

th. The denominator is simply the constant which normalizes its value to

. Thus, we have

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

In other words, the polynomial

is the

th basis polynomial for constructing a polynomial interpolation of order

over the

sample points

. It is an order

polynomial having zeros at all of the samples except the

th, where it is 1. An example of a set of eight basis functions

for randomly selected interpolation points

is shown in Fig.K.1.

**Figure K.1:** 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.
$\includegraphics[width=\twidth]{eps/lagrangebases}$

Subsections

Order a Hardcopy of Physical Audio Signal Processing

Previous: Higher Order Delay Line Interpolation
Next: Relation of Lagrange and Sinc Interpolation

written by Julius Orion Smith III
Julius Smith's background is in electrical engineering (BS Rice 1975, PhD Stanford 1983). He is presently Professor of Music and Associate Professor (by courtesy) of Electrical Engineering at Stanford's Center for Computer Research in Music and Acoustics (CCRMA), teaching courses and pursuing research related to signal processing applied to music and audio systems. See http://ccrma.stanford.edu/~jos/ for details.

Sign in

Search Online Books

Free Online Books

Chapters

Physical Audio Signal Processing
Higher Order Delay Line Interpolation
Lagrange Interpolation