In pure and applied mathematics, particularly the analysis of algorithms, real analysis, and engineering, asymptotic analysis is a method of describing limiting behaviour. Similar limiting behaviour is sometimes expressed in the language of equivalence relations. Moreover, asymptotic analysis refers to solving problems approximately up to such equivalences. For example, given complex-valued functions f and g of a natural number variable n, one writes

f \sim g \quad (\mbox{as } n\to\infty)

to express the fact that

\lim_{n\to\infty} \frac{f(n)}{g(n)} = 1

and f and g are called asymptotically equivalent as n → ∞. This defines an equivalence relation (on the set of functions being nonzero for all n large enough - most mathematicians prefer the definition f\sim g\iff f-g=o(g) in terms of Landau notation, which avoids this restriction). The equivalence class of f consists of all functions g which "behave like" f, in the limit.

Asymptotic notation has been developed to provide a convenient language for the handling of statements about order of growth. It is also called Landau notation, since it became popular first in research in analytic number theory, from about 1900 onwards, introduced by Edmund Landau (originated though by Paul Bachmann). See also Big O notation, for a treatment more from the point of view of analysis of algorithms. The asymptotic point of view is basic in computer science, where the question is typically how to describe the resource implication of scaling-up the size of a computational problem, beyond the 'toy' level.

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 a more and more accurate description of the order of growth of f. An example is Stirling's approximation.

In symbols, it means we have

f \sim g_1

but also

f \sim g_1 + g_2

and

f \sim g_1 + \cdots + g_k

for each fixed k, while some limit is taken, usually with the requirement that g_k+1 = o(g_k), which means the (g_k) form an asymptotic scale. The requirement that the successive sums improve the approximation may then be expressed as f - (g_1 + \cdots + g_k) = o(g_k).

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. However, this optimal partial sum will usually have more terms as the argument approaches the limit value.

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

See also

• Asymptotic computational complexity

References

• Erdélyi, A. Asymptotic Expansions. New York: Dover, 1987.
• ^ J. P. Boyd, The Devil's Invention: Asymptotic, Superasymptotic and Hyperasymptotic Series, Acta Applicandae Mathematicae: An International Survey Journal on Applying Mathematics and Mathematical Applications 56, 1-98 (1999) PDF of preprint

de:Asymptotische Analyse ru:??????????????? ??????