- Lagrange polynomial
In

numerical analysis , a**Lagrange polynomial**, named afterJoseph Louis Lagrange , is the interpolationpolynomial for a given set of data points in the**Lagrange form**. It was first discovered byEdward Waring in 1779 and later rediscovered byLeonhard 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

:$(x\_0,\; y\_0),ldots,(x\_k,\; y\_k)$

where no two "x"

_{"j"}are the same, the**interpolation polynomial in the Lagrange form**is alinear combination :$L(x)\; :=\; sum\_\{j=0\}^\{k\}\; y\_j\; ell\_j(x)$

of Lagrange basis polynomials

:$ell\_j(x)\; :=\; prod\_\{i=0,,\; i\; eq\; j\}^\{k\}\; frac\{x-x\_i\}\{x\_j-x\_i\}\; =\; frac\{(x-x\_0)\}\{(x\_j-x\_0)\}\; cdots\; frac\{(x-x\_\{j-1\})\}\{(x\_j-x\_\{j-1\})\}\; frac\{(x-x\_\{j+1\})\}\{(x\_j-x\_\{j+1\})\}\; cdots\; frac\{(x-x\_\{k\})\}\{(x\_j-x\_\{k\})\}.$

**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(x\_j)\; =\; y\_j\; qquad\; j=0,ldots,k$

The Lagrange polynomial is a solution to the interpolation problem.

As can be seen

# $ell\_j(x)$ is a polynomial and has degree "k".

# $ell\_i(x\_j)\; =\; delta\_\{ij\},quad\; 0\; leq\; i,j\; leq\; k.,$Thus the function "L"("x") is a polynomial with degree at most "k" and

:$L(x\_i)\; =\; sum\_\{j=0\}^\{k\}\; y\_j\; ell\_j(x\_i)\; =\; 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 complicatedVandermonde matrix . By choosing another basis, the Lagrange basis, we get the much simpleridentity matrix = δ_{"i","j"}which we can solve instantly.**Implementation in Java**Note : "pos" and "val" arrays are of size "degree".

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(x)=\; an(x)$ at the points

The interpolating polynomial is::$egin\{align\}L(x)\; =\; \{1\}cdot\{x\; -\; 2\; over\; 1\; -\; 2\}cdot\{x\; -\; 3\; over\; 1\; -\; 3\}+\{8\}cdot\{x\; -\; 1\; over\; 2\; -\; 1\}cdot\{x\; -\; 3\; over\; 2\; -\; 3\}+\{27\}cdot\{x\; -\; 1\; over\; 3\; -\; 1\}cdot\{x\; -\; 2\; over\; 3\; -\; 2\}\; \backslash =\; 6x^2\; -\; 11x\; +\; 6.\; end\{align\}$

**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) orNewton polynomial s.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 atChebyshev nodes .The Lagrange basis polynomials can be used in

numerical integration to derive theNewton–Cotes formulas .**Barycentric interpolation**Using the quantity

:$ell(x)\; =\; (x\; -\; x\_0)(x\; -\; x\_1)\; cdots\; (x\; -\; x\_k)$

we can re-write the Lagrange basis polynomials as

:$ell\_j(x)\; =\; frac\{ell(x)\}\{x-x\_j\}\; frac\{1\}\{prod\_\{i=0,i\; eq\; j\}^k(x\_j-x\_i)\}$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–517

doi = 10.1137/S0036144502417715:$w\_j\; =\; frac\{1\}\{prod\_\{i=0,i\; eq\; j\}^k(x\_j-x\_i)\}$

we can simply write

:$ell\_j(x)\; =\; ell(x)frac\{w\_j\}\{x-x\_j\}$

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(x)\; =\; ell(x)\; sum\_\{j=0\}^k\; frac\{w\_j\}\{x-x\_j\}y\_j$

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

The barycentric interpolation formula can also easily be updated to incorporate a new node $x\_\{k+1\}$ by dividing each of the $w\_j$, $j=0\; dots\; k$ by $(x\_j\; -\; x\_\{k+1\})$ and constructing the new $w\_\{k+1\}$ as above.

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

:$g(x)\; =\; ell(x)\; sum\_\{j=0\}^k\; frac\{w\_j\}\{x-x\_j\}.$

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

:$L(x)\; =\; frac\{sum\_\{j=0\}^k\; frac\{w\_j\}\{x-x\_j\}y\_j\}\{sum\_\{j=0\}^k\; frac\{w\_j\}\{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(x)$ need not be evaluated for each evaluation of $L(x)$.

**ee also***

Polynomial interpolation

*Newton form of the interpolation polynomial

*Bernstein form of the interpolation polynomial

*Newton–Cotes formulas **External links*** [

*http://numericalmethods.eng.usf.edu/topics/lagrange_method.html Lagrange Method of Interpolation — 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*] at

author = Zachary Battles, Lloyd N. Trefethen

year = 2004

title = An Extension ofMatlab to Continuous Functions and Operators

journal = SIAM J. Sci. Comput.

volume = 25

issue = 5

pages = 1743–1770

doi = 10.1137/S1064827503430126Oxford 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