On the power of adaptive information for functions with singularities

Authors:
G. W. Wasilkowski and F. Gao

Journal:
Math. Comp. **58** (1992), 285-304

MSC:
Primary 65D15; Secondary 62L12, 65D30

MathSciNet review:
1106987

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We study from a probabilistic viewpoint the problem of locating singularities of functions using function evaluations. We show that, under the assumption of a Wiener-like probability distribution on the class of singular functions, an adaptive algorithm can locate a singular point accurately with only a small probability of failure. As an application, we show that an integration algorithm that adaptively locates a singular point is probabilistically superior to nonadaptive algorithms.

**[1]**T. W. Anderson,*The integral of a symmetric unimodal function over a symmetric convex set and some probability inequalities*, Proc. Amer. Math. Soc.**6**(1955), 170–176. MR**0069229**, 10.1090/S0002-9939-1955-0069229-1**[2]**S. D. Conte,*Elementary numerical analysis: An algorithmic approach*, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1965. MR**0202267****[3]**Philip J. Davis and Philip Rabinowitz,*Methods of numerical integration*, 2nd ed., Computer Science and Applied Mathematics, Academic Press, Inc., Orlando, FL, 1984. MR**760629****[4]**Carl de Boor,*Splines as linear combinations of 𝐵-splines. A survey*, Approximation theory, II (Proc. Internat. Sympos., Univ.#Texas, Austin, Tex., 1976) Academic Press, New York, 1976, pp. 1–47. MR**0467092****[5]**Feng Gao,*A probabilistic theory for error estimation in automatic integration*, Numer. Math.**56**(1989), no. 4, 309–329. MR**1017833**, 10.1007/BF01396607**[6]**J. F. Traub, G. W. Wasilkowski, and H. Woźniakowski,*Information-based complexity*, Computer Science and Scientific Computing, Academic Press, Inc., Boston, MA, 1988. With contributions by A. G. Werschulz and T. Boult. MR**958691****[7]**Grace Wahba,*Improper priors, spline smoothing and the problem of guarding against model errors in regression*, J. Roy. Statist. Soc. Ser. B**40**(1978), no. 3, 364–372. MR**522220****[8]**G. W. Wasilkowski,*Information of varying cardinality*, J. Complexity**2**(1986), no. 3, 204–228. MR**922813**, 10.1016/0885-064X(86)90002-6

Retrieve articles in *Mathematics of Computation*
with MSC:
65D15,
62L12,
65D30

Retrieve articles in all journals with MSC: 65D15, 62L12, 65D30

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1992-1106987-X

Keywords:
Piecewise regular functions,
approximating/detecting singular points,
probabilistic analysis of algorithms,
adaptive (sequential) algorithms,
adaptive quadratures

Article copyright:
© Copyright 1992
American Mathematical Society