Lebesgue constant (interpolation)


Lebesgue constant (interpolation)

:"For other uses, see: Lebesgue constant."

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"). These constants are named after Henri Lebesgue.

Definition

We fix the interpolation nodes "x"0, …, "x""n" 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.

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.

Properties

The Lebesgue constant bounds the interpolation error:: |f-X(f)| le (Lambda_n(T)+1) |f-p^*|.

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) | le | f-p^{ast} | + | p^{ast} - 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 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::l_j(x) := prod_{egin{smallmatrix}i=0\ j eq iend{smallmatrix^{n} frac{x-x_i}{x_j-x_i} In fact, we have the Lebesgue function: lambda_n(x) = sum_{j=0}^n |l_j(x)|. and the Lebesgue constant (or Lebesgue number) for the grid is its maximum value:Lambda_n(T)=max_{xin [a,b] } lambda_n(x) 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: Lambda_n(T) sim frac{2^{n+1{e , n log n} quadmbox{as}quad n o infty. On the other hand, the Lebesgue constant grows only logarithmically if Chebyshev nodes are used, since we have: frac{2}{pi} log(n+1)+a < Lambda_n(T) < frac{2}{pi} log(n+1) + 1,where "a" = 0.9625&hellip;.

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 "t""i" denote the "i"th Chebyshev node. Then, define "s""i" = "t""i"cos(&pi;&frasl;2("n"+1)). For such nodes::Lambda_n(S)where "b" = 0.7219&hellip;.

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 &radic;8&frasl;3 &le; "a" &le; 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).

ensitivity 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"("t""i")). Let hat{p} be a polynomial obtained by slightly changing the coefficients "u" of the original polynomial "p". Let us consider the equation:: frac{|p-hat{p}{|p\leq Lambda_n(t)frac{|u-hat{u}{|uThis means that the (relative) error in the values of hat{p} 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.

References

* Citation
last = Brutman
first = L.
title = Lebesgue functions for polynomial interpolation &mdash; a survey
journal = Annals of Numerical Mathematics
volume = 4
year = 1997
pages = 111–127
issn = 1021-2655

* Citation
last = Smith
first = Simon J.
author-link=
title = Lebesgue constants in polynomial interpolation
journal = Annales Mathematicae et Informaticae
volume = 33
year = 2006
pages = 109–123
issn = 1787-5021
url = http://www.ektf.hu/tanszek/matematika/ami/2006/2006.htm

* [http://mathworld.wolfram.com/LebesgueConstants.html Lebesgue constants] on MathWorld.


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Lebesgue constant — Two kinds of constants are usually called Lebesgue constants (after Henri Lebesgue): * In the process of interpolation, the Lebesgue constants (with respect to a set of nodes) measure the precision of the polynomial interpolation at those nodes… …   Wikipedia

  • Lebesgue's lemma — For Lebesgue s lemma for open covers of compact spaces in topology see Lebesgue s number lemma In mathematics, Lebesgue s lemma is an important statement in approximation theory. It provides a bound for the projection error.tatementLet ( V , ||… …   Wikipedia

  • Henri Lebesgue — Infobox Scientist name =Henri Lebesgue box width =26em image width =225px caption = birth date =1875 06 28 birth place =Beauvais, France death date =death date and age|1941|7|26|1875|6|28 death place =Paris, France residence = citizenship =… …   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

  • List of numerical analysis topics — This is a list of numerical analysis topics, by Wikipedia page. Contents 1 General 2 Error 3 Elementary and special functions 4 Numerical linear algebra …   Wikipedia

  • List of mathematics articles (L) — NOTOC L L (complexity) L BFGS L² cohomology L function L game L notation L system L theory L Analyse des Infiniment Petits pour l Intelligence des Lignes Courbes L Hôpital s rule L(R) La Géométrie Labeled graph Labelled enumeration theorem Lack… …   Wikipedia

  • Remez algorithm — The Remez algorithm (sometimes also called Remes algorithm, Remez/Remes exchange algorithm), published by Evgeny Yakovlevich Remez in 1934 [E. Ya. Remez, Sur la détermination des polynômes d approximation de degré donnée , Comm. Soc. Math.… …   Wikipedia

  • Padua points — In polynomial interpolation of two variables, the Padua points are the first known example (and up to now the only one) of unisolvent point set (that is, the interpolating polynomial is unique) with minimal growth of their Lebesgue constant,… …   Wikipedia

  • FONCTIONS (REPRÉSENTATION ET APPROXIMATION DES) — Il arrive très souvent que, dans les problèmes issus des mathématiques ou des autres sciences, les fonctions qui interviennent soient définies par des procédés qui ne permettent pas d’étudier de manière efficace leurs propriétés. C’est le cas des …   Encyclopédie Universelle

  • Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… …   Wikipédia en Français


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.