Best approximation and Chebyshev equioscillation

Let f be a real continuous function on a nondegenerate compact interval $[a,b]$, and let $\mathcal P_n$ contain real polynomials of degree at most n, with $n\ge0$. Its best uniform error is the infimum of the maximum absolute residual. The word uniform matters: every point has equal authority to set the objective, regardless of how narrow the region of large error is. Changing the interval or introducing a weight changes the optimization problem.

A best polynomial exists. A minimizing sequence can be restricted to a bounded uniform-norm ball because its residuals are bounded and f is fixed. On the finite-dimensional space $\mathcal P_n$, all norms are equivalent, so its coefficient vectors are bounded and have a convergent subsequence. The corresponding polynomials converge uniformly; continuity of the norm then attains the infimum. Compactness of the interval and finite dimension each play a role here; arbitrary infinite-dimensional approximation sets need not have this property.

For positive error, the polynomial equioscillation theorem says p is the unique best approximant exactly when there are at least n+2 ordered points where its residual reaches the same maximal magnitude with alternating signs. We state the full characterization; the next argument proves its optimality direction. If f already belongs to the polynomial space, its best approximation is f itself with error zero, and the positive-error formulation is unnecessary.

Suppose another polynomial q had strictly smaller uniform error than p. At each alternating extremum, q−p would have to have the sign of f−p, otherwise q would fail to reduce that extreme residual. The intermediate value theorem would force a root of q−p between every consecutive pair, giving at least n+1 distinct roots. A nonzero polynomial of degree at most n cannot have so many roots. This contradiction proves no strict improvement is possible; uniqueness is an additional part of the full equioscillation theorem.

Interpolating n+1 data points enforces zero residual at those nodes, whereas minimax approximation balances extreme residuals across the entire interval. The two can agree in special cases but solve different constraints. Chebyshev polynomials provide useful exact examples: $T_m(\cos\theta)=\cos(m\theta)$ has magnitude at most one on the interval $[-1,1]$ and alternates between plus and minus one at its successive extremal points. A scaled copy can therefore expose an exact best error.

In computation, a dense residual plot suggests extremal locations but does not certify that a sharper spike was missed. A rigorous certificate also bounds the residual between the sampled points, perhaps by derivative information or validated interval computations. Numerical Remez methods search for alternating extrema, but a successful-looking iteration is not a proof without a checked error bound. Separate the mathematical optimization problem, its exact optimality certificate, and the numerical method used to search for that certificate.