Remez algorithm: Difference between revisions

Revision as of 21:53, 18 August 2023

Latest revision as of 00:18, 26 July 2025

(8 intermediate revisions by 8 users not shown)

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. ScSci. '''|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. ScSci. '''|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'''.<ref>{{cnCite journal |last=Chiang |first=Yi-Ling F. |date=DecemberNovember 1988 |title=A Modified Remes Algorithm |url=https://epubs.siam.org/doi/10.1137/0909072 |journal=SIAM Journal on Scientific and Statistical Computing |volume=9 |issue=6 |pages=1058–1072 |doi=10.1137/0909072 |issn=0196-5204|url-access=subscription 2022}}</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 23:

:<math>\lVert f - L_n(f)\rVert_\infty \le (1 + \lVert L_n\rVert_\infty) \inf_{p \in P_n} \lVert f - p\rVert</math>

with the norm or [[Lebesgue constant (interpolation)|Lebesgue constant]] of the Lagrange interpolation operator ''L''_''n'' of the nodes (''t''₁, ..., ''t''_{''n''&nbsp;+&nbsp;1}) being

:<math>\lVert L_n\rVert_\infty = \overline{\Lambda}_n(T) = \max_{-1 \le x \le 1} \lambda_n(T; x),</math>

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

<math>p_2(x)</math> to the ordinates <math>(-1)^i</math>

:<math>p_1(x_i) = f(x_i), p_2(x_i) = (-1)^i, i = 0, ..., n.</math>

To this end, use each time [[Newton polynomial|Newton's interpolation formula]] with the [[divided differences]] of order <math>0, ...,n</math> and <math>O(n^2)</math> arithmetic operations.

differences of order <math>0, ...,n</math> and <math>O(n^2)</math> arithmetic operations.

The polynomial <math>p_2(x)</math> has its ''i''-th zero between <math>x_{i-1}</math> and <math>x_i,\ i=1, ...,n</math>, and thus no further zeroes between <math>x_n</math> and <math>x_{n+1}</math>: <math>p_2(x_n)</math> and <math>p_2(x_{n+1})</math> have the same sign <math>(-1)^n</math>.

Line 83 ⟶ 82:

:<math>p(x_i) - f(x_i) \ = \ -(-1)^i E,\ \ i = 0, ... , n\!+\!1. </math>

The theorem of [[Charlesequioscillation Jean de la Vallée Poussin|de La Vallée Poussintheorem]] states that under this condition no polynomial of degree ''n'' exists with error less than ''E''. Indeed, if such a polynomial existed, call it <math>\tilde p(x)</math>, then the difference

<math>p(x)-\tilde p(x) = (p(x) - f(x)) - (\tilde p(x) - f(x))</math> would still be positive/negative at the ''n''+2 nodes <math>x_i</math> 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''.

Line 93 ⟶ 92:

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 ⟶ 103:

==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.|url-access=subscription }}</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" />

* The Fraser-Hart variant, used to determine the best rational Chebyshev approximation.<ref>{{Cite journal |last=Dunham |first=Charles B. |date=1975 |title=Convergence of the Fraser-Hart algorithm for rational Chebyshev approximation |url=https://www.ams.org/mcom/1975-29-132/S0025-5718-1975-0388732-9/ |journal=Mathematics of Computation |language=en |volume=29 |issue=132 |pages=1078–1082 |doi=10.1090/S0025-5718-1975-0388732-9 |issn=0025-5718|doi-access=free |url-access=subscription }}</ref>

== See also ==

{{Portal|Mathematics}}

* [[Approximation theory]]

* {{annotated link|Hadamard's lemma}}

* {{annotated link|Laurent series}}

* {{annotated link|Padé approximant}}

* {{annotated link|Newton series}}

* [[{{annotated link|Approximation theory]]}}

* {{annotated link|Function approximation}}

==References==