擬蒙特卡羅方法
數值分析中,擬蒙特卡羅方法(Quasi-Monte Carlo method)是使用低差異列(一種確定生成的超均勻分布列,也稱為擬隨機列、次隨機列)來進行數值積分和研究其它一些數值問題的方法。而普通的蒙特卡羅方法或蒙地卡羅積分方法使用的是偽隨機數。MATLAB中提供了生成如哈爾頓列、索博爾列等超均勻分布列的函數[1]。
擬蒙特卡羅方法和蒙特卡羅方法的具體內容相似,要解決的問題都是通過測量某個可測函數 f 在某些點上的取值,而在數值上求它的積分的近似值。例如要求在單位體積上的積分近似,可以設取的點為x1, ..., xN,那麼:
其中的xi都是s維向量。擬蒙特卡羅方法和普通蒙特卡羅方法的區別在於xi的具體選取方式。蒙特卡羅方法用的是偽隨機列,而擬蒙特卡羅方法用到的是哈爾頓列、索博爾列等低差異列。使用低差異列的優點是收斂速率較快。擬蒙特卡羅方法可以達到O(1/N)的收斂速率,而普通蒙特卡羅方法的收斂速率則是 O(N-0.5)[2]。
近年來,擬蒙特卡羅方法在金融數學和計算機數學領域裡得到了越來越多的應用[2],因為其中常常會需要計算高維積分的數值近似。蒙特卡羅方法和擬蒙特卡羅方法可以快捷簡單地得到較好的結果。
誤差估計
擬蒙特卡羅方法的近似誤差可以用取點x1, ..., xN的差異度作為上限。具體來說,Koksma-Hlawka不等式表明,誤差項
被
限制,其中V(f)為函數f的Hardy-Krause變差[3],DN是(x1,...,xN)的差異度,定義為
- ,
其中Q是任何[0,1]s中邊界與坐標軸平行的方形「塊」[3]。表明擬蒙特卡羅方法的近似誤差大約是的量級,於此相對的是普通蒙特卡羅方法的近似誤差為量級。注意這裡的不等式給出的是誤差上限,事實上擬蒙特卡羅方法的收斂速率要比其上限所示的速率快得多[2]。因此,一般來說擬蒙特卡羅方法比起普通的蒙特卡羅方法來說大大加快了收斂的速率。
參考來源
- ^ Generating Quasi-Random Numbers
- ^ 2.0 2.1 2.2 Søren Asmussen and Peter W. Glynn, Stochastic Simulation: Algorithms and Analysis, Springer, 2007, 476 pages
- ^ 3.0 3.1 William J. Morokoff and Russel E. Caflisch, Quasi-Monte Carlo integration, J. Comput. Phys. 122 (1995), no. 2, 218--230. (At CiteSeer: [1] (頁面存檔備份,存於網際網路檔案館))
- R. E. Caflisch, Monte Carlo and quasi-Monte Carlo methods, Acta Numerica vol. 7, Cambridge University Press, 1998, pp. 1-49.
- Josef Dick and Friedrich Pillichshammer, Digital Nets and Sequences. Discrepancy Theory and Quasi-Monte Carlo Integration, Cambridge University Press, Cambridge, 2010, ISBN 978-0-521-19159-3
- Michael Drmota and Robert F. Tichy, Sequences, discrepancies and applications, Lecture Notes in Math.,1651, Springer, Berlin, 1997, ISBN 3-540-62606-9
- William J. Morokoff and Russel E. Caflisch, Quasi-random sequences and their discrepancies, SIAM J. Sci. Comput. 15 (1994), no. 6, 1251--1279 (AtCiteSeer:[2] (頁面存檔備份,存於網際網路檔案館))
- Harald Niederreiter. Random Number Generation and Quasi-Monte Carlo Methods. Society for Industrial and Applied Mathematics, 1992. ISBN 0-89871-295-5
- Harald G. Niederreiter, Quasi-Monte Carlo methods and pseudo-random numbers, Bull. Amer. Math. Soc. 84(1978), no. 6, 957--1041
- Oto Strauch and Štefan Porubský, Distribution of Sequences: A Sampler, Peter Lang Publishing House, Frankfurt am Main 2005, ISBN 3-631-54013-2
外部連結
- (英文)一個直觀的擬蒙特卡羅方法簡介