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

DOI:
https://doi.org/10.1090/S0025-5718-1993-1153164-3

MathSciNet review:
1153164

Full-text PDF

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 , where *y* is the solution of a Fredholm integral equation

*m*-dimensional unit cube , 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 , while the optimal deterministic methods yield rate , 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.

**[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**0215547****[7]**S. M. Ermakov,*\cyr 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**, https://doi.org/10.1216/jiea/1181075619**[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**, https://doi.org/10.1016/0885-064X(91)90036-W**[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**, https://doi.org/10.1007/BF01056451**[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**, https://doi.org/10.1007/BF01060382**[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**

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

DOI:
https://doi.org/10.1090/S0025-5718-1993-1153164-3

Article copyright:
© Copyright 1993
American Mathematical Society