Minimax approximation algorithm: Difference between revisions

Revision as of 05:44, 12 April 2008

Latest revision as of 13:10, 27 September 2021

(34 intermediate revisions by 16 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>

{{context}}

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.

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

Algorithms that minimize the maximum error are known as '''Minimax approximation algorithms'''. One popular approach is the [remez algorithm].

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

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.

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.

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

==References==

{{Reflist}}

==External links==

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

[[Category:Numerical analysis]]

{{math-stub}}