Movatterモバイル変換

Asymptotic analysis

From Wikipedia, the free encyclopedia

Description of limiting behavior of a function

This article is about the behavior of functions as inputs approach infinity or some other limit value. For asymptotes ingeometry, seeAsymptote.

Inmathematical analysis,asymptotic analysis, also known asasymptotics, is a method of describinglimiting behavior.

As an illustration, suppose that we are interested in the properties of a functionf (n) asn becomes very large. Iff(n) =n² + 3n, then asn becomes very large, the term3n becomes insignificant compared ton². The functionf(n) is said to be "asymptotically equivalent ton², asn → ∞". This is often written symbolically asf (n) ~n², which is read as "f(n) is asymptotic ton²".

An example of an important asymptotic result is theprime number theorem. Letπ(x) denote theprime-counting function (which is not directly related to the constantpi), i.e.π(x) is the number ofprime numbers that are less than or equal tox. Then the theorem states that $\pi (x)\sim {\frac {x}{\ln x}}.$

Definition

[edit]

Formally, given functionsf (x) andg(x), we define abinary relation $f(x)\sim g(x)\quad ({\text{as }}x\to \infty )$ if and only if (de Bruijn 1981, §1.4) $\lim _{x\to \infty }{\frac {f(x)}{g(x)}}=1.$

The symbol~ is thetilde. The relation is anequivalence relation on the set of functions ofx; the functionsf andg are said to beasymptotically equivalent. Thedomain off andg 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 ifg(x) is zero infinitely often asx goes to the limiting value. For that reason, some authors use an alternative definition. The alternative definition, inlittle-o notation, is thatf ~g if and only if $f(x)=g(x)(1+o(1)).$

This definition is equivalent to the prior definition ifg(x) is not zero in someneighbourhood of the limiting value.^[1]^[2]

Properties

[edit]

If $f\sim g$ and $a\sim b$ , then, under some mild conditions,^{[further explanation needed]} the following hold:

$f^{r}\sim g^{r}$ , for every realr
$\log(f)\sim \log(g)$ if $\lim g\neq 1$
$f\times a\sim g\times b$
$f/a\sim g/b$

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

Also, if we further have $g\sim h$ , then, because the asymptote is atransitive relation, then we also have $f\sim h$ .

Examples of asymptotic formulas

[edit]

Factorial $n!\sim {\sqrt {2\pi n}}\left({\frac {n}{e}}\right)^{n}$ —this isStirling's approximation
Partition function
For a positive integern, the partition function,p(n), gives the number of ways of writing the integern as a sum of positive integers, where the order of addends is not considered. $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 equationy″ −xy = 0; it has many applications in physics. $\operatorname {Ai} (x)\sim {\frac {e^{-{\frac {2}{3}}x^{\frac {3}{2}}}}{2{\sqrt {\pi }}x^{1/4}}}$
Hankel functions ${\begin{aligned}H_{\alpha }^{(1)}(z)&\sim {\sqrt {\frac {2}{\pi z}}}e^{i\left(z-{\frac {2\pi \alpha -\pi }{4}}\right)}\\H_{\alpha }^{(2)}(z)&\sim {\sqrt {\frac {2}{\pi z}}}e^{-i\left(z-{\frac {2\pi \alpha -\pi }{4}}\right)}\end{aligned}}$

Asymptotic expansion

[edit]

Main article:Asymptotic expansion

Anasymptotic expansion of a functionf(x) is in practice an expression of that function in terms of aseries, thepartial sums of which do not necessarily converge, but such that taking any initial partial sum provides an asymptotic formula forf. The idea is that successive terms provide an increasingly accurate description of the order of growth off.

In symbols, it means we have $f\sim g_{1},$ but also $f-g_{1}\sim g_{2}$ and $f-g_{1}-\cdots -g_{k-1}\sim g_{k}$ for each fixedk. In view of the definition of the $\sim$ symbol, the last equation means $f-(g_{1}+\cdots +g_{k})=o(g_{k})$ in thelittle o notation, i.e., $f-(g_{1}+\cdots +g_{k})$ is much smaller than $g_{k}.$

The relation $f-g_{1}-\cdots -g_{k-1}\sim g_{k}$ takes its full meaning if $g_{k+1}=o(g_{k})$ for allk, which means the $g_{k}$ form anasymptotic scale. In that case, some authors mayabusively write $f\sim g_{1}+\cdots +g_{k}$ to denote the statement $f-(g_{1}+\cdots +g_{k})=o(g_{k}).$ One should however be careful that this is not a standard use of the $\sim$ symbol, and that it does not correspond to the definition given in§ Definition.

