research-article

Validated and Numerically Efficient Chebyshev Spectral Methods for Linear Ordinary Differential Equations

Authors:

Florent Bréhard,

Nicolas Brisebarre,

Mioara JoldeşAuthors Info & Claims

ACM Transactions on Mathematical Software (TOMS), Volume 44, Issue 4

Article No.: 44, Pages 1 - 42

https://doi.org/10.1145/3208103

Published: 31 July 2018 Publication History

Abstract

In this work, we develop a validated numeric method for the solution of linear ordinary differential equations (LODEs). A wide range of algorithms (i.e., Runge-Kutta, collocation, spectral methods) exist for numerically computing approximations of the solutions. Most of these come with proofs of asymptotic convergence, but usually, provided error bounds are nonconstructive. However, in some domains like critical systems and computer-aided mathematical proofs, one needs validated effective error bounds. We focus on both the theoretical and practical complexity analysis of a so-called a posteriori quasi-Newton validation method, which mainly relies on a fixed-point argument of a contracting map. Specifically, given a polynomial approximation, obtained by some numerical algorithm and expressed on a Chebyshev basis, our algorithm efficiently computes an accurate and rigorous error bound. For this, we study theoretical properties like compactness, convergence, and invertibility of associated linear integral operators and their truncations in a suitable coefficient space of Chebyshev series. Then, we analyze the almost-banded matrix structure of these operators, which allows for very efficient numerical algorithms for both numerical solutions of LODEs and rigorous computation of the approximation error. Finally, several representative examples show the advantages of our algorithms as well as their theoretical and practical limits.

References

[1]

M. Abramowitz and I. A. Stegun. 1964. Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables. National Bureau of Standards Applied Mathematics Series, Vol. 55. Courier Corporation. xiv+1046 pages.

[2]

P. R. Arantes Gilz, F. Bréhard, and G. Clément. 2017. Validated semi-analytical transition matrices for linearized spacecraft dynamics via Chebyshev series approximations. Retrieved from https://hal.laas.fr/hal-01540170. Preprint.

[3]

G. Baszenski and M. Tasche. 1997. Fast polynomial multiplication and convolutions related to the discrete cosine transform. Linear Algebra Appl. 252 (1997), 1--25. Retrieved from

[4]

A. Benoit, M. Joldeş, and M. Mezzarobba. 2017. Rigorous uniform approximation of D-finite functions using Chebyshev expansions. Math. Comp. 86, 305 (2017), 1303--1341. Retrieved from

[5]

V. Berinde. 2007. Iterative Approximation of Fixed Points. Lecture Notes in Mathematics, Vol. 1912. Springer, Berlin.

Digital Library

[6]

M. Berz and K. Makino. 2005. Suppression of the wrapping effect by Taylor model-based verified integrators: Long-term stabilization by shrink wrapping. Int. J. Diff. Eq. Appl. 10 (2005), 385--403.

[7]

J. P. Boyd. 2001. Chebyshev and Fourier Spectral Methods. Dover Publications.

[8]

H. Brezis. 2010. Functional Analysis, Sobolev Spaces and Partial Differential Equations. Springer Science 8 Business Media.

[9]

N. Brisebarre and M. Joldeş. 2010. Chebyshev interpolation polynomial-based tools for rigorous computing. In Proceedings of the 2010 International Symposium on Symbolic and Algebraic Computation. ACM, 147--154.

Digital Library

[10]

E. W. Cheney. 1998. Introduction to Approximation Theory. AMS Chelsea Publishing, Providence, RI. xii+259 pages. Reprint of the second (1982) edition.

[11]

S. Chevillard, J. Harrison, M. Joldeş, and C. Lauter. 2011. Efficient and accurate computation of upper bounds of approximation errors. Theor. Comput. Scie. 412, 16 (2011), 1523--1543.

Digital Library

[12]

C. W. Clenshaw. 1957. The numerical solution of linear differential equations in Chebyshev series. In Mathematical Proceedings of the Cambridge Philosophical Society, Vol. 53. Cambridge University Press, 134--149.

[13]

P. Di Lizia. 2008. Robust Space Trajectory and Space System Design using Differential Algebra. Ph.D. thesis. Politecnico di Milano, Milano, Italy.

[14]

