Minimax approximation algorithm

A minimax approximation algorithm (or L^∞ approximation or uniform approximation) 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

$\max _{a\leq x\leq b}|f(x)-p(x)|.$

Polynomial approximations

The conditions for a best appromation are particularly simple if the function p(x) is restricted to polynomials less than a stated degree n. A theorem by Karl Weierstrass states that for any function f ∈ C[-1,1] and any ε > 0 then there exists a polynomial p such that

$\max _{-1\leq x\leq 1}|f(x)-p(x)|<\epsilon .$

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.

One popular minimax approximation algorithm is the Remez algorithm.

External links

• Minimax approximation algorithm at MathWorld