Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4609064 | Journal of Complexity | 2008 | 12 Pages |
Abstract
We study the complexity of randomized solution of initial value problems for systems of ordinary differential equations (ODE). The input data are assumed to be γγ-smooth (γ=r+ργ=r+ρ: the r th derivatives satisfy a ρρ-Hölder condition). Recently, the following almost sharp estimate of the order of the n th minimal error was given by Kacewicz [Almost optimal solution of initial-value problems by randomized and quantum algorithms, J. Complexity 22 (2006) 676–690, see also 〈〈http://arXiv.org/abs/quant-ph/0510045〉〉]:c1n-γ-1/2⩽enran⩽c2(ε)n-γ-1/2+ε,with an arbitrary ε>0ε>0. We present a Taylor Monte Carlo method and show that it has error rate n-γ-1/2n-γ-1/2, this way establishing the exact order of the randomized nth minimal error.
Related Topics
Physical Sciences and Engineering
Mathematics
Analysis
Authors
Stefan Heinrich, Bernhard Milla,