 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. Note that 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 lowdegree polynomial for each segment.
Contents
Optimal polynomials
Once the domain and degree of the polynomial are chosen, the polynomial itself is chosen in such a way as to minimize the worstcase error. That is, the goal is to minimize the maximum value of , where P(x) is the approximating polynomial and f(x) is the actual function. For wellbehaved functions, there exists an Nthdegree polynomial that will lead to an error curve that oscillates back and forth between and a total of N+2 times, giving a worstcase error of . It is seen that an Nthdegree polynomial can interpolate N+1 points in a curve. Such a polynomial is always optimal. 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 and exactly. Note that, 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 Ndegree polynomial that is a better approximation to f than P. In particular, Q is closer to f than P for each value x_{i} where an extreme of P−f occurs, so
  Q(x_{i}) − f(x_{i})  <  P(x_{i}) − f(x_{i})  .
When a maximum of P−f occurs at x_{i}, then
And when a minimum of P−f occurs at x_{i}, 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 x_{i}. 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:
and then cuts off the series after the T_{N} term, one gets an Nthdegree polynomial approximating f(x).
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. That is, the first term after the cutoff dominates all later terms. The same is true if the expansion is in terms of Chebyshev polynomials. If a Chebyshev expansion is cut off after T_{N}, the error will take a form close to a multiple of T_{N + 1}. The Chebyshev polynomials have the property that they are level – they oscillate between +1 and −1 in the interval [−1, 1]. T_{N + 1} has N+2 level extrema. This means that the error between f(x) and its Chebyshev expansion out to T_{N} is close to a level function with N+2 extrema, so it is close to the optimal Nthdegree polynomial.
In the graphs above, note that 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. Note also that the discrepancy is less serious for the exp function, which has an extremely rapid converging power series, than for the log function.
Chebyshev approximation is the basis for Clenshaw–Curtis quadrature, a numerical integration technique.
Remez' 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' algorithm uses the fact that one can construct an Nthdegree polynomial that leads to level and alternating error values, given N+2 test points.
Given N+2 test points x_{1}, x_{2} ... x_{N + 2} (where x_{1} and x_{N + 2} are presumably the end points of the interval of approximation), these equations need to be solved:
The righthand sides alternate in sign.
That is,
Since x_{1} ... x_{N + 2} were given, all of their powers are known, and f(x_{1}) ... f(x_{N + 2}) are also known. That means that the above equations are just N+2 linear equations in the N+2 variables P_{0}, P_{1} ... P_{N}, and . Given the test points x_{1} ... x_{N + 2}, one can solve this system to get the polynomial P and the number .
The graph below shows an example of this, producing a 4th degree polynomial approximating e^{x} over [−1, 1]. The test points were set at −1, −0.7, −0.1, +0.4, +0.9, and 1. Those values are shown in green. The resultant value of is 4.43 x 10^{−4}
Note that the error graph does indeed take on the values at the 6 test points, including the end points, but that those points are not extrema. If the 4 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' 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 P(x)−f(x), 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). Remez' algorithm requires an ability to calculate , , and to extremely high precision. The entire algorithm must be carried out to higher precision than the desired precision of the result.
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. The algorithm converges very rapidly. Convergence is quadratic for wellbehaved functions—if the test points are within 10 ^{− 15} of the correct result, they will be approximately within 10 ^{− 30} of the correct result after the next round.
Remez' algorithm is typically started by choosing the extrema of the Chebyshev polynomial T_{N + 1} as the initial points, since the final error function will be similar to that polynomial.
Main journals
See also
 Chebyshev polynomials
 Generalized Fourier series
 Orthogonal polynomials
 Orthonormal basis
 Fourier series
 Schauder basis
 Padé approximant
