4
$\begingroup$

Let $T = \{ x_0,\ldots,x_n \}$ be a set of $n+1$ different points in the real interval $[a,b]$. Let $X_T$ be the associated interpolation operator on $C[a,b]$: it takes a function $f \in C[a,b]$ into the unique degree-$n$ polynomial $p$ such that $p(x_i) = f(x_i)$ for $i = 0,\ldots,n$. The Lebesgue constant $\Lambda_T$ is the operator norm of $X_T$ with respect to infinity norm $||\cdot||$; that is, $\Lambda_T = \sup_{f \in C[a,b]} ||X_T f||/||f||$.

Besides some well-referenced facts about $\Lambda_T$, the wikipedia entry for the Lebesgue constant includes a section with the title Sensitivity analysis of the values of a polynomial, where (if I understood correctly) the following is claimed without proof or reference:

Let $p$ be a degree-$n$ polynomial and let $u = (u_0,\ldots,u_n)$ where $u_i = p(x_i)$ for $i = 0,\ldots,n$. Let $\hat{u} = (\hat{u}_0,\ldots,\hat{u}_n)$ be a perturbation of $u$ and let $\hat{p}$ be the unique degree-$n$ polynomial such that $\hat{u}_i = \hat{p}(x_i)$ for $i = 0,\ldots,n$. Then: $$ \frac{||p-\hat{p}||}{||p||} \leq \Lambda_T \frac{||u-\hat{u}||}{||u||}. $$ In words, this is meant to say that $\Lambda_T$ can be viewed as the condition number of the process of polynomial interpolation (with respect to some sort of relative error).

Question: Is this an immediate consequence of the definition? Could anyone explain or provide a reference that proves the claim? Unfortunately the entry in the wikipedia gives no reference for it, and the given references (for the other parts of the article) do not seem to include this fact either (or I was not able to find it).

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

A direct consequence of the definition, yes. Note that $X_T$ is in fact defined on $C(T)$, with the same norm $\Lambda _ T$ w.r.to the infinity norm $\|u\|$ (viewing the vector $u:=(u_0,\dots,u_n)$ as an element of $C(T)$, taking $x _ j$ to $ u _ j$). Then $u=p{|_ T}$ so $p=X_T u$ by the uniqueness; and $\hat p = X_T \hat u $ by definition. Therefore $\|p\|\ge \|p{|_ T}\|=\|u\|$ and $\|p-\hat p\| = \|X_T (u-\hat u)\| \le\Lambda _ T \|u-\hat u\|$.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks! But why are the norms the same? I see the inequality $\sup_u ||X_T u||/||u|| \leq \sup_f ||X_T f||/||f||$ but I don't see the converse. In any case, the inequality that I do see is the one that is needed for the argument, so my question is answered. $\endgroup$
    – Back
    Commented Jan 9, 2013 at 23:06
  • $\begingroup$ The equality comes from the fact that, when computing the operator norm of $X_T$ on $C([a,b])$ you may equally do the supremum over all functions $f$ that attain their uniform norm on $T$. This does not change the value of the supremum, and gives the operator norm of $X_T$ on $C(T)$. $\endgroup$
    – Pietro Majer
    Commented Jan 10, 2013 at 9:17
  • $\begingroup$ Yes. Now I see the converse inequality as well ($||f|| \geq ||f|_T||$). $\endgroup$
    – Back
    Commented Jan 12, 2013 at 9:39

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .