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]**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)**

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