Asymptotic analysis




This article is about the behavior of functions as inputs approach infinity, or some other limit value. For asymptotes in geometry, see Asymptote.

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. The theorem states that if π(x) (where π is a function, and is not related to the constant Pi) is the number of prime numbers that are less than or equal to x, then


π(x)∼xlog⁡x.{displaystyle pi (x)sim {frac {x}{log x}}.}{displaystyle pi (x)sim {frac {x}{log x}}.}



Contents






  • 1 Definition


  • 2 Properties


  • 3 Examples of asymptotic formulas


  • 4 Asymptotic expansion


    • 4.1 Examples of asymptotic expansions


    • 4.2 Worked example




  • 5 Asymptotic distribution


  • 6 Applications


  • 7 See also


  • 8 Notes


  • 9 References


  • 10 External links





Definition


Formally, given functions f(x) and g(x), we define a binary relation


f(x)∼g(x)(as x→∞){displaystyle f(x)sim g(x)quad ({text{as }}xto infty )}{displaystyle f(x)sim g(x)quad ({text{as }}xto infty )}

if and only if (de Bruijn 1981, §1.4)


limx→∞f(x)g(x)=1.{displaystyle lim _{xto infty }{frac {f(x)}{g(x)}}=1.}{displaystyle lim _{xto infty }{frac {f(x)}{g(x)}}=1.}

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 little-o notation, is that f ~ g if and only if


f(x)−g(x)=o(g(x)).{displaystyle f(x)-g(x)=o(g(x)).}{displaystyle f(x)-g(x)=o(g(x)).}

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 f∼g{displaystyle fsim g}fsim g and a∼b{displaystyle asim b}asim b, then under some mild conditions, the following hold.




  • fr∼gr{displaystyle f^{r}sim g^{r}}{displaystyle f^{r}sim g^{r}}, for every real r

  • log⁡(f)∼log⁡(g){displaystyle log(f)sim log(g)}{displaystyle log(f)sim log(g)}

  • f×a∼g×b{displaystyle ftimes asim gtimes b}{displaystyle ftimes asim gtimes b}

  • f/a∼g/b{displaystyle f/asim g/b}{displaystyle f/asim g/b}


Such properties allow asymptotically-equivalent functions to be freely exchanged in many algebraic expressions.



Examples of asymptotic formulas


  • Factorial


n!∼2πn(ne)n{displaystyle n!sim {sqrt {2pi n}}left({frac {n}{e}}right)^{n}}{displaystyle n!sim {sqrt {2pi n}}left({frac {n}{e}}right)^{n}}

—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.
p(n)∼14n3eπ2n3{displaystyle p(n)sim {frac {1}{4n{sqrt {3}}}}e^{pi {sqrt {frac {2n}{3}}}}}{displaystyle p(n)sim {frac {1}{4n{sqrt {3}}}}e^{pi {sqrt {frac {2n}{3}}}}}


  • Airy function

The Airy function, Ai(x), is a solution of the differential equation  y'' − xy = 0; it has many applications in physics.
Ai⁡(x)∼e−23x322πx1/4{displaystyle operatorname {Ai} (x)sim {frac {e^{-{frac {2}{3}}x^{frac {3}{2}}}}{2{sqrt {pi }}x^{1/4}}}}{displaystyle operatorname {Ai} (x)sim {frac {e^{-{frac {2}{3}}x^{frac {3}{2}}}}{2{sqrt {pi }}x^{1/4}}}}


  • Hankel functions

Hα(1)(z)∼2πzei(z−2πα−π4)Hα(2)(z)∼2πze−i(z−2πα−π4){displaystyle {begin{aligned}H_{alpha }^{(1)}(z)&sim {sqrt {frac {2}{pi z}}}e^{ileft(z-{frac {2pi alpha -pi }{4}}right)}\H_{alpha }^{(2)}(z)&sim {sqrt {frac {2}{pi z}}}e^{-ileft(z-{frac {2pi alpha -pi }{4}}right)}end{aligned}}}{displaystyle {begin{aligned}H_{alpha }^{(1)}(z)&sim {sqrt {frac {2}{pi z}}}e^{ileft(z-{frac {2pi alpha -pi }{4}}right)}\H_{alpha }^{(2)}(z)&sim {sqrt {frac {2}{pi z}}}e^{-ileft(z-{frac {2pi alpha -pi }{4}}right)}end{aligned}}}


