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 pth-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] BORODIN & I. MUNRO [1975], The Computational Complexity of Algebraic and Numeric Problems, American Elsevier, New York, 1975. MR 0468309 (57:8145)
- [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] P. BRENT & H. T. KUNG [1978], "Fast algorithms for manipulating formal power series," J. Assoc. Comput. Mach., v. 25, 1978, pp. 581-595. MR 0520733 (58:25090)
- [J] C. BUTCHER [1964], "Implicit Runge-Kutta processes," Math. Comp., v. 18, 1964, pp. 50-64. MR 0159424 (28:2641)
- [J] C. BUTCHER [1975], "An order bound for Runge-Kutta methods," SIAM J. Numer. Anal., v. 12, 1975, pp. 304-315. MR 0381315 (52:2212)
- [G] J. COOPER [1969], "Error bounds for some single-step methods," Conf. on the Numerical Solution of Differential Equations, Lecture Notes in Math., vol. 109, Springer-Verlag, Berlin, 1969, pp. 140-147. MR 0278525 (43:4255)
- [G] J. COOPER &. J. H. VERNER [1972], "Some explicit Runge-Kutta methods of high order," SIAM J. Numer. Anal., v. 9, 1972, pp. 389-405. MR 0317546 (47:6093)
- [A] FRIEDMAN [1969], Partial Differential Equations, Holt, Rinehart, and Winston, New York, 1969. MR 0445088 (56:3433)
- [P] HENRICI [1962], Discrete Variable Methods in Ordinary Differential Equations, Wiley, New York, 1962. MR 0135729 (24:B1772)
- [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] B. RALL [1969], Computational Solution of Nonlinear Operator Equations, Wiley, New York, 1969. MR 0240944 (39:2289)
- [H] J. STETTER [1973], Analysis of Discretization Methods for Ordinary Differential Equations, Springer-Verlag, Berlin, 1972. MR 0426438 (54:14381)
- [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