Fast and stable contour integration for high order divided differences via elliptic functions

Lopez-Fernandez, M.; Sauter, S.

doi:10.1090/S0025-5718-2014-02890-1

Fast and stable contour integration for high order divided differences via elliptic functions
HTML articles powered by AMS MathViewer

by M. Lopez-Fernandez and S. Sauter PDF

Math. Comp. 84 (2015), 1291-1315 Request permission

Abstract:

In this paper, we will present a new method for evaluating high order divided differences for certain classes of analytic, possibly, operator-valued functions. This is a classical problem in numerical mathematics but also arises in new applications such as the use of generalized convolution quadrature to solve retarded potential integral equations. The functions which we will consider are allowed to grow exponentially to the left complex half-plane, polynomially to the right half-plane and have an oscillatory behaviour with increasing imaginary part. The interpolation points are scattered in a large real interval. Our approach is based on the representation of divided differences as contour integral and we will employ a subtle parameterization of the contour in combination with a quadrature approximation by the trapezoidal rule.

References

Milton Abramowitz and Irene A. Stegun, Handbook of Mathematical Functions, Applied Mathematics Series 55, National Bureau of Standards, U.S. Department of Commerce, 1972.
A. Bamberger and T. Ha Duong, Formulation variationnelle espace-temps pour le calcul par potentiel retardé de la diffraction d’une onde acoustique. I, Math. Methods Appl. Sci. 8 (1986), no. 3, 405–435 (French, with English summary). MR 859833
L. Banjai and S. Sauter, Rapid solution of the wave equation in unbounded domains, SIAM J. Numer. Anal. 47 (2008/09), no. 1, 227–249. MR 2452859, DOI 10.1137/070690754
L. Banjai and M. Schanz, Wave propagation problems treated with convolution quadrature and BEM, In Fast Boundary Element Methods in Engineering and Industrial Applications, Edited by U. Langer, M. Schanz, O. Steinbach, W.L. Wendland. Vol. 63, Lecture Notes in Applied and Computational Mechanics, Springer, Heidelberg, 2012, pp. 145–187, Chap. 5.
Folkmar Bornemann, Accuracy and stability of computing high-order derivatives of analytic functions by Cauchy integrals, Found. Comput. Math. 11 (2011), no. 1, 1–63. MR 2754188, DOI 10.1007/s10208-010-9075-z
M. Caliari, Accurate evaluation of divided differences for polynomial interpolation of exponential propagators, Computing 80 (2007), no. 2, 189–201. MR 2318505, DOI 10.1007/s00607-007-0227-1
Philip J. Davis, On the numerical integration of periodic analytic functions, On numerical approximation. Proceedings of a Symposium, Madison, April 21-23, 1958, Publication of the Mathematics Research Center, U.S. Army, the University of Wisconsin, no. 1, University of Wisconsin Press, Madison, Wis., 1959, pp. 45–59. Edited by R. E. Langer. MR 0100354
Carl de Boor, Divided differences, Surv. Approx. Theory 1 (2005), 46–69. MR 2221566
T. A. Driscoll, The Schwarz–Christoffel toolbox, available online at http://www.math. udel.edu/\symbol{126}driscoll/software/SC/.
Tobin A. Driscoll, Algorithm 843: improvements to the Schwarz-Christoffel toolbox for MATLAB, ACM Trans. Math. Software 31 (2005), no. 2, 239–251. MR 2266791, DOI 10.1145/1067967.1067971
Ömer Eğecioğlu, E. Gallopoulos, and Çetin K. Koç, Fast computation of divided differences and parallel Hermite interpolation, J. Complexity 5 (1989), no. 4, 417–437. MR 1028905, DOI 10.1016/0885-064X(89)90018-6
M. B. Friedman and R. Shaw, Diffraction of pulses by cylindrical obstacles of arbitrary cross section, Trans. ASME Ser. E. J. Appl. Mech. 29 (1962), 40–46. MR 136238
G. Frobenius, Über die Entwicklung analytischer Functionen in Reihen, die nach gegebenen Functionen fortschreiten, J. Reine Angew. Math. 73 (1871), 1–30.
I. S. Gradshteyn and I. M. Ryzhik, Table of integrals, series, and products, Academic Press, New York-London, 1965. Fourth edition prepared by Ju. V. Geronimus and M. Ju. Ceĭtlin; Translated from the Russian by Scripta Technica, Inc; Translation edited by Alan Jeffrey. MR 0197789
Wolfgang Hackbusch, Wendy Kress, and Stefan A. Sauter, Sparse convolution quadrature for time domain boundary integral formulations of the wave equation by cutoff and panel-clustering, Boundary element analysis, Lect. Notes Appl. Comput. Mech., vol. 29, Springer, Berlin, 2007, pp. 113–134. MR 2298801, DOI 10.1007/978-3-540-47533-0_{5}
Nicholas Hale, Nicholas J. Higham, and Lloyd N. Trefethen, Computing $\textbf {A}^\alpha ,\ \log (\textbf {A})$, and related matrix functions by contour integrals, SIAM J. Numer. Anal. 46 (2008), no. 5, 2505–2523. MR 2421045, DOI 10.1137/070700607
Ch. Hermite, Formule d’interpolation de Lagrange, J. Reine Angew. Math. 84 (1878), 70–79.
Nicholas J. Higham, Accuracy and stability of numerical algorithms, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1996. MR 1368629
Nicholas J. Higham, The numerical stability of barycentric Lagrange interpolation, IMA J. Numer. Anal. 24 (2004), no. 4, 547–556. MR 2094569, DOI 10.1093/imanum/24.4.547
Rainer Kreß, Zur numerischen Integration periodischer Funktionen nach der Rechteckregel, Numer. Math. 20 (1972/73), 87–92 (German, with English summary). MR 317524, DOI 10.1007/BF01436645
Maria Lopez-Fernandez and Stefan A. Sauter, Generalized convolution quadrature with variable time stepping. part II: algorithms and numerical results, Tech. Report 09-2012, Institut für Mathematik, Univ. Zürich, 2012.
—, Generalized convolution quadrature with variable time stepping, IMA J. Numer. Anal. (2013), DOI:10.1093/imanum/drs034.
C. Lubich, Convolution quadrature and discretized operational calculus. I, Numer. Math. 52 (1988), no. 2, 129–145. MR 923707, DOI 10.1007/BF01398686
C. Lubich, Convolution quadrature and discretized operational calculus. II, Numer. Math. 52 (1988), no. 4, 413–425. MR 932708, DOI 10.1007/BF01462237
A. McCurdy, K. C. Ng, and B. N. Parlett, Accurate computation of divided differences of the exponential function, Math. Comp. 43 (1984), no. 168, 501–528. MR 758198, DOI 10.1090/S0025-5718-1984-0758198-0
Lothar Reichel, Newton interpolation at Leja points, BIT 30 (1990), no. 2, 332–346. MR 1039671, DOI 10.1007/BF02017352
Klaus Schiefermayr, Inequalities for the Jacobian elliptic functions with complex modulus, J. Math. Inequal. 6 (2012), no. 1, 91–94. MR 2934569, DOI 10.7153/jmi-06-09
A. Smoktunowicz, I. Wróbel, and P. Kosowski, A new efficient algorithm for polynomial interpolation, Computing 79 (2007), no. 1, 33–52. MR 2282335, DOI 10.1007/s00607-006-0185-z
J. L. Walsh, Interpolation and approximation by rational functions in the complex domain, 4th ed., American Mathematical Society Colloquium Publications, Vol. XX, American Mathematical Society, Providence, R.I., 1965. MR 0218588