Szczegóły publikacji
Opis bibliograficzny
Complexity of the derivative-free solution of systems of IVPs with unknown singularity hypersurface / Bolesław KACEWICZ, Paweł PRZYBYŁOWICZ // Journal of Complexity ; ISSN 0885-064X. — 2015 — vol. 31 iss. 1, s. 75–97. — Bibliogr. s. 97, Abstr.
Autorzy (2)
Słowa kluczowe
Dane bibliometryczne
ID BaDAP | 86502 |
---|---|
Data dodania do BaDAP | 2014-12-13 |
Tekst źródłowy | URL |
DOI | 10.1016/j.jco.2014.07.002 |
Rok publikacji | 2015 |
Typ publikacji | artykuł w czasopiśmie |
Otwarty dostęp | |
Czasopismo/seria | Journal of Complexity |
Abstract
It is well-known that classical integration schemes designed for regular systems of IVPs become inefficient for piecewise regular problems. To avoid a significant increase of the cost of obtaining an epsilon-approximation for piecewise regular problems, special adaptive algorithms are usually designed. Constructing such algorithms is often based on the knowledge of a 'switching function' whose zeros define the singularity hypersurface, or it relies on certain heuristic arguments. In this paper we analyze the worst-case epsilon-complexity of globally continuous and piecewise regular problems with unknown smooth switching function. We consider problems with right-hand side functions from the class F-r,F-rho which consists of piecewise r-smooth functions with Holder r-th partial derivatives with the exponent rho is an element of(0, 1]. In contrast to our previous work, we restrict ourselves to information defined only by values of the right-hand side function (computation of partial derivatives is not allowed). We design an algorithm that is based on the computation of Lagrange interpolation polynomials to locate singularity points and to approximate a function of a single variable at intermediate stages. A rigorous analysis (independent of heuristic arguments) of its error and cost is given. It turns out that both the error and the cost of the algorithm are of the same order as for regular problems. That is, no reduction of the order is observed when passing through singularities, and the cost of the algorithm remains at the same level as for regular problems. In the class F-r,F-rho the algorithm has the worst-case error O(m(-(r+rho))) (in the Chebyshev norm) and the total cost O(m), where m is the number of discretization points. This leads to the conclusion that the worst-case epsilon-complexity of the considered problem in F-r,F-rho is Theta(epsilon(-1/(r+rho))), and the minimal cost is achieved by the defined algorithm that only needs function evaluations. The auxiliary algorithm that locates singularities and approximates a piecewise regular function of a single variable is also original, and it may be of interest per se. (C) 2014 Elsevier Inc. All rights reserved.