# Lagrange polynomial

﻿
Lagrange polynomial

In numerical analysis, a Lagrange polynomial, named after Joseph Louis Lagrange, is the interpolation polynomial for a given set of data points in the Lagrange form. It was first discovered by Edward Waring in 1779 and later rediscovered by Leonhard Euler in 1783.

As there is only one interpolation polynomial for a given set of data points it is a bit misleading to call the polynomial the Lagrange interpolation polynomial. The more precise name is interpolation polynomial in the Lagrange form.

Definition

Given a set of "k" + 1 data points

:$\left(x_0, y_0\right),ldots,\left(x_k, y_k\right)$

where no two "x""j" are the same, the interpolation polynomial in the Lagrange form is a linear combination

:$L\left(x\right) := sum_\left\{j=0\right\}^\left\{k\right\} y_j ell_j\left(x\right)$

of Lagrange basis polynomials

:$ell_j\left(x\right) := prod_\left\{i=0,, i eq j\right\}^\left\{k\right\} frac\left\{x-x_i\right\}\left\{x_j-x_i\right\} = frac\left\{\left(x-x_0\right)\right\}\left\{\left(x_j-x_0\right)\right\} cdots frac\left\{\left(x-x_\left\{j-1\right\}\right)\right\}\left\{\left(x_j-x_\left\{j-1\right\}\right)\right\} frac\left\{\left(x-x_\left\{j+1\right\}\right)\right\}\left\{\left(x_j-x_\left\{j+1\right\}\right)\right\} cdots frac\left\{\left(x-x_\left\{k\right\}\right)\right\}\left\{\left(x_j-x_\left\{k\right\}\right)\right\}.$

Proof

The function we are looking for has to be a polynomial function "L"("x") of degree less than or equal to "k" with

:$L\left(x_j\right) = y_j qquad j=0,ldots,k$

The Lagrange polynomial is a solution to the interpolation problem.

As can be seen
# $ell_j\left(x\right)$ is a polynomial and has degree "k".
# $ell_i\left(x_j\right) = delta_\left\{ij\right\},quad 0 leq i,j leq k.,$

Thus the function "L"("x") is a polynomial with degree at most "k" and

:$L\left(x_i\right) = sum_\left\{j=0\right\}^\left\{k\right\} y_j ell_j\left(x_i\right) = y_i.$

There can be only one solution to the interpolation problem since the difference of two such solutions would be a polynomial with degree at most "k" and "k+1" zeros. This is only possible if the difference is identically zero, so "L"("x") is the unique polynomial interpolating the given data.

Main idea

Solving an interpolation problem leads to a problem in linear algebra where we have to solve a matrix. Using a standard monomial basis for our interpolation polynomial we get the very complicated Vandermonde matrix. By choosing another basis, the Lagrange basis, we get the much simpler identity matrix = &delta;"i","j" which we can solve instantly.

Implementation in Java

Note : "pos" and "val" arrays are of size "degree".