In the present situation, this relation $g_{k}=o(g_{k-1})$ actually follows from combining stepsk andk−1; by subtracting $f-g_{1}-\cdots -g_{k-2}=g_{k-1}+o(g_{k-1})$ from $f-g_{1}-\cdots -g_{k-2}-g_{k-1}=g_{k}+o(g_{k}),$ one gets $g_{k}+o(g_{k})=o(g_{k-1}),$ i.e. $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

[edit]

Gamma function ${\frac {e^{x}}{x^{x}{\sqrt {2\pi x}}}}\Gamma (x+1)\sim 1+{\frac {1}{12x}}+{\frac {1}{288x^{2}}}-{\frac {139}{51840x^{3}}}-\cdots \ (x\to \infty )$
Exponential integral $xe^{x}E_{1}(x)\sim \sum _{n=0}^{\infty }{\frac {(-1)^{n}n!}{x^{n}}}\ (x\to \infty )$
Error function ${\sqrt {\pi }}xe^{x^{2}}\operatorname {erfc} (x)\sim 1+\sum _{n=1}^{\infty }(-1)^{n}{\frac {(2n-1)!!}{n!(2x^{2})^{n}}}\ (x\to \infty )$ wherem!! is thedouble factorial.

Worked example

[edit]

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 theformal power series ${\frac {1}{1-w}}=\sum _{n=0}^{\infty }w^{n}$

The expression on the left is valid on the entirecomplex plane $w\neq 1$ , while the right hand side converges only for $|w|<1$ . Multiplying by $e^{-w/t}$ and integrating both sides yields $\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 theexponential integral. The integral on the right hand side, after the substitution $u=w/t$ , may be recognized as thegamma function. Evaluating both, one obtains the asymptotic expansion $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 oft. However, by keepingt 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 $\operatorname {Ei} (1/t)$ . Substituting $x=-1/t$ and noting that $\operatorname {Ei} (x)=-E_{1}(-x)$ results in the asymptotic expansion given earlier in this article.

Asymptotic distribution

[edit]

Main article:Asymptotic distribution

Inmathematical statistics, anasymptotic 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 variablesZ_i fori = 1, …,n, for some positive integern. An asymptotic distribution allowsi 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, theZ_i go to 0 asi goes to infinity. Some instances of "asymptotic distribution" refer only to this special case.

This is based on the notion of anasymptotic function which cleanly approaches a constant value (theasymptote) 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.

Anasymptote 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={\frac {1}{x}},$ y becomes arbitrarily small in magnitude asx increases.

Applications

[edit]

Asymptotic analysis is used in severalmathematical sciences. Instatistics, asymptotic theory provides limiting approximations of theprobability distribution ofsample statistics, such as thelikelihood ratio statistic and theexpected value of thedeviance. Asymptotic theory does not provide a method of evaluating the finite-sample distributions of sample statistics, however. Non-asymptotic bounds are provided by methods ofapproximation theory.

Examples of applications are the following.

Inapplied mathematics, asymptotic analysis is used to buildnumerical methods to approximateequation solutions.
Inmathematical statistics andprobability theory, asymptotics are used in analysis of long-run or large-sample behaviour of random variables and estimators.
Incomputer science, theanalysis of algorithms evaluate the performance of algorithms and is expressed in terms ofbig O notation.
The behavior ofphysical systems, an example beingstatistical mechanics.
Inaccident 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 theordinary andpartial differential equations which arise in themathematical modelling of real-world phenomena.^[3] An illustrative example is the derivation of theboundary layer equations from the fullNavier-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 thenondimensional ratio of the boundary layer thickness to a typicallength scale 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). TheFeynman graphs inquantum field theory are another example of asymptotic expansions which often do not converge.

Asymptotic versus Numerical Analysis

[edit]

De Bruijn illustrates the use of asymptotics in the following dialog between Dr. N.A., aNumerical Analyst, and Dr. A.A., an Asymptotic Analyst:

N.A.: I want to evaluate my function $f(x)$ for large values of $x {\displaystyle x}$ , with a relative error of at most 1%.
A.A.: $f(x)=x^{-1}+\mathrm {O} (x^{-2})\qquad (x\to \infty )$ .
N.A.: I am sorry, I don't understand.
A.A.: $|f(x)-x^{-1}|<8x^{-2}\qquad (x>10^{4}).$
N.A.: But my value of $x {\displaystyle x}$ is only 100.
A.A.: Why did you not say so? My evaluations give
$|f(x)-x^{-1}|<57000x^{-2}\qquad (x>100).$
N.A.: This is no news to me. I know already that $0<f(100)<1$ .
A.A.: I can gain a little on some of my estimates. Now I find that
$|f(x)-x^{-1}|<20x^{-2}\qquad (x>100).$
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 $x {\displaystyle x}$ ?
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]