Asymptotic expansion


Main article: Asymptotic expansion

An asymptotic expansion of a function f(x) 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 f. The idea is that successive terms provide an increasingly accurate description of the order of growth of f.


In symbols, it means we have


f∼g1{displaystyle fsim g_{1}}f sim g_1

but also


f−g1∼g2{displaystyle f-g_{1}sim g_{2}}f - g_1 sim g_2

and


f−g1−⋯−gk−1∼gk{displaystyle f-g_{1}-cdots -g_{k-1}sim g_{k}}f - g_1 - cdots - g_{k-1} sim g_{k}

for each fixed k.


In view of the definition of the ∼{displaystyle sim }sim symbol, the last equation means


f−(g1+⋯+gk)=o(gk){displaystyle f-(g_{1}+cdots +g_{k})=o(g_{k})}f - (g_1 + cdots + g_k) = o(g_k)

in the little o notation, i.e.,



f−(g1+⋯+gk){displaystyle f-(g_{1}+cdots +g_{k})}f - (g_1 + cdots + g_k) is much smaller than gk{displaystyle g_{k}}g_{k}.

The relation



f−g1−⋯−gk−1∼gk{displaystyle f-g_{1}-cdots -g_{k-1}sim g_{k}}f - g_1 - cdots - g_{k-1} sim g_{k} takes its full meaning if ∀k,gk+1=o(gk){displaystyle forall k,g_{k+1}=o(g_{k})}forall k, g_{k+1} = o(g_k),

which means the gk{displaystyle g_{k}}g_{k} form an asymptotic scale.


In that case, some authors may abusively write


f∼g1+⋯+gk{displaystyle fsim g_{1}+cdots +g_{k}}f sim g_1 + cdots + g_{k}

to denote the statement


f−(g1+⋯+gk)=o(gk).{displaystyle f-(g_{1}+cdots +g_{k})=o(g_{k}),.}f - (g_1 + cdots + g_k) = o(g_k),.

One should however be careful that this is not a standard use of the ∼{displaystyle sim }sim symbol, and that it does not correspond to the definition given in § Definition.


In the present situation, this relation gk=o(gk−1){displaystyle g_{k}=o(g_{k-1})}g_{k} = o(g_{k-1}) actually follows from combining steps k and (k − 1),
by subtracting f−g1−⋯−gk−2=gk−1+o(gk−1){displaystyle f-g_{1}-cdots -g_{k-2}=g_{k-1}+o(g_{k-1})}f - g_1 - cdots - g_{k-2} = g_{k-1} + o(g_{k-1}) from f−g1−⋯−gk−2−gk−1=gk+o(gk){displaystyle f-g_{1}-cdots -g_{k-2}-g_{k-1}=g_{k}+o(g_{k})}f - g_1 - cdots - g_{k-2} - g_{k-1} = g_{k} + o(g_{k})
one gets


gk+o(gk)=o(gk−1),{displaystyle g_{k}+o(g_{k})=o(g_{k-1}),,}g_{k} + o(g_{k})=o(g_{k-1}),,

i.e., gk=o(gk−1){displaystyle g_{k}=o(g_{k-1})}g_{k} = o(g_{k-1}).


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

exxx2πxΓ(x+1)∼1+112x+1288x2−13951840x3−⋯ (x→∞){displaystyle {frac {e^{x}}{x^{x}{sqrt {2pi x}}}}Gamma (x+1)sim 1+{frac {1}{12x}}+{frac {1}{288x^{2}}}-{frac {139}{51840x^{3}}}-cdots (xrightarrow infty )}frac{e^x}{x^x sqrt{2pi x}} Gamma(x+1) sim 1+frac{1}{12x}+frac{1}{288x^2}-frac{139}{51840x^3}-cdots<br /> (x rightarrow infty)

  • Exponential integral

xexE1(x)∼∑n=0∞(−1)nn!xn (x→∞){displaystyle xe^{x}E_{1}(x)sim sum _{n=0}^{infty }{frac {(-1)^{n}n!}{x^{n}}} (xrightarrow infty )}xe^xE_1(x) sim sum_{n=0}^infty frac{(-1)^nn!}{x^n} (x rightarrow infty)

  • Error function


