<< Chapter < Page Chapter >> Page >
Lagrange's interpolation formula is a simple and clever method for finding the unique polynomial of order L that exactly passes through L+1 distinct samples of a signal.

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 ... a L x L k 0 L a k x k and L 1 values of P x k at different x k , k 0 1 ... L , x i x j , i j , the polynomial can be written as P x k 0 L P x k x x 1 x x 2 ... x x k - 1 x x k + 1 ... x x L x k x 1 x k x 2 ... x k x k - 1 x k x k + 1 ... 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, i 0, i k L x x i x k x i 1 x x k 0 x x j j k 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 1 x 0 x 0 2 ... x 0 L 1 x 1 x 1 2 ... x 1 L 1 x 2 x 2 2 ... x 2 L 1 x L x L 2 ... x L L a 0 a 1 a 2 a L P x 0 P x 1 P x 2 P x L 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 .

Get Jobilize Job Search Mobile App in your pocket Now!

Get it on Google Play Download on the App Store Now




Source:  OpenStax, Digital filter design. OpenStax CNX. Jun 09, 2005 Download for free at http://cnx.org/content/col10285/1.1
Google Play and the Google Play logo are trademarks of Google Inc.

Notification Switch

Would you like to follow the 'Digital filter design' conversation and receive update notifications?

Ask