We discussed calculating the minimax polynomial using Remez’s Algorithm, but we overlooked some subtleties. While the algorithm does converge, the coefficients will likely not be representable in finite precision arithmetic (let alone in \(p\) characters). So in reality, we will want to run the algorithm at a higher precision \(q\). But then how do we reduce it to precision \(p\)? Will simple rounding suffice? And does running Remez’s on a finite precision arithmetic even give us the minimax polynomial?
The answer is that mere rounding can result in a much larger minimax error. And there often will exist a polynomial of the same order and precision \(p\) that has a much lower error.
Moreover, keep in mind that the equioscillating property of the error you see for the minimax polynomial need not be preserved for the polynomial in precision \(p\). With rounding of coefficients, the property may be far, far, off (e.g. no oscillation at all).
There are other considerations: There may be some properties of \(f\) that we would like to preserve (e.g. even/odd function). Now when it comes to the minimax polynomial, it maintains the even/odd behavior (assuming even/odd with respect to 0). For proof:
Assume \(f(x)\) is odd. Let \(P(x)\) be the minimax polynomial approximation of \(f(x)\). Set \(Q(x)=-P(-x)\). Now note that \(|f(x)-P(x)|=|f(x)+Q(-x)|=|-f(-x)+Q(-x)|\) which equals \(|Q(-x)-f(-x)|\). Now when we calculate the minimax norm, we are looking at the max error over the whole domain of \(x\). So I might as well look at \(|Q(x)-f(x)|\) (assuming a symmetric domain). The max error is the same: \(\epsilon\). And from the uniqueness of this polynomial, we have that \(Q(x)=P(x)\). It follows that \(P\) is odd.
Now when we do this numerically, though, we may get small deviations to this property (e.g. an odd function may have tiny coefficients of even powers). We usually throw these away as noise.
Now beware. If your function is odd/even, don’t calculate the polynomial using only the positive domain. Use a symmetric domain around 0. It’s not going to magically preserve evenness. Or rather, you may actually get a good approximation, but do not discard odd/even powered coefficients! Then you get a poor approximation.