Remez algorithm

From Wikipedia, the free encyclopedia

The Remez algorithm (sometimes also called Remes algorithm, Remez/Remes exchange algorithm), published by Evgeny Yakovlevich Remez in 1934[1] 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.

Contents

[edit] Procedure

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

  1. Set up a system of equations where each equation is of the form b0 + b1x...bnxn + ( − 1)iE = f(xi) for some x_i \in X, and solve the system for the unknowns (b0,b1...bn,E).
  2. Use the bis to create a polynomial Pn.
  3. Find the points of local maximum error (M) given by | Pn(x) − f(x) | .
  4. If every m \in M is of equal magnitude and alternates, Pn is the minimax approximation polynomial. If not, replace X with M and start over.

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[2].

[edit] On the choice of initialization

The reason for the Chebyshev nodes being a common choice for the initial approximation is in its behavior 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

\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 Ln of the nodes (t1, ..., tn + 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[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. 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[5]

\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[6]

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

Lev Brutman[7] 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[8] obtained from a sharper estimate for n \ge 40

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

[edit] 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.

[edit] 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).
  2. ^ W. Fraser, "A Survey of Methods of Computing Minimax and Near-Minimax Polynomial Approximations for Functions of a Single Independent Variable", J. ACM 12, 295 (1965).
  3. ^ T. A. Kilgore, "A characterization of the Lagrange interpolating projection with minimal Tchebycheff norm", J. Approx. Theory 24, 273 (1978).
  4. ^ C. de Boor and A. Pinkus, "Proof of the conjectures of Bernstein and Erdös concerning the optimal nodes for polynomial interpolation", J. Approx. Theory 24, 289 (1978).
  5. ^ F. W. Luttmann and T. J. Rivlin, "Some numerical experiments in the theory of polynomial interpolation", IBM J. Res. Develop. 9, 187 (1965).
  6. ^ T. Rivlin, "The Lebesgue constants for polynomial interpolation", in Proceedings of the Int. Conf. on Functional Analysis and Its Application, edited by H. G. Garnier et al. (Springer-Verlag, Berlin, 1974), p. 422; The Chebyshev polynomials (Wiley-Interscience, New York, 1974).
  7. ^ L. Brutman, "On the Lebesgue Function for Polynomial Interpolation", SIAM J. Numer. Anal. 15, 694 (1978).
  8. ^ R. Günttner, "Evaluation of Lebesgue Constants", SIAM J. Numer. Anal. 17, 512 (1980).

[edit] See also

[edit] External links