Lagrange Interpolation 1.2 2005/04/20 00:49:01 GMT-5 2007/02/28 00:59:59.193 US/Central Douglas L. Jones dl-jones@uiuc.edu Douglas L. Jones dl-jones@uiuc.edu Jeffrey M Silverman JSilverman@astro.berkeley.edu Kyle Evan Clarkson kclarks@rice.edu interpolation lagrange polynomial 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 Lth-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 point using the polynomial equation. Lagrange interpolation is useful in many applications, including Parks-McClellan FIR Filter Design.

Lagrange interpolation formula Given an Lth-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 Lth-order polynomials is itself an Lth-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 .