The relationship between the best uniform approximation and chebyshev interpolant

Question

I am learning Approximation Theory. I know one polynormial of degree at most $n$ is the best uniform approximation of the function $f \in \mathcal C[a,b]$ if and only if there is exist a set of $n+2$ distinct points $\{x_i\}_{i=0}^{n+1}$ such that $$ f(x_i) - p(x_i) = \lambda \sigma_i ||f-p|| , i = 0,\dots,n+1 $$ where $\sigma_i=(-1)^i$ and $\lambda =1 \text{ or } -1$ is fixed. So there are at lest $n+1$ points such that $f = p$ , thus the best uniform approximation of $f$ can be interpreted as a interpolant polynomail on these $n+1$ points. And I know the Chebyshev interpolant has the good behavior. My question is if the Chebyshev interpolant is the best uniform approximation in some special cases? What the relationship between the best uniform approximation and chebyshev interpolant or chebyshev polynomials? Thanks!

Answer 1

The best approximation (also called minimax polynomial) polynomial $p^*(x)$ you refer to can indeed be interpreted as the interpolant of $n+1$ mesh points $x_i$, $0\leq i\leq n$ such that $f(x_i)=p^*(x_i)$. However, these mesh points are not known in general. But the benefit of this viewpoint is that it allows us to state the following theorem:

Let $f \in C^{n+1}([a,b])$ with $p^*(x)$ the optimal approximation of $f$ of degree at most $n$. Then there exists $n+1$ points $x_i \in [a,b]$, $0\leq i \leq n$, such that for all $x\in[a,b]$

$$f(x)-p^*(x)=\frac{(x-x_0)\cdots(x-x_n)}{(n+1)!}f^{n+1}(\xi)$$

for some $\xi \in [a,b]$.

This is just the interpolation error. But remember the mesh points $x_i$ are unknown. However, we can ask how close to $p^*(x)$ can we get? This amounts to asking what is the "best" mesh $\tilde{x}_i$, $0\leq i \leq n,$ that minimizes the above error i.e. the mesh that minimizes $\|\omega(x)\|_{\infty}$ where $\omega(x)=(x-x_0)\cdots(x-x_n)$ since this is the only part of the error expression that depends on the mesh. To answer this question, one first considers the interval $[-1,1]$. The "best" mesh on this interval is precisely the Chebyshev points (see https://en.wikipedia.org/wiki/Chebyshev_nodes) and the corresponding interpolant of this mesh is the so-called near-minimax polynomial of degree $n+1$. One then uses a change of variables to get from $[-1,1]$ to an arbitrary interval $[a,b]$.

This link has some relevant information and examples: http://homepage.math.uiowa.edu/~whan/3800.d/S4-6.pdf

Answer 2

Let $f \in \mathcal C^{n+1}[-1,1]$ and $Q_n(x)$ be the minmax approximation. Let $E_n(f)$ denote $||f-Q_n||$, where the norm is sup norm or max norm. Because $Q_n$ is the minimax approximation, by above theorem, $Q_n$ is a polynomial interpolation of $n$ degree on $n+1$ points which we denote by $\{y_i\}_{i=0}^{n}$. The truncation error is following $$ f - Q_n = \frac {f^{(n+1)}(\xi_x)}{(n+1)!}w(x) $$ where $w(x) = \prod_{i=0}^{n}(x-y_i)$, exist $x_0$ $$ \max_{-1\le x\le 1} |w(x)| = |w(x_0)| $$ Now we estimate low bound of $E_n(f)$ $$ \begin{align} E_n(f) &= \max_{-1\le x\le 1} |f(x)-Q_n(x)| \\ & \ge \left|\frac {f^{(n+1)}(\xi_{x_{0}})}{(n+1)!}\right||w(x_0)| \\ &= \left|\frac {f^{(n+1)}(\xi_{x_{0}})}{(n+1)!}\right|\max_{-1\le x\le 1} |w(x)|\\ &\ge \min_{-1\le x\le 1}|f^{(n+1)}(\xi_x)|\frac {1}{2^n(n+1)!} \end{align} $$ The up bound of the error of chebyshev interpolation $P_n(x)$ to $f$ on $x\in [-1,1]$ is following $$ \begin{align} ||f - P_n(x)||&=\max_{-1\le x\le 1}|f - P_n(x)| \\ &= \max_{-1\le x\le 1}\left|\frac {f^{(n+1)}(\xi_x)}{(n+1)!}\frac{T_{n+1}(x)}{2^n}\right| \\ &\le \max_{-1\le x\le 1}|f^{(n+1)}(\xi_x)|\frac {1}{2^n(n+1)!} \end{align} $$ where $T_n(x)$ is the chebyshev polynomial of $n$ degree and $$E_n(f)\le ||f-P_n||\le\max_{-1\le x\le 1}|f^{(n+1)}(\xi_x)|\frac {1}{2^n(n+1)!}$$

Finally, we conclude following $$ \min_{-1\le x\le 1}|f^{(n+1)}(\xi_x)|\frac {1}{2^n(n+1)!}\le E_n(f)\le\max_{-1\le x\le 1}|f^{(n+1)}(\xi_x)|\frac {1}{2^n(n+1)!} $$ so if $f^{(n+1)}(x)$ variate small on $[-1,1]$, then chebyshev interpolation is near minimax approximation.