Read weidemann.pdf text version
Computing Special Functions via Inverse Laplace Transforms J.A.C. Weideman Department of Applied Mathematics University of Stellenbosch South Africa
http://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 MittagLeffler functions · The gamma function · The exponential integral · Application to PDEs
PART 1. I NVERSION OF THE L APLACE T RANSFORM
Laplace Transform and Inverse Formula (Bromwich) 1 +i tz F(z) = eztf(t) dt, f(t) = e F(z) dz, 2i i 0
Im z
> 0
0
Re z
Bromwich Integral: 1 f(t) = 2i
+i i
etzF(z) dz,
> 0 Will consider
Efficient 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 [1979]
Im z
Deform 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) 2i
N
ez(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 ,  .  2
Integrand of F(z) = 1/z on Talbot contour
Im z
0.5 0.4
real imaginary
0.3
0.2
Re z
0.1
0
0.1
0.2
Note Wasteful Nodes
3 2 1
0
1
2
3
To eliminate wasteful nodes, we propose a Modified Talbot Method Trefethen & JACW [2005] z() = + µ cot + i , with 0 < < 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, 
<0
f(t) = exp(At) )
By balancing various error terms, the following formulas for optimal contours have been derived JACW [2005] 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.6N , Abs. Error. = O 3.9N , respectively, for the original and modified Talbot contours.
Two recently proposed alternatives to Talbot's contour: Parabolic
Gavrilyuk/Makarov [2000] 2
Hyperbolic
´ ´ LopezFernandez/Palencia [2004]
z = µ iw + 1
z = µ 1 + sin iw   < w <
20
 < w <
20
15
15
10
10
5
5
Im z
0
Im z
15 10 5 0 5
0
5
5
10
10
15
15
20 20
20 20
15
10
5
0
5
Re z
Re z
With optimal parameter choices, the convergence rates are Parabolic Abs. Error = O(2.8N) Hyperbolic Abs. Error = O(3.2N)
Summary Contour Conv Rate Orig Talbot Parabola Hyperbola Mod Talbot O(2.6N) O(2.8N) O(3.2N) O(3.9N)
(Applies to model problem 1 F(z) = z
f(t) = et,
<0)
Estimation of Optimal Parameters? Consider simpler problem: integrals on I R
I(f) =

f(x) dx.
Approximate by trapezoidal sum, with spacing h
Ih(f) = h
k=
f(kh).
Discretization error, DEh(f) = I(f)  Ih(f), often unexpectedly small:
Example:
ex dx = e(1  erf 1) 2  1 + x
exp(x2) (1+x2)1 dx
10
5
2

