Lebesgue constant (interpolation)
Encyclopedia
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 constant for polynomials of degree at most n and for the set of n + 1 nodes T is generally denoted by Λn(T). These constants are named after Henri Lebesgue
.
[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.
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.
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
by the triangle inequality
. But X is a projection on Πn, so p∗ − X(f) =X(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 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 fact, we have the Lebesgue function
and the Lebesgue constant (or Lebesgue number) for the grid is its maximum value
Nevertheless, it is not easy to find an explicit expression for Λn(T).
. More precisely, we have the following asymptotic estimate
On the other hand, the Lebesgue constant grows only logarithmically if Chebyshev nodes
are used, since we have
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, however, not optimal (i.e. they do not minimize the Lebesgue constants) and the search for 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]:
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 case the property is not trivial). One can check that each set of nodes of type (−a,0,a) is optimal when √8⁄3 ≤ a ≤ 1 (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).
If we assume that we take −1 and 1 as nodes for interpolation, then as shown by H.-J. Rack, for the case n = 3, the explicit values of the optimal nodes and the explicit value of the minimal Lebesgue constant are known.
be a polynomial of degree 
expressed in the Lagrangian form
associated with the points in the vector
(i.e. the vector 
of its coefficients is the vector containing the values 
). Let 
be a polynomial obtained by slightly changing the coefficients 
of the original polynomial 
to 
. Let us consider the inequality:
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
to the set of the values of the polynomial with coefficients 
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.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, the Lebesgue constants (depending on a set of nodes and of its size) give an idea of how good the interpolant
Interpolation
In the mathematical field of numerical analysis, interpolation is a method of constructing new data points within the range of a discrete set of known data points....
of a function
Function (mathematics)
In mathematics, a function associates one quantity, the argument of the function, also known as the input, with another quantity, the value of the function, also known as the output. A function assigns exactly one output to each input. The argument and the value may be real numbers, but they can...
(at the given nodes) is in comparison with the best polynomial
Polynomial
In mathematics, a polynomial is an expression of finite length constructed from variables and constants, using only the operations of addition, subtraction, multiplication, and non-negative integer exponents...
approximation
Approximation
An approximation is a representation of something that is not exact, but still close enough to be useful. Although approximation is most often applied to numbers, it is also frequently applied to such things as mathematical functions, shapes, and physical laws.Approximations may be used because...
of the function (the degree of the polynomials are obviously fixed). The Lebesgue constant for polynomials of degree at most n and for the set of n + 1 nodes T is generally denoted by Λn(T). These constants are named after Henri Lebesgue
Henri Lebesgue
Henri Léon Lebesgue was a French mathematician most famous for his theory of integration, which was a generalization of the seventeenth century concept of integration—summing the area between an axis and the curve of a function defined for that axis...
.
Definition
We fix the interpolation nodes x0, …, xn and an intervalInterval (mathematics)
In mathematics, a interval is a set of real numbers with the property that any number that lies between two numbers in the set is also included in the set. For example, the set of all numbers satisfying is an interval which contains and , as well as all numbers between them...
[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
Projection (linear algebra)
In linear algebra and functional analysis, a projection is a linear transformation P from a vector space to itself such that P2 = P. It leaves its image unchanged....
on the subspace Πn of polynomials of degree n or less.
The Lebesgue constant Λn(T) is defined as the operator norm
Operator norm
In mathematics, the operator norm is a means to measure the "size" of certain linear operators. Formally, it is a norm defined on the space of bounded linear operators between two given normed vector spaces.- Introduction and definition :...
of X. This definition requires us to specify a norm on C([a, b]). The maximum norm is usually the most convenient.
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
by the triangle inequality
Triangle inequality
In mathematics, the triangle inequality states that for any triangle, the sum of the lengths of any two sides must be greater than or equal to the length of the remaining side ....
. But X is a projection on Πn, so p∗ − X(f) =X(p∗) − X(f) = X(p∗−f). This finishes the proof. Note that this relation comes also as a special case of Lebesgue's lemma
Lebesgue's lemma
For Lebesgue's lemma for open covers of compact spaces in topology see Lebesgue's number lemmaIn mathematics, Lebesgue's lemma is an important statement in approximation theory. It provides a bound for the projection error.-Statement:...
.
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
Lagrange polynomial
In numerical analysis, Lagrange polynomials are used for polynomial interpolation. For a given set of distinct points x_j and numbers y_j, the Lagrange polynomial is the polynomial of the least degree that at each point x_j assumes the corresponding value y_j...
polynomials:
In fact, we have the Lebesgue function
and the Lebesgue constant (or Lebesgue number) for the grid is its maximum value
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 exponentiallyExponential growth
Exponential growth occurs when the growth rate of a mathematical function is proportional to the function's current value...
. More precisely, we have the following asymptotic estimate
On the other hand, the Lebesgue constant grows only logarithmically if Chebyshev nodes
Chebyshev nodes
In numerical analysis, Chebyshev nodes are the roots of the Chebyshev polynomial of the first kind. They are often used as nodes in polynomial interpolation because the resulting interpolation polynomial minimizes the Runge's phenomenon.-Definition:...
are used, since we have
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, however, not optimal (i.e. they do not minimize the Lebesgue constants) and the search for 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
Computer
A computer is a programmable machine designed to sequentially and automatically carry out a sequence of arithmetic or logical operations. The particular sequence of operations can be changed readily, allowing the computer to solve more than one kind of problem...
, one can approximate the values of the minimal constants, here for the canonical interval [−1,1]:
| n | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|
| Λn(T) | 1.0000 | 1.2500 | 1.4229 | 1.5595 | 1.6722 | 1.7681 | 1.8516 | 1.9255 | 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 case the property is not trivial). One can check that each set of nodes of type (−a,0,a) is optimal when √8⁄3 ≤ a ≤ 1 (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).
If we assume that we take −1 and 1 as nodes for interpolation, then as shown by H.-J. Rack, for the case n = 3, the explicit values of the optimal nodes and the explicit value of the minimal Lebesgue constant are known.
Sensitivity of the values of a polynomial
The Lebesgue constants also arise in another problem. Let be a polynomial of degree expressed in the Lagrangian formLagrange polynomial
In numerical analysis, Lagrange polynomials are used for polynomial interpolation. For a given set of distinct points x_j and numbers y_j, the Lagrange polynomial is the polynomial of the least degree that at each point x_j assumes the corresponding value y_j...
associated with the points in the vector
(i.e. the vector of its coefficients is the vector containing the values ). Let be a polynomial obtained by slightly changing the coefficients of the original polynomial to . Let us consider the inequality: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 numberCondition number
In the field of numerical analysis, the condition number of a function with respect to an argument measures the asymptotically worst case of how much the function can change in proportion to small changes in the argument...
of the operator mapping each coefficient vector
to the set of the values of the polynomial with coefficients 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.