T. A. Driscoll, F. Bornemann, and L. N. Trefethen. 2008. The Chebop system for automatic solution of differential equations. BIT Numer. Math. 48, 4 (2008), 701--723.

[15]

K. Du. 2016. On well-conditioned spectral collocation and spectral methods by the integral reformulation. SIAM J. Sci. Comput. 38, 5 (2016), A3247--A3263. Retrieved from

[16]

T. Dzetkulič. 2015. Rigorous integration of non-linear ordinary differential equations in Chebyshev basis. Numer. Algorithms 69 (2015), 183--205.

Digital Library

[17]

C. Epstein, W. Miranker, and T. Rivlin. 1982a. Ultra-arithmetic I: Function data types. Math. Comput. Simulation 24, 1 (1982), 1--18.

[18]

C. Epstein, W. Miranker, and T. Rivlin. 1982b. Ultra-arithmetic II: intervals of polynomials. Math. Comput. Simulation 24, 1 (1982), 19--29.

[19]

L. Fousse, G. Hanrot, V. Lefèvre, P. Pélissier, and P. Zimmermann. 2007. MPFR: A multiple-precision binary floating-point library with correct rounding. ACM Trans. Math. Software 33, 2 (June 2007), Article 13.

Digital Library

[20]

L. Fox and I. B. Parker. 1968. Chebyshev Polynomials in Numerical Analysis. Oxford University Press, London-New York-Toronto, Ontario, ix+205 pages.

[21]

P. Giorgi. 2012. On polynomial multiplication in Chebyshev basis. IEEE Trans. Comput. 61, 6 (2012), 780--789. Retrieved from

Digital Library

[22]

I. Gohberg, S. Goldberg, and M. A. Kaashoek. 2003. Basic Classes of Linear Operators. Birkhäuser Verlag, Basel. xviii+423 pages. Retrieved from

[23]

D. Gottlieb and S. A. Orszag. 1977. Numerical Analysis of Spectral Methods: Theory and Applications. Vol. 26. Siam.

[24]

L. Greengard. 1991. Spectral integration and two-point boundary value problems. SIAM J. Numer. Anal. 28, 4 (1991), 1071--1080.

Digital Library

[25]

A. Hungria, J.-P. Lessard, and J. D. Mireles James. 2016. Rigorous numerics for analytic solutions of differential equations: The radii polynomial approach. Math. Comp. 85, 299 (2016), 1427--1459.

[26]

A. Iserles. 2009. A First Course in the Numerical Analysis of Differential Equations (2nd ed.). Cambridge University Press, Cambridge. xx+459 pages.

Digital Library

[27]

M. Joldeş. 2011. Rigorous Polynomial Approximations and Applications. Ph.D. Dissertation. École normale supérieure de Lyon -- Université de Lyon, Lyon, France. Retrieved from https://tel.archives-ouvertes.fr/tel-00657843.

[28]

Y. Katznelson. 2004. An Introduction to Harmonic Analysis. Cambridge University Press.

[29]

E. W. Kaucher and W. L. Miranker. 1984. Self-Validating Numerics for Function Space Problems: Computation with Guarantees for Differential and Integral Equations. Vol. 9. Elsevier.

[30]

T. Lalescu. 1911. Introduction à la théorie des équations intégrales (Introduction to the Theory of Integral Equations). Librairie Scientifique A. Hermann.

[31]

J.-P. Lessard and C. Reinhardt. 2014. Rigorous numerics for nonlinear differential equations using Chebyshev series. SIAM J. Numer. Anal. 52, 1 (2014), 1--22.

[32]

K. Makino and M. Berz. 2003. Taylor models and other validated functional inclusion methods. Int. J. Pure Appl. Math. 4, 4 (2003), 379--456. Retrieved from http://bt.pa.msu.edu/pub/papers/TMIJPAM03/TMIJPAM03.pdf.

[33]

K. Makino and M. Berz. 2005. Suppression of the wrapping effect by Taylor model-based verified integrators: Long-term stabilization by preconditioning. Int. J. Diff. Eq. Appl. 10 (2005), 353--384.

[34]

K. Makino and M. Berz. 2006. Suppression of the wrapping effect by Taylor model-based verified integrators: The single step. Int. J. Pure Appl. Math. 36 (2006), 175--197.

[35]

J. C. Mason and D. C. Handscomb. 2002. Chebyshev Polynomials. CRC Press.

