Does minimax mean minimum average error?

No. It minimizes the largest absolute error under the specified formulation.

Does the algorithm always return a nonconstant degree-n polynomial?

No. The permitted degree is an upper bound; symmetry or the target itself can produce a lower-degree result.

Is an alternating error plot enough?

It is useful evidence, but a claim about the entire interval also requires reliable control of errors between displayed sample points.

AI Glossary / Mathematics and optimization / Advanced

Remez algorithm

Definition

The Remez algorithm is an iterative method for finding an approximation whose largest absolute error over a specified interval is as small as possible. In its classical polynomial form, the target is a continuous real function and the approximation is restricted to a chosen maximum degree. The resulting approximation is called minimax, best uniform or Chebyshev approximation.

What it means

Suppose a small polynomial must replace an expensive function. Minimizing average squared error can leave a relatively large error in a narrow region. Minimax approximation instead asks how small the worst error can be across the entire declared interval. Degree, interval and error definition are part of the problem. A result optimized for absolute error need not be best for relative error, and a polynomial that works well inside the interval may behave poorly outside it.

How it works

For degree at most n, select n + 2 ordered reference points. Solve for a trial polynomial and an error level so that the target minus the polynomial alternates between that level and its negative at those points. Locate the actual extreme errors across the interval, then exchange reference points to improve the approximation while maintaining the required alternating pattern. Repeat until the discrepancy between the reference error level and the largest actual error is sufficiently small. The underlying alternation theorem characterizes the best polynomial by at least n + 2 equal-magnitude, alternating extreme errors. Numerical implementations must reliably locate extrema and represent the polynomial without excessive rounding error; solving only the reference equations is insufficient.

Three practical examples

A numerical-software team can construct a low-degree approximation to a smooth function on a limited argument range, then separately test floating-point evaluation error.
A hardware designer can investigate whether a fixed polynomial degree meets a maximum absolute-error budget before choosing an implementation.
Digital-filter design uses related exchange ideas, notably in the Parks - McClellan method. Its frequency-domain formulation and weighting require their own setup rather than simply copying an unweighted polynomial example.

Think of it this way

Think of adjusting a straight shelf above a curved surface so that the largest upward and downward gaps are balanced as tightly as possible. Reducing one extreme gap may enlarge another, so the final arrangement balances the limiting gaps. The analogy illustrates a worst-gap objective. A polynomial approximation is a mathematical function, however, and the alternation requirement depends on its permitted degree rather than on the physical stiffness of a shelf.

Worked example

Approximate f(x) = x² on [−1, 1] using p(x) = ax + b, a polynomial of degree at most one. Choose reference points −1, 0 and 1 and require errors +E, −E and +E. The equations are 1 + a − b = E, −b = −E and 1 − a − b = E. They give a = 0 and b = E = 0.5. Thus p(x) = 0.5, and the error x² − 0.5 stays between −0.5 and +0.5, reaching those extremes in alternating order at the three reference points. The worst absolute error is therefore 0.5. To check optimality directly, any line has error −b at the center, while the average of its two endpoint errors is 1 − b. Its largest absolute error must be at least max(|b|, |1 − b|), which is never below 0.5. The constant approximation attains that bound. At x = 2 its error is 3.5: the interval guarantee does not extend beyond the declared domain.

Illustrative case study

In a fictional project, Marlin Controls evaluates a polynomial replacement for a slowly changing calibration curve. The engineer specifies the input interval and allowed error before choosing a degree. After constructing a minimax candidate, the team checks coefficients as stored on the target device and tests behavior at the interval boundaries. Inputs outside the validated range trigger a separate handling rule. This illustrates a review process, not a claim that the substitution achieved a measured speedup or satisfied a real product requirement.

Common misconceptions and mistakes

Remez is not ordinary interpolation: it deliberately permits nonzero, balanced errors rather than forcing agreement at all reference points. A degree-n best approximation can have more than n + 2 alternating extreme points; the characterization requires a suitable set of that size, not exactly that many overall. A dense sampled grid can miss narrow error peaks, so a grid-only maximum is not automatically a continuous-interval certificate. Rational approximations and weighted problems need the appropriate formulation and conditions. Coefficient rounding can also change the error after an accurate real-arithmetic approximation has been found.

Business use

Use the method when a worst-case approximation budget matters and the input domain can be specified. Record the target function, interval, degree, weighting if any, stopping tolerance and validation method. Separate approximation error from arithmetic rounding, measurement uncertainty and model mismatch. If the target is itself a fitted empirical curve, matching that curve closely does not establish accuracy against reality. Compare execution cost and verified error with simpler alternatives before adopting the approximation, and retain a clear policy for inputs outside its domain.

Check your understanding

A degree-one approximation to x² on [−1, 1] has constant value 0.5. Is it disqualified because its slope is zero?

Answer: No. Constants belong to the space of polynomials of degree at most one, and this one achieves the optimal worst error of 0.5.

Related terms

minimax approximation
equioscillation
Chebyshev polynomial
polynomial interpolation
rational approximation
Parks–McClellan algorithm

Learn next

plot the worked error curve and compare it with the error from p(x) = 0 and p(x) = 1. Then study how a Remez implementation locates extrema, including endpoints, and how it checks the gap between a trial error level and the global maximum.

Global maximum

Sources

Sources: Ricardo Pachón and Lloyd N. Trefethen, Barycentric-Remez Algorithms for Best Polynomial Approximation in the Chebfun System, https://www.chebfun.org/publications/remez.pdf ; Chebfun, Best Approximation with the REMEZ Command, https://www.chebfun.org/examples/approx/BestApprox.html . The quadratic calculation, direct optimality check and fictional calibration workflow are original illustrations.

Previous: Remediation Next: Remosaic