`Computing Special Functions via Inverse Laplace Transforms J.A.C. Weideman Department of Applied Mathematics University of Stellenbosch South Africahttp://dip.sun.ac.za/ weideman Thanks to: · The Organizers of ICNAAM05 · COMLAB, Exeter College (Oxford) · NRF grant 2053756 · Kevin Burrage, Thomas Schmelzer, and Nick TrefethenOutline PART 1. N UMERICAL INVERSION OF THE L APLACE T RANSFORM 1 · Talbot's method on new contours f(t) = etzF(z) dz 2i  · Rational approximation to the exponential PART 2. A PPLICATION TO THE C OMPUTATION OF S PECIAL F UNCTIONS · The exponential function · The Mittag-Leffler functions · The gamma function · The exponential integral · Application to PDEsPART 1. I NVERSION OF THE L APLACE T RANSFORMLaplace Transform and Inverse Formula (Bromwich)  1 +i tz F(z) = e-ztf(t) dt, f(t) = e F(z) dz, 2i -i 0Im z &gt; 00Re zBromwich Integral: 1 f(t) = 2i+i -ietzF(z) dz, &gt; 0 Will considerEfficient quadrature rules for this integral?· Talbot's method (= trapezoidal rule on deformed contour) · Rational approximation to exp(z) Several details are in fact For example, · In Talbot's method, new contours and improved parameters, and · In the rational approximant method, the use of ´ best approximation rather than Pade.Method 1: Talbot Im zDeform Bromwich line to: z() =  + µ  cot  +  i  , This converts Bromwich integral into: 1 f(t) = 2i -Re z-    ez()tF z() z () d.Discretize by trapezoidal/midpoint rule, on uniform grid of [-, ] h f(t)  2iNez(k)tF z(k) z (k).k=1Reason for success? Use partial fraction expansion 1 1 2  cot  = 1 + 2 + 2 + ... 2 - 2 2   - 4 to deduce that integrand decays rapidly on Talbot contour: 2µt2 exp z()t = O exp 2 , ||  -.  - 2Integrand of F(z) = 1/z on Talbot contourIm z0.5 0.4real imaginary0.30.2Re z0.10-0.1-0.2Note Wasteful Nodes-3 -2 -10123To eliminate wasteful nodes, we propose a Modified Talbot Method Trefethen &amp; JACW  z() =  + µ  cot  +  i  , with 0 &lt;  &lt; 1. Optimal parameters , µ, ,  for the two Talbot contours? Analyze with the help of model problem 1  f(t) = et, F(z) = z- (Motivation  A  IRn×n, F(z) = (zI - A)-1, -    &lt;0f(t) = exp(At) )By balancing various error terms, the following formulas for optimal contours have been derived JACW  Original Talbot method: N z= 0.3221  cot  - 0.2407 + 0.2827 i  t Modified Talbot method: N z= 0.5017  cot 0.6407  - 0.6122 + 0.2645 i  t For the model problem F(z) = (z - )-1, f(t) = et, these parameter choices achieve convergence rates Abs. Error. = O 2.6-N , Abs. Error. = O 3.9-N , respectively, for the original and modified Talbot contours.Two recently proposed alternatives to Talbot's contour: ParabolicGavrilyuk/Makarov  2Hyperbolic´ ´ Lopez-Fernandez/Palencia z = µ iw + 1z = µ 1 + sin iw -  - &lt; w &lt; 20- &lt; w &lt; 201515101055Im z0Im z-15 -10 -5 0 50-5-5-10-10-15-15-20 -20-20 -20-15-10-505Re zRe zWith optimal parameter choices, the convergence rates are Parabolic Abs. Error = O(2.8-N) Hyperbolic Abs. Error = O(3.2-N)Summary Contour Conv Rate Orig Talbot Parabola Hyperbola Mod Talbot O(2.6-N) O(2.8-N) O(3.2-N) O(3.9-N)(Applies to model problem 1 F(z) = z-f(t) = et,&lt;0)Estimation of Optimal Parameters? Consider simpler problem: integrals on I RI(f) =-f(x) dx.Approximate by trapezoidal sum, with spacing hIh(f) = hk=-f(kh).Discretization error, DEh(f) = I(f) - Ih(f), often unexpectedly small:Example:e-x dx = e(1 - erf 1) 2 - 1 + x exp(-x2) (1+x2)-1 dx1052-10010-5Discretization Error10-10exp(-2/h)10-1510-2010-2510-30Actual Error Theoretical Error Estimate-110100101hError Estimate Based on Contour Integrals [Martensen, 1968] 1 2i =+iaz h f(z) cot dz = h  NNf(kh)k=-NIm zDEh(f) = Re-+iaf(z) 1-i cot+iaz dz ha aRe z= |DEh(f)|  Often |DEh(f)| = O(e-2a/h) a coth -1 h |f(z)| dz-+iaA question-and-answer session: Q: What if f(z) is entire? A: Growth-rate of f(z) as z  ±i comes into play. Q: What if f(x) is not real-valued? A: Will have two error terms, one for upper half-plane, one for lower. Need to estimate separately. ( = Discretization Error, Two Parts) Q: How does one compute infinite trapezoidal sum? A: Rapidly decaying terms, truncate ( = Truncation Error) (Slowly decaying terms, apply series acceleration.)Apply the above ideas to the Bromwich integral: Match two parts of discretization error to truncation error. This gives two equations. If contour contains only two parameters, solve. If contour contains three parameters, solve for two of these. Thus obtain error estimate involving only one free parameter. Minimize error estimate with univariate routine. Summary (reprise) Contour Conv Rate Orig Talbot Parabola Hyperbola Mod Talbot O(2.6-N) O(2.8-N) O(3.2-N) O(3.9-N)Method 2: Rational Approximation to the ExponentialVlach , Luke Recall the Bromwich integral f(t) = 1 2i etzF(z) dz.Make the change of variables s = zt, i.e., f(t) = 1 2ti esG(s) ds,G(s) = F(s/t).Approximate es by a type (N - 1, N) rational functionNr(s) =k=1ck s - skand substitute into Bromwich integral. This yieldsNf(t) k=1wkG(sk),wk = ckesk t-1Note: This quadrature formula is closely related to Talbot quadrature h f(t)  2i Put s = zt, sk = z(k)t, ck = z (k)N-1; then the two formulas are seen to be identical. Conclusion: The Talbot method may be seen as a rational approximation method, with the nodes of the trapezoidal rule featuring as the poles in the rational approximation. Details inTrefethen, Weideman, Schmelzer, &quot;Talbot Quadratures and Rational Approximation&quot;, Tech. Rep. 05/20, Oxford University Computing Laboratory, 2005. Nez(k)tF z(k) z (k)k=1How to choose r(s)? ´ Pade approximation Vlach , Luke  · Highly accurate, but only in small regions · Coefficients ck grow rapidly as N   Alternative choice of r(s) = ill-conditioned(Trefethen, JACW, Schmelzer )Best approximation to es on IR-(Famous 1/9 problem)· Cody, Meinardus, Varga  Chebyshev rational approximations to e-z, application to parabolic PDE · Carpenter, Ruttan, Varga  Computation of (N, N) coefficients by Remes algorithm · Magnus , Aptekarev  Sup-norm error estimate on IR- es - r(s) = inf es - r(s)  2 9.289 . . .r -(N+1/2),NTechnicality: Literature considers only (N, N), we need (N - 1, N) Define r(s) = r(s) - r() (Not quite optimal, but close for N Compute r(s) by · Remes algorithm (expensive and cumbersome) ´ ´ · Caratheodory-Fejer method (only approximate, but practical) Will refer to this as the CMV-CF method´ ´ (Cody, Meinardus, Varga, Caratheodory, Fejer)1)Summary Contour Conv Rate Mod Talbot CMV-CF O(3.9-N) O(9.3-N)Numerical results were computed in MATLAB: To achieve machine precision 2 9.289 . . .-(N+1/2) 2-52=N  16PART 2. C OMPUTATION OF S PECIAL F UNCTIONSExponential function: ezModified Talbot, N = 1625 25 20 -2 20CMV-CF, N = 16-215 -4 10 -6 515 -4 10 -6 5Im z0-8Im z0-8-5 -10 -10 -12 -15 -14-5 -10 -10 -12 -15 -14-20-20-25 -30-25-20-15-10-50510-25 -30-25-20-15-10-50510Re zRe zApplication to Matrix Exponential: Recall scalar model problem et = 1 2i ezt F(z) dz,F(z) =1 , z-&lt;0Formulas also valid when  eAtA  IRn×n, A s.p.d. z I - A F(z) = v1 v= 2iezt F(z) dz,Note: Each function evaluation in quadrature rule = one linear system solve Linear systems can be solved efficiently: · A single Hessenberg or Schur decomposition of A is required · Can also be solved in parallelExample: Heat equation in 2D ut = c2u,(x, y)  [-1, 1]2Dirichlet BCs u = 0 on boundary, and initial condition u(x, y, 0) = ex(1 - x2)(1 - y2) Problem: To compute solution at t = 1, say. Numerical procedure: Approximate Laplacian by discrete operator (e.g., 5-point finite difference stencil). This gives semi-discrete system ut = D u, with solution u(t) = eDt u0. Approximate as above by inverting Laplace Transform 1 Dt ezt F(z) dz, zI - D F(z) = u0 e u0 = 2i  u(0) = u0.Errors at (x,y,t) = (0, 0, 1) (with c = 0.02 )1002D Heat equation, convergence curves10-2Modified Talbot Absolute Error10-410-610-8CMV-CF9.3-N3.9-N10-1010-12024681012141618NConclusion: To reach 10 digit accuracy elliptic problem (linear system) needs to be solved 5 times in case of CMV-CF method, and 8 times for Mod Talbot.Comparisons with expm (built-in MATLAB routine for matrix exponen´ tials, based on Pade approximation and scaling) Mesh size x = 2/M, y = 2/M, matrix is of order (M - 1)2 × (M - 1)2 Use N = 16 quadrature points:M CMV-CF expm 20 0.10 0.36 40 0.33 20 60 0.73 780CPU time (in s) computed in MATLAB 7 on Pentium 4 (3.4 GHz) Have also found that methods based on Talbot contours are numerically more stable than expmAn advantage of Talbot over CMV: Sols required at many values of t New value of t = new quadrature points = new system solves Can avoid additional system solves by fixing parameters at, say, t = t and solve linear systems once. Then use solution vectors with t dependent coefficients to compute quadrature sum at nearby values of t.N = 12100t =1*10-2Absolute Errors10-410-610-810-1010-12CMV-CF Mod Talbot0 0.5 1 1.5tThe Mittag-Leffler Functions: Recall scalar model problem: 1 exp(t) = ezt F(z) dz, 2i  Generalize to: 1 E(t ) = 2iF(z) =1 z-e F(z) dz,zt1 F(z) = z - z1-Series: E(z) = k=0zk  (k + 1)Special cases: E0(z) = 1 , 1-z E1/2(z) = ez erfc(-z),2E1(z) = ezApplication to (time)-fractional PDEs (sub-diffusion) D u = c t D is Caputo's fractional derivative t Df(t) t 1 =  (1 - )t 0 2uf (s) ds,  (t - s)(0 &lt;  &lt; 1).As   1, fractional derivative Semi-discretize c u(t) =2ordinary derivative.D, and take the Laplace Transform. Then ezt F(z) dz,1 2iz I - z1-D F(z) = u0Numerical experiment: Fractional 1D heat equation, with  = 1/2 Dt u = uxx, subject to u(x, 0) = sin x, Analytical solution u(0, t) = 0, u(, t) = 0.1/20  x  , u(x, t) = e erfc( t) sin x.tQualitative properties similar to u(x, t) = e-t sin x but steady state approached at slower rate.Solution of Fractional Heat Equation at t = 10.5 0.4 0.3 0.2 0.1 0 = 1/2 =100.511.522.53100x Pointwise errors using M = 30, N = 1610-510-10L -error = 1.2e-14 210-1510-2000.511.522.53xGamma Function (Schmelzer &amp; Trefethen, ) Hankel's contour integral for reciprocal of Gamma function Im z1 1 =  () 2ie zz -dzRe z(Actually, well-known formula from tables of Laplace transforms 1 t-1 = ezt z- dz, Re  &gt; 0  () 2i  Let t = 1. ) Approximate Hankel's formula with Talbot/CMV quadrature 1   ()Nwk z- kk=1Relative Error, CMV-CF Method, N = 168 -276-45-6Im 4-83-102-121-14005Re 1015Exponential Integral:E1() =e-t dt, t|arg | &lt; From tables of Laplace Transforms: 1 E1(t) = 2i log(1 + z/) e dz, z ztRe z &gt;0 -Re Put t = 1 and approximate by Talbot and/or CMV quadrature:NE1() k=1wklog(1 + zk/) zkRelative Error, CMV-CF Method, N = 168 -276-45-6Im 4-83-102-121-14005Re 1015Conclusions Two new methods for ILTs were introduced, both work well: · Method based on best approximation to ez on IR- is more accurate, but · Modified Talbot method more flexible and easier to implement As tools for the computation of special functions: · These methods seem to be competitive for functions of matrix argument (matrix exponential, Mittag-Leffler), but · For functions of scalar argument (gamma, exponential integral) further investigation and fine tuning are required`

35 pages

#### Report File (DMCA)

Our content is added by our users. We aim to remove reported files within 1 working day. Please use this link to notify us:

Report this file as copyright or inappropriate

548070