Swiss NSF, Scopes Project IB7320-111079: New Methods of Quadrature
 

Overview of Research Activities November 2005 through November 2007
J\"org Waldvogel, Seminar f\"ur Angewandte Mathematik, ETH Z\"urich

Computing Analytic Integrals to High Precision

The goal of this contribution is to develop universal tools for numerically
approximating integrals of analytic functions over finite, semi-infinite or
doubly infinite intervals (possibly with integrable boundary singularities).
Under quite general assumptions on the integrand exponential convergence may 
be achieved. This results in very fast algorithms for a fixed precision.
Alternatively, high-precision approximations (hundreds of digits) may
practically be obtained.

Previous presentations on earlier states of this contribution were given
on 12/10/2005 in Zurich, on 02/24/2006 in Nis, Serbia, and on 12/09/2006 
again in Zurich. The presentation "Towards a General Error Theory of the 
Trapezoidal Rule", given in Sozopol, Bulgaria on 09/15/2007 was mainly devoted 
to the discretization error as a function of the step size, a topic which is 
still under investigation. Currently, the theory of the discretization error 
is being generalized, and the computer programs are being refined.

Abstract of the paper in preparation:
We present a set of numerical quadrature algorithms which typically show exponential convergence for analytic integrands, even in the presence of integrable boundary singularities. The algorithms are based on mapping the integration interval onto the entire real axis, together with suitable transformations of the integrand, preferrably to a doubly-exponentially decaying function. The transformed integrals are approximated efficiently by the trapezoidal rule; the approximation error may be analyzed by means of Fourier theory.

This method results in a practicable algorithm for computing analytic integrals to a precision of hundreds - or thousands - of digits. Such high precision may prove meaningful for, e.g., identifying new numbers (defined by integrals) with combinations of known mathematical constants. An elegant, almost fully automated experimental implementation in the language PARI/GP is given.


More details on this contribution are available from the home page of 
J\"org Waldvogel,

	http://joerg.waldvogel.com   or
	http://www.sam.math.ethz.ch/~waldvoge/index.html
	Click	"Recent projects", then click the contact site
		"2006: Computing Analytic Integrals to High Precision"

Three items are given so far:

Preliminary version of a paper, in progress, 21 pp.,
   "Computing Analytic Integrals to High Precision": integrals.pdf

Presentation Nis, 18 frames: 
   "Computing Integrals of Analytic Functions: 
   A Universal Algorithm with Exponential Convergence"
   Third Scopes Meeting, ETH Zürich, December 7-10, 2006: nis.pdf

Presentation Sozopol, 33 frames:
   "Towards a General Error Theory of the Trapezoidal Rule"
   Fourth Scopes Meeting, Sozopol, Bulgaria, September 11-18, 2007: sozopol.pdf

Abstract.

The trapezoidal rule is the method of choice for numerical quadrature of
analytic functions to high precision. For an integrable integrand f(z)
analytic in an open strip |Imag(z)| < c (c>0) containing the real line R we
consider the trapezoidal sum  T(h) := sum f(k h)  with step size h>0 as an
approximation of the integral I of f over R. The discretization error
T(h)-I is found to be exponentially small in  omega:=2 pi/h . If f is
periodic this property holds for integrals over a full period.

The trapezoidal rule for integrals over R is particularly attractive for
quickly decaying integrands (at least exponential decay). Then the truncation
of the infinite trapezoidal sums can be handelled effectively. Generally,
transformations like  z=sinh(t)  are useful since they enhance the decay
of the integrand. However, such transformations may bear the danger of
generating new singularities in the complex plane which may slow down the
convergence with respect to  omega.

The discretization error of infinite trapezoidal sums may be expressed in
terms of the Fourier transform  f^hat(omega)  of the integrand by means of
the Poisson summation formula. Since small steps h<<1 correspond to large
values of omega it suffices to investigate the asymptotic behavior of
f^hat(omega). To this end, various techniques of complex analysis will be
discussed: calculus of residues, contour integrals, saddle point asymptotics,
etc. Several typical examples will be given. 


Remark. A second, unrelated, presentation was given in Sozopol on 09/14/2007:



\documentclass[12pt,A4]{article}
\usepackage{amsmath,amssymb,amscd,latexsym}
\usepackage[dvips]{graphicx}
\pagestyle{empty}

\title{Gaussian Quadratures over\\ the Surface of the Sphere}
\author{J\"org Waldvogel, Seminar for Applied Mathematics,\\
Swiss Federal Institute of Technology ETH, CH-8092 Zurich}

\begin{document}
\maketitle

\begin{abstract}
The computation of Integrals $I := \int_{S^2} f(x) \, d\omega$ over the surface
$S^2$ of the unit sphere in ${\bf R^3}$ is an important practical task
(needed for, e.g., accumulating the radiation influx from all directions of
space). However, such integrations often suffer from the nonexistence of
regular parametrizations of $S^2$. Therefore, numerical approximations based on
$$
   I = \sum_{k=1}^n w_k f(x_k) + R_n
$$
with $n$ points
$$
   x_k = (x_k^1,x_k^2,x_k^3) \in S^2, \quad \sum_{j=1}^3 (x_k^j)^2 = 1 \,,
$$
weights $w_k > 0, ~k=1,\dots,n$ and a remainder $R_n$ are of
interest. As in one-dimensional Gaussian quadrature, $x_k, ~w_k$ are chosen
such that $R_n = 0$ for all polynomials $f$ in $x_1, x_2, x_3$ of total degree
$\le D$, where $D$ is as large as possible.

The icosahedral symmetry of the set of points is of particular interest; many
formulas of high precision are expected to exist. We use the monomials in two
invariant polynomials (of degrees 6 and 10) in order to generate the space of
all relevant polynomials on the sphere. The resulting systems of nonlinear
equations are solved numerically. The classical formulas of degree of exactness
$D \le 15$ with $n \le 120$ points are easily recovered. A larger formula
found achieves $D = 47$ with $n = 860$ points, and many more examples were
constructed.
\end{abstract}
\end{document}




\documentstyle[24pt,german,A4]{article}
\begin{document}
%\pagestyle{empty}
%\vspace*{1cm}
{\huge \bf
\begin{verbatim}
            R E F E R E N C E S

1. H.S.M. Coxeter: Regular Complex Polytopes.
   Cambridge University Press 1974, 185 pp.

2. Felix Klein: Vorlesungen ueber das
   Ikosaeder. Teubner, Leipzig 1884.
   Reprint: Birkhaeuser 1993, 343 pp.

3. V.I. Lebedev and A.L. Skorokhodov:
   Quadrature formulas of orders 41, 47,
   and 53 for the sphere.
   Dokl. Math. 45(3), 1992, 587-592.

4. V.I. Lebedev: A quadrature formula for
   the sphere of 59th algebraic order
   of accuracy.
   Dokl. Math. 50(2), 1995, 283-286.

5. A.S. Popov: Cubature formulae for a sphere
   invariant under cyclic rotation groups.
   Russ. J. Numer. Anal. Math. Modelling
   9(6), 1994, 535-546.

6. A.H. Stroud: Approximate Calculation
   of Multiple Integrals.
   Prentice Hall 1971, 431 pp.
\end{verbatim}}
\end{document}