Asymptotic Computation

Devendra Kapadia, 
Wolfram Research, Inc.

Join the Conversation #WolframTechConf

Outline of the Talk

In this talk, I will give an overview of Asymptotic Computation as follows:

Stirling’s Formula

The Asymptotic Function

Integrals, Integral Transforms and Differential Equations

The DiscreteAsymptotic Function

Sums, Products, Summation Transforms and Difference Equations

Asymptotics of Algebraic and Transcendental Equations

Stirling’s Formula

Stirling's formula gives an asymptotic approximation to the factorial function:

AsymptoticEquivalent[x!,(Sqrt[2 π ]) (E^(-x)) (x^(x+(1/2))) ,x->∞]

The ratio of the functions goes to 1.

(Underscript[\[Limit], x->∞])((x!)/((Sqrt[2 π ]) (E^(-x)) (x^(x+(1/2)))))

Asymptotic and DiscreteAsymptotic compute asymptotic approximations for functions, sequences and operators.

The Asymptotic Function

Find the leading asymptotic approximation for Sin at 0:

Asymptotic[Sin[x],x->0]

Plot the function and the approximation:

Plot[{Sin[x],x},{x,-2π,2π},PlotLegends->"Expressions"]

Use SeriesTermGoal to obtain a better approximation:

Asymptotic[Sin[x],x->0,SeriesTermGoal->12]

Plot[{Sin[x],%},{x,-2π,2π}]

A Gallery of Function Asymptotics

Visualize the leading behaviors for a set of functions:

f(x_):={2 (x^3)+3 x+1,(((x^3)-4)/((x^3)-9)),sin(x),(AiryAi[x]),(x^2) cos(8 π x),(PrimePi[x])};

a1={∞,∞,0,∞,0,∞};range={{-5,20},{-8,10},{-π/2,π/2},{-5,5},{-1,1},{10000,200000}};asym={2x^3,1,x,((E^(-((2 (x^(3/2)))/3)))/(2 (Sqrt[π]) (x^(1/4)))),x^2,x/Log[x]};Grid[Partition[Table[With[{r1=f[x][[n]],r2=a1[[n]],r3=range[[n]],r4=asym[[n]],r5=f[x][[n]]},
Plot[{r1,r4},{x,r3[[1]],r3[[2]]},ImageSize->250,PlotLabel->r1,PlotStyle->{{Thickness[0.015],Red},{Thickness[0.015],Dashing[0.03],Blue}}]],
{n,1,6}],2],Frame->All]

Integrals

Approximate a definite integral using Asymptotic:

Asymptotic[(InactiveIntegrate[log((a^2)-2 a cos(x)+1), x, 0, π]), a -> ∞]//Timing

AsymptoticIntegrate[Log[1-2 a Cos[x]+a^2],{x,0,Pi},{a,∞,1}]

The result is exact because the higher-order terms do not contribute to the integral.

Series[Log[1-2 a Cos[x]+(a^2)],{a,∞,3}]//Expand//Normal

Plot[Evaluate[List@@%/.{a-> 1.2}],{x,0,Pi},PlotStyle->Thickness[0.01]]

Integral Transforms

Compute the leading term for a Laplace transform:

f[t_]:=(1/((E^(t^2))+(t^17)))

Plot[f[t],{t,0,2},PlotStyle->Red,Filling->Axis]

Asymptotic[Inactive[LaplaceTransform][f[t],t,s],s->∞]

Compare with a numerical approximation:

%/.{s-> 270.}

NIntegrate[f[t]*E^(-270 t),{t,0,∞}]

Compute the leading term for an inverse Laplace transform:

Asymptotic[InverseLaplaceTransform[(1/(s (Sqrt[(s^3)+1]))),s,t],t->0]

Differential Equations

Consider the following linear ODE with a nonrational coefficient:

deqn=(x^3) y''[x]-(E^x) y[x]==0;

The equation has a singular point at x=0:

ComplexPlot[((E^x)/(x^3)),{x,-2 π-5 I,2 π+5 I}]

Compute an asymptotic series solution for the equation:

Asymptotic[DSolveValue[deqn,y[x],x],{x,0,2}]

Asymptotics of Sequences

Find the leading asymptotic term for n! as n approaches Infinity:

DiscreteAsymptotic[n!,n->∞]

Create a table of leading asymptotic terms for sequences:

flist = {n!,Fibonacci[n], HarmonicNumber[n],Prime[n],Zeta[n],Binomial[n,m],Pochhammer[a,n],EulerE[2n],PartitionsP[n]}; Grid[Join[{{"Sequence","Leading Asymptotic"}},Transpose[{flist,Map[DiscreteAsymptotic[#,n->Infinity]&,flist]}]],Background->{None,{{None,GrayLevel[.9]}},{{1,1}->Hue[.6,.4,1],{1,2}->Hue[.6,.4,1]}},BaseStyle->{FontFamily->Times,FontSize->16,Bold},Dividers->All,FrameStyle->Hue[.6,.4,.8],Spacings->{2,1}]//TraditionalForm

Sums and Products

Compute the leading asymptotic term for a divergent sum:

AsymptoticSum[(((((-1))^n) (Gamma[3 n+(1/2)]))/((((((2 (z^(3/2)))/3)))^n) ((2^n)*(3^(3 n)) (Gamma[n+(1/2)]) (Gamma[n+1])))),{n,0,∞},{z,0,1},Regularization->"Borel",Assumptions->z>0]

Asymptotic expansion for an algebraic product:

AsymptoticProduct[(((k^(13/4))-1)/((k^(13/4))+1)),{k,2,n},{n,∞,3}]

Compare with the exact result:

%/.{n->80}

(∏_(k=2.)^80)(((k^(13/4))-1)/((k^(13/4))+1))

Summation Transforms

Find the asymptotic behavior of a sequence using its generating function:

genfun=(1/(2-(E^z)));

Table[SeriesCoefficient[genfun,{z,0,n}],{n,0,20,5}]

N[%]

Apply DiscreteAsymptotic to compute an asymptotic approximation:

asy=DiscreteAsymptotic[SeriesCoefficient[genfun,{z,0,n}],n->∞]

Compare the approximation with the values of the sequence:

Table[asy,{n,0,20,5}]//N

Difference Equations

Find an asymptotic approximation for the complexity of Karatsuba multiplication:

AsymptoticRSolveValue[{t[n]==3 t[(n/2)+1]+n,t[3]==1},t[n],{n,∞,1}]

N[%]

Compare with the complexity of schoolbook multiplication:

DiscretePlot[{%,(n^2)},{n,5,300},PlotLegends->{"Karatsuba","Schoolbook"}]

Algebraic and Transcendental Equations

Solve Kepler's equation for the eccentric anomaly Ε in terms of the mean anomaly M:

AsymptoticSolve[M==Ε-e Sin[Ε],{Ε,0},{M,0,7}]

Compare with the exact solution for eccentricity e=(1/2):

asympt=First[Ε/.%]/.e->1/2;
exact[M_]:=First[Ε/.Solve[M==Ε-1/2Sin[Ε],Ε,Reals]//Quiet]

Plot[{asympt,exact[M]},{M,0,0.7},PlotStyle->{{Dashed,Thickness[0.01]},Thickness[0.01]},PlotLegends->"Expressions"]

Further examples are available on the reference page for AsymptoticSolve.

Summary and Outlook

Asymptotics provides a powerful third mode of computation, along with symbolic and and numerical methods.

We hope to add further support for asymptotics including continued fractions, multivariate integrals, etc.