Asymptotic analysis
Encyclopedia
In mathematical analysis
, asymptotic analysis is a method of describing limiting
behavior. The methodology has applications across science. Examples are
The simplest example is, when considering a function f(n), there is a need to describe its properties when n becomes very large. Thus, if f(n) = n2+3n, the term 3n becomes insignificant compared to n2 when n is very large. The function "f(n) is said to be asymptotically equivalent to n2 as n → ∞", and this is written symbolically as f(n) ~ n2.
to express the fact, stated terms of little-o notation, that
or equivalently
Explicitly this means that for every positive constant ε there exists a constant N such that
.
Unless g(n) is infinitely often zero (which would make the limit below undefined), this statement is also equivalent to
This relation is an equivalence relation on the set of functions of n. The equivalence class of f informally consists of all functions g which are approximately equal to f in a relative sense, in the limit.
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
but also
and
for each fixed k, while some limit is taken, usually with the requirement that gk+1 = o(gk), which means the (gk) form an asymptotic scale. The requirement that the successive sums improve the approximation may then be expressed as
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 (Laplace's method, 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.
and partial
differential equations which arise in the mathematical model
ling of real-world phenomena. 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 centre around a nondimensional parameter which has been shown, or assumed, to be small through a consideration of the scales of the problem at hand.
without solving it. The process is iterative in that the result obtained by performing the method once can be used as input when the method is repeated, to obtain as many terms in the asymptotic expansion
as desired.
The process is as follows:
1. Assume that the asymptotic behavior has the form
2. Make a clever guess as to which terms in the ODE may be negligible in the limit we are interested in.
3. Drop those terms and solve the resulting ODE.
4. Check that the solution is consistent with step 2. If this is the case, then we have the controlling factor of the asymptotic behavior. Otherwise, we need to try dropping different terms in step 2.
5. Repeat the process using our result as the first term of the solution.
This differential equation cannot be solved exactly. However, it may be useful to know how the solutions behave for large x.
We start by assuming
as 
. We do this with the benefit of hindsight, to make things quicker.
Since we only care about the behavior of y in the large x limit, we set y equal to
, and re-express the ODE in terms of S(x):
Now let us suppose that a solution to this new ODE satisfies
We get the dominant asymptotic behaviour by setting
If
satisfies the above asymptotic conditions, then everything is consistent. The terms we dropped will indeed have been negligible with respect to the ones we kept. 
is not a solution to the ODE for S, but it represents the dominant asymptotic behaviour, which is what we are interested in. Let us check that this choice for 
is consistent:
Everything is indeed consistent. Thus we find the dominant asymptotic behaviour of a solution to our ODE:
By convention, the asymptotic series is written as:
so to get at least the first term of this series we have to do another step to see if there is a power of x out the front.
We proceed by making an ansatz
that we can write
and then attempt to find asymptotic solutions for C(x). Substituting into the ODE for S(x) we find
Repeating the same process as before, we keep C' and (c-a)/x and find that
The leading asymptotic behaviour is therefore
Mathematical analysis
Mathematical analysis, which mathematicians refer to simply as analysis, has its beginnings in the rigorous formulation of infinitesimal calculus. It is a branch of pure mathematics that includes the theories of differentiation, integration and measure, limits, infinite series, and analytic functions...
, asymptotic analysis is a method of describing limiting
Limit (mathematics)
In mathematics, the concept of a "limit" is used to describe the value that a function or sequence "approaches" as the input or index approaches some value. The concept of limit allows mathematicians to define a new point from a Cauchy sequence of previously defined points within a complete metric...
behavior. The methodology has applications across science. Examples are
- in computer scienceComputer scienceComputer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
in the analysis of algorithmsAnalysis of algorithmsTo analyze an algorithm is to determine the amount of resources necessary to execute it. Most algorithms are designed to work with inputs of arbitrary length...
, considering the performance of algorithms when applied to very large input datasets - the behavior of physical systemPhysical systemIn physics, the word system has a technical meaning, namely, it is the portion of the physical universe chosen for analysis. Everything outside the system is known as the environment, which in analysis is ignored except for its effects on the system. The cut between system and the world is a free...
s when they are very large.
The simplest example is, when considering a function f(n), there is a need to describe its properties when n becomes very large. Thus, if f(n) = n2+3n, the term 3n becomes insignificant compared to n2 when n is very large. The function "f(n) is said to be asymptotically equivalent to n2 as n → ∞", and this is written symbolically as f(n) ~ n2.
Definition
Formally, given complex-valued functions f and g of a natural number variable n, one writesto express the fact, stated terms of little-o notation, that
or equivalently
Explicitly this means that for every positive constant ε there exists a constant N such that
.Unless g(n) is infinitely often zero (which would make the limit below undefined), this statement is also equivalent to
This relation is an equivalence relation on the set of functions of n. The equivalence class of f informally consists of all functions g which are approximately equal to f in a relative sense, in the limit.
Asymptotic expansion
An asymptotic expansionAsymptotic expansion
In mathematics an asymptotic expansion, asymptotic series or Poincaré expansion is a formal series of functions which has the property that truncating the series after a finite number of terms provides an approximation to a given function as the argument of the function tends towards a particular,...
of a function f(x) is in practice an expression of that function in terms of a series
Series (mathematics)
A series is the sum of the terms of a sequence. Finite sequences and series have defined first and last terms, whereas infinite sequences and series continue indefinitely....
, 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
Stirling's approximation
In mathematics, Stirling's approximation is an approximation for large factorials. It is named after James Stirling.The formula as typically used in applications is\ln n! = n\ln n - n +O\...
.
In symbols, it means we have
but also
and
for each fixed k, while some limit is taken, usually with the requirement that gk+1 = o(gk), which means the (gk) form an asymptotic scale. The requirement that the successive sums improve the approximation may then be expressed as
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 (Laplace's method, saddle-point method, method of steepest descent) or in the approximation of probability distributions (Edgeworth series
Edgeworth series
The Gram–Charlier A series , and the Edgeworth series are series that approximate a probability distribution in terms of its cumulants...
). The famous Feynman graphs in quantum field theory
Quantum field theory
Quantum field theory provides a theoretical framework for constructing quantum mechanical models of systems classically parametrized by an infinite number of dynamical degrees of freedom, that is, fields and many-body systems. It is the natural and quantitative language of particle physics and...
are another example of asymptotic expansions which often do not converge.
Use in applied mathematics
Asymptotic analysis is a key tool for exploring the ordinaryOrdinary differential equation
In mathematics, an ordinary differential equation is a relation that contains functions of only one independent variable, and one or more of their derivatives with respect to that variable....
and partial
Partial differential equation
In mathematics, partial differential equations are a type of differential equation, i.e., a relation involving an unknown function of several independent variables and their partial derivatives with respect to those variables...
differential equations which arise in the mathematical model
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 not only in the natural sciences and engineering disciplines A mathematical model is a...
ling of real-world phenomena. An illustrative example is the derivation of the boundary layer equations from the full Navier-Stokes equations
Navier-Stokes equations
In physics, the Navier–Stokes equations, named after Claude-Louis Navier and George Gabriel Stokes, describe the motion of fluid substances. These equations arise from applying Newton's second law to fluid motion, together with the assumption that the fluid stress is the sum of a diffusing viscous...
governing fluid flow. In many cases, the asymptotic expansion is in power of a small parameter,
: in the boundary layer case, this is the nondimensionalDimensional analysis
In physics and all science, dimensional analysis is a tool to find or check relations among physical quantities by using their dimensions. The dimension of a physical quantity is the combination of the basic physical dimensions which describe it; for example, speed has the dimension length per...
ratio of the boundary layer thickness to a typical lengthscale of the problem. Indeed, applications of asymptotic analysis in mathematical modelling often centre around a nondimensional parameter which has been shown, or assumed, to be small through a consideration of the scales of the problem at hand.
Method of dominant balance
The method of dominant balance is used to determine the asymptotic behavior of solutions to an ODEOrdinary differential equation
In mathematics, an ordinary differential equation is a relation that contains functions of only one independent variable, and one or more of their derivatives with respect to that variable....
without solving it. The process is iterative in that the result obtained by performing the method once can be used as input when the method is repeated, to obtain as many terms in the asymptotic expansion
Asymptotic expansion
In mathematics an asymptotic expansion, asymptotic series or Poincaré expansion is a formal series of functions which has the property that truncating the series after a finite number of terms provides an approximation to a given function as the argument of the function tends towards a particular,...
as desired.
The process is as follows:
1. Assume that the asymptotic behavior has the form
-
.
2. Make a clever guess as to which terms in the ODE may be negligible in the limit we are interested in.
3. Drop those terms and solve the resulting ODE.
4. Check that the solution is consistent with step 2. If this is the case, then we have the controlling factor of the asymptotic behavior. Otherwise, we need to try dropping different terms in step 2.
5. Repeat the process using our result as the first term of the solution.
Example
Consider this second order ODE:
-
- where c and a are arbitrary constants.
This differential equation cannot be solved exactly. However, it may be useful to know how the solutions behave for large x.
We start by assuming
as . We do this with the benefit of hindsight, to make things quicker.Since we only care about the behavior of y in the large x limit, we set y equal to
, and re-express the ODE in terms of S(x):
-
, or
-
- where we have used the product ruleProduct ruleIn calculus, the product rule is a formula used to find the derivatives of products of two or more functions. It may be stated thus:'=f'\cdot g+f\cdot g' \,\! or in the Leibniz notation thus:...
and chain ruleChain ruleIn calculus, the chain rule is a formula for computing the derivative of the composition of two or more functions. That is, if f is a function and g is a function, then the chain rule expresses the derivative of the composite function in terms of the derivatives of f and g.In integration, the...
to find the derivatives of y.
- where we have used the product rule
Now let us suppose that a solution to this new ODE satisfies
-
as 
-
as 
We get the dominant asymptotic behaviour by setting
If
satisfies the above asymptotic conditions, then everything is consistent. The terms we dropped will indeed have been negligible with respect to the ones we kept. is not a solution to the ODE for S, but it represents the dominant asymptotic behaviour, which is what we are interested in. Let us check that this choice for is consistent:
Everything is indeed consistent. Thus we find the dominant asymptotic behaviour of a solution to our ODE:
By convention, the asymptotic series is written as:
so to get at least the first term of this series we have to do another step to see if there is a power of x out the front.
We proceed by making an ansatz
Ansatz
Ansatz is a German noun with several meanings in the English language.It is widely encountered in physics and mathematics literature.Since ansatz is a noun, in German texts the initial a of this word is always capitalised.-Definition:...
that we can write
and then attempt to find asymptotic solutions for C(x). Substituting into the ODE for S(x) we find
Repeating the same process as before, we keep C' and (c-a)/x and find that
The leading asymptotic behaviour is therefore