[36]

R. E. Moore. 1966. Interval Analysis. Prentice-Hall.

[37]

R. E. Moore and F. Bierbaum. 1979. Methods and Applications of Interval Analysis. Vol. 2. SIAM.

Digital Library

[38]

J.-M. Muller. 2016. Elementary Functions, Algorithms and Implementation (3rd ed.). Birkhäuser, Boston.

Digital Library

[39]

M. Neher, K. R. Jackson, and N. S. Nedialkov. 2007. On Taylor model based integration of ODEs. SIAM J. Numer. Anal. 45, 1 (2007), 236--262. Retrieved from

Digital Library

[40]

A. Neumaier. 1990. Interval Methods for Systems of Equations. Cambridge University Press, Cambridge.

[41]

A. Neumaier. 2003. Taylor forms -- Use and limits. Reliable Computing 9, 1 (2003), 43--79.

[42]

S. Olver and A. Townsend. 2013. A fast and well-conditioned spectral method. SIAM Rev. 55, 3 (2013), 462--489.

Digital Library

[43]

M. J. D. Powell. 1981. Approximation Theory and Methods. Cambridge University Press.

[44]

L. B. Rall. 1969. Computational Solution of Nonlinear Operator Equations. Wiley New York.

[45]

N. Revol and F. Rouillier. 2005. Motivations for an arbitrary precision interval arithmetic and the MPFI library. Reliable Comput. 11 (2005), 1--16. Retrieved from http://mpfi.gforge.inria.fr/.

[46]

T. J. Rivlin. 1974. The Chebyshev Polynomials. Wiley.

[47]

S. M. Rump. 2010. Verification methods: Rigorous results using floating-point arithmetic. Acta Numer. 19 (2010), 287--449. Retrieved from

[48]

B. Salvy. 2005. D-Finiteness: Algorithms and applications. In Proceedings of the 18th International Symposium on Symbolic and Algebraic Computation (ISSAC’05), Manuel Kauers (Ed.). ACM Press, 2--3. Abstract for an invited talk.

Digital Library

[49]

R. P. Stanley. 1980. Differentiably finite power series. Eur. J. Combin. 1, 2 (1980), 175--188.

[50]

L. N. Trefethen. 2007. Computing numerically with functions instead of numbers. Math. Comput. Sci. 1, 1 (2007), 9--19. Retrieved from

[51]

L. N. Trefethen. 2013. Approximation Theory and Approximation Practice. SIAM. Retrieved from http://www.chebfun.org/ATAP/. See http://www.chebfun.org/ATAP/.

Digital Library

[52]

J. Tschauner and P. Hempel. 1964. Optimale Beschleunigungsprogramme fur das Rendezvous-Manover. Acta Astron. 10, 5--6 (1964), 296--307.

[53]

W. Tucker. 2011. Validated Numerics: A Short Introduction to Rigorous Computations. Princeton University Press.

Digital Library

[54]

J. B. van den Berg and J.-P. Lessard. 2015. Rigorous numerics in dynamics. Notices of the AMS 62, 9 (2015), 1057--1061.

[55]

A.-M. Wazwaz. 2011. Linear and Nonlinear Integral Equations: Methods and Applications. Springer Science 8 Business Media.

Digital Library

[56]

N. Yamamoto. 1998. A numerical verification method for solutions of boundary value problems with local uniqueness by Banach’s fixed-point theorem. SIAM J. Numer. Anal. 35, 5 (1998), 2004--2013.

Digital Library

[57]

D. Zeilberger. 1990. A holonomic systems approach to special functions identities. J. Comput. Appl. Math. 32, 3 (1990), 321--368.

Digital Library

[58]

A. Zygmund. 2002. Trigonometric Series Vol. I, II (3rd ed.). Cambridge University Press, Cambridge. xii; Vol. I: xiv+383 pp.; Vol. II: viii+364 pages.

Cited By

Joldes MMaza MZhi L(2022)Validated NumericsProceedings of the 2022 International Symposium on Symbolic and Algebraic Computation10.1145/3476446.3535505(1-2)Online publication date: 4-Jul-2022
https://dl.acm.org/doi/10.1145/3476446.3535505
Colbrook M(2022)Computing Semigroups with Error ControlSIAM Journal on Numerical Analysis10.1137/21M139861660:1(396-422)Online publication date: 14-Feb-2022
https://doi.org/10.1137/21M1398616
Colbrook MAyton L(2022)A contour method for time-fractional PDEs and an application to fractional viscoelastic beam equationsJournal of Computational Physics10.1016/j.jcp.2022.110995454(110995)Online publication date: Apr-2022
https://doi.org/10.1016/j.jcp.2022.110995
Show More Cited By

