Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
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?)


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/S0025-5718-1993-1153164-3
PII: S 0025-5718(1993)1153164-3
Article copyright: © Copyright 1993 American Mathematical Society