Remez algorithm

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.

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 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 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) (where i=1, 2, ... n+2 ), for the unknowns b_0, b_1...b_n and E. Use the b_i as coefficients to form a polynomial P_n . Find the set M of points of local maximum error |P_n(x) - f(x)| . 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 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 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 1 , ..., 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 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}) Rüdiger Günttner obtained from a sharper estimate for n \ge 40 \overline{\Lambda}_n(\hat{T}) - \underline{\Lambda}_n(\hat{T}) ==Detailed discussion== This section provides more information on the steps outlined above. In this section, the index i runs from 0 to n+1. Step 1: Given x_0, x_1, ... x_{n+1} , solve the linear system of n+2 equations b_0 + b_1 x_i+ ... +b_n x_i ^ n + (-1) ^ i E = f(x_i) (where i=0, 1, ... n+1 ), for the unknowns b_0, b_1, ...b_n and E. It should be clear that (-1)^i E in this equation makes sense only if the nodes x_0, ...,x_{n+1} are ordered, either strictly increasing or strictly decreasing. Then this linear system has a unique solution. (As is well known, not every linear system has a solution.) Also, the solution can be obtained with only O(n^2) arithmetic operations while a standard solver from the library would take O(n^3) operations. Here is the simple proof: Compute the standard n-th degree interpolant p_1(x) to f(x) at the first n+1 nodes and also the standard n-th degree interpolant p_2(x) to the ordinates (-1)^i p_1(x_i) = f(x_i), p_2(x_i) = (-1)^i, i = 0, ..., n. To this end, use each time Newton's interpolation formula with the divided differences of order 0, ...,n and O(n^2) arithmetic operations. The polynomial p_2(x) has its i-th zero between x_{i-1} and x_i,\ i=1, ...,n , and thus no further zeroes between x_n and x_{n+1} : p_2(x_n) and p_2(x_{n+1}) have the same sign (-1)^n . The linear combination p(x) := p_1 (x) - p_2(x)\!\cdot\!E is also a polynomial of degree n and p(x_i) = p_1(x_i) - p_2(x_i)\!\cdot\! E \ = \ f(x_i) - (-1)^i E,\ \ \ \ i =0, \ldots, n. This is the same as the equation above for i = 0, ... ,n and for any choice of E. The same equation for i = n+1 is p(x_{n+1}) \ = \ p_1(x_{n+1}) - p_2(x_{n+1})\!\cdot\!E \ = \ f(x_{n+1}) - (-1)^{n+1} E and needs special reasoning: solved for the variable E, it is the definition of E: E \ := \ \frac{p_1(x_{n+1}) - f(x_{n+1})}{p_2(x_{n+1}) + (-1)^n}. As mentioned above, the two terms in the denominator have same sign: E and thus p(x) \equiv b_0 + b_1x + \ldots + b_nx^n are always well-defined. The error at the given n+2 ordered nodes is positive and negative in turn because p(x_i) - f(x_i) \ = \ -(-1)^i E,\ \ i = 0, ... , n\!+\!1. The equioscillation theorem states that under this condition no polynomial of degree n exists with error less than E. Indeed, if such a polynomial existed, call it \tilde p(x) , then the difference p(x)-\tilde p(x) = (p(x) - f(x)) - (\tilde p(x) - f(x)) would still be positive/negative at the n+2 nodes x_i 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 b_0 + b_1x + ... + b_nx^n to p(x) . Step 3 improves upon the input nodes x_0, ..., x_{n+1} and their errors \pm E as follows. In each P-region, the current node x_i is replaced with the local maximizer \bar{x}_i and in each N-region x_i is replaced with the local minimizer. (Expect \bar{x}_0 at A, the \bar {x}_i near x_i , and \bar{x}_{n+1} at B.) No high precision is required here, the standard line search with a couple of quadratic fits should suffice. (See ) Let z_i := p(\bar{x}_i) - f(\bar{x}_i) . Each amplitude |z_i| is greater than or equal to E. The Theorem of de La Vallée Poussin and its proof also apply to z_0, ... ,z_{n+1} with \min\{|z_i|\} \geq E as the new lower bound for the best error possible with polynomials of degree n. Moreover, \max\{|z_i|\} comes in handy as an obvious upper bound for that best possible error. Step 4: With \min\,\{|z_i|\} and \max\,\{|z_i|\} as lower and upper bound for the best possible approximation error, one has a reliable stopping criterion: repeat the steps until \max\{|z_i|\} - \min\{|z_i|\} is sufficiently small or no longer decreases. These bounds indicate the progress. ==Variants== Some modifications of the algorithm are present on the literature. These include: Replacing more than one sample point with the locations of nearby maximum absolute differences. Replacing all of the sample points with in a single iteration with the locations of all, alternating sign, maximum differences. Using the relative error 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; Including zero-error point constraints. The Fraser-Hart variant, used to determine the best rational Chebyshev approximation. ==References== ==External links== Minimax Approximations and the Remez Algorithm, background chapter in the Boost Math Tools documentation, with link to an implementation in C++ Intro to DSP

Text derived from https://en.wikipedia.org/w/index.php?oldid=1365856298 under CC BY-SA 4.0; modifications have been made.