Remez algorithm

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.