|
In mathematics, the Lebesgue constants (depending on a set of nodes and of its size) give an idea of how good the interpolant of a function (at the given nodes) is in comparison with the best polynomial approximation of the function (the degree of the polynomials are obviously fixed). The Lebesgue function for polynomials of degree at most n and for the set of (n+1) nodes T is generally denoted by Λn(T). For other meanings of mathematics or math, see mathematics (disambiguation). ...
In the mathematical subfield of numerical analysis, interpolation is a method of constructing new data points from a discrete set of known data points. ...
In mathematics, a polynomial is an expression in which constants and variables are combined using only addition, subtraction, multiplication, and positive whole number exponents (raising to a power). ...
Definition We fix the interpolation nodes x0, ..., xn and an interval [a, b] containing all the interpolation nodes. The process of interpolation maps the function f to a polynomial p. This defines a mapping X from the space C([a, b]) of all continuous functions on [a, b] to itself. The map X is linear and it is a projection on the subspace Πn of polynomials of degree n or less. In linear algebra, a projection is a linear transformation P such that P2 = P, i. ...
The Lebesgue constant Λn(T) is defined as the operator norm of X. This definition requires us to specify a norm on C([a, b]). The maximum norm is usually the most convenient. In mathematics, the operator norm is a norm defined on the space of bounded operators between two Banach spaces. ...
In mathematical analysis, the uniform norm assigns to real- or complex-valued functions f the nonnegative number This norm is also called the supremum norm or the Chebyshev norm. ...
Properties The Lebesgue constant bounds the interpolation error:  We will here prove this statement with the maximum norm. Let p* denote the best approximation of f among the polynomials of degree n or less. In other words, p* minimizes ||p−f|| among all p in Πn. Then - ||f−X(f)|| ≤ ||f−p*|| + ||p*−X(f)||
by the triangle inequality. But X is a projection on Πn, so p*−X(f) = X(p*−f). This finishes the proof. Note that this relation comes also as a special case of Lebesgue's lemma. In mathematics, triangle inequality is the theorem stating that for any triangle, the measure of a given side must be less than the sum of the other two sides but greater than the difference between the two sides. ...
In mathematics, Lebesgues lemma is an important statement in approximation theory. ...
In other words, the interpolation polynomial is at most a factor Λn(T) + 1 worse than the best possible approximation. This suggests that we look for a set of interpolation nodes with a small Lebesgue constant.
The Lebesgue constant can be expressed in terms of the Lagrange basis polynomials: 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. ...
 In fact, we have: ![Lambda_n(T) = max_{xin[a,b]} sum_{j=0}^n |l_j(x)|.](http://upload.wikimedia.org/math/2/8/c/28cb124767d7ae5cc0b1a776a71668c5.png) Nevertheless, it is not easy to find an explicit expression for Λn(T).
Minimal Lebesgue constants In the case of equidistant nodes, the Lebesgue constant grows exponentially. More precisely, we have the following asymptotic estimate In mathematics, a quantity that grows exponentially is one whose growth rate is always proportional to its current size. ...
 On the other hand, the Lebesgue constant grows only logarithmically if Chebyshev nodes are used, since we have In the mathematical subfield of numerical analysis Chebyshev nodes are the roots of the Chebyshev polynomial of the first kind. ...
 where a = 0.9625….
We conclude again that Chebyshev nodes are a very good choice for polynomial interpolation. However, there is an easy (linear) transformation of Chebyshev nodes that gives a better Lebesgue constant. Let ti denote the ith Chebyshev node. Then, define si = ti / cos(π / 2(n + 1)). For such nodes:
 where b=0.7219....
Those nodes are though not optimal (i.e. they do not minimize the Lebesgue constants) and the research of an optimal set of nodes (which has already been proved to be unique under some assumptions) is still one of the most intriguing topics in mathematics today. Using a computer, one can approximate the values of the minimal constants, here for the canonical interval [-1,1]: A Lego RCX Computer is an example of an embedded computer used to control mechanical devices. ...
| n | Λn(T) | | 1 | 1 | | 2 | 1.25 | | 3 | 1.4229 | | 4 | 1.5595 | | 5 | 1.6722 | | 6 | 1.7681 | | 7 | 1.8516 | | 8 | 1.9255 | | 9 | 1.9917 | There are several sets of nodes that minimize, for fixed n, the Lebesgue constant. Though if we assume that we always take -1 and 1 as nodes for interpolation, then such a set is unique. To illustrate this property, we shall see what happens when n=2 (i.e. we consider 3 interpolation nodes in which cas the property is not trivial). One can check that each set of nodes of type (-a,0,a) is optimal when  (we consider only nodes in [-1,1]). If we force the set of nodes to be of the type (-1,b,1), then b must equal 0 (look at the Lebesgue function, whose maximum is the Lebesgue constant).
Sensitivity of the values of a polynomial The Lebesgue constants also arise in another problem. Let p be a polynomial of degree n expressed in the Lagrangian form associated with the points in the vector t (i.e. the vector u of its coefficients is the vector containing the values p(ti)). Let  be a polynomial obtained by slightly changing the coefficients u of the original polynomial p. Let us consider the equation: 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. ...
 This means that the (relative) error in the values of will not be higher than the appropriate Lebesgue constant times the relative error in the coefficients. In this sense, the Lebesgue constant can be viewed as the relative condition number of the operator mapping each coefficient vector u to the set of the values of the polynomial with coefficients u in the Lagrange form. We can actually define such an operator for each polynomial basis but its condition number is greater than the optimal Lebesgue constant for most convenient bases. In numerical analysis, the condition number associated with a numerical problem is a measure of that quantitys amenability to digital computation, that is, how well-posed the problem is. ...
External links - L. Brutman (1997), Lebesgue functions for polynomial interpolation — a survey, Ann. Numer. Math. 4, 111–127. Preprint available at the MathSoft website
- Lebesgue constants on MathWorld.
| 
Feeds |
Contact