The Monte Carlo complexity of Fredholm integral equations
Authors:
Stefan Heinrich and Peter Mathé
Journal:
Math. Comp. 60 (1993), 257278
MSC:
Primary 65C05; Secondary 45L10, 60J10, 65R20
MathSciNet review:
1153164
Fulltext 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 , where y is the solution of a Fredholm integral equation , on the mdimensional unit cube , where the kernel k and righthand 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 ratesthe standard Monte Carlo rate for general continuous data and the deterministic rate for rsmooth datamultiply. 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,
AddisonWesley Publishing Co., Reading, Mass.LondonAmsterdam, 1975.
Second printing; AddisonWesley Series in Computer Science and Information
Processing. MR
0413592 (54 #1706)
 [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
(58 #3577)
 [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
(22 #6077)
 [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
(88f:00013)
 [5]
Philippe
G. Ciarlet, The finite element method for elliptic problems,
NorthHolland Publishing Co., AmsterdamNew YorkOxford, 1978. Studies in
Mathematics and its Applications, Vol. 4. MR 0520174
(58 #25001)
 [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, Z. Vyčisl. Mat. i Mat. Fiz. 7
(1967), 905–910 (Russian). MR 0215547
(35 #6387)
 [7]
S.
M. \cyr{E}rmakov, Metod MonteKarlo i smezhnye voprosy, Izdat.
“Nauka”, Moscow, 1971 (Russian). Monographs in Probability
Theory and Mathematical Statistics. 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, Multigrid 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
(87a:65191)
 [12]
Stefan
Heinrich, Probabilistic analysis of numerical methods for integral
equations, J. Integral Equations Appl. 3 (1991),
no. 2, 289–319. MR 1116217
(93a:65181a), http://dx.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
(93d:65008), http://dx.doi.org/10.1016/0885064X(91)90036W
 [16]
Erich
Novak, Deterministic and stochastic error bounds in numerical
analysis, Lecture Notes in Mathematics, vol. 1349,
SpringerVerlag, Berlin, 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), no. 6, 1304–1308 (Russian). MR 687906
(84f:65089)
 [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
(90i:65244), http://dx.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
(90i:65245), http://dx.doi.org/10.1007/BF01060382
 [20]
J.
F. Traub, G.
W. Wasilkowski, and H.
Woźniakowski, Informationbased complexity, Computer
Science and Scientific Computing, Academic Press, Inc., Boston, MA, 1988.
With contributions by A. G. Werschulz and T. Boult. MR 958691
(90f:68085)
 [1]
 A. V. Aho, J. E. Hopcroft, and J. D. Ullmann, The design and analysis of computer algorithms, AddisonWesley, 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), 318. (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, NorthHolland, 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), 905910; English transl. in USSR Comput. Math. and Math. Phys. 7 (1967), 259267. 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, Multigrid 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), 251266. MR 813376 (87a:65191)
 [12]
 , Probabilistic analysis of numerical methods for integral equations, J. Integral Equations Appl. 3 (1991), 289319. 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), 261281. 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), 13041308; English transl. in Soviet Math. Dokl. 26 (1982), 770774. 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), 8491; English transl. in Ukrainian Math. J. 40 (1988), 7176. 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), 189193; English transl. in Ukrainian Math. J. 41 (1989), 169173. MR 992820 (90i:65245)
 [20]
 J. F. Traub, G. W. Wasilkowski, and H. Woźniakowski, Informationbased 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
DOI:
http://dx.doi.org/10.1090/S00255718199311531643
PII:
S 00255718(1993)11531643
Article copyright:
© Copyright 1993
American Mathematical Society
