In
mathematical analysis
Analysis is the branch of mathematics dealing with continuous functions, limits, and related theories, such as differentiation, integration, measure, infinite sequences, series, and analytic functions.
These theories are usually studied ...
, asymptotic analysis, also known as asymptotics, is a method of describing
limiting behavior.
As an illustration, suppose that we are interested in the properties of a function as becomes very large. If , then as becomes very large, the term becomes insignificant compared to . The function is said to be "''asymptotically equivalent'' to , as ". This is often written symbolically as , which is read as " is asymptotic to ".
An example of an important asymptotic result is the
prime number theorem. Let denote the
prime-counting function (which is not directly related to the constant
pi), i.e. is the number of
prime number
A prime number (or a prime) is a natural number greater than 1 that is not a Product (mathematics), product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime ...
s that are less than or equal to . Then the theorem states that
Asymptotic analysis is commonly used in
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
as part of the
analysis of algorithms and is often expressed there in terms of
big O notation.
Definition
Formally, given functions and , we define a binary relation
if and only if
The symbol is the
tilde. The relation is an
equivalence relation on the set of functions of ; the functions and are said to be ''asymptotically equivalent''. The
domain
Domain may refer to:
Mathematics
*Domain of a function, the set of input values for which the (total) function is defined
** Domain of definition of a partial function
** Natural domain of a partial function
**Domain of holomorphy of a function
* ...
of and can be any set for which the limit is defined: e.g. real numbers, complex numbers, positive integers.
The same notation is also used for other ways of passing to a limit: e.g. , , . The way of passing to the limit is often not stated explicitly, if it is clear from the context.
Although the above definition is common in the literature, it is problematic if is zero infinitely often as goes to the limiting value. For that reason, some authors use an alternative definition. The alternative definition, in
little-o notation
Big ''O'' notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. Big O is a member of a family of notations invented by Paul Bachmann, Edmund Lan ...
, is that if and only if
This definition is equivalent to the prior definition if is not zero in some
neighbourhood
A neighbourhood (British English, Irish English, Australian English and Canadian English) or neighborhood (American English; see spelling differences) is a geographically localised community within a larger city, town, suburb or rural a ...
of the limiting value.
Properties
If
and
, as
, then the following hold:
*
, for every real
*
if
*
*
Such properties allow asymptotically-equivalent functions to be freely exchanged in many algebraic expressions.
Note that those properties are only correct if and only if
tends to infinity (in other words, those properties are only applied for sufficiently large value of
). If
does not tend to infinity, but instead to some arbitrary finite constants
, then the following limit from above definition:
≠ 1 , for some constant
Similarly:
≠ 1 , for some constant
Thus, those respective functions are no longer asymptotically-equivalent and cannot be applied above properties.
A simple example for this, let
and
, we can see that:
However:
Hence,
and
are not asymptotically-equivalent as
.
Examples of asymptotic formulas
*
Factorial —this is
Stirling's approximation
*
Partition function For a positive integer ''n'', the partition function, ''p''(''n''), gives the number of ways of writing the integer ''n'' as a sum of positive integers, where the order of addends is not considered.
*
Airy function The Airy function, Ai(''x''), is a solution of the differential equation ; it has many applications in physics.
*
Hankel functions
Asymptotic expansion
An
asymptotic expansion of a
Finite field
In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field that contains a finite number of elements. As with any field, a finite field is a set on which the operations of multiplication, addition, subtr ...
is in practice an expression of that function in terms of a
series, the
partial sums of which do not necessarily converge, but such that taking any initial partial sum provides an asymptotic formula for . The idea is that successive terms provide an increasingly accurate description of the order of growth of .
In symbols, it means we have
but also
and
for each fixed ''k''. In view of the definition of the
symbol, the last equation means
in the
little o notation, i.e.,
is much smaller than
The relation
takes its full meaning if
for all ''k'', which means the
form an
asymptotic scale. In that case, some authors may
abusively write
to denote the statement
One should however be careful that this is not a standard use of the
symbol, and that it does not correspond to the definition given in .
In the present situation, this relation
actually follows from combining steps ''k'' and ''k''−1; by subtracting
from
one gets
i.e.
In case the asymptotic expansion does not converge, for any particular value of the argument there will be a particular partial sum which provides the best approximation and adding additional terms will decrease the accuracy. This optimal partial sum will usually have more terms as the argument approaches the limit value.
Examples of asymptotic expansions
*
Gamma function
In mathematics, the gamma function (represented by , the capital letter gamma from the Greek alphabet) is one commonly used extension of the factorial function to complex numbers. The gamma function is defined for all complex numbers excep ...
*
Exponential integral
*
Error function where is the
double factorial.
Worked example
Asymptotic expansions often occur when an ordinary series is used in a formal expression that forces the taking of values outside of its domain of convergence. For example, we might start with the ordinary series
The expression on the left is valid on the entire complex plane
, while the right hand side converges only for
. Multiplying by
and integrating both sides yields
The integral on the left hand side can be expressed in terms of the
exponential integral. The integral on the right hand side, after the substitution
, may be recognized as the
gamma function
In mathematics, the gamma function (represented by , the capital letter gamma from the Greek alphabet) is one commonly used extension of the factorial function to complex numbers. The gamma function is defined for all complex numbers excep ...
. Evaluating both, one obtains the asymptotic expansion
Here, the right hand side is clearly not convergent for any non-zero value of ''t''. However, by keeping ''t'' small, and truncating the series on the right to a finite number of terms, one may obtain a fairly good approximation to the value of
. Substituting
and noting that
results in the asymptotic expansion given earlier in this article.
Asymptotic distribution
In
mathematical statistics, an
asymptotic distribution
In mathematics and statistics, an asymptotic distribution is a probability distribution that is in a sense the "limiting" distribution of a sequence of distributions. One of the main uses of the idea of an asymptotic distribution is in providing ...
is a hypothetical distribution that is in a sense the "limiting" distribution of a sequence of distributions. A distribution is an ordered set of random variables for , for some positive integer . An asymptotic distribution allows to range without bound, that is, is infinite.
A special case of an asymptotic distribution is when the late entries go to zero—that is, the go to 0 as goes to infinity. Some instances of "asymptotic distribution" refer only to this special case.
This is based on the notion of an
asymptotic
In analytic geometry, an asymptote () of a curve is a line such that the distance between the curve and the line approaches zero as one or both of the ''x'' or ''y'' coordinates tends to infinity. In projective geometry and related context ...
function which cleanly approaches a constant value (the ''asymptote'') as the independent variable goes to infinity; "clean" in this sense meaning that for any desired closeness epsilon there is some value of the independent variable after which the function never differs from the constant by more than epsilon.
An
asymptote is a straight line that a curve approaches but never meets or crosses. Informally, one may speak of the curve meeting the asymptote "at infinity" although this is not a precise definition. In the equation
''y'' becomes arbitrarily small in magnitude as ''x'' increases.
Applications
Asymptotic analysis is used in several
mathematical sciences. In
statistics
Statistics (from German: '' Statistik'', "description of a state, a country") is the discipline that concerns the collection, organization, analysis, interpretation, and presentation of data. In applying statistics to a scientific, indust ...
, asymptotic theory provides limiting approximations of the
probability distribution
In probability theory and statistics, a probability distribution is the mathematical function that gives the probabilities of occurrence of different possible outcomes for an experiment. It is a mathematical description of a random phenomenon ...
of
sample statistics, such as the
likelihood ratio statistic
A statistic (singular) or sample statistic is any quantity computed from values in a sample which is considered for a statistical purpose. Statistical purposes include estimating a population parameter, describing a sample, or evaluating a hypo ...
and the
expected value
In probability theory, the expected value (also called expectation, expectancy, mathematical expectation, mean, average, or first moment) is a generalization of the weighted average. Informally, the expected value is the arithmetic mean of a ...
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.
* In
applied mathematics
Applied mathematics is the application of mathematical methods by different fields such as physics, engineering, medicine, biology, finance, business, computer science, and industry. Thus, applied mathematics is a combination of mathemati ...
, asymptotic analysis is used to build
numerical methods to approximate
equation solutions.
* In
mathematical statistics and
probability theory
Probability theory is the branch of mathematics concerned with probability. Although there are several different probability interpretations, probability theory treats the concept in a rigorous mathematical manner by expressing it through a set ...
, asymptotics are used in analysis of long-run or large-sample behaviour of random variables and estimators.
* In
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
in the
analysis of algorithms, considering the performance of algorithms.
* The behavior of
physical systems, an example being
statistical mechanics.
* In
accident analysis when identifying the causation of crash through count modeling with large number of crash counts in a given time and space.
Asymptotic analysis is a key tool for exploring the
ordinary and
partial
Partial may refer to:
Mathematics
*Partial derivative, derivative with respect to one of several variables of a function, with the other variables held constant
** ∂, a symbol that can denote a partial derivative, sometimes pronounced "partial d ...
differential equations which arise in the
mathematical model
A mathematical model is a description of a system using mathematical concepts and language. The process of developing a mathematical model is termed mathematical modeling. Mathematical models are used in the natural sciences (such as physics, ...
ling of real-world phenomena.
[Howison, S. (2005), ]
Practical Applied Mathematics
', Cambridge University Press
Cambridge University Press is the university press of the University of Cambridge. Granted letters patent by King Henry VIII in 1534, it is the oldest university press in the world. It is also the King's Printer.
Cambridge University Pr ...
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
A dimensionless quantity (also known as a bare quantity, pure quantity, or scalar quantity as well as quantity of dimension one) is a quantity to which no physical dimension is assigned, with a corresponding SI unit of measurement of one (or ...
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
In mathematics, Laplace's method, named after Pierre-Simon Laplace, is a technique used to approximate integrals of the form
:\int_a^b e^ \, dx,
where f(x) is a twice- differentiable function, ''M'' is a large number, and the endpoints ''a'' ...
,
saddle-point method
In mathematics, the method of steepest descent or saddle-point method is an extension of Laplace's method for approximating an integral, where one deforms a contour integral in the complex plane to pass near a stationary point ( saddle point), in ...
,
method of steepest descent) or in the approximation of probability distributions (
Edgeworth series). The
Feynman graphs
In theoretical physics, a Feynman diagram is a pictorial representation of the mathematical expressions describing the behavior and interaction of subatomic particles. The scheme is named after American physicist Richard Feynman, who introduc ...
in
quantum field theory are another example of asymptotic expansions which often do not converge.
See also
*
Asymptote
*
Asymptotic computational complexity In computational complexity theory, asymptotic computational complexity is the usage of asymptotic analysis for the estimation of computational complexity of algorithms and computational problems, commonly associated with the usage of the big O nota ...
*
Asymptotic density (in number theory)
*
Asymptotic theory (statistics)
*
Asymptotology
*
Big O notation
*
Leading-order term
*
Method of dominant balance (for ODEs)
*
Method of matched asymptotic expansions
*
Watson's lemma In mathematics, Watson's lemma, proved by G. N. Watson (1918, p. 133), has significant application within the theory on the asymptotic behavior of integrals.
Statement of the lemma
Let 0 -1.
Suppose, in addition, either that
:, \varphi(t), ...
Notes
References
*
*
*
*
*
* {{citation, last1=Paris, first1= R. B., last2= Kaminsky, first2= D. , year=2001, title= Asymptotics and Mellin-Barnes Integrals, publisher=
Cambridge University Press
Cambridge University Press is the university press of the University of Cambridge. Granted letters patent by King Henry VIII in 1534, it is the oldest university press in the world. It is also the King's Printer.
Cambridge University Pr ...
, url=https://www.researchgate.net/publication/39064661
External links
''Asymptotic Analysis'' —home page of the journal, which is published by
IOS Press
A paper on time series analysis using asymptotic distribution
Mathematical series