References
 N. I. Achiezer (Akhiezer), Theory of approximation, Translated by Charles J. Hyman Frederick Ungar Publishing Co., New York 1956 x+307 pp.
 A. F. Timan, Theory of approximation of functions of a real variable, 1963 ISBN 048667830X
 C. Hastings, Jr. Approximations for Digital Computers. Princeton University Press, 1955.
 J. F. Hart, E. W. Cheney, C. L. Lawson, H. J. Maehly, C. K. Mesztenyi, J. R. Rice, H. C. Thacher Jr., C. Witzgall, Computer Approximations. Wiley, 1968, Lib. Cong. 6723326.
 L. Fox and I. B. Parker. "Chebyshev Polynomials in Numerical Analysis." Oxford University Press London, 1968.
 Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), "Section 5.8. Chebyshev Approximation", Numerical Recipes: The Art of Scientific Computing (3rd ed.), New York: Cambridge University Press, ISBN 9780521880688, http://apps.nrbook.com/empanel/index.html?pg=233
 W. J. Cody Jr., W. Waite, Software Manual for the Elementary Functions. PrenticeHall, 1980, ISBN 0138220646.
 E. Remes [Remez], "Sur le calcul effectif des polynomes d'approximation de Tschebyscheff". 1934 C. R. Acad. Sci., Paris, 199, 337340.
 K.G. Steffens, The History of Approximation Theory: From Euler to Bernstein Birkhauser, Boston 2006 ISBN 0817643532.
 T. Erdélyi, "Extensions of the BlochPólya theorem on the number of distinct realzeros of polynomials", Journal de théorie des nombres de Bordeaux 20 (2008), 281–287.
 T. Erdélyi, "The Remez inequality for linear combinations of shifted Gaussians", Math. Proc. Cambridge Phil. Soc. 146 (2009), 523–530.
External links
Categories:
Wikimedia Foundation. 2010.
Look at other dictionaries:
Approximation theory/Proofs — Proof that an N th degree polynomial that gives rise to an error function that has N + 2 maxima, of alternating signs and equal magnitudes, is optimal in the sense of approximation theory. Such an optimal polynomial gives the minimum value, over… … Wikipedia
Journal of Approximation Theory — Infobox Journal title = Journal of Approximation Theory discipline = mathematics abbreviation = J. Approx. Theory publisher = Elsevier country = U.S. ISSN = 0021 9045 CODEN = JAXTAZ history = 1968 to present website = http://www.math.ohio… … Wikipedia
Approximation — (lat.: proximus, „der Nächste“) ist zunächst ein Synonym für Näherung; der Begriff wird in der Mathematik allerdings noch präzisiert. Es gibt vor allem zwei Gründe in der Mathematik, Näherungen zu untersuchen: Einmal könnte das Objekt des… … Deutsch Wikipedia
Approximation — An approximation (represented by the symbol ≈) is an inexact representation of something that is still close enough to be useful. Although approximation is most often applied to numbers, it is also frequently applied to such things as… … Wikipedia
Approximation de Bernstein — En analyse, l approximation de Bernstein est une méthode d approximation polynomiale, permettant d approcher uniformément une fonction continue f définie sur l intervalle [0,1] par une suite de combinaisons linéaires des polynômes de Bernstein.… … Wikipédia en Français
Approximation in algebraic groups — In mathematics, strong approximation in linear algebraic groups is an important arithmetic property of matrix groups. In rough terms, it explains to what extent there can be an extension of the Chinese remainder theorem to various kinds of… … Wikipedia
Theory — The word theory has many distinct meanings in different fields of knowledge, depending on their methodologies and the context of discussion.In science a theory is a testable model of the manner of interaction of a set of natural phenomena,… … Wikipedia
Theory of incomplete measurements — The Theory of Incomplete Measurements (TIM) is an attempt to unify Quantum Mechanics and General Relativity by focusing on physical measurement processes. In that theory, general relativity is a continuous approximation of discrete measurements,… … Wikipedia
Approximation der Eins — Eine Approximation der Eins ist ein Begriff aus der mathematischen Theorie der Banachalgebren. Viele für Anwendungen wichtige Banachalgebren haben kein Einselement. Eine Adjunktion eines Einselement wäre in der Regel ein unnatürliches Vorgehen.… … Deutsch Wikipedia
Approximation algorithm — In computer science and operations research, approximation algorithms are algorithms used to find approximate solutions to optimization problems. Approximation algorithms are often associated with NP hard problems; since it is unlikely that there … Wikipedia