Back to Search
Start Over
Complexity of certain nonlinear two-point BVPs with Neumann boundary conditions.
- Source :
-
Journal of Complexity . Feb2017, Vol. 38, p6-21. 16p. - Publication Year :
- 2017
-
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 g is assumed to be r times ( r ≥ 1 ) continuously differentiable with the r th derivative being a Hölder function with exponent ϱ ∈ ( 0 , 1 ] . The boundary conditions are defined through a continuously differentiable function f . We define an algorithm for solving the problem with error of order m − ( r + ϱ ) and cost of order m log m evaluations of g and f and arithmetic operations, where m ∈ 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 ) is essentially Θ ( ( 1 / ε ) 1 / ( r + ϱ ) ) , up to a log 1 / ε factor in the upper bound. The same bounds hold for r + ϱ ≥ 2 even if we additionally assume convexity of g . For r = 1 , ϱ ∈ ( 0 , 1 ] and convex functions g , the information ε -complexity is shown to be Θ ( ( 1 / ε ) 1 / 2 ) . [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 0885064X
- Volume :
- 38
- Database :
- Academic Search Index
- Journal :
- Journal of Complexity
- Publication Type :
- Academic Journal
- Accession number :
- 119653745
- Full Text :
- https://doi.org/10.1016/j.jco.2016.02.005