Remez algorithm: Difference between revisions

Revision as of 18:56, 16 July 2024

Revision as of 03:25, 10 January 2025

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>{{cite journal |author-link=Evgeny Yakovlevich Remez |first=E. Ya. |last=Remez, "|title=Sur la détermination des polynômes d'approximation de degré donnée", |journal=Comm. Soc. Math. Kharkov '''|volume=10''', |pages=41 (|date=1934); }}<br/>"{{cite journal |author-mask=1 |first=E. |last=Remes (Remez) |title=Sur un procédé convergent d'approximations successives pour déterminer les polynômes d'approximation, |journal=Compt. Rend. Acad. Sc. '''|volume=198''', 2063|pages=2063–5 (|language=fr |date=1934); |url=https://gallica.bnf.fr/ark:/12148/bpt6k31506/f2063.item}}<br/>"{{cite journal |author-mask=1 |first=E. |last=Remes (Remez) |title=Sur le calcul effectiveffectif des polynômespolynomes d'approximation desde Tschebyscheff",Tschebyschef |journal=Compt. Rend. AcadeAcad. Sc. '''|volume=199''', 337|issue= (|pages=337–340 |language=fr |date=1934) |url=https://gallica.bnf.fr/ark:/12148/bpt6k3151h/f337.item}}</ref> It is sometimes referred to as '''Remes algorithm''' or '''Reme algorithm'''.{{cn|date=December 2022}}

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 41:

:<math>0 < \alpha_n < \frac{\pi}{72 n^2}</math> for <math>n \ge 1,</math>

and upper bound<ref>{{cite book |first=T.J. |last=Rivlin, "|chapter=The Lebesguelebesgue constants for polynomial interpolation", in ''Proceedings of the Int|chapter-url=https://link.springer.com/chapter/10.1007/BFb0063594 Conf|doi=10.1007/BFb0063594 on|series=Lecture FunctionalNotes Analysisin andMathematics Its|volume=399 Application'', edited by|editor-last=Garnir |editor-first=H. G. Garnier|editor2-last=Unni ''et al|editor2-first=K.R.'' (Springer|editor3-Verlag,last=Williamson Berlin,|editor3-first=J.H. 1974),|title=Functional p.Analysis 422;and ''Theits ChebyshevApplications polynomials''|publisher=Springer (Wiley|date=1974 |isbn=978-Interscience,3-540-37827-3 New|pages=422–437 York, 1974).}}</ref>

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

Line 93:

In each P-region, the current node <math>x_i</math> is replaced with the local maximizer <math>\bar{x}_i</math> and in each N-region <math>x_i</math> is replaced with the local minimizer. (Expect <math>\bar{x}_0</math> at ''A'', the <math>\bar {x}_i</math> near <math>x_i</math>, and <math>\bar{x}_{n+1}</math> at ''B''.) No high precision is required here,

the standard ''line search'' with a couple of ''quadratic fits'' should suffice. (See <ref>David{{cite book |last1=Luenberger |first1=D.G. Luenberger:|last2=Ye ''Introduction|first2=Y. to|chapter=Basic Descent Methods |chapter-url=https://link.springer.com/chapter/10.1007/978-0-387-74503-9_8 |title=Linear and Nonlinear Programming'', Addison-Wesley|publisher=Springer Publishing|edition=3rd Company|series=International 1973Series in Operations Research & Management Science |volume=116 |date=2008 |isbn=978-0-387-74503-9 |pages=215–262 |doi=10.1007/978-0-387-74503-9_8}}</ref>)

Let <math>z_i := p(\bar{x}_i) - f(\bar{x}_i)</math>. Each amplitude <math>|z_i|</math> is greater than or equal to ''E''. The Theorem of ''de La Vallée Poussin'' and its proof also

Line 104:

==Variants==

Some modifications of the algorithm are present on the literature.<ref>{{Citation |last1=Egidi |first1=Nadaniela |title=A New Remez-Type Algorithm for Best Polynomial Approximation |date=2020 |url=http://link.springer.com/10.1007/978-3-030-39081-5_7 |work=Numerical Computations: Theory and Algorithms |volume=11973 |pages=56–69 |editor-last=Sergeyev |editor-first=Yaroslav D. |place=Cham |publisher=Springer International Publishing |language=en |doi=10.1007/978-3-030-39081-5_7 |isbn=978-3-030-39080-8 |access-date=2022-03-19 |last2=Fatone |first2=Lorella |last3=Misici |first3=Luciano |s2cid=211159177 |editor2-last=Kvasov |editor2-first=Dmitri E.}}</ref> These include:

* Replacing more than one sample point with the locations of nearby maximum absolute differences.{{Citation needed|date=March 2022}}

* Replacing all of the sample points with in a single iteration with the locations of all, alternating sign, maximum differences.<ref name="toobs">{{cite journal |last1=Temes, |first1=G.C.; |last2=Barcilon, |first2=V.; |last3=Marshall, |first3=F.C. (1973). "|title=The optimization of bandlimited systems". ''|journal=Proceedings of the IEEE''. '''|volume=61''' (|issue=2): |pages=196–234. [[Doi|date=1973 (identifier)|doi]]:=10.1109/PROC.1973.9004. [[ISSN (identifier)|ISSN]]&nbsp;issn=0018-9219.}}</ref>

* 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.<ref name="toobs" />