Russian Journal of Numerical Analysis and Mathematical Modelling, 17(1) (2002), 41-69

We develop the base principles of the theory of implicit extrapolation methods for ordinary differential equations. Of considerable importance for the practical implementation of these methods are the estimates of a sufficient number of iterations in an iteration method used to solve the system of algebraic equations, which results from the discretization of the original problem. In this paper we consider three best known iterative processes, viz. the simple iteration method, the generalized and modified Newton methods for which we prove the estimates of a sufficient number of iterations when extrapolating the numerical solution. Naturally, implicit extrapolation methods are very time-consuming. However, if they are based on the implicit Runge-Kutta methods with appropriate stability properties, the algorithms thus obtained are applicable for solving a broader class of problems. Moreover, in this paper we construct the theory of minimum implicit one-step methods whose extrapolation process requires the least (in the class of implicit methods) computer time. We prove that the above estimates of a sufficient number of iterations allow us to correctly realize implicit quadratic extrapolation in practice. The efficiency of the new class of methods and the importance of the sufficient estimates of the number of iterations for implicit extrapolation methods are demonstrated with numerical examples.

CEMAT - Center for Computational and Stochastic Mathematics