On the Petras algorithm for verified integration of piecewise analytic functions
This work offers a more complete complexity analysis of an existing algorithm for verified integration, benefiting researchers in numerical analysis and verified computing.
The paper provides upper and lower complexity bounds for Petras' verified integration algorithm, showing it achieves Θ(|ln ε|/ε^{p-1}) complexity for a wider class of piecewise analytic functions, where ε is the desired accuracy.
We consider the algorithm for verified integration of piecewise analytic functions given by Petras. The analysis of the algorithm contained in Patras' paper is limited to a narrow class of functions and gives upper bounds only. We present an estimation of the complexity (measured by a number of evaluations of an integrand) of the algorithm, both upper and lower bounds, for a wider class of functions. We show examples with complexity $Θ(|\ln\eps|/\eps^{p-1})$, for any $p >1$, where $\eps$ is the desired accuracy of the computed integral.