= Solution
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)^rw_r$ have the same sign. Thus the <single-point exchange in polynomial minimax approximation> gives
$$
\boxed{|h_1|=|h_0|+\frac{|w_s|}{\sum_r|w_r|}(M-|h_0|)>|h_0|.}
$$
The <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.
Back to article page
