Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

   
 

 

Rigorous uniform approximation of D-finite functions using Chebyshev expansions


Authors: Alexandre Benoit, Mioara Joldeş and Marc Mezzarobba
Journal: Math. Comp. 86 (2017), 1303-1341
MSC (2010): Primary 68W30, 33C45, 65L05, 65G20
DOI: https://doi.org/10.1090/mcom/3135
Published electronically: October 20, 2016
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: A wide range of numerical methods exists for computing polynomial approximations of solutions of ordinary differential equations based on Chebyshev series expansions or Chebyshev interpolation polynomials. We consider the application of such methods in the context of rigorous computing (where we need guarantees on the accuracy of the result), and from the complexity point of view.

It is well known that the order-$ n$ truncation of the Chebyshev expansion of a function over a given interval is a near-best uniform polynomial approximation of the function on that interval. In the case of solutions of linear differential equations with polynomial coefficients, the coefficients of the expansions obey linear recurrence relations with polynomial coefficients. Unfortunately, these recurrences do not lend themselves to a direct recursive computation of the coefficients, owing among other things to a lack of initial conditions.

We show how they can nevertheless be used, as part of a validated process, to compute good uniform approximations of D-finite functions together with rigorous error bounds, and we study the complexity of the resulting algorithms. Our approach is based on a new view of a classical numerical method going back to Clenshaw, combined with a functional enclosure method.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 68W30, 33C45, 65L05, 65G20

Retrieve articles in all journals with MSC (2010): 68W30, 33C45, 65L05, 65G20


Additional Information

Alexandre Benoit
Affiliation: Éducation nationale, France
Email: alexandrebenoit@yahoo.fr

Mioara Joldeş
Affiliation: CNRS, LAAS, 7 Avenue du Colonel Roche, 31077 Toulouse, Cedex 4, France
Email: joldes@laas.fr

Marc Mezzarobba
Affiliation: CNRS, UMR 7606, LIP6, F-75005, Paris, France – and – Sorbonne Universités, UPMC Univ Paris 06, UMR 7606, LIP6, F-75005, Paris, France
Email: marc@mezzarobba.net

DOI: https://doi.org/10.1090/mcom/3135
Keywords: Rigorous computing, computer algebra, complexity, D-finite functions, recurrence relation, Chebyshev series, Clenshaw method, Miller algorithm, asymptotics, functional enclosure
Received by editor(s): July 10, 2014
Received by editor(s) in revised form: November 7, 2015, and November 22, 2015
Published electronically: October 20, 2016
Additional Notes: This research was partly supported by the Austria Science Fund (FWF) grants P22748-N18 and Y464-N18, and previously by the MSR-Inria joint research center
This work is in the public domain. As such, it is not subject to copyright. In jurisdictions where it is not possible to consider this work as released into the public domain, the authors grant any entity the right to use this work for any purpose, without any conditions, unless such conditions are required by law.
Article copyright: © Copyright 2016 by the authors