10
0
10
5
Discretization Error
10
10
exp(2/h)
10
15
10
20
10
25
10
30
Actual Error Theoretical Error Estimate
1
10
10
0
10
1
h
Error Estimate Based on Contour Integrals [Martensen, 1968] 1 2i =
+ia
z h f(z) cot dz = h N
N
f(kh)
k=N
Im z
DEh(f) = Re
+ia
f(z) 1i cot
+ia
z dz h
a a
Re z
= DEh(f) Often DEh(f) = O(e2a/h) a coth 1 h f(z) dz
+ia
A questionandanswer session: Q: What if f(z) is entire? A: Growthrate of f(z) as z ±i comes into play. Q: What if f(x) is not realvalued? A: Will have two error terms, one for upper halfplane, 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.6N) O(2.8N) O(3.2N) O(3.9N)
Method 2: Rational Approximation to the Exponential
Vlach [1969], Luke [1972]
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 function
N
r(s) =
k=1
ck s  sk
and substitute into Bromwich integral. This yields
N
f(t)
k=1
wkG(sk),
wk = ckesk t1
Note: This quadrature formula is closely related to Talbot quadrature h f(t) 2i Put s = zt, sk = z(k)t, ck = z (k)N1; 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 in
Trefethen, Weideman, Schmelzer, "Talbot Quadratures and Rational Approximation", Tech. Rep. 05/20, Oxford University Computing Laboratory, 2005. N
ez(k)tF z(k) z (k)
k=1
How to choose r(s)? ´ Pade approximation Vlach [1969], Luke [1972] · Highly accurate, but only in small regions · Coefficients ck grow rapidly as N Alternative choice of r(s) = illconditioned
(Trefethen, JACW, Schmelzer [2005])
Best approximation to es on IR
(Famous 1/9 problem)
· Cody, Meinardus, Varga [1969] Chebyshev rational approximations to ez, application to parabolic PDE · Carpenter, Ruttan, Varga [1984] Computation of (N, N) coefficients by Remes algorithm · Magnus [1994], Aptekarev [2002] Supnorm 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) ´ ´ · CaratheodoryFejer method (only approximate, but practical) Will refer to this as the CMVCF method
´ ´ (Cody, Meinardus, Varga, Caratheodory, Fejer)
1)
Summary Contour Conv Rate Mod Talbot CMVCF O(3.9N) O(9.3N)
Numerical results were computed in MATLAB: To achieve machine precision 2 9.289 . . .
(N+1/2)
252
=
N 16
PART 2. C OMPUTATION OF S PECIAL F UNCTIONS
Exponential function: ez
Modified Talbot, N = 16
25 25 20 2 20
CMVCF, N = 16
2
15 4 10 6 5
15 4 10 6 5
Im z
0
8
Im z
0
8
5 10 10 12 15 14
5 10 10 12 15 14
20
20
25 30
25
20
15
10
5
0
5
10
25 30
25
20
15
10
5
0
5
10
Re z
Re z
Application to Matrix Exponential: Recall scalar model problem et = 1 2i ezt F(z) dz,
F(z) =
1 , z
<0
Formulas also valid when e
At
A IRn×n, A s.p.d. z I  A F(z) = v
1 v= 2i
ezt 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 = c
2
u,
(x, y) [1, 1]2
Dirichlet 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., 5point finite difference stencil). This gives semidiscrete 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 )
10
0
2D Heat equation, convergence curves
10
2
Modified Talbot Absolute Error
10
4
10
6
10
8
CMVCF
9.3
N
3.9
N
10
10
10
12
0
2
4
6
8
10
12
14
16
18
N
Conclusion: To reach 10 digit accuracy elliptic problem (linear system) needs to be solved 5 times in case of CMVCF method, and 8 times for Mod Talbot.
Comparisons with expm (builtin 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 CMVCF expm 20 0.10 0.36 40 0.33 20 60 0.73 780
CPU 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 = 12
10
0
t =1
*
10
2
Absolute Errors
10
4
10
6
10
8
10
10
10
12
CMVCF Mod Talbot
0 0.5 1 1.5
t
The MittagLeffler Functions: Recall scalar model problem: 1 exp(t) = ezt F(z) dz, 2i Generalize to: 1 E(t ) = 2i
F(z) =
1 z
e F(z) dz,
zt
1 F(z) = z  z1
Series: E(z) =
k=0
zk (k + 1)
Special cases: E0(z) = 1 , 1z E1/2(z) = ez erfc(z),
2
E1(z) = ez
Application to (time)fractional PDEs (subdiffusion) D u = c t D is Caputo's fractional derivative t Df(t) t 1 = (1  )
t 0 2
u
f (s) ds, (t  s)
(0 < < 1).
As 1, fractional derivative Semidiscretize c u(t) =
2
ordinary derivative.
D, and take the Laplace Transform. Then ezt F(z) dz,
1 2i
z I  z1D 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/2
0 x ,
u(x, t) = e erfc( t) sin x.
t
Qualitative properties similar to u(x, t) = et sin x but steady state approached at slower rate.
Solution of Fractional Heat Equation at t = 1
0.5 0.4 0.3 0.2 0.1 0
= 1/2 =1
0
0.5
1
1.5
2
2.5
3
10
0
x Pointwise errors using M = 30, N = 16
10
5
10
10
L error = 1.2e14 2
10
15
10
20
0
0.5
1
1.5
2
2.5
3
x
Gamma Function (Schmelzer & Trefethen, [2005]) Hankel's contour integral for reciprocal of Gamma function
Im z
1 1 = () 2i
e z
z 
dz
Re z
(Actually, wellknown formula from tables of Laplace transforms 1 t1 = ezt z dz, Re > 0 () 2i Let t = 1. ) Approximate Hankel's formula with Talbot/CMV quadrature 1 ()
N
wk z k
k=1
Relative Error, CMVCF Method, N = 16
8 2
7
6
4
5
6
Im
4
8
3
10
2
12
1
14
0
0
5
Re
10
15
Exponential Integral:
E1() =
et dt, t
arg  <
From tables of Laplace Transforms: 1 E1(t) = 2i log(1 + z/) e dz, z
zt
Re z >
0 Re
Put t = 1 and approximate by Talbot and/or CMV quadrature:
N
E1()
k=1
wk
log(1 + zk/) zk
Relative Error, CMVCF Method, N = 16
8 2
7
6
4
5
6
Im
4
8
3
10
2
12
1
14
0
0
5
Re
10
15
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, MittagLeffler), but · For functions of scalar argument (gamma, exponential integral) further investigation and fine tuning are required
Information
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