使用Monte-Carlo方法計算n球的體積

我想在MATLAB中創建一個計算R^n中的n球體積的函數。爲此，我使用Monte-Carlo方法在n立方體中隨機生成點，然後使用n球內的點與所有生成點相乘的比率乘以n立方體的體積。這裏是我迄今爲止產生的代碼：使用Monte-Carlo方法計算n球的體積

function [ approximate_volume ] = MonteCarloHypersphereVolume(radius, dimension, number_of_generations) 
%MonteCarloHypersphereVolume Computes the volume of a 
%'dimension'-dimensional hypersphere by the Monte Carlo method 

number_within_sphere = 0; 
parfor i = 1 : number_of_generations 
    randoms = zeros(1, dimension); 
    for j = 1 : dimension 
     randoms(j) = randi(radius * 2) - radius; 
    end 

    if sum(randoms .^ 2) <= radius^2 
     number_within_sphere = number_within_sphere + 1; 
    end 
end 

approximate_volume = (number_within_sphere/number_of_generations) * (2*radius)^dimension; 

end

但是，這看起來是非常不準確的;根據維基百科，單位10球的數量應該是：V_10 = pi^5/5！ = 2.5502，但是當運行1000000次迭代的函數時，它返回11.0067，確實多次運行它總是返回一個大約爲11的值，這比它應該高得多？

此外，有沒有辦法使用GPGPU編程來提高此功能的性能？除了number_within_sphere的數據依賴性外，它似乎很容易並行化？

來源

2014-01-20 Thomas Russell

我可以使用R來驗證一般的方法應該工作。你使用了什麼「半徑」？你知道['randi']（http://www.mathworks.de/de/help/matlab/ref/randi.html）返回*整數*嗎？你可能更喜歡['rand']（http://www.mathworks.de/de/help/matlab/ref/rand.html），你可以對它進行矢量化處理以放棄你的'for'循環。 – MvG

你的循環也不需要依賴'radius'。 'number_within_sphere'可以計算一個單位的n球。不要問兩個單獨的問題是個好主意。 – horchler

您必須使用rand而不是randi以連續均勻分佈對每個維度進行採樣。即，更換線

randoms(j) = randi(radius * 2) - radius;

通過

randoms(j) = rand*radius*2 - radius;

來源

2014-01-20 20:14:43

這種方法不結垢，由於n-單元時二維球的體積與所述n維立方體的體積[-1的比率， 1]^n趨於零指數快速（並且因此單位立方體內的幾乎每個隨機點將在單位球外部;例如，對於n = 30，立方體的體積大約是5 * 10^13倍大比球的體積）。

相反應該然而在這裏使用的多項式複雜蒙特卡洛算法尋找如所述的，例如一個凸體的體積，在

http://www.cs.berkeley.edu/~sinclair/cs294/n16.pdf

在它被寫下來的形式，一個已經假定n維球的體積爲的公式（我們需要知道文本中B_0的體積）。然而，人們可能會採取一系列具有類似屬性的增加立方體（第一個立方體是單位球中的一個立方體，最後一個是[-1,1]），而不是像文中那樣增加同心球的順序，^n，並且連續立方體的邊之間的比率是（至多）1 + 1/n），凸體K是單位球，並且然後可以使用相同的算法來找到單位球的體積。

來源

2014-02-05 11:22:50

使用Monte-Carlo方法計算n球的體積

回答

相關問題