Remez algorithm

The Remez algorithm, published by Evgeny Yakovlevich Remez in 1934^[1] (also called the Remez exchange algorithm) is an iterative algorithm for best approximation in the uniform norm L_∞ in the Chebyshev space. A typical example of Chebyshev space is the subspace of polynomial of order n in the space of real continuous function on an interval, C[a, b].

The polynomial of best approximation of a given degree is defined to be the one that minimizes the maximum absolute difference between the polynomial and the function.

Procedure

The Remez algorithm starts with a set of sample points in the approximation interval, usually the Chebyshev nodes linearly mapped to the interval.

1. A polynomial approximation of the function at the sample points is obtained through Lagrange interpolation.
2. The difference between the approximation and the function is measured across the interval. The point where the difference has the largest absolute value is found.
3. The sample point nearest the ___location of the maximum absolute difference is replaced with the ___location of the maximum absolute difference.
4. The process is repeated until all sample points converge to the points of maximum absolute difference, and the sign of the difference between the function and the polynomial alternates.

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

Variants

Sometimes more than one sample point is replaced at the same time with the locations of nearby maximum absolute differences.

Sometimes relative error is used to measure the difference between the approximation and the function, especially if the approximation will be used to compute the function on a computer which uses floating-point arithmetic.

References

1. E. Ya. Remez, "Sur la détermination des polynômes d'approximation de degré donnée", Comm. Soc. Math. Kharkov 10, 41 (1934);
   "Sur un procédé convergent d'approximations successives pour déterminer les polynômes d'approximation, Compt. Rend. Acad. Sc. 198, 2063 (1934);
   "Sur le calcul effectiv des polynômes d'approximation des Tschebyscheff, Compt. Rend. Acade. Sc. 199, 337 (1934).

External links

• Intro to DSP
• Remez Algorithm from MathWorld