Szczegóły publikacji

Opis bibliograficzny

Autor

• AGHKacewicz Bolesław

Słowa kluczowe

Dane bibliometryczne

ID BaDAP	102592
Data dodania do BaDAP	2016-12-29
Tekst źródłowy	URL
DOI	10.1016/j.jco.2016.02.005
Rok publikacji	2017
Typ publikacji	artykuł w czasopiśmie
Otwarty dostęp
Czasopismo/seria	Journal of Complexity

Abstract

We study the solution of two-point boundary-value problems for second order ODEs with boundary conditions imposed on the first derivative of the solution. The right-hand side function gg is assumed to be rr times (r≥1r≥1) continuously differentiable with the rrth derivative being a Hölder function with exponent ϱ∈(0,1]ϱ∈(0,1]. The boundary conditions are defined through a continuously differentiable function ff. We define an algorithm for solving the problem with error of order m−(r+ϱ)m−(r+ϱ) and cost of order mlogmmlogm evaluations of gg and ff and arithmetic operations, where View the MathML sourcem∈N. We prove that this algorithm is optimal up to the logarithmic factor in the cost. This yields that the worst-case εε-complexity of the problem (i.e., the minimal cost of solving the problem with the worst-case error at most ε>0ε>0) is essentially Θ((1/ε)1/(r+ϱ))Θ((1/ε)1/(r+ϱ)), up to a log1/εlog1/ε factor in the upper bound. The same bounds hold for r+ϱ≥2r+ϱ≥2 even if we additionally assume convexity of gg. For r=1r=1, ϱ∈(0,1]ϱ∈(0,1] and convex functions gg, the information εε-complexity is shown to be Θ((1/ε)1/2)Θ((1/ε)1/2).

Publikacje, które mogą Cię zainteresować