Convergence rates for adaptive approximation of ordinary differential equations

This paper constructs an adaptive algorithm for ordinary differential equations and analyzes its asymptotic behavior as the error tolerance parameter tends to zero. An adaptive algorithm, based on the error indicators and successive subdivision of time steps, is proven to stop with the optimal number, N, of steps up to a problem independent factor defined in the algorithm. A version of the algorithm with decreasing tolerance also stops with the total number of steps, including all refinement levels, bounded by script O sign (N). The alternative version with constant tolerance stops with script O sign (N log N) total steps. The global error is bounded by the tolerance parameter asymptotically as the tolerance tends to zero. For a p-th order accurate method the optimal number of adaptive steps is proportional to the p-th root of the L^1/p+1 quasi-norm of the error density, while the number of uniform steps, with the same error, is proportional to the p-th root of the larger L¹-norm of the error density.