{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T15:20:38Z","timestamp":1753888838314,"version":"3.41.0"},"reference-count":56,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2018,7,31]],"date-time":"2018-07-31T00:00:00Z","timestamp":1532995200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"ANR","award":["FastRelax project ANR-14-CE25-0018-01"],"award-info":[{"award-number":["FastRelax project ANR-14-CE25-0018-01"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Math. Softw."],"published-print":{"date-parts":[[2018,12,31]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1145\/3208103","type":"journal-article","created":{"date-parts":[[2018,7,31]],"date-time":"2018-07-31T15:56:23Z","timestamp":1533052583000},"page":"1-42","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Validated and Numerically Efficient Chebyshev Spectral Methods for Linear Ordinary Differential Equations"],"prefix":"10.1145","volume":"44","author":[{"given":"Florent","family":"Br\u00e9hard","sequence":"first","affiliation":[{"name":"LIP, ENS Lyon and LAAS-CNRS, Toulouse, France"}]},{"given":"Nicolas","family":"Brisebarre","sequence":"additional","affiliation":[{"name":"CNRS, LIP, ENS Lyon, Lyon Cedex, France"}]},{"given":"Mioara","family":"Jolde\u015f","sequence":"additional","affiliation":[{"name":"CNRS, LAAS, Toulouse, France"}]}],"member":"320","published-online":{"date-parts":[[2018,7,31]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"National Bureau of Standards Applied Mathematics Series","volume":"55","author":"Abramowitz M.","unstructured":"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. 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."},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","unstructured":"P. R. Arantes Gilz F. Br\u00e9hard and G. Cl\u00e9ment. 2017. Validated semi-analytical transition matrices for linearized spacecraft dynamics via Chebyshev series approximations. Retrieved from https:\/\/hal.laas.fr\/hal-01540170. Preprint.  P. R. Arantes Gilz F. Br\u00e9hard and G. Cl\u00e9ment. 2017. Validated semi-analytical transition matrices for linearized spacecraft dynamics via Chebyshev series approximations. Retrieved from https:\/\/hal.laas.fr\/hal-01540170. Preprint.","DOI":"10.2514\/6.2018-1960"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(95)00696-6"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1090\/mcom\/3135"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/SYNASC.2007.49"},{"key":"e_1_2_1_6_1","first-page":"385","article-title":"Suppression of the wrapping effect by Taylor model-based verified integrators: Long-term stabilization by shrink wrapping","volume":"10","author":"Berz M.","year":"2005","unstructured":"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 . 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.","journal-title":"Int. J. Diff. Eq. Appl."},{"volume-title":"Chebyshev and Fourier Spectral Methods","author":"Boyd J. P.","key":"e_1_2_1_7_1","unstructured":"J. P. Boyd . 2001. Chebyshev and Fourier Spectral Methods . Dover Publications . J. P. Boyd. 2001. Chebyshev and Fourier Spectral Methods. Dover Publications."},{"volume-title":"Functional Analysis, Sobolev Spaces and Partial Differential Equations","author":"Brezis H.","key":"e_1_2_1_8_1","unstructured":"H. Brezis . 2010. Functional Analysis, Sobolev Spaces and Partial Differential Equations . Springer Science 8 Business Media. H. Brezis. 2010. Functional Analysis, Sobolev Spaces and Partial Differential Equations. Springer Science 8 Business Media."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1837934.1837966"},{"key":"e_1_2_1_10_1","volume-title":"Introduction to Approximation Theory","author":"Cheney E. W.","year":"1982","unstructured":"E. W. Cheney . 1998. Introduction to Approximation Theory . AMS Chelsea Publishing , Providence, RI . xii+259 pages. Reprint of the second ( 1982 ) edition. E. W. Cheney. 1998. Introduction to Approximation Theory. AMS Chelsea Publishing, Providence, RI. xii+259 pages. Reprint of the second (1982) edition."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.11.052"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100032072"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10543-008-0198-4"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1046629"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11075-014-9889-x"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/0378-4754(82)90045-3"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/0378-4754(82)90046-5"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1236463.1236468"},{"key":"e_1_2_1_20_1","unstructured":"L. Fox and I. B. Parker. 1968. Chebyshev Polynomials in Numerical Analysis. Oxford University Press London-New York-Toronto Ontario ix+205 pages.  L. Fox and I. B. Parker. 1968. Chebyshev Polynomials in Numerical Analysis. Oxford University Press London-New York-Toronto Ontario ix+205 pages."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2011.110"},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","unstructured":"I. Gohberg S. Goldberg and M. A. Kaashoek. 2003. Basic Classes of Linear Operators. Birkh\u00e4user Verlag Basel. xviii+423 pages. Retrieved from  I. Gohberg S. Goldberg and M. A. Kaashoek. 2003. Basic Classes of Linear Operators. Birkh\u00e4user Verlag Basel. xviii+423 pages. Retrieved from","DOI":"10.1007\/978-3-0348-7980-4"},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","unstructured":"D. Gottlieb and S. A. Orszag. 1977. Numerical Analysis of Spectral Methods: Theory and Applications. Vol. 26. Siam.  D. Gottlieb and S. A. Orszag. 1977. Numerical Analysis of Spectral Methods: Theory and Applications. Vol. 26. Siam.","DOI":"10.1137\/1.9781611970425"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/0728057"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1090\/mcom\/3046"},{"key":"e_1_2_1_26_1","volume-title":"A First Course in the Numerical Analysis of Differential Equations","author":"Iserles A.","unstructured":"A. Iserles . 2009. A First Course in the Numerical Analysis of Differential Equations ( 2 nd ed.). Cambridge University Press , Cambridge . xx+459 pages. A. Iserles. 2009. A First Course in the Numerical Analysis of Differential Equations (2nd ed.). Cambridge University Press, Cambridge. xx+459 pages.","edition":"2"},{"volume-title":"An Introduction to Harmonic Analysis","author":"Katznelson Y.","key":"e_1_2_1_28_1","unstructured":"Y. Katznelson . 2004. An Introduction to Harmonic Analysis . Cambridge University Press . Y. Katznelson. 2004. An Introduction to Harmonic Analysis. Cambridge University Press."},{"key":"e_1_2_1_29_1","doi-asserted-by":"crossref","unstructured":"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.  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.","DOI":"10.1016\/B978-0-12-402020-7.50008-6"},{"key":"e_1_2_1_30_1","unstructured":"T. Lalescu. 1911. Introduction \u00e0 la th\u00e9orie des \u00e9quations int\u00e9grales (Introduction to the Theory of Integral Equations). Librairie Scientifique A. Hermann.  T. Lalescu. 1911. Introduction \u00e0 la th\u00e9orie des \u00e9quations int\u00e9grales (Introduction to the Theory of Integral Equations). Librairie Scientifique A. Hermann."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/13090883X"},{"key":"e_1_2_1_32_1","first-page":"379","article-title":"Taylor models and other validated functional inclusion methods","volume":"4","author":"Makino K.","year":"2003","unstructured":"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. 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.","journal-title":"Int. J. Pure Appl. Math."},{"key":"e_1_2_1_33_1","first-page":"353","article-title":"Suppression of the wrapping effect by Taylor model-based verified integrators: Long-term stabilization by preconditioning","volume":"10","author":"Makino K.","year":"2005","unstructured":"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 . 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.","journal-title":"Int. J. Diff. Eq. Appl."},{"key":"e_1_2_1_34_1","first-page":"175","article-title":"Suppression of the wrapping effect by Taylor model-based verified integrators: The single step","volume":"36","author":"Makino K.","year":"2006","unstructured":"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 . 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.","journal-title":"Int. J. Pure Appl. Math."},{"key":"e_1_2_1_35_1","doi-asserted-by":"crossref","unstructured":"J. C. Mason and D. C. Handscomb. 2002. Chebyshev Polynomials. CRC Press.  J. C. Mason and D. C. Handscomb. 2002. Chebyshev Polynomials. CRC Press.","DOI":"10.1201\/9781420036114"},{"volume-title":"Interval Analysis","author":"Moore R. E.","key":"e_1_2_1_36_1","unstructured":"R. E. Moore . 1966. Interval Analysis . Prentice-Hall . R. E. Moore. 1966. Interval Analysis. Prentice-Hall."},{"key":"e_1_2_1_37_1","doi-asserted-by":"crossref","unstructured":"R. E. Moore and F. Bierbaum. 1979. Methods and Applications of Interval Analysis. Vol. 2. SIAM.   R. E. Moore and F. Bierbaum. 1979. Methods and Applications of Interval Analysis. Vol. 2. SIAM.","DOI":"10.1137\/1.9781611970906"},{"key":"e_1_2_1_38_1","volume-title":"Elementary Functions, Algorithms and Implementation","author":"Muller J.-M.","unstructured":"J.-M. Muller . 2016. Elementary Functions, Algorithms and Implementation ( 3 rd ed.). Birkh\u00e4user , Boston . J.-M. Muller. 2016. Elementary Functions, Algorithms and Implementation (3rd ed.). Birkh\u00e4user, Boston.","edition":"3"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1137\/050638448"},{"volume-title":"Interval Methods for Systems of Equations","author":"Neumaier A.","key":"e_1_2_1_40_1","unstructured":"A. Neumaier . 1990. Interval Methods for Systems of Equations . Cambridge University Press , Cambridge . A. Neumaier. 1990. Interval Methods for Systems of Equations. Cambridge University Press, Cambridge."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1023061927787"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1137\/120865458"},{"volume-title":"Approximation Theory and Methods","author":"Powell M. J. D.","key":"e_1_2_1_43_1","unstructured":"M. J. D. Powell . 1981. Approximation Theory and Methods . Cambridge University Press . M. J. D. Powell. 1981. Approximation Theory and Methods. Cambridge University Press."},{"volume-title":"Computational Solution of Nonlinear Operator Equations","author":"Rall L. B.","key":"e_1_2_1_44_1","unstructured":"L. B. Rall . 1969. Computational Solution of Nonlinear Operator Equations . Wiley New York . L. B. Rall. 1969. Computational Solution of Nonlinear Operator Equations. Wiley New York."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11155-005-6891-y"},{"volume-title":"The Chebyshev Polynomials","author":"Rivlin T. J.","key":"e_1_2_1_46_1","unstructured":"T. J. Rivlin . 1974. The Chebyshev Polynomials . Wiley . T. J. Rivlin. 1974. The Chebyshev Polynomials. Wiley."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1017\/S096249291000005X"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/1073884.1073886"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0195-6698(80)80051-5"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11786-007-0001-y"},{"key":"e_1_2_1_51_1","unstructured":"L. N. Trefethen. 2013. Approximation Theory and Approximation Practice. SIAM. Retrieved from http:\/\/www.chebfun.org\/ATAP\/. See http:\/\/www.chebfun.org\/ATAP\/.   L. N. Trefethen. 2013. Approximation Theory and Approximation Practice. SIAM. Retrieved from http:\/\/www.chebfun.org\/ATAP\/. See http:\/\/www.chebfun.org\/ATAP\/."},{"key":"e_1_2_1_52_1","first-page":"5","article-title":"Optimale Beschleunigungsprogramme fur das Rendezvous-Manover","volume":"10","author":"Tschauner J.","year":"1964","unstructured":"J. Tschauner and P. Hempel . 1964 . Optimale Beschleunigungsprogramme fur das Rendezvous-Manover . Acta Astron. 10 , 5 -- 6 (1964), 296--307. J. Tschauner and P. Hempel. 1964. Optimale Beschleunigungsprogramme fur das Rendezvous-Manover. Acta Astron. 10, 5--6 (1964), 296--307.","journal-title":"Acta Astron."},{"volume-title":"Validated Numerics: A Short Introduction to Rigorous Computations","author":"Tucker W.","key":"e_1_2_1_53_1","unstructured":"W. Tucker . 2011. Validated Numerics: A Short Introduction to Rigorous Computations . Princeton University Press . W. Tucker. 2011. Validated Numerics: A Short Introduction to Rigorous Computations. Princeton University Press."},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1090\/noti1276"},{"volume-title":"Linear and Nonlinear Integral Equations: Methods and Applications","author":"Wazwaz A.-M.","key":"e_1_2_1_55_1","unstructured":"A.-M. Wazwaz . 2011. Linear and Nonlinear Integral Equations: Methods and Applications . Springer Science 8 Business Media. A.-M. Wazwaz. 2011. Linear and Nonlinear Integral Equations: Methods and Applications. Springer Science 8 Business Media."},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0036142996304498"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1016\/0377-0427(90)90042-X"},{"key":"e_1_2_1_58_1","volume-title":"II","author":"Zygmund A.","unstructured":"A. Zygmund . 2002. Trigonometric Series Vol. I , II ( 3 rd ed.). Cambridge University Press , Cambridge . xii; Vol. I: xiv+ 383 pp.; Vol. II: viii+364 pages. 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.","edition":"3"}],"container-title":["ACM Transactions on Mathematical Software"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3208103","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3208103","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:08:06Z","timestamp":1750212486000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3208103"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,7,31]]},"references-count":56,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,12,31]]}},"alternative-id":["10.1145\/3208103"],"URL":"https:\/\/doi.org\/10.1145\/3208103","relation":{},"ISSN":["0098-3500","1557-7295"],"issn-type":[{"type":"print","value":"0098-3500"},{"type":"electronic","value":"1557-7295"}],"subject":[],"published":{"date-parts":[[2018,7,31]]},"assertion":[{"value":"2017-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-07-31","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}