Remez algorithm - Revision history

Paul2520: clears CS1 date error(s) (via WP:JWB)

2025-05-28T20:20:41Z

← Previous revision		Revision as of 20:20, 28 May 2025
Line 1:		Line 1:
	{{Short description\|Algorithm to approximate functions}}		{{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''<sub>∞</sub> 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. Sci. \|volume=198 \|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 effectif des polynomes d'approximation de Tschebyschef \|journal=Compt. Rend. Acad. Sci. \|volume=199 \|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>{{Cite journal \|last=Chiang \|first=Yi-Ling F. \|date=1988~~-11~~ \|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}}</ref>		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''<sub>∞</sub> 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. Sci. \|volume=198 \|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 effectif des polynomes d'approximation de Tschebyschef \|journal=Compt. Rend. Acad. Sci. \|volume=199 \|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>{{Cite journal \|last=Chiang \|first=Yi-Ling F. \|date=November 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}}</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]].		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]].

81.103.250.124: Add an instance of the Remez Algorithm being referred to as "Remes Algorithm"

2025-05-28T16:11:18Z

Add an instance of the Remez Algorithm being referred to as "Remes Algorithm"

← Previous revision		Revision as of 16:11, 28 May 2025
Line 1:		Line 1:
	{{Short description\|Algorithm to approximate functions}}		{{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''<sub>∞</sub> 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. Sci. \|volume=198 \|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 effectif des polynomes d'approximation de Tschebyschef \|journal=Compt. Rend. Acad. Sci. \|volume=199 \|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~~}}		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''<sub>∞</sub> 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. Sci. \|volume=198 \|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 effectif des polynomes d'approximation de Tschebyschef \|journal=Compt. Rend. Acad. Sci. \|volume=199 \|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>{{Cite journal \|last=Chiang \|first=Yi-Ling F. \|date=1988-11 \|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}}</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]].		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]].

Headbomb: ce

2025-02-07T01:38:48Z

← Previous revision		Revision as of 01:38, 7 February 2025
Line 1:		Line 1:
	{{Short description\|Algorithm to approximate functions}}		{{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''<sub>∞</sub> 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 \|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 effectif des polynomes d'approximation de Tschebyschef \|journal=Compt. Rend. Acad. Sc. \|volume=199 \|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}}		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''<sub>∞</sub> 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. Sci. \|volume=198 \|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 effectif des polynomes d'approximation de Tschebyschef \|journal=Compt. Rend. Acad. Sci. \|volume=199 \|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]].		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]].

RDBrown: →cite journal, book, update editions, tweak cites | Add: authors 1-1. Removed parameters. Some additions/deletions were parameter name changes. | Use this tool. Report bugs. | #UCB_Gadget

2025-01-10T03:25:28Z

→cite journal, book, update editions, tweak cites | Add: authors 1-1. Removed parameters. Some additions/deletions were parameter name changes. | Use this tool. Report bugs. | #UCB_Gadget

Devharsh: /* See also */

2024-07-16T18:56:23Z

Comp.arch at 17:42, 15 January 2024

2024-01-15T17:42:01Z

← Previous revision		Revision as of 17:42, 15 January 2024
Line 1:		Line 1:
	{{Short description\|Algorithm to approximate functions}}		{{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''<sub>∞</sub> 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> It is sometimes referred to as '''Remes algorithm''' or '''Reme algorithm'''.{{cn\|date=December 2022}}		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''<sub>∞</sub> 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> 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]].		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:		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>		:<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''<sub>''n''</sub> of the nodes (''t''<sub>1</sub>, ..., ''t''<sub>''n'' + 1</sub>) being		with the norm or [[Lebesgue constant]] of the Lagrange interpolation operator ''L''<sub>''n''</sub> of the nodes (''t''<sub>1</sub>, ..., ''t''<sub>''n'' + 1</sub>) being

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

OAbot: Open access bot: doi updated in citation with #oabot.

2023-08-18T21:53:59Z

Open access bot: doi updated in citation with #oabot.

← Previous revision		Revision as of 21:53, 18 August 2023
Line 31:		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>		:<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 \|pages=273–288 \|year=1978 \|issue=4 \|doi-access=~~free~~ }}</ref> Carl de Boor, and Allan Pinkus<ref>{{cite journal \|doi=10.1016/0021-9045(78)90014-X \|first1=C. \|last1=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 \|pages=289–303 \|year=1978 \|issue=4 \|doi-access=free }}</ref> proved that there exists a unique ''t''<sub>''i''</sub> for each ''L''<sub>''n''</sub>, 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>		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 \|pages=273–288 \|year=1978 \|issue=4 \|doi-access= }}</ref> Carl de Boor, and Allan Pinkus<ref>{{cite journal \|doi=10.1016/0021-9045(78)90014-X \|first1=C. \|last1=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 \|pages=289–303 \|year=1978 \|issue=4 \|doi-access=free }}</ref> proved that there exists a unique ''t''<sub>''i''</sub> for each ''L''<sub>''n''</sub>, 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 \|first1=F. W. \|last1=Luttmann \|first2=T. J. \|last2=Rivlin \|title=Some numerical experiments in the theory of polynomial interpolation \|journal=IBM J. Res. Dev. \|volume=9 \|pages=187–191 \|year=1965 \|issue=3 \|doi= 10.1147/rd.93.0187}}</ref>		For Chebyshev nodes, which provides a suboptimal, but analytically explicit choice, the asymptotic behavior is known as<ref>{{cite journal \|first1=F. W. \|last1=Luttmann \|first2=T. J. \|last2=Rivlin \|title=Some numerical experiments in the theory of polynomial interpolation \|journal=IBM J. Res. Dev. \|volume=9 \|pages=187–191 \|year=1965 \|issue=3 \|doi= 10.1147/rd.93.0187}}</ref>

