The Remez algorithm or Remez exchange algorithm, published by Evgeny Yakovlevich Remez in 1934, is an iterative algorithm used to find simple approximations to functions, specifically, approximations by functions in a Chebyshev space that are the best in the uniform norm L∞ sense. It is sometimes referred to as Remes algorithm or Reme algorithm. A typical example of a Chebyshev space is the subspace of Chebyshev polynomials of order n in the space of real continuous functions on an interval, C[a, b]. The polynomial of best approximation within a given subspace is defined to be the one that minimizes the maximum absolute difference between the polynomial and the function. In this case, the form of the solution is precised by the equioscillation theorem.
Procedure The Remez algorithm starts with the function f {\displaystyle f} to be approximated and a set X {\displaystyle X} of n + 2 {\displaystyle n+2} sample points x 1 , x 2 , . . . , x n + 2 {\displaystyle x_{1},x_{2},...,x_{n+2}} in the approximation interval, usually the extrema of Chebyshev polynomial linearly mapped to the interval. The steps are:
Solve the linear system of equations
b 0 + b 1 x i + . . . + b n x i n + ( − 1 ) i E = f ( x i ) {\displaystyle b_{0}+b_{1}x_{i}+...+b_{n}x_{i}^{n}+(-1)^{i}E=f(x_{i})} (where i = 1 , 2 , . . . n + 2 {\displaystyle i=1,2,...n+2} ), for the unknowns b 0 , b 1 . . . b n {\displaystyle b_{0},b_{1}...b_{n}} and E. Use the b i {\displaystyle b_{i}} as coefficients to form a polynomial P n {\displaystyle P_{n}} . Find the set M {\displaystyle M} of points of local maximum error | P n ( x ) − f ( x ) | {\displaystyle |P_{n}(x)-f(x)|} . If the errors at every m ∈ M {\displaystyle m\in M} are of equal magnitude and alternate in sign, then P n {\displaystyle P_{n}} is the minimax approximation polynomial. If not, replace X {\displaystyle X} with M {\displaystyle M} and repeat the steps above. The result is called the polynomial of best approximation or the minimax approximation algorithm. A review of technicalities in implementing the Remez algorithm is given by W. Fraser.
Choice of initialization The Chebyshev nodes are a common choice for the initial approximation because of their role in the theory of polynomial interpolation. For the initialization of the optimization problem for function f by the Lagrange interpolant Ln(f), it can be shown that this initial approximation is bounded by
‖ f − L n ( f ) ‖ ∞ ≤ ( 1 + ‖ L n ‖ ∞ ) inf p ∈ P n ‖ f − p ‖ {\displaystyle \lVert f-L_{n}(f)\rVert _{\infty }\leq (1+\lVert L_{n}\rVert _{\infty })\inf _{p\in P_{n}}\lVert f-p\rVert }
with the norm or Lebesgue constant of the Lagrange interpolation operator Ln of the nodes (t1, ..., tn + 1) being
‖ L n ‖ ∞ = Λ ¯ n ( T ) = max − 1 ≤ x ≤ 1 λ n ( T ; x ) , {\displaystyle \lVert L_{n}\rVert _{\infty }={\overline {\Lambda }}_{n}(T)=\max _{-1\leq x\leq 1}\lambda _{n}(T;x),}
T being the zeros of the Chebyshev polynomials, and the Lebesgue functions being
… excerpt ends here. Continue reading the full article.
