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.<\/p>\n
\n It is well known that the order-\n 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.<\/p>","DOI":"10.1090\/mcom\/3135","type":"journal-article","created":{"date-parts":[[2016,10,20]],"date-time":"2016-10-20T15:12:14Z","timestamp":1476976334000},"page":"1303-1341","source":"Crossref","is-referenced-by-count":10,"title":["Rigorous uniform approximation of D-finite functions using Chebyshev expansions"],"prefix":"10.1090","volume":"86","author":[{"given":"Alexandre","family":"Benoit","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mioara","family":"Jolde\u015f","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Marc","family":"Mezzarobba","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"14","published-online":{"date-parts":[[2016,10,20]]},"reference":[{"issue":"3","key":"1","doi-asserted-by":"publisher","first-page":"507","DOI":"10.2307\/1989081","article-title":"On the irregular cases of the linear ordinary difference equation","volume":"30","author":"Adams, C. Raymond","year":"1928","journal-title":"Trans. Amer. Math. Soc.","ISSN":"https:\/\/id.crossref.org\/issn\/0002-9947","issn-type":"print"},{"issue":"1","key":"2","first-page":"29","article-title":"Computation of formal solutions of systems of linear difference equations","volume":"5","author":"Balser, Werner","year":"2010","journal-title":"Adv. Dyn. Syst. Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/0973-5321","issn-type":"print"},{"key":"3","unstructured":"A. Benoit, Algorithmique semi-num\u00e9rique rapide des s\u00e9ries de Tchebychev, Th\u00e8se de doctorat, \u00c9cole polytechnique, 2012."},{"key":"4","isbn-type":"print","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1145\/1576702.1576709","article-title":"Chebyshev expansions for solutions of linear differential equations","author":"Benoit, Alexandre","year":"2009","ISBN":"https:\/\/id.crossref.org\/isbn\/9781605586090"},{"key":"5","series-title":"British Association for the Advancement of Science, Mathematical Tables, vol. 10","volume-title":"Bessel functions. Part II. Functions of positive integer order","author":"Bickley, W. G.","year":"1952"},{"issue":"1","key":"6","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1007\/BF02547522","article-title":"Formal theory of irregular linear difference equations","volume":"54","author":"Birkhoff, George D.","year":"1930","journal-title":"Acta Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0001-5962","issn-type":"print"},{"issue":"1","key":"7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF02398269","article-title":"Analytic theory of singular difference equations","volume":"60","author":"Birkhoff, George D.","year":"1933","journal-title":"Acta Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0001-5962","issn-type":"print"},{"key":"8","isbn-type":"print","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1145\/1390768.1390806","article-title":"Power series composition and change of basis","author":"Bostan, Alin","year":"2008","ISBN":"https:\/\/id.crossref.org\/isbn\/9781595939043"},{"key":"9","series-title":"Cambridge Monographs on Applied and Computational Mathematics","isbn-type":"print","volume-title":"Modern computer arithmetic","volume":"18","author":"Brent, Richard P.","year":"2011","ISBN":"https:\/\/id.crossref.org\/isbn\/9780521194693"},{"key":"10","isbn-type":"print","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1145\/1837934.1837966","article-title":"Chebyshev interpolation polynomial-based tools for rigorous computing","author":"Brisebarre, Nicolas","year":"2010","ISBN":"https:\/\/id.crossref.org\/isbn\/9781450301503"},{"key":"11","doi-asserted-by":"crossref","unstructured":"M. Bronstein and B. Salvy, Full partial fraction decomposition of rational functions, In M. Bronstein, editor, ISSAC \u201993, ACM, 1993, pp. 157\u2013160.","DOI":"10.1145\/164081.164114"},{"key":"12","isbn-type":"print","volume-title":"Introduction to approximation theory","author":"Cheney, E. W.","year":"1998","ISBN":"https:\/\/id.crossref.org\/isbn\/0821813749"},{"issue":"16","key":"13","doi-asserted-by":"publisher","first-page":"1523","DOI":"10.1016\/j.tcs.2010.11.052","article-title":"Efficient and accurate computation of upper bounds of approximation errors","volume":"412","author":"Chevillard, S.","year":"2011","journal-title":"Theoret. Comput. Sci.","ISSN":"https:\/\/id.crossref.org\/issn\/0304-3975","issn-type":"print"},{"key":"14","doi-asserted-by":"crossref","unstructured":"S. Chevillard, M. Jolde\u015f, and C. Lauter, Sollya: An environment for the development of numerical codes, In K. Fukuda, J. van der Hoeven, M. Joswig, and N. Takayama, editors, Mathematical Software - ICMS 2010, Lecture Notes in Computer Science, vol. 6327, Springer, Heidelberg, Germany, September 2010, pp. 28\u201331.","DOI":"10.1007\/978-3-642-15582-6_5"},{"key":"15","doi-asserted-by":"crossref","first-page":"118","DOI":"10.1090\/S0025-5718-1955-0071856-0","article-title":"A note on the summation of Chebyshev series","volume":"9","author":"Clenshaw, C. W.","year":"1955","journal-title":"Math. Tables Aids Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0891-6837","issn-type":"print"},{"key":"16","doi-asserted-by":"publisher","first-page":"134","DOI":"10.1017\/s0305004100032072","article-title":"The numerical solution of linear differential equations in Chebyshev series","volume":"53","author":"Clenshaw, C. W.","year":"1957","journal-title":"Proc. Cambridge Philos. Soc.","ISSN":"https:\/\/id.crossref.org\/issn\/0008-1981","issn-type":"print"},{"issue":"4","key":"17","doi-asserted-by":"publisher","first-page":"701","DOI":"10.1007\/s10543-008-0198-4","article-title":"The chebop system for automatic solution of differential equations","volume":"48","author":"Driscoll, Tobin A.","year":"2008","journal-title":"BIT","ISSN":"https:\/\/id.crossref.org\/issn\/0006-3835","issn-type":"print"},{"key":"18","doi-asserted-by":"crossref","unstructured":"T. H. Einwohner and R. J. Fateman, A MACSYMA package for the generation and manipulation of Chebyshev series, In G. H. Gonnet, editor, ISSAC \u201989, ACM, 1989, pp. 180\u2013185.","DOI":"10.1145\/74540.74562"},{"issue":"3","key":"19","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1016\/0898-1221(93)90145-L","article-title":"A unified approach to the tau method and Chebyshev series expansion techniques","volume":"25","author":"El-Daou, M. K.","year":"1993","journal-title":"Comput. Math. Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/0898-1221","issn-type":"print"},{"issue":"1","key":"20","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0378-4754(82)90045-3","article-title":"Ultra-arithmetic. I. Function data types","volume":"24","author":"Epstein, C.","year":"1982","journal-title":"Math. Comput. Simulation","ISSN":"https:\/\/id.crossref.org\/issn\/0378-4754","issn-type":"print"},{"issue":"1","key":"21","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/0378-4754(82)90046-5","article-title":"Ultra-arithmetic. II. Intervals of polynomials","volume":"24","author":"Epstein, C.","year":"1982","journal-title":"Math. Comput. Simulation","ISSN":"https:\/\/id.crossref.org\/issn\/0378-4754","issn-type":"print"},{"key":"22","doi-asserted-by":"publisher","first-page":"318","DOI":"10.1093\/comjnl\/4.4.318","article-title":"Chebyshev methods for ordinary differential equations","volume":"4","author":"Fox, L.","year":"1961","journal-title":"Comput. J.","ISSN":"https:\/\/id.crossref.org\/issn\/0010-4620","issn-type":"print"},{"key":"23","volume-title":"Chebyshev polynomials in numerical analysis","author":"Fox, L.","year":"1968"},{"key":"24","unstructured":"K. O. Geddes, Symbolic computation of recurrence equations for the Chebyshev series solution of linear ODE\u2019s, In Proceedings of the 1977 MACSYMA User\u2019s Conference, July 1977, pp. 405\u2013423."},{"issue":"1-3","key":"25","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1016\/0012-365X(95)00133-H","article-title":"Effective asymptotics of linear recurrences with rational coefficients","volume":"153","author":"Gourdon, Xavier","year":"1996","journal-title":"Discrete Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0012-365X","issn-type":"print"},{"key":"26","series-title":"Collection Universitaire de Math\\'{e}matiques, XII","volume-title":"Calcul des diff\\'{e}rences finies","author":"Guelfond, A. O.","year":"1963"},{"issue":"1","key":"27","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1137\/0522014","article-title":"Reduction to canonical forms and the Stokes phenomenon in the theory of linear difference equations","volume":"22","author":"Immink, G. K.","year":"1991","journal-title":"SIAM J. Math. Anal.","ISSN":"https:\/\/id.crossref.org\/issn\/0036-1410","issn-type":"print"},{"issue":"1","key":"28","doi-asserted-by":"publisher","first-page":"168","DOI":"10.1006\/jdeq.1996.0093","article-title":"On the relation between global properties of linear difference and differential equations with polynomial coefficients. II","volume":"128","author":"Immink, G. K.","year":"1996","journal-title":"J. Differential Equations","ISSN":"https:\/\/id.crossref.org\/issn\/0022-0396","issn-type":"print"},{"key":"29","unstructured":"M. Jolde\u015f, Rigorous polynomial approximations and applications, Th\u00e8se de doctorat, \u00c9cole normale sup\u00e9rieure de Lyon, 2011."},{"key":"30","series-title":"Notes and Reports in Computer Science and Applied Mathematics","isbn-type":"print","volume-title":"Self-validating numerics for function space problems","volume":"9","author":"Kaucher, Edgar W.","year":"1984","ISBN":"https:\/\/id.crossref.org\/isbn\/0124020208"},{"key":"31","isbn-type":"print","first-page":"403","article-title":"Validating computation in a function space","author":"Kaucher, Edgar","year":"1988","ISBN":"https:\/\/id.crossref.org\/isbn\/0125056303"},{"key":"32","doi-asserted-by":"crossref","unstructured":"M. Kauers, The holonomic toolkit, Computer Algebra in Quantum Field Theory: Integration, Summation and Special Functions, Texts and Monographs in Symbolic Computation, 2013.","DOI":"10.1007\/978-3-7091-1616-6_5"},{"key":"33","doi-asserted-by":"crossref","unstructured":"C. Lanczos, Trigonometric interpolation of empirical and analytical functions, Journal of Mathematical Physics 17 (1938), 123\u2013199.","DOI":"10.1002\/sapm1938171123"},{"key":"34","volume-title":"Applied analysis","author":"Lanczos, Cornelius","year":"1956"},{"issue":"3","key":"35","first-page":"345","article-title":"Construction of a recurrence relation of the lowest order for coefficients of the Gegenbauer series","volume":"15","author":"Lewanowicz, S.","year":"1976","journal-title":"Zastos. Mat.","ISSN":"https:\/\/id.crossref.org\/issn\/0044-1899","issn-type":"print"},{"issue":"2","key":"36","first-page":"303","article-title":"A new approach to the problem of constructing recurrence relations for the Jacobi coefficients","volume":"21","author":"Lewanowicz, S.","year":"1991","journal-title":"Zastos. Mat.","ISSN":"https:\/\/id.crossref.org\/issn\/0044-1899","issn-type":"print"},{"issue":"4","key":"37","first-page":"379","article-title":"Taylor models and other validated functional inclusion methods","volume":"4","author":"Makino, Kyoko","year":"2003","journal-title":"Int. J. Pure Appl. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/1311-8080","issn-type":"print"},{"key":"38","unstructured":"Maplesoft (Waterloo Maple, Inc.), Maple, 1980."},{"key":"39","isbn-type":"print","volume-title":"Chebyshev polynomials","author":"Mason, J. C.","year":"2003","ISBN":"https:\/\/id.crossref.org\/isbn\/0849303559"},{"issue":"2","key":"40","doi-asserted-by":"publisher","first-page":"596","DOI":"10.1016\/j.cam.2005.10.013","article-title":"Chebyshev series expansion of inverse polynomials","volume":"196","author":"Mathar, Richard J.","year":"2006","journal-title":"J. Comput. Appl. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0377-0427","issn-type":"print"},{"key":"41","series-title":"Studia Mathematica, Bd. XIV","volume-title":"Differenzengleichungen","author":"Meschkowski, Herbert","year":"1959"},{"key":"42","unstructured":"M. Mezzarobba, Autour de l\u2019\u00e9valuation num\u00e9rique des fonctions D-finies, Th\u00e8se de doctorat, \u00c9cole polytechnique, Nov. 2011."},{"key":"43","volume-title":"The Calculus of Finite Differences","author":"Milne-Thomson, L. M.","year":"1951"},{"key":"44","series-title":"SIAM Studies in Applied Mathematics","isbn-type":"print","doi-asserted-by":"crossref","DOI":"10.1137\/1.9781611970906","volume-title":"Methods and applications of interval analysis","volume":"2","author":"Moore, Ramon E.","year":"1979","ISBN":"https:\/\/id.crossref.org\/isbn\/0898711614"},{"issue":"1","key":"45","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1023\/A:1023061927787","article-title":"Taylor forms\u2014use and limits","volume":"9","author":"Neumaier, Arnold","year":"2003","journal-title":"Reliab. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/1385-3139","issn-type":"print"},{"issue":"3","key":"46","doi-asserted-by":"publisher","first-page":"462","DOI":"10.1137\/120865458","article-title":"A fast and well-conditioned spectral method","volume":"55","author":"Olver, Sheehan","year":"2013","journal-title":"SIAM Rev.","ISSN":"https:\/\/id.crossref.org\/issn\/1095-7200","issn-type":"print"},{"issue":"12","key":"47","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/0898-1221(96)00080-6","article-title":"Optimal and nearly optimal algorithms for approximating polynomial zeros","volume":"31","author":"Pan, V. Y.","year":"1996","journal-title":"Comput. Math. Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/0898-1221","issn-type":"print"},{"issue":"3","key":"48","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1016\/S0898-1221(97)00283-6","article-title":"New fast algorithms for polynomial interpolation and evaluation on the Chebyshev node set","volume":"35","author":"Pan, V. Y.","year":"1998","journal-title":"Comput. Math. Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/0898-1221","issn-type":"print"},{"key":"49","series-title":"Podstawowe Algorytmy Numeryczne. [Fundamental Numerical Algorithms]","volume-title":"Zastosowania numeryczne wielomian\\'{o}w i szereg\\'{o}w Czebyszewa","author":"Paszkowski, Stefan","year":"1975"},{"issue":"3","key":"50","doi-asserted-by":"publisher","first-page":"203","DOI":"10.2307\/2369270","article-title":"Sur les Equations Lineaires aux Differentielles Ordinaires et aux Differences Finies","volume":"7","author":"Poincare, H.","year":"1885","journal-title":"Amer. J. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0002-9327","issn-type":"print"},{"key":"51","volume-title":"Computational solution of nonlinear operator equations","author":"Rall, Louis B.","year":"1969"},{"key":"52","unstructured":"L. Rebillard, Etude th\u00e9orique et algorithmique des s\u00e9ries de Chebyshev solutions d\u2019\u00e9quations diff\u00e9rentielles holonomes, Th\u00e8se de doctorat, Institut National Polytechnique de Grenoble, 1998."},{"key":"53","series-title":"Pure and Applied Mathematics","volume-title":"The Chebyshev polynomials","author":"Rivlin, Theodore J.","year":"1974"},{"key":"54","doi-asserted-by":"crossref","unstructured":"B. Salvy, D-finiteness: Algorithms and applications, In M. Kauers, editor, ISSAC \u201905, ACM, 2005, pp. 2\u20133.","DOI":"10.1145\/1073884.1073886"},{"key":"55","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1007\/BF01112693","article-title":"L\u00f6sungstypen von Differenzengleichungen und Summengleichungen in normierten abelschen Gruppen","volume":"88","author":"Sch\u00e4fke, F. W.","year":"1965","journal-title":"Math. Z.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5874","issn-type":"print"},{"issue":"2","key":"56","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1016\/S0195-6698(80)80051-5","article-title":"Differentiably finite power series","volume":"1","author":"Stanley, R. P.","year":"1980","journal-title":"European J. Combin.","ISSN":"https:\/\/id.crossref.org\/issn\/0195-6698","issn-type":"print"},{"key":"57","unstructured":"\u00c9. Tournier, Solutions formelles d\u2019\u00e9quations diff\u00e9rentielles, Doctorat d\u2019tat, Universit\u00e9 scientifique, technologique et m\u00e9dicale de Grenoble, 1987."},{"issue":"1","key":"58","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1007\/s11786-007-0001-y","article-title":"Computing numerically with functions instead of numbers","volume":"1","author":"Trefethen, Lloyd N.","year":"2007","journal-title":"Math. Comput. Sci.","ISSN":"https:\/\/id.crossref.org\/issn\/1661-8270","issn-type":"print"},{"key":"59","isbn-type":"print","volume-title":"Approximation theory and approximation practice","author":"Trefethen, Lloyd N.","year":"2013","ISBN":"https:\/\/id.crossref.org\/isbn\/9781611972399"},{"key":"60","isbn-type":"print","volume-title":"Validated numerics","author":"Tucker, Warwick","year":"2011","ISBN":"https:\/\/id.crossref.org\/isbn\/9780691147819"},{"key":"61","first-page":"255","article-title":"The formal theory of systems of irregular homogeneous linear difference and differential equations","volume":"5","author":"Turrittin, H. L.","year":"1960","journal-title":"Bol. Soc. Mat. Mexicana (2)"},{"key":"62","series-title":"Lecture Notes in Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0096118","volume-title":"Galois theory of difference equations","volume":"1666","author":"van der Put, Marius","year":"1997","ISBN":"https:\/\/id.crossref.org\/isbn\/3540632433"},{"key":"63","isbn-type":"print","volume-title":"Modern computer algebra","author":"von zur Gathen, Joachim","year":"2003","ISBN":"https:\/\/id.crossref.org\/isbn\/0521826462","edition":"2"},{"key":"64","doi-asserted-by":"crossref","unstructured":"J. Wimp, On recursive computation, Technical Report ARL 69-0186, Aerospace Research Laboratories, 1969.","DOI":"10.21236\/AD0700326"},{"key":"65","series-title":"Applicable Mathematics Series","isbn-type":"print","volume-title":"Computation with recurrence relations","author":"Wimp, Jet","year":"1984","ISBN":"https:\/\/id.crossref.org\/isbn\/0273085085"},{"issue":"4","key":"66","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1007\/BF01399606","article-title":"A mathematical analysis of Miller\u2019s algorithm","volume":"27","author":"Zahar, R. V. M.","year":"1976","journal-title":"Numer. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0029-599X","issn-type":"print"},{"issue":"3","key":"67","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1016\/0377-0427(90)90042-X","article-title":"A holonomic systems approach to special functions identities","volume":"32","author":"Zeilberger, Doron","year":"1990","journal-title":"J. Comput. Appl. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0377-0427","issn-type":"print"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/2017-86-305\/S0025-5718-2016-03135-X\/S0025-5718-2016-03135-X.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2017-86-305\/S0025-5718-2016-03135-X\/S0025-5718-2016-03135-X.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T19:08:49Z","timestamp":1776798529000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2017-86-305\/S0025-5718-2016-03135-X\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,10,20]]},"references-count":67,"journal-issue":{"issue":"305","published-print":{"date-parts":[[2017,5]]}},"alternative-id":["S0025-5718-2016-03135-X"],"URL":"https:\/\/doi.org\/10.1090\/mcom\/3135","archive":["CLOCKSS","Portico"],"relation":{},"ISSN":["1088-6842","0025-5718"],"issn-type":[{"value":"1088-6842","type":"electronic"},{"value":"0025-5718","type":"print"}],"subject":[],"published":{"date-parts":[[2016,10,20]]}}}