Movatterモバイル変換

Approximation theory

From Wikipedia, the free encyclopedia

This article includes alist of references,related reading, orexternal links,but its sources remain unclear because it lacksinline citations. Please helpimprove this article byintroducing more precise citations.(November 2025) (Learn how and when to remove this message)

Theory of getting acceptably close inexact mathematical calculations

Inmathematics,approximation theory is concerned with howfunctions can best beapproximated with simpler functions, and withquantitatively characterizing theerrors introduced thereby. What is meant bybest andsimpler will depend on the application.

A closely related topic is the approximation of functions bygeneralized Fourier series, that is, approximations based upon summation of a series of terms based uponorthogonal polynomials.

One problem of particular interest is that of approximating a function in acomputer 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 withpolynomial orrational (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'sfloating point arithmetic. This is accomplished by using a polynomial of highdegree, 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.

Error between optimal polynomial and log(x) (red), and Chebyshev approximation and log(x) (blue) over the interval [2, 4]. Vertical divisions are 10⁻⁵. Maximum error for the optimal polynomial is 6.07 × 10⁻⁵.

Error between optimal polynomial and exp(x) (red), and Chebyshev approximation and exp(x) (blue) over the interval [−1, 1]. Vertical divisions are 10⁻⁴. Maximum error for the optimal polynomial is 5.47 × 10⁻⁴.

Optimal polynomials

[edit]

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 $\mid P(x)-f(x)\mid$ , whereP(x) is the approximating polynomial,f(x) is the actual function, andx varies over the chosen interval. For well-behaved functions, there exists anNth-degree polynomial that will lead to an error curve that oscillates back and forth between $+\varepsilon$ and $-\varepsilon$ a total ofN+2 times, giving a worst-case error of $\varepsilon$ . It is seen that there exists anNth-degree polynomial that can interpolateN+1 points in a curve. That such a polynomial is always optimal is asserted by theequioscillation theorem. It is possible to make contrived functionsf(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) forN = 4. The red curves, for the optimal polynomial, arelevel, that is, they oscillate between $+\varepsilon$ and $-\varepsilon$ exactly. In each case, the number of extrema isN+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.

ErrorP(x) − f(x) for level polynomial (red), and for purported better polynomial (blue)

To prove this is true in general, supposeP is a polynomial of degreeN having the property described, that is, it gives rise to an error function that hasN + 2 extrema, of alternating signs and equal magnitudes. The red graph to the right shows what this error function might look like forN = 4. SupposeQ(x) (whose error function is shown in blue to the right) is anotherN-degree polynomial that is a better approximation tof thanP. In particular,Q is closer tof thanP for each valuex_i where an extreme ofP−f occurs, so

|Q(x_{i})-f(x_{i})|<|P(x_{i})-f(x_{i})|.

When a maximum ofP−f occurs atx_i, then

Q(x_{i})-f(x_{i})\leq |Q(x_{i})-f(x_{i})|<|P(x_{i})-f(x_{i})|=P(x_{i})-f(x_{i}),

And when a minimum ofP−f occurs atx_i, then

f(x_{i})-Q(x_{i})\leq |Q(x_{i})-f(x_{i})|<|P(x_{i})-f(x_{i})|=f(x_{i})-P(x_{i}).

So, as can be seen in the graph, [P(x) − f(x)] − [Q(x) − f(x)] must alternate in sign for theN + 2 values ofx_i. But [P(x) − f(x)] − [Q(x) − f(x)] reduces toP(x) − Q(x) which is a polynomial of degreeN. This function changes sign at leastN+1 times so, by theIntermediate value theorem, it hasN+1 zeroes, which is impossible for a polynomial of degreeN.

Chebyshev approximation

[edit]

One can obtain polynomials very close to the optimal one by expanding the given function in terms ofChebyshev polynomials and then cutting off the expansion at the desired degree. This is similar to theFourier 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:

f(x)\sim \sum _{i=0}^{\infty }c_{i}T_{i}(x)

and then cuts off the series after the $T_{N}$ term, one gets anNth-degree polynomial approximatingf(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 $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}$ hasN+2 level extrema. This means that the error betweenf(x) and its Chebyshev expansion out to $T_{N}$ is close to a level function withN+2 extrema, so it is close to the optimalNth-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 forClenshaw–Curtis quadrature, anumerical integration technique.

Remez's algorithm

[edit]

Main article:Remez algorithm

TheRemez algorithm (sometimes spelled Remes) is used to produce an optimal polynomialP(x) approximating a given functionf(x) over a given interval. It is an iterative algorithm that converges to a polynomial that has an error function withN+2 level extrema. By the theorem above, that polynomial is optimal.

Remez's algorithm uses the fact that one can construct anNth-degree polynomial that leads to level and alternating error values, givenN+2 test points.

GivenN+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:

{\begin{aligned}P(x_{1})-f(x_{1})&=+\varepsilon \\P(x_{2})-f(x_{2})&=-\varepsilon \\P(x_{3})-f(x_{3})&=+\varepsilon \\&\ \ \vdots \\P(x_{N+2})-f(x_{N+2})&=\pm \varepsilon .\end{aligned}}

The right-hand sides alternate in sign.

That is,

{\begin{aligned}P_{0}+P_{1}x_{1}+P_{2}x_{1}^{2}+P_{3}x_{1}^{3}+\dots +P_{N}x_{1}^{N}-f(x_{1})&=+\varepsilon \\P_{0}+P_{1}x_{2}+P_{2}x_{2}^{2}+P_{3}x_{2}^{3}+\dots +P_{N}x_{2}^{N}-f(x_{2})&=-\varepsilon \\&\ \ \vdots \end{aligned}}

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 justN+2 linear equations in theN+2 variables $P_{0}$ , $P_{1}$ , ..., $P_{N}$ , and $\varepsilon$ . Given the test points $x_{1}$ , ..., $x_{N+2}$ , one can solve this system to get the polynomialP and the number $\varepsilon$ .

The graph below shows an example of this, producing a fourth-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 $\varepsilon$ is 4.43 × 10⁻⁴

Error of the polynomial produced by the first step of Remez's algorithm, approximating e^x over the interval [−1, 1]. Vertical divisions are 10⁻⁴.

The error graph does indeed take on the values $\pm \varepsilon$ 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 functionP(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 ofNewton's method. Since one knows the first and second derivatives ofP(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 off(x). Remez's algorithm requires an ability to calculate $f(x)\,$ , $f'(x)\,$ , and $f''(x)\,$ 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 $10^{-15}$ of the correct result, they will be approximately within $10^{-30}$ of the correct result after the next round.

Remez's 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

[edit]

References

[edit]

Achiezer (Akhiezer), N.I. (2013) [1956].Theory of approximation. Translated by Hyman, C.J. Dover.ISBN 978-0-486-15313-1.OCLC 1067500225.
Timan, A.F. (2014) [1963].Theory of approximation of functions of a real variable. International Series in Pure and Applied Mathematics. Vol. 34. Elsevier.ISBN 978-1-4831-8481-4.
Hastings, Jr., C. (2015) [1955].Approximations for Digital Computers. Princeton University Press.ISBN 978-1-4008-7559-7.
Hart, J.F.;Cheney, E.W.; Lawson, C.L.; Maehly, H.J.; Mesztenyi, C.K.;Rice, Jr., J.R.; Thacher, H.C.; Witzgall, C. (1968).Computer Approximations. Wiley.OCLC 0471356301.
Fox, L.; Parker, I.B. (1968).Chebyshev Polynomials in Numerical Analysis. Oxford mathematical handbooks. Oxford University Press.ISBN 978-0-19-859614-1.OCLC 9036207.
Press, WH;Teukolsky, S.A.; Vetterling, W.T.;Flannery, B.P. (2007). "§5.8 Chebyshev Approximation".Numerical Recipes: The Art of Scientific Computing (3rd ed.). Cambridge University Press.ISBN 978-0-521-88068-8.
Cody, Jr., W.J.; Waite, W. (1980).Software Manual for the Elementary Functions. Prentice-Hall.ISBN 0-13-822064-6.OCLC 654695035.
Remes (Remez), E. (1934)."Sur le calcul effectif des polynomes d'approximation de Tschebyschef".C. R. Acad. Sci. (in French).199:337–340.
Steffens, K.-G. (2006). Anastassiou, George A. (ed.).The History of Approximation Theory: From Euler to Bernstein. Birkhauser.doi:10.1007/0-8176-4475-X.ISBN 0-8176-4353-2.
Erdélyi, T. (2008)."Extensions of the Bloch-Pólya theorem on the number of distinct real zeros of polynomials".Journal de théorie des nombres de Bordeaux.20:281–7.doi:10.5802/jtnb.627.
Erdélyi, T. (2009). "The Remez inequality for linear combinations of shifted Gaussians".Mathematical Proceedings of the Cambridge Philosophical Society.146 (3):523–530.doi:10.1017/S0305004108001849.
Trefethen, L.N. (2020).Approximation theory and approximation practice. SIAM.ISBN 978-1-61197-594-9.Ch. 1–6 of 2013 edition

External links

[edit]

Industrial and applied mathematics

Computational

Mathematical software	Arbitrary-precision arithmetic Finite element analysis Tensor software Interactive geometry software Optimization software Statistical software Numerical-analysis software Numerical libraries Solvers

Algebraic structures	Algebra of physical space Particle physics and representation theory Feynman integral Poisson algebra Quantum group Renormalization group Spacetime algebra Superalgebra Supersymmetry algebra