In
mathematics
Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
, approximation theory is concerned with how
functions can best be
approximated with simpler functions, and with
quantitative
Quantitative may refer to:
* Quantitative research, scientific investigation of quantitative properties
* Quantitative analysis (disambiguation)
* Quantitative verse, a metrical system in poetry
* Statistics, also known as quantitative analysis
...
ly
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
In mathematics, an orthogonal polynomial sequence is a family of polynomials such that any two different polynomials in the sequence are orthogonal
In mathematics, orthogonality (mathematics), orthogonality is the generalization of the geom ...
.
One problem of particular interest is that of approximating a function in a
computer
A computer is a machine that can be Computer programming, programmed to automatically Execution (computing), carry out sequences of arithmetic or logical operations (''computation''). Modern digital electronic computers can perform generic set ...
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
In mathematics, a polynomial is a Expression (mathematics), mathematical expression consisting of indeterminate (variable), indeterminates (also called variable (mathematics), variables) and coefficients, that involves only the operations of addit ...
or
rational
Rationality is the quality of being guided by or based on reason. In this regard, a person acts rationally if they have a good reason for what they do, or a belief is rational if it is based on strong evidence. This quality can apply to an ...
(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
In computing, floating-point arithmetic (FP) is arithmetic on subsets of real numbers formed by a ''significand'' (a signed sequence of a fixed number of digits in some base) multiplied by an integer power of that base.
Numbers of this form ...
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
Once the domain (typically an interval) and degree of the polynomial are chosen, the polynomial itself is chosen in such a way as to minimize the worst-case error. That is, the goal is to minimize the maximum value of
, 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 ''N''
th-degree polynomial that will lead to an error curve that oscillates back and forth between
and
a total of ''N''+2 times, giving a worst-case error of
. It is seen that there exists an ''N''
th-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, that is, they oscillate between
and
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 ''x
i'' where an extreme of ''P''−''f'' occurs, so
:
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'')nbsp;−
'Q''(''x'') − ''f''(''x'')must alternate in sign for the ''N'' + 2 values of ''x
i''. But
'P''(''x'') − ''f''(''x'')nbsp;−
'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
In mathematical analysis, the intermediate value theorem states that if f is a continuous function whose domain contains the interval , then it takes on any given value between f(a) and f(b) at some point within the interval.
This has two imp ...
, 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
The Chebyshev polynomials are two sequences of orthogonal polynomials related to the cosine and sine functions, notated as T_n(x) and U_n(x). They can be defined in several equivalent ways, one of which starts with trigonometric functions:
...
and then cutting off the expansion at the desired degree.
This is similar to the
Fourier analysis
In mathematics, Fourier analysis () is the study of the way general functions may be represented or approximated by sums of simpler trigonometric functions. Fourier analysis grew from the study of Fourier series, and is named after Joseph Fo ...
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
term, one gets an ''N''
th-degree 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 bucking polynomials. If a Chebyshev expansion is cut off after
, the error will take a form close to a multiple of
. The Chebyshev polynomials have the property that they are level – they oscillate between +1 and −1 in the interval
��1, 1 has ''N''+2 level extrema. This means that the error between ''f''(''x'') and its Chebyshev expansion out to
is close to a level function with ''N''+2 extrema, so it is close to the optimal ''N''
th-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
Clenshaw–Curtis quadrature and Fejér quadrature are methods for numerical integration, or "quadrature", that are based on an expansion of the Integrand#Terminology and notation, integrand in terms of Chebyshev polynomials. Equivalently, they em ...
, a
numerical integration
In analysis, numerical integration comprises a broad family of algorithms for calculating the numerical value of a definite integral.
The term numerical quadrature (often abbreviated to quadrature) is more or less a synonym for "numerical integr ...
technique.
Remez's algorithm
The
Remez algorithm
The Remez algorithm or Remez exchange algorithm, published by Evgeny Yakovlevich Remez in 1934, is an iterative algorithm used to find simple approximations to functions, specifically, approximations by functions in a Chebyshev space that are the ...
(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 ''N''
th-degree polynomial that leads to level and alternating error values, given ''N''+2 test points.
Given ''N''+2 test points
,
, ...
(where
and
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,
:
Since
, ...,
were given, all of their powers are known, and
, ...,
are also known. That means that the above equations are just ''N''+2 linear equations in the ''N''+2 variables
,
, ...,
, and
. Given the test points
, ...,
, one can solve this system to get the polynomial ''P'' and the number
.
The graph below shows an example of this, producing a fourth-degree polynomial approximating
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 × 10
−4
The error graph does indeed take on the values
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
In numerical analysis, the Newton–Raphson method, also known simply as Newton's method, named after Isaac Newton and Joseph Raphson, is a root-finding algorithm which produces successively better approximations to the roots (or zeroes) of a ...
. 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''). Remez's 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 well-behaved functions—if the test points are within
of the correct result, they will be approximately within
of the correct result after the next round.
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.
Main journals
* ''
Journal of Approximation Theory
The ''Journal of Approximation Theory'' is "devoted to advances in pure and applied approximation theory and related areas."
References
External links
''Journal of Approximation Theory'' web site''Journal of Approximation Theory'' home page a ...
''
* ''
Constructive Approximation
''Constructive Approximation'' is "an international mathematics journal dedicated to Approximations, expansions, and related research in: computation, function theory, functional analysis
Functional analysis is a branch of mathematical analys ...
''
* ''
East Journal on Approximations
The East Journal on Approximations is a journal about approximation theory published in Sofia, Bulgaria
Bulgaria, officially the Republic of Bulgaria, is a country in Southeast Europe. It is situated on the eastern portion of the Balkans ...
''
See also
*
Estimation theory
Estimation theory is a branch of statistics that deals with estimating the values of Statistical parameter, parameters based on measured empirical data that has a random component. The parameters describe an underlying physical setting in such ...
*
Fourier series
A Fourier series () is an Series expansion, expansion of a periodic function into a sum of trigonometric functions. The Fourier series is an example of a trigonometric series. By expressing a function as a sum of sines and cosines, many problems ...
*
Function approximation
In general, a function approximation problem asks us to select a function (mathematics), function among a that closely matches ("approximates") a in a task-specific way. The need for function approximations arises in many branches of applied ...
*
Numerical analysis
Numerical analysis is the study of algorithms that use numerical approximation (as opposed to symbolic computation, symbolic manipulations) for the problems of mathematical analysis (as distinguished from discrete mathematics). It is the study of ...
*
Orthonormal basis
In mathematics, particularly linear algebra, an orthonormal basis for an inner product space V with finite Dimension (linear algebra), dimension is a Basis (linear algebra), basis for V whose vectors are orthonormal, that is, they are all unit vec ...
*
Padé approximant
In mathematics, a Padé approximant is the "best" approximation of a function near a specific point by a rational function of given order. Under this technique, the approximant's power series agrees with the power series of the function it is ap ...
*
Schauder basis
In mathematics, a Schauder basis or countable basis is similar to the usual ( Hamel) basis of a vector space; the difference is that Hamel bases use linear combinations that are finite sums, while for Schauder bases they may be infinite sums. This ...
*
Kalman filter
In statistics and control theory, Kalman filtering (also known as linear quadratic estimation) is an algorithm that uses a series of measurements observed over time, including statistical noise and other inaccuracies, to produce estimates of unk ...
References
*
*
*
*
*
*
*
*
*
*
*
Ch. 1–6 of 2013 edition
External links
History of Approximation Theory (HAT)Surveys in Approximation Theory (SAT)
{{Authority control
Numerical analysis