Minimax approximation algorithm: Difference between revisions

Revision as of 21:17, 9 May 2016

Latest revision as of 13:10, 27 September 2021

(7 intermediate revisions by 6 users not shown)

Line 1:

A '''minimax approximation algorithm''' (or '''L^∞ approximation''' or '''uniform approximation''') is a method to find an approximation of a [[mathematical function]] that minimizes maximum error.<ref name="Muller_2010">{{cite book |author-last1=Muller |author-first1=Jean-Michel |author-last2=Brisebarre |author-first2=Nicolas |author-last3=de Dinechin |author-first3=Florent |author-last4=Jeannerod |author-first4=Claude-Pierre |author-last5=Lefèvre |author-first5=Vincent |author-last6=Melquiond |author-first6=Guillaume |author-last7=Revol |author-first7=Nathalie|author7-link=Nathalie Revol |author-last8=Stehlé |author-first8=Damien |author-last9=Torres |author-first9=Serge |title=Handbook of Floating-Point Arithmetic |url=https://archive.org/details/handbookfloating00mull_867 |url-access=limited |year=2010 |publisher=[[Birkhäuser]] |edition=1 |isbn=978-0-8176-4704-9<!-- print --> |doi=10.1007/978-0-8176-4705-6 |lccn=2009939668<!-- |id=ISBN 978-0-8176-4705-6 (online), ISBN-10 0-8176-4704-X (print) --> |page=[https://archive.org/details/handbookfloating00mull_867/page/n388 376]}}</ref> or '''uniform approximation'''<ref name="phillips">{{Cite book | doi = 10.1007/0-387-21682-0_2 | first = George M. | last = Phillips| chapter = Best Approximation | title = Interpolation and Approximation by Polynomials | url = https://archive.org/details/interpolationapp00phil_282 | url-access = limited | series = CMS Books in Mathematics | pages = 49–11[https://archive.org/details/interpolationapp00phil_282/page/n63 49]–11 | year = 2003 | publisher = Springer | isbn = 0-387-00215-4 | pmid = | pmc = }}</ref>) is a method to find an approximation of a [[mathematical function]] that minimizes maximum error.

For example, given a function <math>f</math> defined on the interval <math>[a,b]</math> and a degree bound <math>n</math>, a minimax polynomial approximation algorithm will find a polynomial <math>p</math> of degree at most <math>n</math> to minimize
::<math>\max_{a \leq x \leq b}|f(x)-p(x)|.</math><ref name="powell">{{cite book | chapter = 7: The theory of minimax approximation | first = M. J. D. | last= Powell | authorlinkauthor-link=Michael J. D. Powell | year = 1981 | publisher= Cambridge University Press | title = Approximation Theory and Methods | isbn = 0521295149}}</ref>

::<math>\max_{a \leq x \leq b}|f(x)-p(x)|.</math>

==Polynomial approximations==

Line 12:

One popular minimax approximation algorithm is the [[Remez algorithm]].

==References==

{{Reflist}}

==External links==

*[http://mathworld.wolfram.com/MinimaxApproximation.html Minimax approximation algorithm at MathWorld]

==References==

{{Reflist}}

[[Category:Numerical analysis]]

{{algorithm-stub}}