nach oben

BIT Numerical Mathematics

Erschienen in:

02.08.2018

Backward error analysis of polynomial approximations for computing the action of the matrix exponential

verfasst von: Marco Caliari, Peter Kandolf, Franco Zivcovich

Erschienen in: BIT Numerical Mathematics | Ausgabe 4/2018

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

We describe how to perform the backward error analysis for the approximation of \(\exp (A)v\) by \(p(s^{-1}A)^sv\), for any given polynomial p(x). The result of this analysis is an optimal choice of the scaling parameter s which assures a bound on the backward error, i.e. the equivalence of the approximation with the exponential of a slightly perturbed matrix. Thanks to the SageMath package expbea we have developed, one can optimize the performance of the given polynomial approximation. On the other hand, we employ the package for the analysis of polynomials interpolating the exponential function at so called Leja–Hermite points. The resulting method for the action of the matrix exponential can be considered an extension of both Taylor series approximation and Leja point interpolation. We illustrate the behavior of the new approximation with several numerical examples.

Vorheriger Artikel Weak convergence of Galerkin approximations for fractional elliptic stochastic PDEs with spatial white noise

Nächster Artikel Exact formulae and matrix-less eigensolvers for block banded symmetric Toeplitz matrices

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

The excerpts of code reported here do work in SageMath. Furthermore, we feel they are short, easy to understand, and can be regarded as pseudo-codes.

In [7], \(\theta _m\) was selected equal to \(\bar{c}_m\) and therefore the values reported in Table 3 are larger than those in [7, Table 1].

Al-Mohy, A.H., Higham, N.J.: A new scaling and squaring algorithm for the matrix exponential. SIAM J. Matrix Anal. Appl. 31(3), 970–989 (2009)MathSciNetCrossRef

Al-Mohy, A.H., Higham, N.J.: Computing the action of the matrix exponential with an application to exponential integrators. SIAM J. Sci. Comput. 33(2), 488–511 (2011)MathSciNetCrossRef

Bergamaschi, L., Caliari, M., Vianello, M.: Efficient approximation of the exponential operator for discrete 2D advection–diffusion problems. Numer. Linear Algebra Appl. 10(3), 271–289 (2003)MathSciNetCrossRef

Berrut, J.P., Trefethen, N.: Barycentric Lagrange Interpolation. SIAM Rev. 46(3), 501–517 (2004)MathSciNetCrossRef

Bos, L.P., Caliari, M.: Application of modified Leja sequences to polynomial interpolation. Dolomites Res. Notes Approx. 8, 66–74 (2015)MathSciNetCrossRef

Caliari, M.: Accurate evaluation of divided differences for polynomial interpolation of exponential propagators. Computing 80(2), 189–201 (2007)MathSciNetCrossRef

Caliari, M., Kandolf, P., Ostermann, A., Rainer, S.: The Leja method revisited: backward error analysis for the matrix exponential. SIAM J. Sci. Comput. 38(3), A1639–A1661 (2016)MathSciNetCrossRef

Caliari, M., Ostermann, A., Rainer, S.: Meshfree exponential integrators. SIAM J. Sci. Comput. 35(1), A431–A452 (2013)MathSciNetCrossRef

Caliari, M., Vianello, M., Bergamaschi, L.: Interpolating discrete advection–diffusion propagators at Leja sequences. J. Comput. Appl. Math. 172(1), 79–99 (2004)MathSciNetCrossRef

10.

Deadman, E.: Estimating the condition number of \(f(A)b\). Numer. Algorithms 70, 287–308 (2015)MathSciNetCrossRef

11.

Druskin, V.L., Knizhnerman, L.A.: Two polynomial methods of calculating functions of symmetric matrices. USSR Comput. Math. Math. Phys. 29(6), 112–121 (1989)MathSciNetCrossRef

12.

Fischer, T.M.: On the algorithm by Al-Mohy and Higham for computing the action of the matrix exponential: a posteriori roundoff error estimation. Linear Algebra Appl. 531, 141–168 (2017)MathSciNetCrossRef

