- Lagrange polynomial
numerical analysis, a Lagrange polynomial, named after Joseph Louis Lagrange, is the interpolation polynomialfor a given set of data points in the Lagrange form. It was first discovered by Edward Waringin 1779 and later rediscovered by Leonhard Eulerin 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.
Given a set of "k" + 1 data points
where no two "x""j" are the same, the interpolation polynomial in the Lagrange form is a
of Lagrange basis polynomials
The function we are looking for has to be a polynomial function "L"("x") of degree less than or equal to "k" with
The Lagrange polynomial is a solution to the interpolation problem.
As can be seen
# is a polynomial and has degree "k".
Thus the function "L"("x") is a polynomial with degree at most "k" and
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.
Solving an interpolation problem leads to a problem in linear algebra where we have to solve a matrix. Using a standard
monomial basisfor 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".
We wish to interpolate at the points
The interpolating polynomial is::
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
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 integrationto derive the Newton–Cotes formulas.
Using the quantity
we can re-write the Lagrange basis polynomials as
: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 ]
we can simply write
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
which, if the weights have been pre-computed, requires only operations (evaluating and the weights ) as opposed to for evaluating the Lagrange basis polynomials individually.
The barycentric interpolation formula can also easily be updated to incorporate a new node by dividing each of the , by and constructing the new as above.
We can further simplify the first form by first considering the barycentric interpolation of the constant function :
Dividing by does not modify the interpolation, yet yields
which is referred to as the "second form" or "true form" of the barycentric interpolation formula. This second form has the advantage, that need not be evaluated for each evaluation of .
* [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
author = Zachary Battles, Lloyd N. Trefethen
year = 2004
title = An Extension of
Matlabto Continuous Functions and Operators
journal = SIAM J. Sci. Comput.
volume = 25
issue = 5
pages = 1743–1770
doi = 10.1137/S1064827503430126 ] at
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