Remez algorithm

The Remez algorithm (sometimes also called Remes algorithm, Remez/Remes exchange algorithm, or simply 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.

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 to be approximated and a set X of $n + 2$ sample points $x_1, x_2, ...,x_{n+2}$ in the approximation interval, usually the Chebyshev nodes linearly mapped to the interval. The steps are:

1. Solve the linear system of equations

$b_0 + b_1 x_i+ ... +b_n x_i ^ n + (-1) ^ i E = f(x_i)$ (where $i=1, 2, ... n+2$),

for the unknowns $b_0, b_1...b_n$ and E.

1. Use the $b_i$ as coefficients to form a polynomial $P_n$.
2. Find the set M of points of local maximum error $|P_n(x) - f(x)|$.
3. If the errors at every $m \in M$ are of equal magnitude and alternate in sign, then $P_n$ 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.

On the 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 L_n(f), it can be shown that this initial approximation is bounded by

$\lVert f - L_n(f)\rVert_\infty \le (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 L_n of the nodes (t₁, ..., t_n + 1) being

$\lVert L_n\rVert_\infty = \overline{\Lambda}_n(T) = \max_{-1 \le x \le 1} \lambda_n(T; x),$

T being the zeros of the Chebyshev polynomials, and the Lebesgue functions being

$\lambda_n(T; x) = \sum_{j = 1}^{n + 1} \left| l_j(x) \right|, \quad l_j(x) = \prod_{\stackrel{i = 1}{i \ne j}}^{n + 1} \frac{(x - t_i)}{(t_j - t_i)}.$

Theodore A. Kilgore, Carl de Boor, and Allan Pinkus proved that there exists a unique t_i for each L_n, although not known explicitly for (ordinary) polynomials. Similarly, $\underline{\Lambda}_n(T) = \min_{-1 \le x \le 1} \lambda_n(T; x)$, and the optimality of a choice of nodes can be expressed as $\overline{\Lambda}_n - \underline{\Lambda}_n \ge 0.$

For Chebyshev nodes, which provides a suboptimal, but analytically explicit choice, the asymptotic behavior is known as

$\overline{\Lambda}_n(T) = \frac{2}{\pi} \log(n + 1) + \frac{2}{\pi}\left(\gamma + \log\frac{8}{\pi}\right) + \alpha_{n + 1}$

(γ being the Euler-Mascheroni constant) with

$0 < \alpha_n < \frac{\pi}{72 n^2}$ for $n \ge 1,$

and upper bound

$\overline{\Lambda}_n(T) \le \frac{2}{\pi} \log(n + 1) + 1$

Lev Brutman obtained the bound for $n \ge 3$, and $\hat{T}$ being the zeros of the expanded Chebyshev polynomials:

$\overline{\Lambda}_n(\hat{T}) - \underline{\Lambda}_n(\hat{T}) < \overline{\Lambda}_3 - \frac{1}{6} \cot \frac{\pi}{8} + \frac{\pi}{64} \frac{1}{\sin^2(3\pi/16)} - \frac{2}{\pi}(\gamma - \log\pi)\approx 0.201.$

Rüdiger Günttner obtained from a sharper estimate for $n \ge 40$

$\overline{\Lambda}_n(\hat{T}) - \underline{\Lambda}_n(\hat{T}) < 0.0196.$

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.

See also

• Approximation theory

External links

• Intro to DSP
• Aarts, Ronald M.; Bond, Charles; Mendelsohn, Phil; and Weisstein, Eric W., "Remez Algorithm" from MathWorld.