float lagrangeInterpolatingPolynomial (float pos [] , float val [] , int degree, float desiredPos) { float retVal = 0;

for (int i = 0; i < degree; ++i) { float weight = 1;

for (int j = 0; j < degree; ++j) { // The i-th term has to be skipped if (j != i) { weight *= (desiredPos - pos [j] ) / (pos [i] - pos [j] ); } }

retVal += weight * val [i] ; }

return retVal; }

Usage

Example 1

We wish to interpolate $f\left(x\right)= an\left(x\right)$ at the points

The interpolating polynomial is::

Notes

The Lagrange form of the interpolation polynomial shows the linear character of polynomial interpolation and the uniqueness of the interpolation polynomial. Therefore, it is preferred in proofs and theoretical arguments. But, as can be seen from the construction, each time a node "x""k" changes, all Lagrange basis polynomials have to be recalculated. A better form of the interpolation polynomial for practical (or computational) purposes is the barycentric form of the Lagrange interpolation (see below) or Newton polynomials.

Lagrange and other interpolation at equally spaced points, as in the example above, yield a polynomial oscillating above and below the true function. This behaviour tends to grow with the number of points, leading to a divergence known as Runge's phenomenon; the problem may be eliminated by choosing interpolation points at Chebyshev nodes.

The Lagrange basis polynomials can be used in numerical integration to derive the Newton–Cotes formulas.

Barycentric interpolation

Using the quantity

:$ell\left(x\right) = \left(x - x_0\right)\left(x - x_1\right) cdots \left(x - x_k\right)$

we can re-write the Lagrange basis polynomials as

:$ell_j\left(x\right) = frac\left\{ell\left(x\right)\right\}\left\{x-x_j\right\} frac\left\{1\right\}\left\{prod_\left\{i=0,i eq j\right\}^k\left(x_j-x_i\right)\right\}$or, by defining the "barycentric weights" [cite online journal
author = Jean-Paul Berrut, Lloyd N. Trefethen
year = 2004
title = Barycentric Lagrange Interpolation
journal = SIAM Review
volume = 46
issue = 3
pages = 501&ndash;517
doi = 10.1137/S0036144502417715
]

:$w_j = frac\left\{1\right\}\left\{prod_\left\{i=0,i eq j\right\}^k\left(x_j-x_i\right)\right\}$

we can simply write

:$ell_j\left(x\right) = ell\left(x\right)frac\left\{w_j\right\}\left\{x-x_j\right\}$

which is commonly referred to as the "first form" of the barycentric interpolation formula.

The advantage of this representation is that the interpolation polynomial may now be evaluated as

:$L\left(x\right) = ell\left(x\right) sum_\left\{j=0\right\}^k frac\left\{w_j\right\}\left\{x-x_j\right\}y_j$

which, if the weights $w_j$ have been pre-computed, requires only $mathcal O\left(n\right)$ operations (evaluating $ell\left(x\right)$ and the weights $w_j/\left(x-x_j\right)$) as opposed to $mathcal O\left(n^2\right)$ for evaluating the Lagrange basis polynomials $ell_j\left(x\right)$ individually.

The barycentric interpolation formula can also easily be updated to incorporate a new node $x_\left\{k+1\right\}$ by dividing each of the $w_j$, $j=0 dots k$ by $\left(x_j - x_\left\{k+1\right\}\right)$ and constructing the new $w_\left\{k+1\right\}$ as above.

We can further simplify the first form by first considering the barycentric interpolation of the constant function $g\left(x\right)equiv 1$:

:$g\left(x\right) = ell\left(x\right) sum_\left\{j=0\right\}^k frac\left\{w_j\right\}\left\{x-x_j\right\}.$

Dividing $L\left(x\right)$ by $g\left(x\right)$ does not modify the interpolation, yet yields

:$L\left(x\right) = frac\left\{sum_\left\{j=0\right\}^k frac\left\{w_j\right\}\left\{x-x_j\right\}y_j\right\}\left\{sum_\left\{j=0\right\}^k frac\left\{w_j\right\}\left\{x-x_j$

which is referred to as the "second form" or "true form" of the barycentric interpolation formula. This second form has the advantage, that $ell\left(x\right)$ need not be evaluated for each evaluation of $L\left(x\right)$.

ee also

*Polynomial interpolation
*Newton form of the interpolation polynomial
*Bernstein form of the interpolation polynomial
*Newton–Cotes formulas

* [http://numericalmethods.eng.usf.edu/topics/lagrange_method.html Lagrange Method of Interpolation &mdash; Notes, PPT, Mathcad, Mathematica, Matlab, Maple] at [http://numericalmethods.eng.usf.edu Holistic Numerical Methods Institute]
* [http://www.math-linux.com/spip.php?article71 Lagrange interpolation polynomial] on www.math-linux.com
*
* [http://math.fullerton.edu/mathews/n2003/LagrangePolyMod.html Module for Lagrange Polynomials by John H. Mathews]
* [http://www.comlab.ox.ac.uk/projects/chebfun/ The chebfun Project] [cite online journal
author = Zachary Battles, Lloyd N. Trefethen
year = 2004
title = An Extension of Matlab to Continuous Functions and Operators
journal = SIAM J. Sci. Comput.
volume = 25
issue = 5
pages = 1743&ndash;1770
doi = 10.1137/S1064827503430126
] at Oxford University

References

Wikimedia Foundation. 2010.

### Look at other dictionaries:

• Lagrange (disambiguation) — Lagrange may refer to: * Château Lagrange, the wine from Bordeaux, France * Joseph Louis Lagrange, (1736–1813) mathematician and mathematical physicist * Léo Lagrange, (1900–1940) french ministre * Georges Lagrange, (1928–2004) esperanto writerIn …   Wikipedia

• Lagrange's formula — may refer to a number of results named after Joseph Louis Lagrange: *Lagrange s interpolation formula Lagrange polynomial *Lagrange Bürmann formula Lagrange inversion theorem *Vector triple product *Mean value theorem …   Wikipedia

• Lagrange's theorem (group theory) — Lagrange s theorem, in the mathematics of group theory, states that for any finite group G , the order (number of elements) of every subgroup H of G divides the order of G . Lagrange s theorem is named after Joseph Lagrange. Proof of Lagrange s… …   Wikipedia

• Lagrange's theorem (number theory) — Lagrange s theorem, in the mathematics of number theory, states that::If p is a prime number and f(x) is a polynomial of degree n, then f(x) = 0 (mod p) has at most n integral solutions for 0 < x < p .If the modulus is not prime, then it is… …   Wikipedia

• Polynomial interpolation — In the mathematical subfield of numerical analysis, polynomial interpolation is the interpolation of a given data set by a polynomial. In other words, given some data points (such as obtained by sampling), the aim is to find a polynomial which… …   Wikipedia

• Lagrange inversion theorem — In mathematical analysis, the Lagrange inversion theorem, also known as the Lagrange Bürmann formula, gives the Taylor series expansion of the inverse function of an analytic function. Theorem statementSuppose the dependence between the variables …   Wikipedia

• List of polynomial topics — This is a list of polynomial topics, by Wikipedia page. See also trigonometric polynomial, list of algebraic geometry topics.Basics*Polynomial *Coefficient *Monomial *Polynomial long division *Polynomial factorization *Rational function *Partial… …   Wikipedia

• Newton polynomial — In the mathematical field of numerical analysis, a Newton polynomial, named after its inventor Isaac Newton, is the interpolation polynomial for a given set of data points in the Newton form. The Newton polynomial is sometimes called Newton s… …   Wikipedia

• Wilkinson's polynomial — In numerical analysis, Wilkinson s polynomial is a specific polynomial which was used by James H. Wilkinson in 1963 to illustrate a difficulty when finding the root of a polynomial: the location of the roots can be very sensitive to perturbations …   Wikipedia

• Symmetric polynomial — This article is about individual symmetric polynomials. For the ring of symmetric polynomials, see ring of symmetric functions. In mathematics, a symmetric polynomial is a polynomial P(X1, X2, …, Xn) in n variables, such that if any of the… …   Wikipedia