Minimax approximation algorithm: Difference between revisions
Content deleted Content added
Bluelink 2 books for verifiability (prndis)) #IABot (v2.0) (GreenC bot |
m Task 18 (cosmetic): eval 3 templates: del empty params (2×); hyphenate params (1×); |
||
| Line 1: | Line 1: | ||
A '''minimax approximation algorithm''' (or '''L<sup>∞</sup> 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 |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 |
A '''minimax approximation algorithm''' (or '''L<sup>∞</sup> 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 |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> |
||
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 |
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 | |
::<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== |
==Polynomial approximations== |
||
Revision as of 08:28, 30 December 2020
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.[1][2]
For example, given a function defined on the interval and a degree bound , a minimax polynomial approximation algorithm will find a polynomial of degree at most to minimize
![{\displaystyle [a,b]}](/media/api/rest_v1/media/math/render/svg/9c4b788fc5c637e26ee98b45f89a5c08c85f7935)
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.[2] 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.
External links
References
- ^ Muller, Jean-Michel; Brisebarre, Nicolas; de Dinechin, Florent; Jeannerod, Claude-Pierre; Lefèvre, Vincent; Melquiond, Guillaume; Revol, Nathalie; Stehlé, Damien; Torres, Serge (2010). Handbook of Floating-Point Arithmetic (1 ed.). Birkhäuser. p. 376. doi:10.1007/978-0-8176-4705-6. ISBN 978-0-8176-4704-9. LCCN 2009939668.
- ^ a b Phillips, George M. (2003). "Best Approximation". Interpolation and Approximation by Polynomials. CMS Books in Mathematics. Springer. pp. 49–11. doi:10.1007/0-387-21682-0_2. ISBN 0-387-00215-4.
- ^ Powell, M. J. D. (1981). "7: The theory of minimax approximation". Approximation Theory and Methods. Cambridge University Press. ISBN 0521295149.