BALL_VOLUME_MONTE_CARLO is a MATLAB program which investigates the behavior of a Monte Carlo procedure when it is applied to compute the integral of a discontinuous function. In particular, our integration region is the M-dimensional and our function f(x) is 1 if the point x is inside the hypersphere of radius 1, and 0 otherwise.
The program uses the Monte Carlo method to estimate the volume. Estimates are made starting with 2^0 (=1) points and doubling repeatedly up to 2^25 points.
Because the integrand is discontinuous, any quadrature rule based on the idea of interpolation will probably be unable to do a good job. A family of quadrature rules, which rely on increasing the order of interpolation to improve accuracy, will probably get increasingly bad answers.
By contrast, a basic Monte Carlo rule, which assumes nothing about the function, integrates this function just as well as it integrates most any other square-integrable function. (That's both the strength and weakness of the blunt instrument we call Monte Carlo integration.)
ball_volume_monte_carlo ( dim_num, seed )where
Here are the results for dimension 4:
Log(N) N Estimate Error
0 1 0.0000000 4.9
1 2 0.0000000 4.9
2 4 4.0000000 0.93
3 8 4.0000000 0.93
4 16 3.0000000 1.9
5 32 4.0000000 0.93
6 64 5.5000000 0.57
7 128 5.3750000 0.44
8 256 5.2500000 0.32
9 512 5.0625000 0.13
10 1024 5.0625000 0.13
11 2048 4.9140625 0.21E-01
12 4096 4.9648438 0.30E-01
13 8192 4.9394531 0.47E-02
14 16384 4.9990234 0.64E-01
15 32768 4.9746094 0.40E-01
16 65536 4.9738770 0.39E-01
17 131072 4.9431152 0.83E-02
18 262144 4.9287109 0.61E-02
19 524288 4.9505920 0.16E-01
20 1048576 4.9356537 0.85E-03
21 2097152 4.9341202 0.68E-03
22 4194304 4.9353104 0.51E-03
23 8388608 4.9374676 0.27E-02
24 16777216 4.9353895 0.59E-03
25 33554432 4.9356027 0.80E-03
oo oo 4.9348022 0.0
The computer code and data files described and made available on this web page are distributed under the GNU LGPL license.
BALL_VOLUME_MONTE_CARLO is available in a C version and a C++ version and a FORTRAN77 version and a FORTRAN90 version and a MATLAB version.
NINTLIB, a MATLAB library which numerically estimates integrals in multiple dimensions.
SPHERE_MONTE_CARLO, a MATLAB library which applies a Monte Carlo method to estimate the integral of a function over the surface of the unit sphere in 3D;
STROUD, a MATLAB library which defines quadrature rules for a variety of unusual areas, surfaces and volumes in 2D, 3D and multiple dimensions.
TETRAHEDRON_MONTE_CARLO, a MATLAB program which uses the Monte Carlo method to estimate integrals over a tetrahedron.
TRIANGLE_MONTE_CARLO, a MATLAB program which uses the Monte Carlo method to estimate integrals over a triangle.
You can go up one level to the MATLAB source codes.