13.

Higham, N.J.: Functions of Matrices. SIAM, Philadelphia (2008)CrossRef

14.

Higham, N.J., Relton, S.D.: Higher order Fréchet derivatives of matrix functions and the level-2 condition number SIAM. J. Matrix Anal. Appl. 35(3), 1019–1037 (2014)MathSciNetCrossRef

15.

Higham, N.J., Tisseur, F.: A block algorithm for matrix 1-norm estimation, with an application to 1-norm pseudospectra. SIAM J. Matrix Anal. Appl. 21(4), 1185–1201 (2000)MathSciNetCrossRef

16.

Hochbruck, M., Ostermann, A.: Exponential integrators. Acta Numer. 19, 209–286 (2010)MathSciNetCrossRef

17.

Kalantari, B.: Generalization of Taylor’s theorem and Newton’s method via a new family of determinantal interpolation formulas and its applications. J. Comput. Appl. Math. 126, 287–318 (2000)MathSciNetCrossRef

18.

Luan, V.T., Ostermann, A.: Parallel exponential Rosenbrock methods. Comput. Math. Appl. 71, 1137–1150 (2016)MathSciNetCrossRef

19.

Martínez, A., Bergamaschi, L., Caliari, M., Vianello, M.: A massively parallel exponential integrator for advection–diffusion models. J. Comput. Appl. Math. 231(1), 82–91 (2009)MathSciNetCrossRef

20.

McCurdy, A.: Accurate computation of divided differences. Technical report, University of California—ERL (1980)

21.

McCurdy, A., Ng, K.C., Parlett, B.N.: Accurate computation of divided differences of the exponential function. Math. Comput. 43(168), 501–528 (1984)MathSciNetCrossRef

22.

Moret, I., Novati, P.: An interpolatory approximation of the matrix exponential based on Faber polynomials. J. Comput. Appl. Math. 131, 361–380 (2001)MathSciNetCrossRef

23.

Novati, P.: A polynomial method based on Fejèr points for the computation of functions of unsymmetric matrices. Appl. Numer. Math. 44, 201–224 (2003)MathSciNetCrossRef

24.

Opitz, V.G.: Steigungsmatrizen. Z. Angew. Math. Mech. 44, T52–T54 (1964)MathSciNetMATH

25.

Reichel, L.: Newton interpolation at Leja points. BIT 30, 332–346 (1990)MathSciNetCrossRef

26.

Schaefer, M.J.: A polynomial based iterative method for linear parabolic equations. J. Comput. Appl. Math. 29, 35–50 (1990)MathSciNetCrossRef

27.

Stetekluh, J.: http://stetekluh.com/NewtonPoly.html. Accessed 4 Oct 2017

28.

Tal-Ezer, H.: High degree polynomial interpolation in Newton form. SIAM J. Sci. Stat. Comput. 12(3), 648–667 (1991)MathSciNetCrossRef

Titel: Backward error analysis of polynomial approximations for computing the action of the matrix exponential
verfasst von: Marco Caliari
Peter Kandolf
Franco Zivcovich
Publikationsdatum: 02.08.2018
Verlag: Springer Netherlands
Erschienen in: BIT Numerical Mathematics / Ausgabe 4/2018
Print ISSN: 0006-3835
Elektronische ISSN: 1572-9125
DOI: https://doi.org/10.1007/s10543-018-0718-9

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Springer Professional "Wirtschaft+Technik"

Weitere Artikel der Ausgabe 4/2018

Regular solutions of DAE hybrid systems and regularization techniques

On the zero-stability of multistep methods on smooth nonuniform grids

An accelerated Poisson solver based on multidomain spectral discretization

Multiple orthogonal polynomials applied to matrix function evaluation

Stochastic discrete Hamiltonian variational integrators

Weak convergence of Galerkin approximations for fractional elliptic stochastic PDEs with spatial white noise