A minimax approximation algorithm (or L^∞ approximation or uniform approximation) is a method to find an approximation of a

mathematical function In mathematics, a function from a set to a set assigns to each element of exactly one element of .; the words map, mapping, transformation, correspondence, and operator are often used synonymously. The set is called the domain of the functi ...

that minimizes maximum error. For example, given a function

f

defined on the interval

,b /math> and a degree bound n, a minimax polynomial approximation algorithm will find a polynomial p of degree at most n to minimize
:: \max_, f(x)-p(x), .

Polynomial approximations

The

Weierstrass approximation theorem Karl Theodor Wilhelm Weierstrass (german: link=no, Weierstraß ; 31 October 1815 – 19 February 1897) was a German mathematician often cited as the "father of modern analysis". Despite leaving university without a degree, he studied mathematics ...

states that every continuous function defined on a closed interval ,bcan be uniformly approximated as closely as desired by a polynomial function. 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 In mathematics, the Taylor series or Taylor expansion of a function is an infinite sum of terms that are expressed in terms of the function's derivatives at a single point. For most common functions, the function and the sum of its Taylor serie ...

expansion are often convenient for theoretical work but less useful for practical applications. Truncated

Chebyshev series The Chebyshev polynomials are two sequences of polynomials related to the cosine and sine functions, notated as T_n(x) and U_n(x). They can be defined in several equivalent ways, one of which starts with trigonometric functions: The Chebyshe ...

, however, closely approximate the minimax polynomial. One popular minimax approximation algorithm is the

Remez algorithm The Remez algorithm or Remez exchange algorithm, published by Evgeny Yakovlevich Remez in 1934, is an iterative algorithm used to find simple approximations to functions, specifically, approximations by functions in a Chebyshev space that are the ...

References

{{Reflist

External links

Minimax approximation algorithm at MathWorld
Numerical analysis