Lagrange polynomial

Not to be confused with Legendre polynomials (the orthogonal basis of function space).
This image shows, for four points ((−9, 5), (−4, 2), (−1, −2), (7, 9)), the (cubic) interpolation polynomial L(x) (dashed, black), which is the sum of the scaled basis polynomials y0ℓ0(x), y1ℓ1(x), y2ℓ2(x) and y3ℓ3(x). The interpolation polynomial passes through all four control points, and each scaled basis polynomial passes through its respective control point and is 0 where x corresponds to the other three control points.

In numerical analysis, the Lagrange interpolating polynomial is the unique polynomial of lowest degree that interpolates a given set of data.

Given a data set of coordinate pairs with the are called nodes and the are called values. The Lagrange polynomial has degree and assumes each value at the corresponding node,

Although named after Joseph-Louis Lagrange, who published it in 1795,[1] the method was first discovered in 1779 by Edward Waring.[2] It is also an easy consequence of a formula published in 1783 by Leonhard Euler.[3]

Uses of Lagrange polynomials include the Newton–Cotes method of numerical integration, Shamir's secret sharing scheme in cryptography, and Reed–Solomon error correction in coding theory.

For equispaced nodes, Lagrange interpolation is susceptible to Runge's phenomenon of large oscillation.

  1. ^ Lagrange, Joseph-Louis (1795). "Leçon Cinquième. Sur l'usage des courbes dans la solution des problèmes". Leçons Elémentaires sur les Mathématiques (in French). Paris. Republished in Serret, Joseph-Alfred, ed. (1877). Oeuvres de Lagrange. Vol. 7. Gauthier-Villars. pp. 271–287. Translated as "Lecture V. On the Employment of Curves in the Solution of Problems". Lectures on Elementary Mathematics. Translated by McCormack, Thomas J. (2nd ed.). Open Court. 1901. pp. 127–149.
  2. ^ Waring, Edward (1779). "Problems concerning interpolations". Philosophical Transactions of the Royal Society. 69: 59–67. doi:10.1098/rstl.1779.0008.
  3. ^ Meijering, Erik (2002). "A chronology of interpolation: from ancient astronomy to modern signal and image processing" (PDF). Proceedings of the IEEE. 90 (3): 319–342. doi:10.1109/5.993400.