πxex2erfc(x)∼1+∑n=1∞(−1)n(2n−1)!!n!(2x2)n (x→∞){displaystyle {sqrt {pi }}xe^{x^{2}}{rm {erfc}}(x)sim 1+sum _{n=1}^{infty }(-1)^{n}{frac {(2n-1)!!}{n!(2x^{2})^{n}}} (xrightarrow infty )}{displaystyle {sqrt {pi }}xe^{x^{2}}{rm {erfc}}(x)sim 1+sum _{n=1}^{infty }(-1)^{n}{frac {(2n-1)!!}{n!(2x^{2})^{n}}} (xrightarrow infty )}
where (2n − 1)!! 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


11−w=∑n=0∞wn{displaystyle {frac {1}{1-w}}=sum _{n=0}^{infty }w^{n}}{frac {1}{1-w}}=sum _{{n=0}}^{infty }w^{n}

The expression on the left is valid on the entire complex plane w≠1{displaystyle wneq 1}wne 1, while the right hand side converges only for |w|<1{displaystyle |w|<1}|w|< 1. Multiplying by e−w/t{displaystyle e^{-w/t}}e^{-w/t} and integrating both sides yields


∫0∞e−wt1−wdw=∑n=0∞tn+1∫0∞e−uundu{displaystyle int _{0}^{infty }{frac {e^{-{frac {w}{t}}}}{1-w}},dw=sum _{n=0}^{infty }t^{n+1}int _{0}^{infty }e^{-u}u^{n},du}{displaystyle int _{0}^{infty }{frac {e^{-{frac {w}{t}}}}{1-w}},dw=sum _{n=0}^{infty }t^{n+1}int _{0}^{infty }e^{-u}u^{n},du}

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 u=w/t{displaystyle u=w/t}u=w/t, may be recognized as the gamma function. Evaluating both, one obtains the asymptotic expansion


e−1tEi⁡(1t)=∑n=0∞n!tn+1{displaystyle e^{-{frac {1}{t}}}operatorname {Ei} left({frac {1}{t}}right)=sum _{n=0}^{infty }n!;t^{n+1}}{displaystyle e^{-{frac {1}{t}}}operatorname {Ei} left({frac {1}{t}}right)=sum _{n=0}^{infty }n!;t^{n+1}}

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 Ei⁡(1/t){displaystyle operatorname {Ei} (1/t)}operatorname{Ei}(1/t). Substituting x=−1/t{displaystyle x=-1/t}{displaystyle x=-1/t} and noting that Ei⁡(x)=−E1(−x){displaystyle operatorname {Ei} (x)=-E_{1}(-x)}{displaystyle operatorname {Ei} (x)=-E_{1}(-x)} results in the asymptotic expansion given earlier in this article.



Asymptotic distribution


Main 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{displaystyle Z_{i}}Z_{i}

for i=1{displaystyle i=1}i=1 to n{displaystyle n}n, for some positive integer n{displaystyle n}n. An asymptotic distribution allows i{displaystyle i}i to range without bound, that is, n{displaystyle n}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 asymptotic 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=1x,{displaystyle y={frac {1}{x}},}{displaystyle y={frac {1}{x}},}

y{displaystyle y}y becomes arbitrarily small in magnitude as x{displaystyle x}x increases.



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.



  • 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 ordinary and partial differential equations which arise in the mathematical modelling of real-world phenomena.[3] 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 lengthscale of the problem. Indeed, applications of asymptotic analysis in mathematical modelling often[3] 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




  • Asymptote

  • Asymptotic computational complexity


  • 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




