Abstract
We investigate the optimal solution of systems of initial-value problems with smooth right-hand side functions f from a Hölder class \(F^{r,\varrho }_{\text {reg}}\), where r ≥ 0 is the number of continuous derivatives of f, and ϱ ∈ (0, 1] is the Hölder exponent of rth partial derivatives. We consider algorithms that use n evaluations of f, the ith evaluation being corrupted by a noise δ i of deterministic or random nature. For δ ≥ 0, in the deterministic case the noise δ i is a bounded vector, ∥δ i ∥≤δ. In the random case, it is a vector-valued random variable bounded in average, (E(∥δ i ∥q))1/q ≤ δ, q ∈ [1, + ∞). We point out an algorithm whose L p error (p ∈ [0, + ∞]) is O(n − (r + ϱ) + δ), independently of the noise distribution. We observe that the level n − (r + ϱ) + δ cannot be improved in a class of information evaluations and algorithms. For ε > 0, and a certain model of δ-dependent cost, we establish optimal values of n(ε) and δ(ε) that should be used in order to get the error at most ε with minimal cost.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Daun, T.: On the randomized solution of initial value problems. J. Complexity 27, 300–311 (2011)
Heinrich, S., Milla, B.: The randomized complexity of initial value problems. J. Complexity 24, 77–88 (2008)
Kacewicz, B.: How to increase the order to get minimal-error algorithms for systems of ODE. Numer. Math. 45, 93–104 (1984)
Kacewicz, B.: Minimum asymptotic error of algorithms for solving ODE. J. Complexity 4, 373–389 (1988)
Kacewicz, B.: Almost optimal solution of initial-value problems by randomized and quantum algorithms. J. Complexity 22, 676–690 (2006)
Kacewicz, B., Milanese, M., Vicino, A.: Conditionally optimal algorithms and estimation of reduced order models. J. Complexity 4, 73–85 (1988)
Kacewicz, B., Plaskota, L.: The minimal cost of approximating linear operators using perturbed information – the asymptotic setting. J. Complexity 9, 113–134 (1993)
Kacewicz, B., Przybyłowicz, P.: Complexity of the derivative-free solution of systems of IVPs with unknown singularity hypersurface. J. Complexity 31, 75–97 (2015)
Novak, E.: Deterministic and stochastic error bounds in numerical analysis, Lecture Notes in Math. Springer, Berlin (1349)
Plaskota, L.: Noisy information and computational complexity. Cambridge University Press, Cambridge (1996a)
Plaskota, L.: Worst case complexity of problems with random information noise. J. Complexity 12, 416–439 (1996b)
Plaskota, L.: Noisy information: optimality, complexity, tractability. In: Dick, J., Kuo, F.Y., Peters, G.W., Sloan, I.H. (eds.) Monte Carlo and quasi-Monte Carlo Methods, pp. 173–209. Springer (2012)
Traub, J.F., Wasilkowski, G.W., Woźniakowski, H.: Information–based complexity. Academic, New York (1988)
Werschulz, A.G.: The complexity of definite elliptic problems with noisy data. J. Complexity 12, 440–473 (1996)
Werschulz, A.G.: The complexity of indefinite elliptic problems with noisy data. J. Complexity 13, 457–479 (1997)
Author information
Authors and Affiliations
Corresponding author
Additional information
This research was partly supported by the Polish NCN grant – decision No. DEC-2013/09/B/ST1/04275 and by the Polish Ministry of Science and Higher Education
Rights and permissions
About this article
Cite this article
Kacewicz, B., Przybyłowicz, P. On the optimal robust solution of IVPs with noisy information. Numer Algor 71, 505–518 (2016). https://doi.org/10.1007/s11075-015-0006-6
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11075-015-0006-6