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.
[citation needed] 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.
The Remez algorithm starts with the function
A review of technicalities in implementing the Remez algorithm is given by W.
[2] 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 with the norm or Lebesgue constant of the Lagrange interpolation operator Ln of the nodes (t1, ..., tn + 1) being T being the zeros of the Chebyshev polynomials, and the Lebesgue functions being Theodore A. Kilgore,[3] Carl de Boor, and Allan Pinkus[4] proved that there exists a unique ti for each Ln, although not known explicitly for (ordinary) polynomials.
, and the optimality of a choice of nodes can be expressed as
For Chebyshev nodes, which provides a suboptimal, but analytically explicit choice, the asymptotic behavior is known as[5] (γ being the Euler–Mascheroni constant) with and upper bound[6] Lev Brutman[7] obtained the bound for
being the zeros of the expanded Chebyshev polynomials: Rüdiger Günttner[8] obtained from a sharper estimate for
This section provides more information on the steps outlined above.
, solve the linear system of n+2 equations It should be clear that
in this equation makes sense only if the nodes
Then this linear system has a unique solution.
arithmetic operations while a standard solver from the library would take
Here is the simple proof: Compute the standard n-th degree interpolant
at the first n+1 nodes and also the standard n-th degree interpolant
To this end, use each time Newton's interpolation formula with the divided differences of order
and for any choice of E. The same equation for i = n+1 is As mentioned above, the two terms in the denominator have same sign: E and thus
The error at the given n+2 ordered nodes is positive and negative in turn because The theorem of de La Vallée Poussin states that under this condition no polynomial of degree n exists with error less than E. Indeed, if such a polynomial existed, call it
and therefore have at least n+1 zeros which is impossible for a polynomial of degree n. Thus, this E is a lower bound for the minimum error which can be achieved with polynomials of degree n. Step 2 changes the notation from
Step 3 improves upon the input nodes
No high precision is required here, the standard line search with a couple of quadratic fits should suffice.
is greater than or equal to E. The Theorem of de La Vallée Poussin and its proof also apply to
as the new lower bound for the best error possible with polynomials of degree n. Moreover,
comes in handy as an obvious upper bound for that best possible error.
as lower and upper bound for the best possible approximation error, one has a reliable stopping criterion: repeat the steps until
is sufficiently small or no longer decreases.
Some modifications of the algorithm are present on the literature.