Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



The Monte Carlo complexity of Fredholm integral equations

Authors: Stefan Heinrich and Peter Mathé
Journal: Math. Comp. 60 (1993), 257-278
MSC: Primary 65C05; Secondary 45L10, 60J10, 65R20
MathSciNet review: 1153164
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: A complexity study of Monte Carlo methods for Fredholm integral equations is carried out. We analyze the problem of computing a functional $ \mu (y)$, where y is the solution of a Fredholm integral equation

$\displaystyle y(s) = \int_{{I^m}} {k(s,t)y(t)\;dt + f(s),\quad s \in {I^m}} $

, on the m-dimensional unit cube $ {I^m}$, where the kernel k and right-hand side f are given r times differentiable functions. We permit stochastic numerical methods which can make use of function evaluations of k and f only.

All Monte Carlo methods known to the authors for solving the above problem are of the order $ {n^{ - 1/2}}$, while the optimal deterministic methods yield rate $ {n^{ - r/(2m)}}$, thus taking into account the given smoothness of the data. Here, n denotes the (average) number of function evaluations performed. The optimal algorithm we present combines deterministic and stochastic methods in an optimal way. It can be seen that both rates--the standard Monte Carlo rate for general continuous data and the deterministic rate for r-smooth data--multiply. This provides the smallest error that stochastic methods of given computational cost can achieve.

References [Enhancements On Off] (What's this?)

  • [1] A. V. Aho, J. E. Hopcroft, and J. D. Ullmann, The design and analysis of computer algorithms, Addison-Wesley, Reading, MA, 1974. MR 0413592 (54:1706)
  • [2] K. E. Atkinson, A survey of numerical methods for the solution of Fredholm integral equations of the second kind, SIAM, Philadelphia, 1976. MR 0483585 (58:3577)
  • [3] N. S. Bakhvalov, On approximate computation of multiple integrals, Vestnik Moskov. Univ. Ser. I Mat. Mekh. 4 (1959), 3-18. (Russian) MR 0115275 (22:6077)
  • [4] Yu. A. Brychkov, O. I. Marichev, and A. P. Prudnikov, Integrals and series, Volume 1: Elementary functions, Gordon & Breach, New York, London, and Paris, 1986. MR 874986 (88f:00013)
  • [5] P. G. Ciarlet, The finite element method for elliptic problems, North-Holland, Amsterdam, New York, and Oxford, 1978. MR 0520174 (58:25001)
  • [6] K. V. Emelyanov and A. M. Ilin, On the number of arithmetic operations, necessary for the approximate solution of Fredholm integral equations of the second kind, Zh. Vychisl. Mat. i Mat. Fiz. 7 (1967), 905-910; English transl. in USSR Comput. Math. and Math. Phys. 7 (1967), 259-267. MR 0215547 (35:6387)
  • [7] S. M. Ermakov, The Monte Carlo method and related problems, Nauka, Moscow, 1971. (Russian) MR 0388718 (52:9552)
  • [8] S. M. Ermakov and G. A. Michailov, The theory of statistical trials, 2nd ed., Nauka, Moscow, 1982. (Russian)
  • [9] S. M. Ermakov, W. W. Nekrutkin, and A. S. Sipin, Random processes for classical equations of mathematical physics, Math. Appl. (Soviet Ser.), vol. 34, Kluwer, Dordrecht, 1989.
  • [10] W. Hackbusch, Multi-grid methods and applications, Springer, Berlin, Heidelberg, and New York, 1985.
  • [11] S. Heinrich, On the optimal error of degenerate kernel methods, J. Integral Equations 9 (1985), 251-266. MR 813376 (87a:65191)
  • [12] -, Probabilistic analysis of numerical methods for integral equations, J. Integral Equations Appl. 3 (1991), 289-319. MR 1116217 (93a:65181a)
  • [13] St. Kaczmarz and H. Steinhaus, Theory of orthogonal series, 2nd ed., Chelsea, New York, 1951.
  • [14] M. Loève, Probability theory, 4th ed., Graduate Texts in Math., vol. 46, Springer, New York, 1978.
  • [15] P. Mathé, Random approximation of Sobolev embeddings, J. Complexity 7 (1991), 261-281. MR 1128021 (93d:65008)
  • [16] E. Novak, Deterministic and stochastic error bounds in numerical analysis, Springer, Berlin, Heidelberg, and New York, 1988. MR 971255 (90a:65004)
  • [17] S. V. Pereverzev, On the optimization of adaptive methods for the approximate solution of integral equations, Dokl. Akad. Nauk SSSR 267 (1982), 1304-1308; English transl. in Soviet Math. Dokl. 26 (1982), 770-774. MR 687906 (84f:65089)
  • [18] -, On the complexity of the problem of finding solutions of Fredholm equations of the second kind with smooth kernels. I, Ukrain. Mat. Zh. 40 (1988), 84-91; English transl. in Ukrainian Math. J. 40 (1988), 71-76. MR 936406 (90i:65244)
  • [19] -, On the complexity of the problem of finding solutions of Fredholm equations of the second kind with smooth kernels. II, Ukrain. Mat. Zh. 41 (1989), 189-193; English transl. in Ukrainian Math. J. 41 (1989), 169-173. MR 992820 (90i:65245)
  • [20] J. F. Traub, G. W. Wasilkowski, and H. Woźniakowski, Information-based complexity, Academic Press, New York, 1988. MR 958691 (90f:68085)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 65C05, 45L10, 60J10, 65R20

Retrieve articles in all journals with MSC: 65C05, 45L10, 60J10, 65R20

Additional Information

Article copyright: © Copyright 1993 American Mathematical Society

American Mathematical Society