Notes




  1. ^ Hazewinkel, Michiel, ed. (2001) [1994], "Asymptotic equality", Encyclopedia of Mathematics, Springer Science+Business Media B.V. / Kluwer Academic Publishers, ISBN 978-1-55608-010-4.mw-parser-output cite.citation{font-style:inherit}.mw-parser-output q{quotes:"""""""'""'"}.mw-parser-output code.cs1-code{color:inherit;background:inherit;border:inherit;padding:inherit}.mw-parser-output .cs1-lock-free a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/6/65/Lock-green.svg/9px-Lock-green.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .cs1-lock-limited a,.mw-parser-output .cs1-lock-registration a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/d/d6/Lock-gray-alt-2.svg/9px-Lock-gray-alt-2.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .cs1-lock-subscription a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/a/aa/Lock-red-alt-2.svg/9px-Lock-red-alt-2.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .cs1-subscription,.mw-parser-output .cs1-registration{color:#555}.mw-parser-output .cs1-subscription span,.mw-parser-output .cs1-registration span{border-bottom:1px dotted;cursor:help}.mw-parser-output .cs1-hidden-error{display:none;font-size:100%}.mw-parser-output .cs1-visible-error{font-size:100%}.mw-parser-output .cs1-subscription,.mw-parser-output .cs1-registration,.mw-parser-output .cs1-format{font-size:95%}.mw-parser-output .cs1-kern-left,.mw-parser-output .cs1-kern-wl-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right,.mw-parser-output .cs1-kern-wl-right{padding-right:0.2em}


  2. ^ Estrada & Kanwal (2002, §1.2)


  3. ^ ab Howison, S. (2005), Practical Applied Mathematics, Cambridge University Press



References




  • Balser, W. (1994), From Divergent Power Series To Analytic Functions, Springer-Verlag


  • de Bruijn, N. G. (1981), Asymptotic Methods in Analysis, Dover Publications


  • Estrada, R.; Kanwal, R. P. (2002), A Distributional Approach to Asymptotics, Birkhäuser


  • Miller, P. D. (2006), Applied Asymptotic Analysis, American Mathematical Society


  • Murray, J. D. (1984), Asymptotic Analysis, Springer


  • 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




-

Popular posts from this blog

Eastern Orthodox Church

Image
Not to be confused with Oriental Orthodoxy, Eastern Christianity, or Eastern Catholic Churches. "Eastern Orthodoxy", "Orthodox Church", "Orthodox Catholic Church", and "Orthodox Christian Church" redirect here. For other uses, see Orthodox (disambiguation). This article may be too long to read and navigate comfortably . The readable prose size is 132 kilobytes. Please consider splitting content into sub-articles, condensing it, or adding or removing subheadings. ( January 2018 ) Part of a series on the Eastern Orthodox Church Mosaic of Christ Pantocrator, Hagia Sophia Overview Structure Theology (History of theology) Liturgy Church history Holy Mysteries View of salvation View of Mary View of icons Background Crucifixion / Resurrection / Ascension of Jesus Christianity Christian Church Apostolic succession Four Marks of the Church Orthodoxy Organization Autocephaly Patriarchate ...
Read more

Zagreb

Image
This article is about the Croatian capital city. For other uses, see Zagreb (disambiguation). City in City of Zagreb, Croatia Zagreb City Grad Zagreb City of Zagreb Clockwise, from top: St. Mark's Square, Croatian State Archives, Zagreb Tram, Art Pavilion, Cibona & HOTO towers and Croatian National Theatre. Flag Coat of arms Zagreb Location of Zagreb in Croatia Show map of Croatia Zagreb Zagreb (Europe) Show map of Europe Coordinates: 45°49′N 15°59′E  /  45.817°N 15.983°E  / 45.817; 15.983 Coordinates: 45°49′N 15°59′E  /  45.817°N 15.983°E  / 45.817; 15.983 Country   Croatia County City of Zagreb RC diocese 1094 Free royal city 1242 Unified 1850 Subdivisions 17 city districts 218 local committees (70 settlements) Government  • Type Mayor-Council  • Mayor Milan Bandić (BM 365)  • City Assembly 51 members BM 365, ZL, NS-R (14) SDP, GLAS, HNS, HSS, NH-PS (13) ...
Read more

Understanding the information contained in the Deep Space Network XML data?

Image
up vote 1 down vote favorite NASA's Deep Space Network activity can be viewed conveniently at https://eyes.nasa.gov/dsn/dsn.html but if you would like data in a more raw XML form, it can be accessed as described in this answer Below is a small Python script that reads the XML into a list of dictionaries, and saves it to disk as a JSON. The dictionaries are organized at the higher level by dish, then by spacecraft per dish. Question: What are the most-likely meanings of all the data field contained in the Deep Space Network XML data? This is the example url from the other answer, used in the script below: https://eyes.nasa.gov/dsn/data/1365107113.xml def dictify(r,root=True): # https://stackoverflow.com/questions/2148119/how-to-convert-an-xml-string-to-a-dictionary-in-python/30923963#30923963 if root: ret...
Read more