Minimax approximation algorithm: Difference between revisions

Revision as of 18:29, 29 August 2012

Latest revision as of 13:10, 27 September 2021

(25 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>

{{unreferenced|date=August 2012}}

{{Context|date=October 2009}}

A '''minimax approximation algorithm''' 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>{{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

Polynomial expansions such as the [[Taylor series]] expansion are often convenient for theoretical work but less useful for practical applications. 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.

A '''minimax approximation algorithm''' is ::<math>\max_{a method\leq whichx aims to find an approximation such that the maximum error is minimized. Suppose we seek to approximate the function\leq b}|f(''x'') by a function -p(''x'') on the interval [''a'',''b'']|. Then a minimax approximation algorithm will aim to minimize</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>

==Polynomial approximations==

One popular approach is the [[Remez algorithm]].

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

==External links==

Polynomial expansions such as the [[Taylor series]] expansion are often convenient for theoretical work but less useful for practical applications. 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.

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

Polynomial expansions such as the [[Taylor series]] expansion are often convenient for theoretical work but less useful for practical applications. Truncated [[Chebyshev series]], however, closely approximate the minimax polynomial.

==References==

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

==References==

{{Reflist}}

==External links==

[[Category:Numerical analysis]]

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

[[Category:Numerical analysis]]

{{math-stub}}