Complexity of initial-value problems for ordinary differential equations of order \(k\) (Q2507590)

The worst-case \(\varepsilon\)-complexity of nonlinear initial value problem \[ u^{(k)}(x)= g(x,u(x), u'(x),\dots,u^{(q)}(x)), \quad x\in[a,b], \;0\leq q< k, \] with given initial conditions is studied. With the assumption that the function \(g\) has \(r\) \((r\geq 1)\) continuous bounded partial derivatives, two algorithms are derived (based on standard and linear information). For standard information, the worst-case complexity is \(\theta((1/\varepsilon)^{1/r})\) which is independed of \(k\) and \(q\). For linear information, the complexity is \(0((1/\varepsilon)^{1/(r+k-q)})\). So, it is proved that linear information is more powerful than standard, for \(q= 0\). A lower bound on the \(\varepsilon\)-complexity is also given for linear information \(\Omega((1/\varepsilon)^{1/(r+k)})\).