Monte Carlo complexity of global solution of integral equations. (English) Zbl 0920.65090
This paper is devoted to the theoretical complexity analysis of randomized solutions of the global problem of the Fredholm integral equation
\[
u(s)- \int_G k(s,t) u(t)dt= f(s).
\]
The framework for this analysis is provided by information-based complexity theory. The present work complements previous research on the deterministic complexity of the local and the global problem and on the Monte Carlo complexity of the local problem. The result shows that randomized methods are superior to deterministic ones for the global problem. However, the difference between the optimal stochastic and deterministic convergence rate in the global case is smaller than in the local case.
Reviewer: N.Parhi (Berhampur)
MSC:
| 65R20 | Numerical methods for integral equations |
| 65C05 | Monte Carlo methods |
| 65Y20 | Complexity and performance of numerical algorithms |
| 45B05 | Fredholm integral equations |
Keywords:
Fredholm integral equation; information-based complexity; Monte Carlo complexity; convergenceReferences:
| [1] | Bakhvalov, N. S., On approximate calculation of integrals, Vestnik Moskow. Gos. Univ. Ser Mat. Mekh. Astronom Fiz. Khim, 4, 3-18 (1959) · Zbl 0780.73045 |
| [2] | Emelyanov, K. V.; Ilin, A. M., 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, 905-910 (1967) |
| [3] | Ermakov, S. M., The Monte Carlo Method and Related Problems (1971), Nauka: Nauka Moscow · Zbl 0228.65004 |
| [4] | Heinrich, S., Random approximation in numerical analysis, Functional Analysis (1994), Dekker: Dekker New York, p. 123-171 · Zbl 0794.65005 |
| [5] | Heinrich, S., Complexity of Monte Carlo Algorithms, The Mathematics of Numerical Analysis. The Mathematics of Numerical Analysis, Lectures in Applied Mathematics, 32 (1996), AMS-SIAM Summer Seminar: AMS-SIAM Summer Seminar Park City, p. 1621-1633 · Zbl 0853.65004 |
| [6] | Heinrich, S.; Mathé, P., The Monte Carlo complexity of Fredholm integral equations, Math. Comp., 60, 257-278 (1993) · Zbl 0795.65095 |
| [7] | Ledoux, M.; Talagrand, M., Probability in Banach Spaces (1991), Springer: Springer Berlin/Heidelberg/New York · Zbl 0662.60008 |
| [8] | Linde, W.; Pietsch, A., Mappings of Gaussian measures of cylindrical sets in Banach spaces, Theory Probab. Appl., 19, 445-460 (1974) · Zbl 0312.60005 |
| [9] | Mathé, P., Approximation Theory of Stochastic Numerical Methods (1994) |
| [10] | Mikhailov, G. A., Minimization of Computational Costs of Non-Analogue Monte Carlo Methods (1991), World Scientific: World Scientific Singapore · Zbl 0778.65007 |
| [11] | Mikhailov, G. A., Optimization of Weighted Monte Carlo Methods (1991), Springer: Springer Berlin/Heidelberg/New York · Zbl 0816.65140 |
| [12] | Mikhailov, G. A., New Monte Carlo Methods with Estimating Derivatives (1995), VSP: VSP Utrecht · Zbl 0841.65003 |
| [13] | Novak, E., Deterministic and Stochastic Error Bounds in Numerical Analysis. Deterministic and Stochastic Error Bounds in Numerical Analysis, Lecture Notes in Mathematics, 1349 (1988), Springer: Springer Berlin/Heidelberg/New York/London/Paris/Tokyo · Zbl 0656.65047 |
| [14] | Spanier, J.; Howell, J. R., Monte Carlo Principles and Neutron Transport Problems (1969), Addison-Wesley: Addison-Wesley Reading · Zbl 0244.62004 |
| [15] | Siegel, R.; Howell, J. R., Thermal Radiation Heat Transfer (1992), Hemisphere: Hemisphere New York |
| [16] | Tomczak-Jaegermann, N., Banach-Mazur Distances and Finite-Dimensional Operator Ideals (1988), Longman: Longman Essex · Zbl 0721.46004 |
| [17] | Traub, J. F.; Wasilkowski, G. W.; Woźniakowski, H., Information-Based Complexity (1988), Academic Press: Academic Press New York · Zbl 0674.68039 |
| [18] | Voytishek, A. V., Asymptotics of convergence of discretely stochastic numerical methods of the global estimate of the solution to an integral equation of the second kind, Sibirsk. Mat. Zh., 35, 728-736 (1994) · Zbl 0852.65125 |
| [19] | Voytishek, A. V., On the errors of discretely stochastic procedures in estimating globally the solution of an integral equation of the second kind, Russian J. Numer. Anal. Math. Modelling, 11, 71-92 (1996) · Zbl 0854.65120 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
