We fix the interpolation nodes and an interval containing all the interpolation nodes. The process of interpolation maps the function to a polynomial. This defines a mapping from the spaceC of all continuous functions on to itself. The map X is linear and it is a projection on the subspace of polynomials of degree or less. The Lebesgue constant is defined as the operator norm of X. This definition requires us to specify a norm on C. The uniform norm is usually the most convenient.
Properties
The Lebesgue constant bounds the interpolation error: let denote the best approximation of f among the polynomials of degree or less. In other words, minimizes among all p in Πn. Then We will here prove this statement with the maximum norm. by the triangle inequality. But X is a projection on Πn, so This finishes the proof since. 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 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 for the grid is its maximum value Nevertheless, it is not easy to find an explicit expression for.
Minimal Lebesgue constants
In the case of equidistant nodes, the Lebesgue constant grows exponentially. 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 We conclude again that Chebyshev nodes are a very good choice for polynomial interpolation. However, there is an easy transformation of Chebyshev nodes that gives a better Lebesgue constant. Let denote the -thChebyshev node. Then, define For such nodes: Those nodes are, however, not optimal and the search for an optimal set of nodes is still an intriguing topic in mathematics today. However, this set of nodes is optimal for interpolation over the set of times differentiable functions whose -th derivatives are bounded in absolute values by a constant as shown by N. S. Hoang. Using a computer, one can approximate the values of the minimal Lebesgue constants, here for the canonical interval : There are uncountable infinitely many sets of nodes in that minimize, for fixed > 1, the Lebesgue constant. Though if we assume that we always take −1 and 1 as nodes for interpolation, then such a set is unique and zero-symmetric. To illustrate this property, we shall see what happens when n = 2. One can check that each set of nodes of type is optimal when . If we force the set of nodes to be of the type, then b must equal 0. All arbitrary optimal sets of nodes in when n = 2 have been determined by F. Schurer, and in an alternative fashion by H.-J. Rack and R. Vajda. 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 4 interpolation nodes and the explicit value of the minimal Lebesgue constant are known. All arbitrary optimal sets of 4 interpolation nodes in when n = 3 have been explicitly determined, in two different but equivalent fashions, by H.-J. Rack and R. Vajda. The Padua points provide another set of nodes with slow growth and with the additional property of being a unisolvent point set.
Sensitivity of the values of a polynomial
The Lebesgue constants also arise in another problem. Let p be a polynomial of degree expressed in the Lagrangian form associated with the points in the vector t. Let be a polynomial obtained by slightly changing the coefficients u of the original polynomial p to. Consider the inequality: This means that the 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.
