zbMATH — the first resource for mathematics

Rigorous uniform approximation of D-finite functions using Chebyshev expansions. (English) Zbl 1361.65045
Summary: 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.

65L05 Numerical methods for initial value problems
34A30 Linear ordinary differential equations and systems, general
65L70 Error bounds for numerical methods for ordinary differential equations
65G20 Algorithms with automatic result verification
chebop; MACSYMA; Maple; Sollya
Full Text: DOI
[1] Adams, C. Raymond, On the irregular cases of the linear ordinary difference equation, Trans. Amer. Math. Soc., 30, 3, 507-541, (1928) · JFM 54.0483.01
[2] Balser, Werner; Bothner, Thomas, Computation of formal solutions of systems of linear difference equations, Adv. Dyn. Syst. Appl., 5, 1, 29-47, (2010)
[3] Benoit2012 A. Benoit, \newblock \em Algorithmique semi-num\'erique rapide des s\'eries de Tchebychev, \newblock Th\`ese de doctorat, \'Ecole polytechnique, 2012.
[4] Benoit, Alexandre; Salvy, Bruno, Chebyshev expansions for solutions of linear differential equations. ISSAC 2009—Proceedings of the 2009 International Symposium on Symbolic and Algebraic Computation, 23-30, (2009), ACM, New York · Zbl 1237.68250
[5] Bickley, W. G.; Comrie, L. J.; Miller, J. C. P.; Sadler, D. H.; Thompson, A. J., Bessel Functions. Part II. Functions of Positive Integer Order, British Association for the Advancement of Science, Mathematical Tables, vol. X, xl+255 pp., (1952), University Press, Cambridge · Zbl 0049.09409
[6] Birkhoff, George D., Formal theory of irregular linear difference equations, Acta Math., 54, 1, 205-246, (1930) · JFM 56.0402.01
[7] Birkhoff, George D.; Trjitzinsky, W. J., Analytic theory of singular difference equations, Acta Math., 60, 1, 1-89, (1933) · Zbl 0006.16802
[8] Bostan, Alin; Salvy, Bruno; Schost, \'Eric, Power series composition and change of basis. ISSAC 2008, 269-276, (2008), ACM, New York
[9] Brent, Richard P.; Zimmermann, Paul, Modern Computer Arithmetic, Cambridge Monographs on Applied and Computational Mathematics 18, xvi+221 pp., (2011), Cambridge University Press, Cambridge · Zbl 1230.68014
[10] Brisebarre, Nicolas; Jolde\cs, Mioara, Chebyshev interpolation polynomial-based tools for rigorous computing. ISSAC 2010—Proceedings of the 2010 International Symposium on Symbolic and Algebraic Computation, 147-154, (2010), ACM, New York · Zbl 1321.65018
[11] BronsteinSalvy1993 M. Bronstein and B. Salvy, Full partial fraction decomposition of rational functions, \newblock In M. Bronstein, editor, \em ISSAC ’93, ACM, 1993, pp. 157–160. · Zbl 0920.12006
[12] Cheney, E. W., Introduction to Approximation Theory, xii+259 pp., (1998), AMS Chelsea Publishing, Providence, RI · Zbl 0912.41001
[13] Chevillard, S.; Harrison, J.; Jolde\cs, M.; Lauter, Ch., Efficient and accurate computation of upper bounds of approximation errors, Theoret. Comput. Sci., 412, 16, 1523-1543, (2011) · Zbl 1211.65025
[14] ChevillardJoldesLauter2010 S. Chevillard, M. Jolde\c s, and C. Lauter, Sollya: An environment for the development of numerical codes, \newblock In K. Fukuda, J. van der Hoeven, M. Joswig, and N. Takayama, editors, \em Mathematical Software - ICMS 2010, Lecture Notes in Computer Science, vol. 6327, Springer, Heidelberg, Germany, September 2010, pp. 28–31. · Zbl 1295.65143
[15] Clenshaw, C. W., A note on the summation of Chebyshev series, Math. Tables Aids Comput., 9, 118-120, (1955) · Zbl 0065.05403
[16] Clenshaw, C. W., The numerical solution of linear differential equations in Chebyshev series, Proc. Cambridge Philos. Soc., 53, 134-149, (1957) · Zbl 0077.32503
[17] Driscoll, Tobin A.; Bornemann, Folkmar; Trefethen, Lloyd N., The chebop system for automatic solution of differential equations, BIT, 48, 4, 701-723, (2008) · Zbl 1162.65370
[18] EinwohnerFateman1989 T. H. Einwohner and R. J. Fateman, A MACSYMA package for the generation and manipulation of Chebyshev series, \newblock In G. H. Gonnet, editor, \em ISSAC ’89, ACM, 1989, pp. 180–185.
[19] El-Daou, M. K.; Ortiz, E. L.; Samara, H., A unified approach to the tau method and Chebyshev series expansion techniques, Comput. Math. Appl., 25, 3, 73-82, (1993) · Zbl 0777.65051
[20] Epstein, C.; Miranker, W. L.; Rivlin, T. J., Ultra-arithmetic. I. Function data types, Math. Comput. Simulation, 24, 1, 1-18, (1982) · Zbl 0493.42005
[21] Epstein, C.; Miranker, W. L.; Rivlin, T. J., Ultra-arithmetic. II. Intervals of polynomials, Math. Comput. Simulation, 24, 1, 19-29, (1982) · Zbl 1402.65040
[22] Fox, L., Chebyshev methods for ordinary differential equations, Comput. J., 4, 318-331, (1961/1962) · Zbl 0103.34203
[23] Fox, L.; Parker, I. B., Chebyshev Polynomials in Numerical Analysis, ix+205 pp., (1968), Oxford University Press, London-New York-Toronto, Ont.
[24] Geddes1977a K. O. Geddes, Symbolic computation of recurrence equations for the Chebyshev series solution of linear ODE’s, \newblock In Proceedings of the 1977 MACSYMA User’s Conference, July 1977, pp. 405–423.
[25] Gourdon, Xavier; Salvy, Bruno, Effective asymptotics of linear recurrences with rational coefficients, Discrete Math.. Proceedings of the 5th Conference on Formal Power Series and Algebraic Combinatorics (Florence, 1993), 153, 1-3, 145-163, (1996) · Zbl 0852.68075
[26] Guelfond, A. O., Calcul des diff\'erences finies, Collection Universitaire de Math\'ematiques, XII. Traduit par G. Rideau, x+378 pp., (1963), Dunod, Paris · Zbl 0108.27503
[27] Immink, G. K., Reduction to canonical forms and the Stokes phenomenon in the theory of linear difference equations, SIAM J. Math. Anal., 22, 1, 238-259, (1991) · Zbl 0733.39004
[28] Immink, G. K., On the relation between global properties of linear difference and differential equations with polynomial coefficients. II, J. Differential Equations, 128, 1, 168-205, (1996) · Zbl 0856.34007
[29] Joldes2011 M. Jolde\c s, \newblock \em Rigorous polynomial approximations and applications, \newblock Th\`ese de doctorat, \'Ecole normale sup\'erieure de Lyon, 2011.
[30] Kaucher, Edgar W.; Miranker, Willard L., Self-validating Numerics for Function Space Problems, Notes and Reports in Computer Science and Applied Mathematics 9, xiii+255 pp., (1984), Academic Press, Inc., Orlando, FL · Zbl 0548.65028
[31] Kaucher, Edgar; Miranker, Willard L., Validating computation in a function space. Reliability in computing, Perspect. Comput. 19, 403-425, (1988), Academic Press, Boston, MA · Zbl 0659.65058
[32] Kauers2013 M. Kauers, The holonomic toolkit, \newblock \em Computer Algebra in Quantum Field Theory: Integration, Summation and Special Functions, Texts and Monographs in Symbolic Computation, 2013.
[33] Lanczos1938 C. Lanczos, Trigonometric interpolation of empirical and analytical functions, Journal of Mathematical Physics <span class=”textbf”>1</span>7 (1938), 123–199.
[34] Lanczos, Cornelius, Applied analysis, xx+539 pp., (1956), Prentice Hall, Inc., Englewood Cliffs, NJ
[35] Lewanowicz, S., Construction of a recurrence relation of the lowest order for coefficients of the Gegenbauer series, Zastos. Mat., 15, 3, 345-396, (1976) · Zbl 0357.33006
[36] Lewanowicz, S., A new approach to the problem of constructing recurrence relations for the Jacobi coefficients, Zastos. Mat., 21, 2, 303-326, (1991) · Zbl 0765.33005
[37] Makino, Kyoko; Berz, Martin, Taylor models and other validated functional inclusion methods, Int. J. Pure Appl. Math., 4, 4, 379-456, (2003) · Zbl 1022.65051
[38] Maple Maplesoft (Waterloo Maple, Inc.), \newblock Maple, 1980.
[39] \bibMasonHandscomb2003book author=Mason, J. C., author=Handscomb, D. C., title=Chebyshev Polynomials, pages=xiv+341, publisher=Chapman & Hall/CRC, Boca Raton, FL, date=2003, isbn=0-8493-0355-9, review=\MR 1937591 (2004h:33001),
[40] Mathar, Richard J., Chebyshev series expansion of inverse polynomials, J. Comput. Appl. Math., 196, 2, 596-607, (2006) · Zbl 1098.33006
[41] \bibMeschkowski1959book author=Meschkowski, Herbert, title=Differenzengleichungen, series=Studia Mathematica, Bd. XIV, pages=243, publisher=Vandenhoeck & Ruprecht, G\"ottingen, date=1959, language=German, review=\MR 0109264 (22 #151),
[42] Mezzarobba2011 M. Mezzarobba, \newblock \em Autour de l’\'evaluation num\'erique des fonctions D-finies, \newblock Th\`ese de doctorat, \'Ecole polytechnique, Nov. 2011.
[43] Milne-Thomson, L. M., The Calculus of Finite Differences, xxiii+558 pp., (1951), Macmillan and Co., Ltd., London
[44] Moore, Ramon E., Methods and Applications of Interval Analysis, SIAM Studies in Applied Mathematics 2, xi+190 pp., (1979), Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA
[45] Neumaier, Arnold, Taylor forms—use and limits, Reliab. Comput., 9, 1, 43-79, (2003) · Zbl 1071.65070
[46] Olver, Sheehan; Townsend, Alex, A fast and well-conditioned spectral method, SIAM Rev., 55, 3, 462-489, (2013) · Zbl 1273.65182
[47] Pan, V. Y., Optimal and nearly optimal algorithms for approximating polynomial zeros, Comput. Math. Appl., 31, 12, 97-138, (1996) · Zbl 0859.65045
[48] Pan, V. Y., New fast algorithms for polynomial interpolation and evaluation on the Chebyshev node set, Comput. Math. Appl., 35, 3, 125-129, (1998) · Zbl 0914.65002
[49] Paszkowski, Stefan, Zastosowania numeryczne wielomian\'ow i szereg\'ow Czebyszewa, 481 pp., (1975), Pa\'nstwowe Wydawnictwo Naukowe, Warsaw · Zbl 0423.65012
[50] Poincare, H., Sur les Equations Lineaires aux Differentielles Ordinaires et aux Differences Finies, Amer. J. Math., 7, 3, 203-258, (1885) · JFM 17.0290.01
[51] \bibRall1969book author=Rall, Louis B., title=Computational solution of nonlinear operator equations, series=With an appendix by Ramon E. Moore, pages=viii+225, publisher=John Wiley & Sons, Inc., New York-London-Sydney, date=1969, review=\MR 0240944 (39 #2289),
[52] Rebillard1998 L. Rebillard, \newblock \em Etude th\'eorique et algorithmique des s\'eries de Chebyshev solutions d’\'equations diff\'erentielles holonomes, \newblock Th\`ese de doctorat, Institut National Polytechnique de Grenoble, 1998.
[53] \bibRivlin1974book author=Rivlin, Theodore J., title=The Chebyshev polynomials, pages=vi+186, publisher=Wiley-Interscience [John Wiley & Sons], New York-London-Sydney, date=1974, note=Pure and Applied Mathematics, review=\MR 0450850 (56 #9142),
[54] Salvy2005 B. Salvy, D-finiteness: Algorithms and applications, \newblock In M. Kauers, editor, \em ISSAC ’05, ACM, 2005, pp. 2–3.
[55] Sch\`‘afke, F. W., L\'’osungstypen von Differenzengleichungen und Summengleichungen in normierten abelschen Gruppen, Math. Z., 88, 61-104, (1965) · Zbl 0134.06401
[56] Stanley, R. P., Differentiably finite power series, European J. Combin., 1, 2, 175-188, (1980) · Zbl 0445.05012
[57] Tournier1987 \'E. Tournier, \newblock \em Solutions formelles d’\'equations diff\'erentielles, \newblock Doctorat d’tat, Universit\'e scientifique, technologique et m\'edicale de Grenoble, 1987.
[58] Trefethen, Lloyd N., Computing numerically with functions instead of numbers, Math. Comput. Sci., 1, 1, 9-19, (2007) · Zbl 1145.41302
[59] Trefethen, Lloyd N., Approximation theory and approximation practice, viii+305 pp.+back matter pp., (2013), Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA · Zbl 1264.41001
[60] Tucker, Warwick, Validated Numerics, xii+138 pp., (2011), Princeton University Press, Princeton, NJ · Zbl 1231.65077
[61] Turrittin, H. L., The formal theory of systems of irregular homogeneous linear difference and differential equations, Bol. Soc. Mat. Mexicana (2), 5, 255-264, (1960) · Zbl 0100.08201
[62] van der Put, Marius; Singer, Michael F., Galois Theory of Difference Equations, Lecture Notes in Mathematics 1666, viii+180 pp., (1997), Springer-Verlag, Berlin · Zbl 0930.12006
[63] von zur Gathen, Joachim; Gerhard, J\"urgen, Modern Computer Algebra, xiv+785 pp., (2003), Cambridge University Press, Cambridge · Zbl 1055.68168
[64] Wimp1969 J. Wimp, On recursive computation, \newblock Technical Report ARL 69-0186, Aerospace Research Laboratories, 1969.
[65] Wimp, Jet, Computation with recurrence relations, Applicable Mathematics Series, xii+310 pp., (1984), Pitman (Advanced Publishing Program), Boston, MA · Zbl 0543.65084
[66] Zahar, R. V. M., A mathematical analysis of Miller’s algorithm, Numer. Math., 27, 4, 427-447, (1976/77) · Zbl 0336.65056
[67] Zeilberger, Doron, A holonomic systems approach to special functions identities, J. Comput. Appl. Math., 32, 3, 321-368, (1990) · Zbl 0738.33001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.