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 ( x j , y j ) {\displaystyle \textstyle (x_{j},y_{j})} , the x j {\displaystyle \textstyle x_{j}} are called nodes and the y j {\displaystyle \textstyle y_{j}} are called values. The Lagrange polynomial L ( x ) {\displaystyle L(x)} which interpolates the data assumes each value at the corresponding node, L ( x j ) = y j {\displaystyle \textstyle L(x_{j})=y_{j}} . If there are k + 1 {\displaystyle k+1} data pairs, the Lagrange polynomial has degree ≤ k {\displaystyle \leq k} . Although named after Joseph-Louis Lagrange, who published it in 1795, the method was first discovered in 1779 by Edward Waring. It is also an easy consequence of a formula published in 1783 by Leonhard Euler. 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.
Definition Given a set of k + 1 {\displaystyle k+1} nodes { x 0 , x 1 , … , x k } {\displaystyle \{x_{0},x_{1},\ldots ,x_{k}\}} , which must all be distinct, x j ≠ x m {\displaystyle \textstyle x_{j}\neq x_{m}} for indices j ≠ m {\displaystyle j\neq m} , the Lagrange basis for polynomials of degree ≤ k {\displaystyle \leq k} for those nodes is the set of polynomials { ℓ 0 ( x ) , ℓ 1 ( x ) , … , ℓ k ( x ) } {\displaystyle \textstyle \{\ell _{0}(x),\ell _{1}(x),\ldots ,\ell _{k}(x)\}} each of degree k {\displaystyle k} which take values ℓ j ( x m ) = 0 {\displaystyle \textstyle \ell _{j}(x_{m})=0} if m ≠ j {\displaystyle m\neq j} and ℓ j ( x j ) = 1 {\displaystyle \textstyle \ell _{j}(x_{j})=1} . Using the Kronecker delta this can be written ℓ j ( x m ) = δ j m {\displaystyle \textstyle \ell _{j}(x_{m})=\delta _{jm}} . Each basis polynomial can be explicitly described by the product:
… excerpt ends here. Continue reading the full article.
