Carl de Boor poses the following problem in his A Practical Guide to Splines (1978 - Chapter II, p. 38, problem 4):
The calculation of $||g|| = \max\{|g(x)| : a \le x \le b\}$ is a nontrivial task. Prove that, for $p \in \mathbb{P}_n$, though, a good and cheap approximation to $||p||$ is provided by $||p||_C := \max\{ |p(\tau_i^C)| : i = 1, ..., n \}$, with $(\tau_i^C)$ given by (6) [Chebyshev points]. [...]
My first question is, if $p$ is really taken to be as general as a random polynomial of order $n$ or if we have to limit ourselves to polynomial interpolations of a function $g:\mathbb{R}\rightarrow\mathbb{R}$ at the Chebyshev points $\tau = [\tau_1^C, ..., \tau_n^C]$?
My second question is, how an approximation $||p||_C$, as defined above, could possibly cover all the arbitrary behaviour between two successive interpolation points $\tau_i^C$ and $\tau_{i+1}^C$.
I have a whole stack of properties which could come at hand for a proof but I am just not able to combine them in a suitable manner. Here they are:
A polynomial $p$ (interpolated at Chebyshev points) is bounded by the approximated function's norm scaled by an order-dependent norm of the Lesbesgue function $||\lambda_n^C||$: $$ ||p|| \le ||g|| \cdot ||\lambda_n^C|| $$
The error $||g - p||$ of a Chebyshev-based approximation is bounded as follows: $$ ||g-p|| \le \max_{a\le x\le b} \left| \frac{g^{(n)}(x)}{n!} \right| \frac{2(b-a)^2}{4^n}$$
A Chebyshev-based polynomial interpolation can be represented like this:
$$p(x) = \sum_{i=1}^n \alpha_i T_{i-1}(y(x)),$$
where
$$\alpha_{i+1} := \sum_{j=1}^n \frac{g(\tau_j^C)T_i(\tau_j^*)}{< T_i, T_i >}, \qquad y(x) := \frac{2x - (a+b)}{(b-a)}, \qquad \tau_j^* = \cos\left(\frac{(2j - 1)\pi}{2n}\right).$$
and the polynomial interpolation agrees with the approximated function at the $\tau_i^C$:
$$ p(\tau^C_i) = g(\tau^C_i) \qquad \forall i = 1, ..., n$$
Can anybody help me putting the pieces together?
How about this one:
Define a piecewise linear function $$ g(x) = \begin{cases} p(\tau_1^C) & \text{if } x < \tau_1^C \\ p(\tau_i^C) & \text{if } x = \tau_i^C \\ p(\tau_i^C) + \frac{x - \tau_i^C}{\tau_{i+1}^C - \tau_i^C} \left( p(\tau_{i+1}^C) - p(\tau_i^C) \right) & \text{if } x \in (\tau_i^C, \tau_{i+1}^C) \\ p(\tau_n^C) & \text{if } x > \tau_n^C \\ \end{cases}, $$ where $\tau_i^C$ are Chebyshev points such that $$ \max_{a \le x \le b} |g(x)| = \max_{1\le i \le n} |p(\tau_i^C)|$$ and $$ p(x) = \sum_{i=1}^n \alpha_i T_{i-1}(y(x)) $$ as given in the question above. From the upper bound of $p$ we then have $$ ||p|| \le ||g|| \cdot ||\lambda_n^C|| = \max_{1\le i \le n} |p(\tau_i^C)| \cdot ||\lambda_n^C||, $$ with $$ ||\lambda_n^C|| := \max_{a\le x \le b} \sum_{i=1}^n |l_i^C(x)|, $$ where $l_i^C(x)$ is the Lagrange polynomial based on Chebyshev points.
This qualifies $||p||_C = \max\limits_{1\le i\le n} p(\tau_i^C)$ as a good approximation of $||p||$.
Does that make sense?