Remez Algorithm - Procedure

Procedure

The Remez algorithm starts with the function f to be approximated and a set X of sample points in the approximation interval, usually the Chebyshev nodes linearly mapped to the interval. The steps are:

1. Solve the linear system of equations

(where ),

for the unknowns and E.

1. Use the as coefficients to form a polynomial .
2. Find the set M of points of local maximum error .
3. If the errors at every are of equal magnitude and alternate in sign, then is the minimax approximation polynomial. If not, replace X with M and repeat the steps above.

The result is called the polynomial of best approximation, the Chebyshev approximation, or the minimax approximation.

A review of technicalities in implementing the Remez algorithm is given by W. Fraser.