San José State University
Department of Economics

applet-magic.com
Thayer Watkins
Silicon Valley
& Tornado Alley
USA

Asymptotic Orders of Functions:
Big O and Little o

The functions, Big O and Little o, are functions from the set of functions to the set of equivalence classes. Their definitions are as follows:

The more convenient tests are:

Perturbation Theory

Example: Particle Motion Near a Planet's Surface

Let R be the radius of the planet and y be the distance above its surface. The distance to the center of mass of the planet is thus R+y and hence the force upon a particle of mass m is

-GmM/(R+y)2,

where M is the mass of the planet and G is the gravitational constant.

By Newton's First Law

md2/dt2((R+y)r^) =
-GmM/(R+y)2r^,

where r^ is a unit vector directed radially away from the center of the planet.

The mass of the particle cancels. For convenience let GM/R2 and note that R is a constant so the equation for the motion of the particle reduces to:

d2/dt2 ((R+y)r^) =
d2/dt2(yr^) =
-gR2/(R+y)2r^.

Since all motion takes place in the radial direction the r^ can be dropped from the analysis.

A particle at the surface of the planet with an initial vertical velocity of V and subjected to an acceleration of -g will rise to an maximum altitude of V2/2g. For convenience later let us define the characteristic length hm as twice this height; i.e.,

hm = V2/g.

The time taken for the velocity to fall from the initial V to zero is

tm = V/g.

Define new nondimensional variables

x = y/hm
and s = t/tm.

The equation of motion is then:

[hm/tm2]d2x/ds2 = -gR2/[hmx +R]2<.

Since [hm/tm2] = g the equation of motion can be reduced to:

d2x/ds2 = -[(hm/R)x + 1]-2.

The quantity hm/R is small and nondimensional; let us call it ε. Now the equation of motion is:

d2x/ds2 = -[1 + εx]-2.

the initial conditions are now that:

x(0) = 0 and dx(0)/ds = 1.

The function on the righthand side of the equation can be expanded into a power series in εx. Note that

[1+z]-1 = 1 - z + z2 - z3 + ....

If we take the derivative of each side of this equation we get

-[1+z]-2 = -1 + 2z - 3z2 +....

Thus the equation of motion takes the form:

d2x/ds2 =
-1 + 2(εx) - 3(εx)2 +....

If x(s, ε) has an expansion of the form:

x(s, ε) = Σxi(s) εi
for i = 0 to infinity.

Then it must be that:

x0" + x1"ε + x2"(ε)2 + . . . = -1 +
2ε[x0 + x1ε + x2(ε)2 + . . .]
- 3ε2[x0 + x1ε + x2(ε)2 + . . .]
+ 4ε3[x0 + x1ε + x2(ε)2 + . . .] + . . .

The coefficient of each power of ε must be the same on each side of the above equation. Therefore:

ε0:   x0" = -1;
ε1:   x1" = 2x0;
ε2:   x1" = 2x1 - 3x02;

The initial condition of x(0)=0 implies that

xi(0) = 0 for all i

and the initial condition of x'(0)=1 implies that

x0(0) = 1 and
xi(0) = 0 for all i>0

These initial value problems can be solved successively. The results are:

x0 = -(1/2)s2 + s;
x1 = - (1/12)s4 + (1/3)t3
x2 = - (11/360)s6 + (11/60)s5
- (1/4)s4

Therefore we have:

x(s, ε) = (-(1/2)s2 + s) +
ε(- (1/12)s4 + (1/3)s3) +
ε2(- (11/360)s6 + (11/60)s5
- (1/4)s4) + . . .

The analytic solution to:

d2x/ds2 = -[1 + εx]-2
with the initial conditions that
x(0) = 0 and dx(0)/ds = 1

can be achieved conveniently by letting [1 + εx]=z and s=rε so the equation of motion becomes:

z2d2z/dr2=-1

and the initial conditions are now that z(0)=1 and dz/dr(0)=1. Now the equation can be integrated using the technique of integration by parts.

Thus,

z2dz/dr -1 - ∫ 2z(dz/dr)dr = -r

or

z2dz/dr -1 + z2 -1 = -r

Regular Perturbation

Consider a Taylor series expansion such as

exp(-εt) -1 = -εt + (-εt)2/2! + . . .

Such a series is said to be uniform or asymptotically regular if

O((εt)2) < O(εt).

But if

O(εt) = O(1)

then the series ordering breaks down and the series is said to be nonuniform and cannot be used for approximations. The region where the series ordering breaks down is called a boundary layer.

Asymptotic Series

Consider the differential equation:

dy/dx + y = 1/x

If one looks for a solution to this equation in the form of series in x that is valid as x- >∞ one obtains:

Y(x) = 1/x + 1/x2 + 2!/x3 + ... + (n-1)!/xn + . . .

As can be seen from the ratio test this series does not converge.

Perturbation Analysis of a Damped Linear Oscillator

Consider

md2Y/dT2 + bdY/dT + kY = I0δ(T),
Y(0-) = 0, dY/dT(0-) = 0
where δ(T) is the Dirac delta function.

An integration over 0- to 0+ produces the result:

