Asymptotic analysis

Figure 1. Asymptotic approximation: The function f(x)=x is an asymptotic approximation for the function f(x)=x+e−x for large positive values of x.

In mathematical analysis, asymptotic analysis, also known as asymptotics, is the development and application of methods that generate an approximate analytical solution to a mathematical problem when a variable or parameter assumes a value that is large or small.

An example of asymptotic analysis is function approximation. For example, the function y~(x)=x accurately approximates the function y(x)=x+e−x for large positive x values (Figure 1). For any desired accuracy, there is a corresponding range of x values where this accuracy occurs. In this case, a chosen accuracy with a relative error of less than 1% occurs when the x values are greater than 3.4.

The prime number theorem is an example of an asymptotic result. For any real number x, the prime counting function, denoted as π⁡(x), is the number of prime numbers less than or equal to x. There is no formula for π⁡(x), but it can be approximated by the function x/ln⁡(x), for large x. As in the preceding example, as x becomes larger, the approximation becomes more accurate.

Asymptotic analysis impacts on many areas of mathematics. Mathematicians use asymptotic analysis for computing function approximations, implicit functions, integrals, iterated functions, series summation, partial sums, solutions of difference equations, solutions of differential equations and properties of computer algorithms. Asymptotic reasoning plays a central role in explaining universal behaviour in physics.

Definitions and notation

There are three important definitions that are used to describe the relative magnitude of functions in asymptotic analysis.

Big-O notation

The function f(z) is said to be of order g(z) as z tends to L, written with big-O notation as either f(z)=O(g(z)) (z→L) or f(z)=O(g(z)) as z→L, if there exists a positive constant M such that |f(z)|≤M|g(z)| for z in V, where the set V is a neighbourhood of L if L is finite, or the set of points where z>N for some positive number N in the case z→∞.

Simple examples of the finite and infinite cases are cos⁡x−1=O(x2) (x→0) and (z+2)(3z2−4z)=O(z3) (z→∞).

The big-O notation may apply to all elements z in a set S: f(z)=O(g(z)) (z∈S). If g(z) is nonzero for z near L, except possibly at L, then f(z)=O(g(z)) (z→L) indicates that the quotient |f(z)/g(z)| is bounded.

Little-o notation

The function f(z) is much less than g(z) as z approaches L, written as f(z)≪g(z) (z→L) if for any positive number c there is a neighborhood V of L meeting the condition |f(z)|≤c|g(z)| for z in V. This is also written using little-o notation, as f(z)=o(g(z)) (z→L)

As long as g(z) is nonzero for z near L, except possibly at L, then f(z)=o(g(z)) (z→L) indicates that the quotient |f(z)/g(z)| has limit 0 as z approaches L: limz→L f(z)g(z)=0.

As for the big-O notation, little-o can also be used for the limit z→∞. For example, z6=o(ez) as z→∞.

Asymptotic equivalence

Given functions f(x) and g(x), we write f(x)∼g(x)as x→∞ if and only if (de Bruijn 1981, §1.4) limx→∞f(x)g(x)=1.

The symbol ~ is the tilde. The functions f and g are said to be asymptotically equivalent. The domain of the two functions can be any set for which the limit is defined: e.g. real numbers, complex numbers, positive integers.

For the example shown in Figure 1, we have e−x+x∼xas x→∞.

The same notation is also used for the limit x→0, for example sin⁡x∼xas x→0.

Properties of O, o and ~

Both Big-O and little-o satisfy the partial ordering property. In the case of little-o, if f(x)=o(g(x)) and g(x)=o(h(x)) then f(x)=o(h(x)), and the same holds for Big-O.

Asymptotic equivalence is an equivalence relation, since it has the reflexive, symmetric and transitive properties: f(x)∼f(x), f(x)∼g(x)⟹g(x)∼f(x), and f(x)∼g(x),g(x)∼h(x)⟹f(x)∼h(x).

The zero function, f(z)=0, can never be asymptotically equivalent to any other function.

If f(x)∼g(x) then f(x)=O(g(x)), but the converse is not generally true.

