Past exam of the approximation theory and finite element methods course of the University of Oxford / 2008 / A / 4 / a

The equioscillation theorem says that a best degree-at-most-$n$ polynomial approximation to a continuous real function on $[a,b]$ has $n+2$ ordered extreme-error points with alternating signs and equal absolute error. Conversely such alternation proves optimality. If the error is zero, the target is already a polynomial of the required degree.

For the single-point exchange in polynomial minimax approximation, start with $n+2$ ordered reference points $t_j$ and solve the linear systemfor the $n+1$ polynomial coefficients and $E$. Locate a point of largest absolute error on the interval. If its magnitude is no larger than $|E|$ within the desired tolerance, alternation certifies the approximation.

Otherwise insert that point and delete one old reference point so that the ordered signs still alternate. If the new point lies between two reference points, delete the neighboring point with the same error sign. If it lies outside the reference range, either replace the adjacent same-sign endpoint or, for opposite sign, insert it and drop the far endpoint. Solve again and repeat. This is the one-point Remez algorithm; a global extreme-error search is required for its stopping certificate, rather than merely checking the old reference points.