Best uniform approximation

Given a family $A$ of approximating functions, a best uniform approximation to $f$ is an element $p\in A$ satisfying

For $0<k<1$, $x^k-x$ is nonnegative on $[0,1]$ and has its maximum $(1-k)k^{k/(1-k)}$ at $x=k^{1/(1-k)}$. Shifting the chord $x$ upwards by half this maximum creates three alternating errors of equal magnitude. The equioscillation theorem proves that the displayed line is the unique best uniform linear approximation, with error equal to its constant shift.

The Remez algorithm searches for a best uniform approximation by solving alternation equations on a reference set, finding extrema of the error, and exchanging reference points. For real degree-at-most-$n$ polynomials, the equioscillation theorem characterizes success by $n+2$ ordered alternating maximal errors. The alternating-reference error bound supplies a certified lower bound at each step, while the largest absolute error supplies an upper bound. Their gap measures how close the current polynomial is to optimal, provided the upper bound is established globally rather than only on a finite grid.

Suppose a reference polynomial $q$ has nonzero alternating errors of magnitude $|h|$, and another point $\eta$ has error magnitude $M>|h|$. Insert $\eta$ and delete a reference point so that the retained errors, in spatial order, still alternate. Solving the new alternation equations gives the displayed strict increase in reference height, with $w_j={\prod }_{k\ne j}(z_j-z_k{)}^{-1}$ on the new ordered set. To prove this, apply the order-$(n+1)$ divided difference to the old and new degree-at-most-$n$ polynomials. Both vanish, so the new signed height is the sum of the old errors times $w_j$, divided by ${\sum }_j(-1{)}^j{w}_j$. All these signed weight products have one sign. Its absolute value is therefore the positive weighted average of one value $M$ and $n+1$ values $|h|$.

For an interior $\eta$, replace the endpoint of its containing reference interval with the same error sign. If $\eta$ is exterior, replace the nearest endpoint when the signs agree; if they disagree, insert $\eta$ and drop the farthest endpoint. These rules preserve ordered alternation. The nearest point with the same sign need not be an adjacent point on an irregular grid, and an unqualified nearest-same-sign replacement does not ensure the strict increase.

Cosine substitution is an isometry from continuous functions on $[-1,1]$ to even continuous $2\pi$-periodic functions. It satisfies $\omega (\tilde{f},\delta )\le \omega (f,\delta )$ because cosine is Lipschitz continuous with constant one. Even degree-at-most-$n$ trigonometric polynomials correspond exactly to algebraic polynomials via $T_j(\cos \theta )=\cos (j\theta )$. Averaging a periodic approximant with its reflection cannot increase its error against an even target, so the algebraic and periodic best errors are equal.

If a bounded linear map $P$ reproduces every element of an approximating polynomial space $V$, then $f-Pf=(f-v)-P(f-v)$ for every $v\in V$. The triangle inequality and infimum over $v$ prove the displayed error bound. The same argument works for any linear approximating space, and applies in particular to de la Vallée Poussin sums.

For a fixed degree bound, two best approximating polynomials have a best approximating average. At each active point of that average their errors agree, hence the two polynomials agree. There must be at least two more active points than the degree: otherwise polynomial interpolation constructs a strictly improving sign-matching perturbation. The difference has too many zeros and must vanish. Finite-dimensional coefficient compactness also gives existence.

For real $f$, a candidate $u\in U\subset C(K,\mathbb{R})$, and active set $E=\{x:|f(x)-u(x)|=\Vert f-u{\Vert }_{\infty }\}$, the candidate is best precisely when every $v\in U$ has some $x\in E$ with $(f(x)-u(x))v(x)\le 0$. A direction with strictly matching error signs on the whole active set gives a uniformly improving small perturbation by compactness. Conversely one oppositely signed active value already prevents improvement. This criterion yields the Chebyshev alternation theorem.