The Remez Algorithm: Minimax Polynomial Approximation

April 12, 2026 · Luciano Muratore

The Remez Algorithm is a classic numerical method to find the best polynomial approximation of a function. “Best” here means minimizing the maximum error, also known as the minimax problem.

Intuition Behind the Remez Algorithm

The goal is to find a polynomial $p(x)$ that minimizes the maximum error:

$\max_{x \in [a,b]} |f(x) - p(x)|$

Key idea: Equal Ripple (Equioscillation)

A minimax polynomial has an error curve that oscillates with equal positive and negative peaks, alternating signs, and identical magnitude. This creates an equal-ripple shape, meaning:

$p(x) - f(x) = \pm E, \text{ same amplitude everywhere.}$

Equal-Ripple Behavior of the Minimax Polynomial

Below is a visualization of the error curve. This oscillation pattern is the signature of the optimal Remez solution.

How the Algorithm Works (Intuitive View)

The algorithm works in iterative steps:

1. Pick initial points: Assume where the error should alternate.
2. Solve a linear system: Enforce alternating errors $p(x_i) - f(x_i) = (-1)^i E$.
3. Find true error peaks: Sample the interval and identify max positive/negative errors.
4. Replace points: Update with the true extremal points.
5. Iterate until error peaks stabilize.

This forces the polynomial to become perfectly balanced — the essence of the minimax solution.

Function: Polynomial Evaluation

The first building block is a simple function to evaluate a polynomial at a given point. It computes $p(x) = a_0 + a_1 x + \cdots + a_n x^n$ and is used repeatedly to evaluate the error $e(x) = p(x) - f(x)$.

Function: Gaussian Elimination Solver

To solve the Remez linear system for $[a_0, \ldots, a_n, E]^T$, we implement Gaussian elimination with partial pivoting for numerical stability.

Function: Find Extremal Points

This function detects where the error reaches its positive and negative peaks across the interval. These local extrema become the new alternation points for the next iteration.

Function: Build Remez Linear System

This function enforces the alternating error constraints at the current extremal points, constructing the matrix $A$ and vector $b$ for the linear system.

Function: One Remez Iteration

A single iteration builds the linear system, solves it via Gaussian elimination, and extracts new polynomial coefficients along with the current ripple amplitude $E$.

Function: Convergence Check

The algorithm stops when both the extremal points and the maximum error have stabilized within a given tolerance.

Function: Full Remez Algorithm

The top-level function orchestrates the full approximation loop — initializing extremal points, iterating, checking convergence, and returning the result.

Example Usage

As a demonstration, we approximate $\sin(x)$ on $[0, \pi]$ with a degree-5 minimax polynomial.

Summary

The Remez algorithm systematically forces the error to achieve perfect balance, producing an optimal uniform approximation. It covered:

• Intuition: equal-ripple minimax error
• Core components of the Remez algorithm
• Step-by-step modular implementation in C++
• Visual behavior of the optimal polynomial

Key takeaway: The Remez algorithm systematically forces the error to achieve perfect balance, producing an optimal uniform approximation.