On the randomized solution of initial value problems

We study the randomized solution of initial value problems for systems of ordinary differential equations y′(x)=f(x,y(x)),x∈[a,b],y(a)=y0∈Rd. Recently Heinrich and Milla (2008) [4] presented an order optimal randomized algorithm solving this problem for γγ-smooth input data (i.e. γ=r+ργ=r+ρ: the rr-th derivatives of ff satisfy a ρρ-Hölder condition). This algorithm uses function values and values of derivatives of ff. In this paper we present an order optimal randomized algorithm for the class of γγ-smooth functions that uses only values of ff. For this purpose we show how to obtain an order optimal randomized algorithm from an order (sub)optimal deterministic one.