Computational complexity of one-step methods for systems of differential equations

Author:
Arthur G. Werschulz

Journal:
Math. Comp. **34** (1980), 155-174

MSC:
Primary 65L05; Secondary 34A50, 68C25

DOI:
https://doi.org/10.1090/S0025-5718-1980-0551295-0

MathSciNet review:
551295

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: The problem is to calculate an approximate solution of an initial value problem for an autonomous system of *N* ordinary differential equations. Using fast power series techniques, we exhibit an algorithm for the *p*th-order Taylor series method requiring only arithmetic operations per step as . (Moreover, we show that any such algorithm requires at least operations per step.) We compute the order which minimizes the complexity bounds for Taylor series and linear Runge-Kutta methods and show that in all cases this optimal order increases as the error criterion decreases, tending to infinity as tends to zero. Finally, we show that if certain derivatives are easy to evaluate, then Taylor series methods are asymptotically better than linear Runge-Kutta methods for problems of small dimension *N*.

**[A]**Allan Borodin and Ian Munro,*The computational complexity of algebraic and numeric problems*, American Elsevier Publishing Co., Inc., New York-London-Amsterdam, 1975. Elsevier Computer Science Library; Theory of Computation Series, No. 1. MR**0468309****[R]**P. BRENT [1974],*Efficient Methods for Finding Zeros of Functions Whose Derivatives are Easy to Evaluate*, Computer Science Department Report, Carnegie-Mellon University, 1974.**[R]**R. P. Brent and H. T. Kung,*Fast algorithms for manipulating formal power series*, J. Assoc. Comput. Mach.**25**(1978), no. 4, 581–595. MR**0520733**, https://doi.org/10.1145/322092.322099**[J]**J. C. Butcher,*Implicit Runge-Kutta processes*, Math. Comp.**18**(1964), 50–64. MR**0159424**, https://doi.org/10.1090/S0025-5718-1964-0159424-9**[J]**J. C. Butcher,*An order bound for Runge-Kutta methods*, SIAM J. Numer. Anal.**12**(1975), 304–315. MR**0381315**, https://doi.org/10.1137/0712025**[G]**G. J. Cooper,*Error bounds for some single step methods*, Conf. on Numerical Solution of Differential Equations (Dundee, 1969) Springer, Berlin, 1969, pp. 140–147. MR**0278525****[G]**G. J. Cooper and J. H. Verner,*Some explicit Runge-Kutta methods of high order*, SIAM J. Numer. Anal.**9**(1972), 389–405. MR**0317546**, https://doi.org/10.1137/0709037**[A]**Avner Friedman,*Partial differential equations*, Holt, Rinehart and Winston, Inc., New York-Montreal, Que.-London, 1969. MR**0445088****[P]**Peter Henrici,*Discrete variable methods in ordinary differential equations*, John Wiley & Sons, Inc., New York-London, 1962. MR**0135729****[A]**C. HINDMARSH [1974],*Numerical Solution of Ordinary Differential Equations*:*Lecture Notes*, Lawrence Livermore Laboratory Report No. UCID-16588, June, 1974.**[G]**PÓLYA & G. SZEGÖ [1925],*Aufgaben und Lehrsätze der Analysis*, Vol. I, Springer-Verlag, Berlin, 1925.**[L]**Louis B. Rall,*Computational solution of nonlinear operator equations*, With an appendix by Ramon E. Moore, John Wiley & Sons, Inc., New York-London-Sydney, 1969. MR**0240944****[H]**Hans J. Stetter,*Analysis of discretization methods for ordinary differential equations*, Springer-Verlag, New York-Heidelberg, 1973. Springer Tracts in Natural Philosophy, Vol. 23. MR**0426438****[G]**SZEGÖ [1959],*Orthogonal Polynomials*, Amer. Math. Soc. Colloq. Publ., Vol. 23, Amer. Math. Soc., Providence, R. I., 1959.**[J]**F. TRAUB & H. WOŹNIAKOWSKI [1976], "Strict lower and upper bounds on iterative complexity," in*Analytic Computational Complexity*(J. F. Traub, Ed.), Academic Press, New York, 1976.**[A]**G. WERSCHULZ [1976],*Optimal Order and Minimal Complexity of One-Step Methods for Initial Value Problems*, Computer Science Department Report, Carnegie-Mellon University, 1976.

Retrieve articles in *Mathematics of Computation*
with MSC:
65L05,
34A50,
68C25

Retrieve articles in all journals with MSC: 65L05, 34A50, 68C25

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1980-0551295-0

Article copyright:
© Copyright 1980
American Mathematical Society