Computational Complexity of One-Step Methods for the Numerical Solution of Initial Value Problems

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.