md2Y/dT2 + bdY/dT + kY = 0
Y(0+ = 0, dY/dT(0+)= I0/m

This equation can be put into nondimensional form by making the substitutions

t = [k/m]1/2T,
ε = b/(2[km]1/2
y = Y[km]1/2/I0

The nondimensional form of the equation is then:

d2y/dt2 + 2εdy/dt + y = 0
y(0+ = 0, dy/dt(0+)= 1

The exact solution of this system is known and it is:

y(t) =
exp(-εt)sin([1-εt]1/2t)/ [1-εt]1/2

This exact solution is useful for comparison with the approximation derived using perturbation theory.

Regular perturbation theory makes the assumption that the solution can be expression in a series of the form:

y(t,ε) = f0(t) + εf1(t) + ε2 f2(t) + . . .

When this series form is substituted into the differential equation the result is:

f"0(t) + εf"1(t) + ε2 f"2(t) + . . .
     2εf'0(t) + 2ε2f'1(t) +
                                             2ε3 f'2(t) + . . .
f0(t) + εf1(t) + ε2 f2(t) + . . .
= 0

Equating the coefficients of the poweres of ε to zero gives:

ε0: f"0(t) + f0(t)= 0;
ε1: f"1(t) + 2f'0(t) + f1(t) = 0

the initial conditions are that:

f0(0) = 0, f'0(0) = 1
f1(0) = 0, f'1(0) = 0

The solutions are:

f0(t) = sin(t), f1(0) = -tsin(t),

Thus the approximate solution is:

y(t,ε) (1 - εt)sin(t)

This approximation is good only for ε t being small. For sufficiently large t the approximate solution differs very drastically from the exact solution.

Singular Perturbation Analysis

The previous example illustrates regular perturbation ananlysis where the damping coefficient is a vanishingly small parameter. But the damped linear oscillator also provides a case of singular perturbation analysis when the mass is a vanishingly small parameter.

The difference between the two cases is that mass is the coefficient of the second derivative in the equation so its vanishing reduces the order of the differential equation from two to one. This reduction in order makes it impossible to simultaneously satisfy both initial conditions. This problem leads to boundary layer phenomena.

First consider the limiting case of m=0. The original system is then

bdY/dT + kY = I0δ, Y(0-)=0.

Integration across 0- to 0+ gives

bY(0+) = I0

Now the system for t>0 is

bdY/dT + kY = 0 and Y(0+) = I0/b.

The solution to this initial value problem is:

Y(T) = (I0/b)[1 - exp(-bt/m)].

The original problem can be transformed into a nondimensional form by letting

y =(b/I0)Y, t =(k/b)T,
and ε = mk/b2.

The result of these transformations is:

εd2y/dt2 + dy/dt + y 0
y(0) = 0, y'(0) = 1/ε.

The initial condition of y'(0) = 1/ε precludes the series used in regular perturbation analysis because such an initial condition cannot be satisfied by that series. An alternatet series is:

y(t, ε) =
ν0(ε)h0(t) + ν1(ε)h1(t) + ν2(ε)h2(t) +
where νn+1 o(νn)
so νn+1n -> 0 as ε ->0.

Substitution of this form into the nondimensional differential equation results in

          ε0(ε)h"0(t) + εν1(ε)h"1(t) + εν2(ε)h"2(t) +
ν0(ε)h'0(t) + ν1(ε)h'1(t) +
ν2(ε)h'2(t) +
ν0(ε)h0(t) + ν1(ε)h1(t) +
ν2(ε)h2(t) = 0

Since the νn(ε) are of different orders of magnitude we get the conditions

h'0(t) + h0(t) = 0
and
h'1(t) + h1(t) + h"0(t) = 0
if h0(t) = εν0(ε) = ν1(ε)
or
h'1(t) + h1(t) = 0
if εν 0(ε)/ ν1(ε) ->0 as ε ->0.

and likewise for n>1.

The initial conditions for the hn(t) functions are uncertain.

Leaving the initial conditions unspecified, the solutions for h0(t) and h1(t) are:

h0(t) = A0exp(-t)
and
h1(t) = A1exp(-t) - A0t exp(-t)
if εν01=1
or
h1(t) = A1exp(-t)
if εν01=0

This is the outer solution.

Inner Solution

An inner solution is a solution which is valid in the vicinity of the boundary or intitial condition. In this an inner solution is one that is valid for small values of time.

Consider a general transformation of the time variable; i.e.,

τ = t/ φ (ε)
where φ(ε) ->0 as ε->0

In terms of τ the differential equation is:

(ε/φ2(ε)(d2y/dτ2) + (1/φ(ε))(dy/dτ) + y = 0.

Now consider the various possibilities for φ (ε).

Case I: ord(φ) < ord(ε)

In this case (ε/φ) -> 0 as ε -> 0.

Since

(d2y/dτ2) + (φ(ε)/ε)(dy/dτ) + (φ2/ε)y = 0 and hence as ε -> 0 the equation goes to
d2y/dτ2 = 0.

Since this is a second order equation the initial conditions of y(0)= 0 and y'(0) = 1/ε can be satisfied.

Case I: φ(ε) = ε

In this case the differential equation, in terms of τ, becomes:

(d2y/dτ2) + (dy/dτ) + εy = 0
and hence in the limit as ε -> 0 the equation goes to
d2y/dτ2 + dy/dτ
which has the solution
y(τ) = 1 - exp(-τ)
= 1 - exp(-t/ε)

(to be continued)