|
A '''minimax approximation algorithm''' (or '''L<sup>∞</sup> approximation'''<ref>{{cite bookor |'''uniform titleapproximation''') =is Handbooka ofmethod Floating-Pointto Arithmeticfind |an pageapproximation =of 376a |[[mathematical publisherfunction]] =that Springer |minimizes yearmaximum error.<ref name="Muller_2010">{{cite 2009book | isbn author-last1= 081764704XMuller | author-first1=Jean-Michel | last1=Muller|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 displayof Floating-authors=1Point }}<Arithmetic |url=https:/ref>/archive.org/details/handbookfloating00mull_867 or|url-access=limited '''uniform|year=2010 approximation'''<ref|publisher=[[Birkhäuser]] name|edition="phillips">{{cite doi1 |isbn=978-0-8176-4704-9<!-- print --> |doi=10.1007/978-0-3878176-216824705-0_2}}6 |lccn=2009939668</ref>)!-- is|id=ISBN a method which aims to find an approximation such that the maximum error is minimized. Suppose we seek to978-0-8176-4705-6 approximate the function f(''x''online), byISBN a0-8176-4704-X function p(''x''print) on the interval--> |page=[''a'',''b'']https://archive.org/details/handbookfloating00mull_867/page/n388 Then a minimax approximation algorithm will aim to find a function p(''x'') to minimize376]}}</ref><ref name="powellphillips">{{citeCite book | chapterdoi = 7:10.1007/0-387-21682-0_2 The| theoryfirst of= minimaxGeorge approximationM. | firstlast = M.Phillips| J.chapter D.= Best Approximation | lasttitle = PowellInterpolation and Approximation by Polynomials | authorlinkurl =Michael Jhttps://archive.org/details/interpolationapp00phil_282 D.| Powellurl-access = limited | yearseries = 1981CMS Books in Mathematics | publisherpages = Cambridge[https://archive.org/details/interpolationapp00phil_282/page/n63 University Press49]–11 | titleyear = Approximation2003 Theory| andpublisher Methods= Springer | isbn = 05212951490-387-00215-4 }}</ref>
::<math>\max_{a \leq x \leq b}|f(x)-p(x)|.</math>
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 | author-link=Michael J. D. Powell | year = 1981 | publisher= Cambridge University Press | title = Approximation Theory and Methods | isbn = 0521295149}}</ref>
==Polynomial approximations==
The [[Weierstrass approximation theorem]] states that every continuous function defined on a closed interval [a,b] can be uniformly approximated as closely as desired by a polynomial function.<ref name="phillips" />
For practical work it is often desirable to minimize the maximum absolute or relative error of a polynomial fit for any given number of terms in an effort to reduce computational expense of repeated evaluation.
Polynomial expansions such as the [[Taylor series]] expansion are often convenient for theoretical work but less useful for practical applications. ForTruncated practical[[Chebyshev workseries]], ithowever, isclosely often desirable to minimizeapproximate the maximum absolute or relative error of aminimax polynomial fit for any given number of terms in an effort to reduce computational expense of repeated evaluation.
One popular minimax approximation algorithm is the [[Remez algorithm]]. [[Chebyshev polynomials of the first kind]] closely approximate the minimax polynomial.<ref>{{cite web | url = http://mathworld.wolfram.com/MinimaxPolynomial.html | title = Minimax Polynomial | publisher = Wolfram MathWorld | accessdate= 2012-09-03}}</ref>
==External links==
*[http://mathworld.wolfram.com/MinimaxApproximation.html Minimax approximation algorithm at MathWorld]
[[Category:Numerical analysis]]
{{math-stub}}
| 