OAbot: Open access bot: doi added to citation with #oabot.

2023-08-12T19:06:19Z

Open access bot: doi added to citation with #oabot.

← Previous revision		Revision as of 19:06, 12 August 2023
Line 16:		Line 16:
	The result is called the polynomial of best approximation or the [[minimax approximation algorithm]].		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 \|pages=295–314 \|year=1965 \|issue=3 \|s2cid=2736060 }}</ref>		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 \|pages=295–314 \|year=1965 \|issue=3 \|s2cid=2736060 \|doi-access=free }}</ref>

	===Choice of initialization===		===Choice of initialization===

OAbot: Open access bot: doi added to citation with #oabot.

2023-01-29T14:50:53Z

Open access bot: doi added to citation with #oabot.

← Previous revision		Revision as of 14:50, 29 January 2023
Line 110:		Line 110:
	* 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;		* 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" />		* 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}}</ref>		* 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 }}</ref>

	==See also==		==See also==

Citation bot: Add: s2cid, authors 1-1. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by SemperIocundus | #UCB_webform 979/2500

2023-01-03T19:10:31Z

Add: s2cid, authors 1-1. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by SemperIocundus | #UCB_webform 979/2500

← Previous revision		Revision as of 19:10, 3 January 2023
Line 104:		Line 104:

	==Variants==		==Variants==
	Some modifications of the algorithm are present on the literature.<ref>{{Citation \|~~last~~=Egidi \|~~first~~=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 \|editor2-last=Kvasov \|editor2-first=Dmitri E.}}</ref> These include:		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 more than one sample point with the locations of nearby maximum absolute differences.{{Citation needed\|date=March 2022}}

← Previous revision		Revision as of 20:20, 28 May 2025
Line 1:		Line 1:
	{{Short description\|Algorithm to approximate functions}}		{{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''<sub>∞</sub> 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. Sci. \|volume=198 \|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 effectif des polynomes d'approximation de Tschebyschef \|journal=Compt. Rend. Acad. Sci. \|volume=199 \|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>{{Cite journal \|last=Chiang \|first=Yi-Ling F. \|date=1988~~-11~~ \|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}}</ref>		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''<sub>∞</sub> 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. Sci. \|volume=198 \|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 effectif des polynomes d'approximation de Tschebyschef \|journal=Compt. Rend. Acad. Sci. \|volume=199 \|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>{{Cite journal \|last=Chiang \|first=Yi-Ling F. \|date=November 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}}</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]].		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]].

← Previous revision		Revision as of 16:11, 28 May 2025
Line 1:		Line 1:
	{{Short description\|Algorithm to approximate functions}}		{{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''<sub>∞</sub> 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. Sci. \|volume=198 \|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 effectif des polynomes d'approximation de Tschebyschef \|journal=Compt. Rend. Acad. Sci. \|volume=199 \|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~~}}		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''<sub>∞</sub> 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. Sci. \|volume=198 \|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 effectif des polynomes d'approximation de Tschebyschef \|journal=Compt. Rend. Acad. Sci. \|volume=199 \|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>{{Cite journal \|last=Chiang \|first=Yi-Ling F. \|date=1988-11 \|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}}</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]].		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]].

← Previous revision		Revision as of 01:38, 7 February 2025
Line 1:		Line 1:
	{{Short description\|Algorithm to approximate functions}}		{{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''<sub>∞</sub> 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 \|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 effectif des polynomes d'approximation de Tschebyschef \|journal=Compt. Rend. Acad. Sc. \|volume=199 \|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}}		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''<sub>∞</sub> 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. Sci. \|volume=198 \|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 effectif des polynomes d'approximation de Tschebyschef \|journal=Compt. Rend. Acad. Sci. \|volume=199 \|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]].		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]].

← Previous revision		Revision as of 18:56, 16 July 2024
Line 112:		Line 112:
	* 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 }}</ref>		* 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 }}</ref>

	==See also==		== 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==		==References==

