Must the approximation pass through the target at the endpoints?

No. The worked optimum has nonzero endpoint errors.

Does Remez always solve every approximation variant without difficulty?

No. Conditioning, extremum searches, rational poles, and added constraints can complicate the computation.

Is a smaller mean error enough to establish a better minimax result?

No. The relevant comparison is the maximum error under the specified metric.

AI Glossary / Mathematics and optimization / Intermediate

Minimax approximation algorithm

Definition

A minimax approximation algorithm finds an approximation that minimizes the largest error over a specified domain, within a chosen family of approximating functions. For example, it may choose a polynomial of degree at most n that best approximates a continuous function on a closed interval in maximum absolute error. Remez exchange is a prominent algorithm for this task.

What it means

A function approximation can have a small average error while still being poor near one point. Minimax approximation focuses directly on that worst error. The answer depends on the interval, the permitted approximation family, and whether error is absolute, relative, or weighted.
The term names a class of methods rather than one universal procedure. Polynomial, rational, constrained, and discrete-grid versions require different details. A result optimized only at sampled points need not be optimal over the continuous interval. Likewise, coefficients that are optimal in exact arithmetic can behave differently after rounding and finite-precision evaluation.

How it works

In the classical unweighted polynomial problem, a best approximation of degree at most n is characterized by an error curve attaining equal-magnitude alternating extremes at at least n+2 ordered points, unless the target is already represented exactly. This equioscillation property guides Remez-type methods.
Choose reference points, solve for coefficients and an alternating error level, then locate the actual error extrema. Exchange reference points to reflect those extrema and repeat. Checking the full interval is essential: equal errors at the current reference points do not prove that a larger error is absent elsewhere. Numerical implementations also need reliable extremum searches and stable solutions of the coefficient equations.

Three practical examples

A mathematical software library can replace a costly function with a polynomial or rational approximation that has a controlled worst error over a specified interval.
An embedded application can select a low-degree formula subject to accuracy requirements and limited computational resources.
A signal-processing design can use an appropriate weighted minimax formulation to balance the largest deviations across prescribed frequency bands.

Think of it this way

Think of adjusting a flexible strip so that its largest gaps above and below a target shape are balanced. Making one extreme smaller can make another larger, so the final compromise controls the worst gap. The analogy is limited because the permitted formulas and error metric impose precise mathematical restrictions; visual balance alone is not an optimality proof.

Worked example

Consider an original worked derivation of the best affine approximation p(x)=ax+b to f(x)=x² on [0,1]. Begin with reference points zero, 0.4, and one, and require the errors f−p to alternate as E, −E, E.
The endpoint equations are −b=E and 1−a−b=E, so a=1 and b=−E. At 0.4, the error is 0.16−0.4+E=−E. Therefore E=0.12 and the first candidate is p(x)=x−0.12.
Its error is e(x)=x²−x+0.12. The derivative 2x−1 vanishes at x=0.5, where the error is −0.13. The endpoints have error +0.12. Thus the reference level 0.12 understates the actual maximum absolute error 0.13.
Exchange the interior reference point for 0.5 and solve again. The endpoint equations still give a=1 and b=−E. At the midpoint, 0.25−0.5+E=−E gives E=0.125. The resulting approximation is p(x)=x−1/8.
Its error is +1/8 at zero, −1/8 at one-half, and +1/8 at one. Since the quadratic error has its sole interior extremum at one-half, its absolute value nowhere exceeds 1/8. These three alternating extrema satisfy the degree-one minimax criterion.
By comparison, the line p(x)=x matches both endpoints exactly, but its midpoint error is −1/4. Checking only endpoints would incorrectly suggest perfect accuracy. The minimax line deliberately accepts endpoint error to halve the worst error across the whole interval. The example is an exact hand-derived exchange calculation, not a performance test of a particular software implementation.

Illustrative case study

In a fictional sensor-software team, engineers replace a nonlinear conversion formula with an inexpensive approximation over the sensor's calibrated range. They record the interval and error criterion, then validate the rounded coefficients in the target numeric format. They also test behavior outside the calibrated range rather than extending the minimax claim automatically. This is an illustrative design process, not evidence of a certified sensor or measured speed improvement.

Common misconceptions and mistakes

Minimax approximation is different from interpolation, which matches selected points, and from least squares, which minimizes an aggregate squared error. None of those objectives is universally preferable; they answer different accuracy questions.
Relative error needs special care where the target function vanishes, because dividing by a zero target is undefined. Rational approximations also require attention to denominator zeros and poles. Finally, a visually convincing alternation pattern is insufficient if another unexamined extremum has greater magnitude. A reliable bound concerns the entire stated domain and the actual evaluated formula.

Business use

For a business software product, this approach can help make a computational cost versus accuracy tradeoff explicit. Specify the maximum tolerated error, input range, representation, and consequences of exceeding the range. Test both approximation error and floating-point evaluation error. A theoretical minimax result for real coefficients is only one part of delivering a trustworthy numerical component.

Check your understanding

Why was the first candidate x−0.12 not optimal?

Answer: Its midpoint error had magnitude 0.13, larger than the 0.12 level at the selected reference points. Moving the reference point exposed and corrected that imbalance.

Related terms

Remez algorithm
Least squares
Equioscillation
Uniform norm
Chebyshev approximation
Polynomial approximation
Rational approximation
Interpolation

Learn next

Approximate x² by a constant on [0,1]. Determine the constant that balances the endpoint errors and compare its maximum error with the affine approximation's 1/8. This shows how enlarging the permitted family changes the best achievable bound.

Sources

Primary technical reference: NIST Digital Library of Mathematical Functions, section 3.11(i), minimax polynomial approximation and alternating extrema: https://dlmf.nist.gov/3.11 . Implementation background: Boost Math Remez documentation: https://www.boost.org/doc/libs/boost_1_85_0/libs/math/doc/html/math_toolkit/remez.html . The exchange example here is original.

Previous: Minimax Next: Minimax decision