Past exam of the approximation theory and finite element methods course of the University of Oxford / 2010 / A / 3

Put $m={\min }_r|u(x_r)-q(x_r)|$ and $M={\max }_r|u(x_r)-q(x_r)|$. If the best uniform approximation had error below $m$, the values of $p_n^{\ast }-q$ would strictly alternate in sign at all $n+2$ reference points. The intermediate value theorem would give at least $n+1$ distinct roots of a polynomial of degree at most $n$, a contradiction. If $m=0$ the lower bound is immediate.

At least one reference point attains the global error maximum of $q$, so $M=\Vert u-q{\Vert }_{\infty }$. Optimality of $p_n^{\ast }$ gives the upper bound, and thereforeThis is the unequal-height version of the alternating-reference error bound.

Here the exchange point lies between adjacent reference points and has the same, positive error sign as the point it replaces. Hence the new set remains spatially ordered, and the old error at its points alternates in sign. Its magnitudes are $|h_0|$ everywhere except at $\eta$, where $M=u(\eta )-q(\eta )>|h_0|$.

Set $w_r={\prod }_{j\ne r}(z_r-z_j{)}^{-1}$. Apply the order-$(n+1)$ divided difference to $q$ and $v$; both vanish because their degrees are at most $n$. In the new alternation equations, all products $(-1{)}^r{w}_r$ have the same sign. Thus the single-point exchange in polynomial minimax approximation givesThe Remez algorithm repeatedly solves for the reference polynomial and common signed height, locates a larger error extreme, and performs an order-preserving exchange. The reference height bounds the optimum from below and the global error maximum bounds it from above. Their gap provides an optimality stopping certificate. A general implementation also needs the endpoint exchange rule when the new extreme lies outside the reference set.

For a line $p(x)=ax+b$, the error $e^x-ax-b$ is strictly convex. Its two endpoint maxima must agree, giving $a=e-1$. Its unique interior minimum is at $c=\log a\in (0,1)$. Equating its magnitude to the endpoint error givesThe errors at $0,c,1$ are respectively $E_1,-E_1,E_1$. The equioscillation theorem therefore certifies this best uniform approximation directly.

For degree above one, subtracting a general polynomial does not preserve convexity of the error. The required $n+2$ alternating extreme points include additional unknown interior points, and their derivative and equal-height equations form a coupled nonlinear problem. The simple endpoint-and-single-minimum calculation therefore does not extend as a direct higher-degree recipe.