Computational Complexity of One-Step Methods for Systems of Differential Equations.
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 O((p to the N power) ln p) arithmetic operations per step as p goes to plus infinity. (Moreover, we show that any such algorithm requires at least O(p to the N power) 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 epsilon decreases, tending to infinity as epsilon 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. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Sep 01, 1976
- Accession Number
- ADA035929
Entities
People
- Arthur G. Werschulz
Organizations
- Carnegie Mellon University