Index Terms

Validated and Numerically Efficient Chebyshev Spectral Methods for Linear Ordinary Differential Equations
1. Mathematics of computing
  1. Mathematical analysis

Recommendations

On shifted Jacobi spectral approximations for solving fractional differential equations

In this paper, a new formula of Caputo fractional-order derivatives of shifted Jacobi polynomials of any degree in terms of shifted Jacobi polynomials themselves is proved. We discuss a direct solution technique for linear multi-order fractional ...
Solving linear ordinary differential equations using singly diagonally implicit Runge-Kutta fifth order five-stage method

We constructed a new fifth order five-stage singly diagonally implicit Runge-Kutta (DIRK) method which is specially designed for the integrations of linear ordinary differential equations (LODEs). The restriction to linear ordinary differential ...
A Newton-like Validation Method for Chebyshev Approximate Solutions of Linear Ordinary Differential Systems
ISSAC '18: Proceedings of the 2018 ACM International Symposium on Symbolic and Algebraic Computation

We provide a new framework for a posteriori validation of vector-valued problems with componentwise tight error enclosures, and use it to design a symbolic-numeric Newton-like validation algorithm for Chebyshev approximate solutions of coupled systems ...

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Mathematical Software

ACM Transactions on Mathematical Software Volume 44, Issue 4

December 2018

305 pages

ISSN:0098-3500

EISSN:1557-7295

DOI:10.1145/3233179

Editors:
Zhaojun Bai
University of California at Davis, USA
,
Wolfgang Bangerth
Colorado State University, USA

Issue’s Table of Contents

Copyright © 2018 ACM.

Publication rights licensed to ACM. ACM acknowledges that this contribution was authored or co-authored by an employee, contractor or affiliate of a national government. As such, the Government retains a nonexclusive, royalty-free right to publish or reproduce this article, or to allow others to do so, for Government purposes only.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 31 July 2018

Accepted: 01 April 2018

Revised: 01 March 2018

Received: 01 July 2017

Published in TOMS Volume 44, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

ANR

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
234
Total Downloads

Downloads (Last 12 months)20
Downloads (Last 6 weeks)0

Reflects downloads up to 15 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Joldes MMaza MZhi L(2022)Validated NumericsProceedings of the 2022 International Symposium on Symbolic and Algebraic Computation10.1145/3476446.3535505(1-2)Online publication date: 4-Jul-2022
https://dl.acm.org/doi/10.1145/3476446.3535505
Colbrook M(2022)Computing Semigroups with Error ControlSIAM Journal on Numerical Analysis10.1137/21M139861660:1(396-422)Online publication date: 14-Feb-2022
https://doi.org/10.1137/21M1398616
Colbrook MAyton L(2022)A contour method for time-fractional PDEs and an application to fractional viscoelastic beam equationsJournal of Computational Physics10.1016/j.jcp.2022.110995454(110995)Online publication date: Apr-2022
https://doi.org/10.1016/j.jcp.2022.110995
Bréhard F(2021)A Symbolic-Numeric Validation Algorithm for Linear ODEs with Newton–Picard MethodMathematics in Computer Science10.1007/s11786-021-00510-7Online publication date: 15-May-2021
https://doi.org/10.1007/s11786-021-00510-7
Lessard JJames J(2020)A Rigorous Implicit $$C^1$$ Chebyshev Integrator for Delay EquationsJournal of Dynamics and Differential Equations10.1007/s10884-020-09880-1Online publication date: 19-Aug-2020
https://doi.org/10.1007/s10884-020-09880-1
Hashemi B(2019)Enclosing Chebyshev Expansions in Linear TimeACM Transactions on Mathematical Software10.1145/331939545:3(1-33)Online publication date: 30-Jul-2019
https://dl.acm.org/doi/10.1145/3319395

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

HTML Format

View this article in HTML Format.

Media

Figures

Other

Tables

View Issue’s Table of Contents