Remez algorithm: Difference between revisions

Revision as of 01:42, 14 July 2020

Revision as of 03:22, 5 November 2020

Line 1:

{{Short description|Algorithm to approximate functions}}

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.<ref>E. Ya. Remez, "Sur la détermination des polynômes d'approximation de degré donnée", Comm. Soc. Math. Kharkov '''10''', 41 (1934);<br/>"Sur un procédé convergent d'approximations successives pour déterminer les polynômes d'approximation, Compt. Rend. Acad. Sc. '''198''', 2063 (1934);<br/>"Sur le calcul effectiv des polynômes d'approximation des Tschebyscheff", Compt. Rend. Acade. Sc. '''199''', 337 (1934).</ref>

A typical example of a Chebyshev space is the subspace of [[Chebyshev polynomials]] of order ''n'' in the [[Vector space|space]] of real [[continuous function]]s on an [[interval (mathematics)|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]].

Line 16:

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.<ref>{{cite journal |doi=10.1145/321281.321282 |first=W. |last=Fraser |title=A Survey of Methods of Computing Minimax and Near-Minimax Polynomial Approximations for Functions of a Single Independent Variable |journal=J. ACM |volume=12 |issue= |pages=295 |year=1965 }}</ref>

===On the choice of initialization===

Line 31:

:<math>\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)}.</math>

Theodore A. Kilgore,<ref>{{cite journal |doi=10.1016/0021-9045(78)90013-8 |first=T. A. |last=Kilgore |title=A characterization of the Lagrange interpolating projection with minimal Tchebycheff norm |journal=J. Approx. Theory |volume=24 |issue= |pages=273 |year=1978 |doi-access=free }}</ref> Carl de Boor, and Allan Pinkus<ref>{{cite journal |doi=10.1016/0021-9045(78)90014-X |first=C. |last=de Boor |first2=A. |last2=Pinkus |title=Proof of the conjectures of Bernstein and Erdös concerning the optimal nodes for polynomial interpolation |journal=[[Journal of Approximation Theory]] |volume=24 |issue= |pages=289 |year=1978 |doi-access=free }}</ref> proved that there exists a unique ''t''_''i'' for each ''L''_''n'', although not known explicitly for (ordinary) polynomials. Similarly, <math>\underline{\Lambda}_n(T) = \min_{-1 \le x \le 1} \lambda_n(T; x)</math>, and the optimality of a choice of nodes can be expressed as <math>\overline{\Lambda}_n - \underline{\Lambda}_n \ge 0.</math>

For Chebyshev nodes, which provides a suboptimal, but analytically explicit choice, the asymptotic behavior is known as<ref>{{cite journal |first=F. W. |last=Luttmann |first2=T. J. |last2=Rivlin |title=Some numerical experiments in the theory of polynomial interpolation |journal=IBM J. Res. Dev. |volume=9 |issue= |pages=187 |year=1965 |doi= 10.1147/rd.93.0187}}</ref>

:<math>\overline{\Lambda}_n(T) = \frac{2}{\pi} \log(n + 1) + \frac{2}{\pi}\left(\gamma + \log\frac{8}{\pi}\right) + \alpha_{n + 1}</math>

Line 45:

:<math>\overline{\Lambda}_n(T) \le \frac{2}{\pi} \log(n + 1) + 1</math>

Lev Brutman<ref>{{cite journal |doi=10.1137/0715046 |first=L. |last=Brutman |title=On the Lebesgue Function for Polynomial Interpolation |journal=SIAM J. Numer. Anal. |volume=15 |issue= |pages=694 |year=1978 }}</ref> obtained the bound for <math>n \ge 3</math>, and <math>\hat{T}</math> being the zeros of the expanded Chebyshev polynomials:

:<math>\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.</math>

Rüdiger Günttner<ref>{{cite journal |doi=10.1137/0717043 |first=R. |last=Günttner |title=Evaluation of Lebesgue Constants |journal=SIAM J. Numer. Anal. |volume=17 |issue= |pages=512 |year=1980 }}</ref> obtained from a sharper estimate for <math>n \ge 40</math>

:<math>\overline{\Lambda}_n(\hat{T}) - \underline{\Lambda}_n(\hat{T}) < 0.0196.</math>

Line 116:

==References==

{{reflistReflist}}

==External links==

*[https://www.boost.org/doc/libs/1_73_0/libs/math/doc/html/math_toolkit/remez.html The Remez Method], Boost Documentation

*[http://www.bores.com/courses/intro/filters/4_equi.htm Intro to DSP]

*{{MathWorld|urlname=RemezAlgorithm|title=Remez Algorithm|author=Aarts, Ronald M.; |author2=Bond, Charles; |author3=Mendelsohn, Phil; and|author4= Weisstein, Eric W.|name-list-style=amp}}

[[Category:Polynomials]]