Asymptotic analysis
In mathematical analysis, 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 f (n) as n becomes very large. If f(n) = n2 + 3n, then as n becomes very large, the term 3n becomes insignificant compared to n2. The function f(n) is said to be "asymptotically equivalent to n2, as n → ∞". This is often written symbolically as f (n) ~ n2, which is read as "f(n) is asymptotic to n2".
An example of an important asymptotic result is the prime number theorem. Let π(x) denote the prime-counting function (which is not directly related to the constant pi), i.e. π(x) is the number of prime numbers that are less than or equal to x. Then the theorem states that
Asymptotic analysis is commonly used in computer science as part of the analysis of algorithms and is often expressed there in terms of big O notation.
Definition
Formally, given functions f (x) and g(x), we define a binary relation
The symbol ~ is the tilde. The relation is an equivalence relation on the set of functions of x; the functions f and g are said to be asymptotically equivalent. The domain of f and g 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. x → 0, x ↓ 0, |x| → 0. 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 g(x) is zero infinitely often as x goes to the limiting value. For that reason, some authors use an alternative definition. The alternative definition, in
This definition is equivalent to the prior definition if g(x) is not zero in some neighbourhood of the limiting value.[1][2]
Properties
If and , then, under some mild conditions,[further explanation needed] the following hold:
- , for every real r
- if
Such properties allow asymptotically-equivalent functions to be freely exchanged in many algebraic expressions.
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 y″ − xy = 0; it has many applications in physics.
- Hankel functions
Asymptotic expansion
An
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
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
- Exponential integral
- Error function where m!! 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. 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 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 Zi for i = 1, …, n, for some positive integer n. An asymptotic distribution allows i to range without bound, that is, n is infinite.
A special case of an asymptotic distribution is when the late entries go to zero—that is, the Zi go to 0 as i goes to infinity. Some instances of "asymptotic distribution" refer only to this special case.
This is based on the notion of an
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
Examples of applications are the following.
- In applied mathematics, asymptotic analysis is used to build numerical methods to approximate equation solutions.
- In mathematical statistics and probability theory, asymptotics are used in analysis of long-run or large-sample behaviour of random variables and estimators.
- In computer science 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
Asymptotic expansions typically arise in the approximation of certain integrals (
Asymptotic versus Numerical Analysis
Debruijn illustrates the use of asymptotics in the following dialog between Miss N.A., a Numerical Analyst, and Dr. A.A., an Asymptotic Analyst:
N.A.: I want to evaluate my function for large values of , with a relative error of at most 1%.
A.A.: .
N.A.: I am sorry, I don't understand.
A.A.:
N.A.: But my value of is only 100.
A.A.: Why did you not say so? My evaluations give
N.A.: This is no news to me. I know already that .
A.A.: I can gain a little on some of my estimates. Now I find that
N.A.: I asked for 1%, not for 20%.
A.A.: It is almost the best thing I possibly can get. Why don't you take larger values of ?
N.A.: !!! I think it's better to ask my electronic computing machine.
Machine: f(100) = 0.01137 42259 34008 67153
A.A.: Haven't I told you so? My estimate of 20% was not far off from the 14% of the real error.
N.A.: !!! . . . !
Some days later, Miss N.A. wants to know the value of f(1000), but her machine would take a month of computation to give the answer. She returns to her Asymptotic Colleague, and gets a fully satisfactory reply.[4]
See also
- Asymptote – Limit of the tangent line at a point that tends to infinity
- Asymptotic computational complexity – in theory of computation
- Asymptotic density– Concept in number theory
- Asymptotic theory (statistics) – Study of convergence properties of statistical estimators
- Asymptotology – Dealing with applied mathematical systems in limiting cases
- Big O notation – Describes limiting behavior of a function
- Leading-order term – Terms in a mathematical expression with the largest order of magnitude
- Method of dominant balance – Method to determine the asymptotic behavior of solutions to ODEs without fully solving the equation
- Method of matched asymptotic expansions
- Watson's lemma – lemma on the asymptotic behavior of integrals
Notes
- ^ "Asymptotic equality", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
- ^ Estrada & Kanwal (2002, §1.2)
- ^ a b Howison, S. (2005), Practical Applied Mathematics, Cambridge University Press
- ISBN 978-0-486-64221-5.
References
- Balser, W. (1994), From Divergent Power Series To Analytic Functions, ISBN 9783540485940
- ISBN 9780486642215
- Estrada, R.; Kanwal, R. P. (2002), A Distributional Approach to Asymptotics, ISBN 9780817681302
- Miller, P. D. (2006), Applied Asymptotic Analysis, ISBN 9780821840788
- Murray, J. D. (1984), Asymptotic Analysis, Springer, ISBN 9781461211228
- Paris, R. B.; Kaminsky, D. (2001), Asymptotics and Mellin-Barnes Integrals, Cambridge University Press
External links
- Asymptotic Analysis —home page of the journal, which is published by IOS Press
- A paper on time series analysis using asymptotic distribution