← Previous revision		Revision as of 21:53, 18 August 2023
Line 31:		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>		:<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 \|pages=273–288 \|year=1978 \|issue=4 \|doi-access=~~free~~ }}</ref> Carl de Boor, and Allan Pinkus<ref>{{cite journal \|doi=10.1016/0021-9045(78)90014-X \|first1=C. \|last1=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 \|pages=289–303 \|year=1978 \|issue=4 \|doi-access=free }}</ref> proved that there exists a unique ''t''<sub>''i''</sub> for each ''L''<sub>''n''</sub>, 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>		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 \|pages=273–288 \|year=1978 \|issue=4 \|doi-access= }}</ref> Carl de Boor, and Allan Pinkus<ref>{{cite journal \|doi=10.1016/0021-9045(78)90014-X \|first1=C. \|last1=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 \|pages=289–303 \|year=1978 \|issue=4 \|doi-access=free }}</ref> proved that there exists a unique ''t''<sub>''i''</sub> for each ''L''<sub>''n''</sub>, 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 \|first1=F. W. \|last1=Luttmann \|first2=T. J. \|last2=Rivlin \|title=Some numerical experiments in the theory of polynomial interpolation \|journal=IBM J. Res. Dev. \|volume=9 \|pages=187–191 \|year=1965 \|issue=3 \|doi= 10.1147/rd.93.0187}}</ref>		For Chebyshev nodes, which provides a suboptimal, but analytically explicit choice, the asymptotic behavior is known as<ref>{{cite journal \|first1=F. W. \|last1=Luttmann \|first2=T. J. \|last2=Rivlin \|title=Some numerical experiments in the theory of polynomial interpolation \|journal=IBM J. Res. Dev. \|volume=9 \|pages=187–191 \|year=1965 \|issue=3 \|doi= 10.1147/rd.93.0187}}</ref>

← Previous revision		Revision as of 03:25, 10 January 2025
Line 1:		Line 1:
	{{Short description\|Algorithm to approximate functions}}		{{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''<sub>∞</sub> 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> It is sometimes referred to as '''Remes algorithm''' or '''Reme algorithm'''.{{cn\|date=December 2022}}		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''<sub>∞</sub> 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 \|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 effectif des polynomes d'approximation de Tschebyschef \|journal=Compt. Rend. Acad. Sc. \|volume=199 \|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]].		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:		Line 41:
	:<math>0 < \alpha_n < \frac{\pi}{72 n^2}</math> for <math>n \ge 1,</math>		:<math>0 < \alpha_n < \frac{\pi}{72 n^2}</math> for <math>n \ge 1,</math>

	and upper bound<ref>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).~~</ref>		and upper bound<ref>{{cite book \|first=T.J. \|last=Rivlin \|chapter=The lebesgue constants for polynomial interpolation \|chapter-url=https://link.springer.com/chapter/10.1007/BFb0063594 \|doi=10.1007/BFb0063594 \|series=Lecture Notes in Mathematics \|volume=399 \|editor-last=Garnir \|editor-first=H.G. \|editor2-last=Unni \|editor2-first=K.R. \|editor3-last=Williamson \|editor3-first=J.H. \|title=Functional Analysis and its Applications \|publisher=Springer \|date=1974 \|isbn=978-3-540-37827-3 \|pages=422–437 }}</ref>

	:<math>\overline{\Lambda}_n(T) \le \frac{2}{\pi} \log(n + 1) + 1</math>		:<math>\overline{\Lambda}_n(T) \le \frac{2}{\pi} \log(n + 1) + 1</math>
Line 93:		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,		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~~ G. ~~Luenberger:~~ ~~''Introduction~~ to Linear and Nonlinear Programming~~'',~~ ~~Addison-Wesley~~ ~~Publishing~~ ~~Company~~ ~~1973~~.</ref>)		the standard ''line search'' with a couple of ''quadratic fits'' should suffice. (See <ref>{{cite book \|last1=Luenberger \|first1=D.G. \|last2=Ye \|first2=Y. \|chapter=Basic Descent Methods \|chapter-url=https://link.springer.com/chapter/10.1007/978-0-387-74503-9_8 \|title=Linear and Nonlinear Programming \|publisher=Springer \|edition=3rd \|series=International Series 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		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:		Line 104:

	==Variants==		==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:		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 \|doi=10.1007/978-3-030-39081-5_7 \|isbn=978-3-030-39080-8 \|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 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">Temes, G.C.; Barcilon, V.; Marshall, F.C. ~~(1973). "~~The optimization of bandlimited systems". ''Proceedings of the IEEE~~''.~~ ~~'''~~61~~'''~~ (2): 196–234. ~~[[Doi~~ ~~(identifier)~~\|doi~~]]:~~10.1109/PROC.1973.9004. ~~[[ISSN (identifier)~~\|~~ISSN]] ~~0018-9219.</ref>		* 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. \|title=The optimization of bandlimited systems \|journal=Proceedings of the IEEE \|volume=61 \|issue=2 \|pages=196–234 \|date=1973 \|doi=10.1109/PROC.1973.9004 \|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;		* 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" />		* Including zero-error point constraints.<ref name="toobs" />