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

:$(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 a linear 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 complicated Vandermonde matrix. By choosing another basis, the Lagrange basis, we get the much simpler identity matrix = δ_"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(x)=\; an(x)$ 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(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&ndash;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 &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