Minimax Equioscillation Error

Worked Example: Target Cubic with Minimax Approximation

Let's consider approximating the cubic target function f(x) = x³ on the interval [-1, 1]. The Minimax approximation seeks to minimize the maximum absolute error. The optimal degree 1 minimax polynomial for x³ on [-1, 1] is 0.75x.

1. The target function is f(x) = x³.
2. The minimax approximation is P(x) = 0.75x.
3. The residual (error) function is E(x) = P(x) - f(x) = 0.75x - x³. This is a scaled Chebyshev polynomial of degree 3, T₃(x) / 4.
4. Evaluating at a probe point x = 0.5:
   • Target value: f(0.5) = (0.5)³ = 0.125.
   • Approximation value: P(0.5) = 0.75 * 0.5 = 0.375.
   • Signed residual: 0.375 - 0.125 = -0.25.
5. The uniform error on the interval is the maximum of |E(x)|. By the alternation theorem, E(x) achieves this maximum at exactly degree + 2 = 3 + 1 = 4 points on the interval, which are the extrema of T₃(x). These points are x = ±1 and x = ±0.5. At all these points, |E(x)| = 0.25. So the uniform error is 0.25.

Experiment

Open the Minimax Equioscillation Error module and follow these steps to see the differences between approximation methods.

1. Set the Target to "Cubic".
2. Set the Approximation to "Minimax". Observe the uniform error on the interval, which should be 0.25. The residual curve oscillates evenly between -0.25 and 0.25, hitting the extrema 4 times.
3. Change the Approximation to "Least squares". The error curve no longer equioscillates, and the uniform error on the interval increases, but the overall squared area under the residual curve is minimized.
4. Change the Approximation to "Node interpolation". The residual curve passes exactly through the endpoints (and other specific nodes depending on the target), but can result in much larger maximum errors between nodes.
5. Change the Probe x value to see the exact numeric values of the approximation, target, and signed residual at different points.

Limitations

This module uses pre-computed, bounded polynomial families for specific target functions (Quadratic, Cubic, Quartic). It does not implement a general Remez exchange algorithm solver, which would be required to find the minimax approximation for arbitrary continuous functions. The uniform error is calculated exactly using known critical points and endpoints for these specific families, rather than a generic sampled-grid maximum.

References

The properties of Minimax approximation and the equioscillation theorem are well-documented in Approximation Theory. For a comprehensive guide, see Chebfun Guide 4: Approximation Theory, which discusses polynomial interpolation, least-squares, and Chebyshev polynomials in depth.