In mathematics, approximation theory is concerned with how functionss can best be approximated with simpler functions, and with quantitativelyly characterizing the errors introduced thereby. What is meant by best and simpler will depend on the application.

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. This is typically done with polynomial or rational (ratio of polynomials) approximations.

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. This is accomplished by using a polynomial of high degree, and/or narrowing the domain over which the polynomial has to approximate the function. Narrowing the domain can often be done through the use of various addition or scaling formulas for the function being approximated. Modern mathematical libraries often reduce the domain into many tiny segments and use a low-degree polynomial for each segment.

Optimal polynomials

, 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 a total of N. It is seen that there exists an Nth-degree polynomial that can interpolate N+1 points in a curve. That such a polynomial is always optimal is asserted by the equioscillation theorem. 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 exactly. In each case, the number of extrema is N+2, that is, 6. 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. Suppose Q(x) (whose error function is shown in blue to the right) is another N-degree polynomial that is a better approximation to f than P. In particular, Q is closer to f than P for each value xi where an extreme of P−f occurs, so

When a maximum of P−f occurs at xi, then

And when a minimum of P−f occurs at xi, then

So, as can be seen in the graph, [P(x)−f(x)]−[Q(x)−f(x)] must alternate in sign for the N+2 values of xi. But [P(x)−f(x)]−[Q(x)−f(x)] reduces to P(x)−Q(x) which is a polynomial of degree N. This function changes sign at least N+1 times so, by the Intermediate value theorem, it has N+1 zeroes, which is impossible for a polynomial of degree N.

Chebyshev approximation

One can obtain polynomials very close to the optimal one by expanding the given function in terms of Chebyshev polynomials and then cutting off the expansion at the desired degree. This is similar to the Fourier analysis of the function, using the Chebyshev polynomials instead of the usual trigonometric functions.

If one calculates the coefficients in the Chebyshev expansion for a function:

term, one gets an Nth-degree polynomial approximating f(x).

has N+2 level extrema. This means that the error between f(x is close to a level function with N+2 extrema, so it is close to the optimal Nth-degree polynomial.

In the graphs above, the blue error function is sometimes better than (inside of) the red function, but sometimes worse, meaning that it is not quite the optimal polynomial. The discrepancy is less serious for the exp function, which has an extremely rapidly converging power series, than for the log function.

Chebyshev approximation is the basis for Clenshaw–Curtis quadrature, a numerical integration technique.

Remez's algorithm

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. By the theorem above, that polynomial is optimal.

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.

Given N are presumably the end points of the interval of approximation), these equations need to be solved:

The right-hand sides alternate in sign.

That is,

are also known. That means that the above equations are just N+2 linear equations in the N, one can solve this system to get the polynomial P.

is 4.43 × 10−4

at the six test points, including the end points, but that those points are not extrema. 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. For example, one can tell from looking at the graph that the point at −0.1 should have been at about −0.28. The way to do this in the algorithm is to use a single round of Newton's method. Since one knows the first and second derivatives of , one can calculate approximately how far a test point has to be moved so that the derivative will be zero.

Calculating the derivatives of a polynomial is straightforward. One must also be able to calculate the first and second derivatives of f(x to extremely high precision. The entire algorithm must be carried out to higher precision than the desired precision of the result.

of the correct result after the next round.

as the initial points, since the final error function will be similar to that polynomial.

Main journals

• Journal of Approximation Theory

• Constructive Approximation

• East Journal on Approximations

See also

• Estimation theory

• Fourier series

• Function approximation

• Numerical analysis

• Orthonormal basis

• Padé approximant

• Schauder basis

• Kalman filter

References

• Ch. 1–6 of 2013 edition

External links

• History of Approximation Theory (HAT)

• Surveys in Approximation Theory (SAT)