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] Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman, The design and analysis of computer algorithms, Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1975. Second printing; Addison-Wesley Series in Computer Science and Information Processing. MR 0413592
  • [2] Kendall E. Atkinson, A survey of numerical methods for the solution of Fredholm integral equations of the second kind, Society for Industrial and Applied Mathematics, Philadelphia, Pa., 1976. MR 0483585
  • [3] N. S. Bahvalov, Approximate computation of multiple integrals, Vestnik Moskov. Univ. Ser. Mat. Meh. Astr. Fiz. Him. 1959 (1959), no. 4, 3–18 (Russian). MR 0115275
  • [4] A. P. Prudnikov, Yu. A. Brychkov, and O. I. Marichev, Integrals and series. Vol. 1, Gordon & Breach Science Publishers, New York, 1986. Elementary functions; Translated from the Russian and with a preface by N. M. Queen. MR 874986
  • [5] Philippe G. Ciarlet, The finite element method for elliptic problems, North-Holland Publishing Co., Amsterdam-New York-Oxford, 1978. Studies in Mathematics and its Applications, Vol. 4. MR 0520174
  • [6] K. V. Emel′janov and A. M. Il′in, The number of arithmetical operations necessary for the approximate solution of Fredholm’s integral equation of the second kind, Ž. Vyčisl. Mat i Mat. Fiz. 7 (1967), 905–910 (Russian). MR 215547
  • [7] S. M. Ermakov, Metod Monte-Karlo i smezhnye voprosy, Izdat. “Nauka”, Moscow, 1971 (Russian). Monographs in Probability Theory and Mathematical Statistics. MR 0388718
  • [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), no. 3, 251–266. MR 813376
  • [12] Stefan Heinrich, Probabilistic analysis of numerical methods for integral equations, J. Integral Equations Appl. 3 (1991), no. 2, 289–319. MR 1116217,
  • [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] Peter Mathé, Random approximation of Sobolev embeddings, J. Complexity 7 (1991), no. 3, 261–281. MR 1128021,
  • [16] Erich Novak, Deterministic and stochastic error bounds in numerical analysis, Lecture Notes in Mathematics, vol. 1349, Springer-Verlag, Berlin, 1988. MR 971255
  • [17] S. V. Pereverzev, On the optimization of adaptive methods for the approximate solution of integral equations, Dokl. Akad. Nauk SSSR 267 (1982), no. 6, 1304–1308 (Russian). MR 687906
  • [18] S. V. Pereverzev, On the complexity of the problem of finding the solutions of Fredholm equations of the second kind with smooth kernels. I, Ukrain. Mat. Zh. 40 (1988), no. 1, 84–91, 134 (Russian); English transl., Ukrainian Math. J. 40 (1988), no. 1, 71–76. MR 936406,
  • [19] S. V. Pereverzev, On the complexity of the problem of finding the solutions of Fredholm equations of the second kind with smooth kernels. II, Ukrain. Mat. Zh. 41 (1989), no. 2, 189–193, 287 (Russian); English transl., Ukrainian Math. J. 41 (1989), no. 2, 169–173. MR 992820,
  • [20] 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

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