Copyright (c) Susan Laflin. August 1999.

Minimax Approximation.

This is obtained by when we define the `best-fitting' curve as that which corresponds to the minimum value of the L-infinity-norm. Since the L-infinity-norm is defined as the maximum value of the error function over the interval or set of points, this curve gives the MINImum value of the MAXimum error - hence the name `minimax'.

This problem was studied by Chebyshev and he formulated and proved the `Chebyshev Equioscillation Theorem', which is the basis for these methods.

Chebyshev Equioscillation Theorem

Let f(x) be a continuous function defined on a finite interval [a,b]. If pn(x) is a minimax polynomial approximation to f(x) over the interval [a,b], with an error function en(x)=pn(x)-f(x), then there are at least n+2 points x1, x2,...,x{n+2} in [a,b], where a <= x1 < x2 < ..... < x{n+2} <= b , such that |en(x)| = En, i = 1,2, n+2 where En is the error bound for the approximation, and

en(xi) = - en(x{i+1}) i = 1,2,...,n+1

There is ONLY ONE polynomial of degree < = n with this property.

Example of minimax curve

Replace the function f(x) by the best-fitting straight line.

Decreasing the error in one place will increase it somewhere else. Applying the equioscillation theorem, we note

f(0) - (a0 + a1*0) = -E
f(X) - (a0 + a1*X) = E
f(1) - (a0 + a1*1) = -E

We also note that the error has a maximum at the point X. hence

d/dx (f(x) - a0 - a1*x ) = 0 at x = X

or df/dx - a1 = 0

In the diagram above, f(x) = x^2 and so
			a0 = -E 
			X^2 - a0 - a1 X = E 
			1 - a0 - a1 = -E 
			2X = a1 
 which gives  y = x - 1/8 as the best fitting line, with E = 1/8 .

Second Remez Algorithm