Approximation theory
In mathematics, approximation theory is concerned with how functions can best be approximated with simpler functions, and with quantitatively characterizing the errors introduced thereby.
A closely related topic is the approximation of functions by generalized Fourier series, that is, approximations based upon summation of a series of terms based upon orthogonal polynomials.
One problem of particular interest is that of approximating a function in a computer mathematical library, using operations that can be performed on the computer or calculator (e.g. addition and multiplication), such that the result is as close to the actual function as possible.
The objective is to make the approximation as close as possible to the actual function, typically with an accuracy close to that of the underlying computer's floating point arithmetic.
Narrowing the domain can often be done through the use of various addition or scaling formulas for the function being approximated.
, where P(x) is the approximating polynomial, f(x) is the actual function, and x varies over the chosen interval.
For well-behaved functions, there exists an Nth-degree polynomial that will lead to an error curve that oscillates back and forth between
It is seen that there exists an Nth-degree polynomial that can interpolate N+1 points in a curve.
It is possible to make contrived functions f(x) for which no such polynomial exists, but these occur rarely in practice.
For example, the graphs shown to the right show the error in approximating log(x) and exp(x) for N = 4.
The red curves, for the optimal polynomial, are level, that is, they oscillate between
Two of the extrema are at the end points of the interval, at the left and right edges of the graphs.
To prove this is true in general, suppose P is a polynomial of degree N having the property described, that is, it gives rise to an error function that has N + 2 extrema, of alternating signs and equal magnitudes.
The red graph to the right shows what this error function might look like for N = 4.
If one calculates the coefficients in the Chebyshev expansion for a function: and then cuts off the series after the
The reason this polynomial is nearly optimal is that, for functions with rapidly converging power series, if the series is cut off after some term, the total error arising from the cutoff is close to the first term after the cutoff.
The same is true if the expansion is in terms of bucking polynomials.
The Chebyshev polynomials have the property that they are level – they oscillate between +1 and −1 in the interval [−1, 1].
Chebyshev approximation is the basis for Clenshaw–Curtis quadrature, a numerical integration technique.
The Remez algorithm (sometimes spelled Remes) is used to produce an optimal polynomial P(x) approximating a given function f(x) over a given interval.
It is an iterative algorithm that converges to a polynomial that has an error function with N+2 level extrema.
Remez's algorithm uses the fact that one can construct an Nth-degree polynomial that leads to level and alternating error values, given N+2 test points.
are presumably the end points of the interval of approximation), these equations need to be solved: The right-hand sides alternate in sign.
The graph below shows an example of this, producing a fourth-degree polynomial approximating
If the four interior test points had been extrema (that is, the function P(x)f(x) had maxima or minima there), the polynomial would be optimal.
The second step of Remez's algorithm consists of moving the test points to the approximate locations where the error function had its actual local maxima or minima.
After moving the test points, the linear equation part is repeated, getting a new polynomial, and Newton's method is used again to move the test points again.
This sequence is continued until the result converges to the desired accuracy.
Remez's algorithm is typically started by choosing the extrema of the Chebyshev polynomial
as the initial points, since the final error function will be similar to that polynomial.
