Minimax approximation algorithm: Difference between revisions

Revision as of 13:42, 3 September 2012

Latest revision as of 13:10, 27 September 2021

(21 intermediate revisions by 12 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 0-8176-4704-X (print) --> |page=[https://archive.org/details/handbookfloating00mull_867/page/n388 376]}}</ref><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 = [https://archive.org/details/interpolationapp00phil_282/page/n63 49]–11 | year = 2003 | publisher = Springer | isbn = 0-387-00215-4 }}</ref>

A '''minimax approximation algorithm''' (or '''L^∞ approximation'''<ref>{{cite book | title = Handbook of Floating-Point Arithmetic | page = 376 | publisher = Springer | year = 2009 | isbn = 081764704X | first1=Jean-Michel | last1=Muller }}</ref> or '''uniform approximation'''<ref name="phillips">{{cite book | page = 87 | title = Interpolation and Approximation by Polynomials | first = George M. | last = Phillips | publisher = Springer | year = 2003 | isbn = 0387002154}}</ref>) is a method which aims to find an approximation such that the maximum error is minimized. Suppose we seek to approximate the function f(''x'') by a function p(''x'') on the interval [''a'',''b'']. Then a minimax approximation algorithm will aim to minimize<ref name="powell">{{cite book | chapter = 7: The theory of minimax approximation | first = M. J. D. | last= Powell | authorlink=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>

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" />

The conditions for a best appromation are particularly simple if the function p(''x'') is restricted to polynomials less than a stated degree ''n''.<ref name="powell" /> A theorem by [[Karl Weierstrass]] states that for any function f&nbsp;∈&nbsp;[[continuous function|C]][-1,1] and any ''ε''&nbsp;>&nbsp;0 then there exists a polynomial p such that<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.

::<math>|f(x)-p(x)| < \epsilon,\quad -1\leq x \leq 1.</math>

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]].

==References==

{{Reflist}}

==External links==

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

==References==

{{Reflist}}

[[Category:Numerical analysis]]

{{math-stub}}