Optimal solution of ordinary differential equations (Q1102074)

This is a survey of theoretical optimality results for the numerical solution of initial value problems for ODE's. First one assumes that the algorithms has only partial information of the right-hand side f, e.g. values of f at n points and some a priori knowledge about the smoothness of f. Since many right-hand-sides share the same information no algorithm can overcome this uncertainty. The main results of the article consist of upper and lower bounds for the minimum error. Upper bounds are found by giving the error of some algorithm. The lower bound is found by algorithm-independent consideration. Two different settings are considered. The worst case situation for a class of right-hand sides and the asymptotic behavior of the error for a fixed f. The crucial parameters are the number n of evaluations of f and the number r of continuous partial derivatives. The bounds found depend on whether the information is given by point values, linear functionals or nonlinear continuous functionals. The results are then used to determine the \(\epsilon\)-complexity which is defined following Woźniakowsky as the minimum cost to approximate a solution with accuracy \(\epsilon\), where the right-hand sides have to belong to a certain set.