Computational Complexity of One-Step Methods for the Numerical Solution of Initial Value Problems
Abstract
The task of numerically approximating the solution of an ordinary differential equation initial-value problems is discussed. Two questions are considered: (1) For any given one-step method, what is the complexity of finding an approximate solution with error less than epsilon. (2) Given an infinite sequence of one-step methods of increasing order, how should the method and the step-size be picked so as to minimize the complexity of finding such an approximation. A methodology is described that handles both questions. It is found that within such a sequence of methods, the following hold under very general circumstances: For any epsilon, O < epsilon < 1, there is a unique choice of order and step-size which minimizes the complexity. (2) As epsilon decreases, both the optimal order and the complexity increase monotonically, tending to infinity as epsilon tends to zero. These results are applied to several classes of one-step methods. In doing so, some new Taylor series methods are used that are asymptotically better than Runge-Kutta methods for problems of small dimension. Moreover, it is proven that among all classes of nonlinear Runge-Kutta methods, those due to Brent have the highest order possible.
Document Details
- Document Type
- Technical Report
- Publication Date
- Sep 01, 1976
- Accession Number
- ADA032346
Entities
People
- Arthur G. Werschulz
Organizations
- Carnegie Mellon University