On the complexity of self-validating numerical integration and approximation of functions with singularities (Q1273730)

The author presents a self-correcting algorithm for quadrature within \(\varepsilon>0\) of functions in \(C^k([a,b]\setminus Z_0)\), where \(Z_0\) is a finite set of points, which has cost \(O(\varepsilon^{-1/k})\) for a subclass of functions which are said to allow ``realistic'' range estimates. Let \(S^k[a,b]\) be bounded functions in \(C^k([a,b]\setminus Z_0)\) with the property (i) there exists \(c>0\) such that, for all \(f\), \(| f^{(k)}(x)|< c\text{ dist.}(x,Z)^{-k}\), \(Z= Z_0\sqcup(a- 1)\). Functions in \(S^k[a,b]\) are said to allow ``realistic'' range estimators \(E_0(f,[c,d]), E_k(f^{(k)},\) \([c,d])\), \([c,d]\subset [a,b]\) (constructed by interval arithmetic and automatic differentiation) if \(E_0= [c_0, d_0]\), \(E_k= [c_k, d_k]\) satisfy (ii) there exist \(M>0\), \(\delta>0\) such that, for \(| d-c|< \delta\), \(E_0\supset f([c,d])\), \(| d_0- c_0|< M\), (iii) there exist \(\beta>1\), \(\gamma>0\) such that \(E_k\supset f^{(k)}([c,d])\), \(| c_k|,| d_k|<\gamma N_k([c,d])\), \(N_k= \text{dist.}([x- \beta y,x+\beta y], Z)^{-k}\), \(x= 1/2(c+ d)\), \(y= 1/2(d- c)\). A similar algorithm is presented for uniform piecewise approximation to functions in \(C^k([a,b]\setminus Z_0)\) by polynomials. The cost of an \(\varepsilon> 0\) approximation is again \(O(\varepsilon^{-1/k})\) for a subclass of functions which allow similarly defined range estimators.