If f(x)∼g(x)(x→L), then the functions raised to the real power r are also equivalent: (f(x))r∼(g(x))r (x→L).

If f(x)∼g(x)(x→L), and h(x)∼k(x)(x→L), then the quotients are equivalent: f(x)h(x)∼g(x)k(x) (x→L) These properties allow asymptotically equivalent functions to be freely exchanged in many algebraic expressions.

Asymptotically equivalent functions remain asymptotically equivalent under integration if requirements related to convergence are met. There are more stringent requirements for asymptotically equivalent functions to remain asymptotically equivalent under differentiation.

Examples of asymptotic formulas

tan⁡x∼x as x→0

Asymptotic expansion

A sequence of functions, {g0(z),g1(z),…}, defined on domain D is an asymptotic sequence as z approaches L if each function is much less than (lower order) than the preceding function of the sequence, gm+1(z)=o(gm(z)) (z→L).

Given an asymptotic sequence, {g0(z),g1(z),…}, an asymptotic expansion or asymptotic series to N terms of a function f(z) is defined as the series f(z)=∑m=0Namgm(z)+o(gN(z)) (z→L).

The examples of asymptotic formulas given in the previous section are all one-term asymptotic series. Further terms can be added to the series, as shown in the following section.

A truncated asymptotic expansion is an asymptotic expansion containing a finite number of terms.

An asymptotic expansion of any number of terms, possibly infinite, has this form. f(z)∼∑m=0∞amgm(z) (z→L)

In many examples, as shown below, an asymptotic expansion is a series whose terms first decrease, reach a minimum and then start to increase again.

Examples of asymptotic expansions

  • Gamma function exxx2πxΓ(x+1)∼1+112x+1288x2−13951840x3−⋯ (x→∞)

Note that the first term in this series is equivalent to Stirling's formula for the factorial function given above. As an illustration, consider 8! = 40320. Stirling's formula gives (to the nearest integer) 39902, with an error of about 1%. Including the next term, ⁠1/12x⁠, gives 40318, which is remarkably accurate considering that 8 is not a very large number.

The exponential integral is defined by E1(x)=∫x∞e−ttdt. For large ⁠x⁠, repeated integration by parts gives the asymptotic series xexE1(x)∼∑n=0∞(−1)nn!xn (x→∞)

Divergent but asymptotic series

Consider the series given above for the exponential integral ⁠E1(x)⁠. The magnitude of the ratio of the ⁠(n+1)⁠th term to the ⁠n⁠th term is ⁠(n+1)/x⁠. This ratio tends to infinity as ⁠n→∞⁠ for a fixed ⁠x⁠, so the series diverges, by the ratio test. However, the ratio tends to 0 as ⁠x→∞⁠ at fixed ⁠n⁠, so the series is asymptotic. This behaviour is typical for asymptotic series. In fact the series given above for the gamma function and the error function are also divergent. However, these series can be useful when truncated, as shown above for the factorial function.

Applications

Asymptotic analysis is used in several mathematical sciences. In statistics, asymptotic theory provides limiting approximations of the probability distribution of sample statistics, such as the likelihood ratio statistic and the expected value of the deviance. Asymptotic theory does not provide a method of evaluating the finite-sample distributions of sample statistics, however. Non-asymptotic bounds are provided by methods of approximation theory.

Examples of applications are the following.

Asymptotic analysis is a key tool for exploring the ordinary and partial differential equations which arise in the mathematical modelling of real-world phenomena. An illustrative example is the derivation of the boundary layer equations from the full Navier-Stokes equations governing fluid flow. In many cases, the asymptotic expansion is in power of a small parameter, ε: in the boundary layer case, this is the nondimensional ratio of the boundary layer thickness to a typical length scale of the problem. Indeed, applications of asymptotic analysis in mathematical modelling often center around a nondimensional parameter which has been shown, or assumed, to be small through a consideration of the scales of the problem at hand.

Asymptotic expansions typically arise in the approximation of certain integrals (Laplace's method, saddle-point method, method of steepest descent) or in the approximation of probability distributions (Edgeworth series). The Feynman graphs in quantum field theory are another example of asymptotic expansions which often do not converge.

See also