# Lebesgue constant as condition number of polynomial interpolation

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).

-

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\|$.
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. –  Back Jan 9 '13 at 23:06
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)$. –  Pietro Majer Jan 10 '13 at 9:17
Yes. Now I see the converse inequality as well ($||f|| \geq ||f|_T||$). –  Back Jan 12 '13 at 9:39