Квазі-Монте Карло методи

Апроксимаційна похибка методу квазі-Монте-Карло обмежена значенням, пропорційним невідповідності комплекту х₁, ..., х_n. Зокрема, з нерівності Koksma-Hlawka маємо, що похибка

${\displaystyle \epsilon =\left|\int _{[0,1]^{s}}f(u)\,{\rm {d}}u-{\frac {1}{N}}\,\sum _{i=1}^{N}f(x_{i})\right|}$

є обмеженою

${\displaystyle |\epsilon |\leq V(f)D_{N}}$,

де V(F) є варіацією Харді-Краузе для функції f (див. Morokoff і Кафлиш (1995) для детального визначення). Dn - це так звана головна  розбіжність набору (х₁,...,x_n) і визначається як

${\displaystyle D_{N}=\sup _{Q\subset [0,1]^{s}}\left|{\frac {{\mbox{number of points in }}Q}{N}}-{\mbox{volume}}(Q)\right|}$,

де Q - прямокутна [0,1]^s фігура зі сторонами, паралельними осям координат. Нерівність ${\displaystyle |\epsilon |\leq V(f)D_{N}}$ може бути використана, щоб показати, що похибка апроксимації методом квазі-Монте-Карло метод рівна ${\displaystyle O\left({\frac {(\log N)^{s}}{N}}\right)}$, у той час як метод Монте-Карло має імовірнісну похибку ${\displaystyle O\left({\frac {1}{\sqrt {N}}}\right)}$. Хоча ми можемо тільки констатувати верхню межу похибки апроксимації, збіжність розрахунку методу квазі-Монте-Карло на практиці, як правило, набагато швидша за його теоретичну межу. Отже, в загальному випадку, точність методу квазі-Монте-Карло збільшується швидше, ніж збіжність методу Монте-Карло. Однак, ця перевага забезпечується тільки якщо N досить велике і якщо варіація скінченна.

Для одновимірного інтегрування, квадратурні методи, такі як методи трапецій, Сімпсона, або формула Ньютона–Котеса , відомі як ефективні, якщо функція є гладкою. Ці підходи можуть бути також використані для багатовимірної інтеграції, повторюючи одновимірні інтегрування за кількома вимірами. Однак кількість обчислень функції зростає експоненціально з числом вимірів s. Отже, щоб подолати це прокляття розмірності слід використовувати для багатовимірних інтегралів дещо інший метод. Стандартний метод Монте-Карло часто використовується, коли квадратурні методи складно або дорого реалізувати.[2] Методи Монте-Карло і квазі-Монте Карло точні і відносно швидкі, коли розмірність сягає 300 і вище.[3]

Мороков і Кафлиша вивчали продуктивність методів Монте-Карло і квазі-Монте Карло у інтегруванні. У статті, Халтон, Соболь, і Фор послідовності для квазі-Монте-Карло порівнюють із стандартним методом Монте-Карло з використанням псевдовипадкових послідовностей. Вони виявили, що метод з  Халтон послідовністю найбільш ефективний для розмірностей до приблизно 6; метод з Соболевими послідовністями працює краще для більш високих розмірностей; і метод з Фор послідовностями, хоч і є гіршим за вказані дві інші послідновності, досі працює краще, ніж псевдовипадкові послідовності.

Однак, Мороков і Кафлиша навели приклади, де перевага методу квазі-Монте-Карло менша, ніж очікувалося теоретично. Ще, в прикладах вивчені Мороковим і Кафлишею, метод квазі-Монте-Карло  не дає більш точний результат, ніж метод Монте-Карло з однаковою кількістю очок. Мороков і Кафлиша зауважили, що перевага методу квазі-Монте-Карло є значною, якщо під-інтегральний вираз є гладкою функцією, і кількість вимірів s інтегралу мала.

Лем'є виділив недоліки методу квазі-Монте-Карло:[4]

• Для того щоб оцінка ${\displaystyle O\left({\frac {(\log N)^{s}}{N}}\right)}$ була меншою за ${\displaystyle O\left({\frac {1}{\sqrt {N}}}\right)}$,${\displaystyle s}$ повинен бути достатньо малим і ${\displaystyle N}$ повинен бути великим (наприклад, ${\displaystyle N>2^{s}}$).
• Для багатьох функцій, що виникають на практиці, ${\displaystyle V(f)=\infty }$.
• Ми знаємо тільки верхню межу помилки (тобто ε ≤ V(f) D_N), і важко обчислити ${\displaystyle D_{N}^{*}}$ і ${\displaystyle V(f)}$.

Для того, щоб подолати деякі з цих недоліків, ми можемо використати рандомізований метод квазі-Монте-Карло .

Оскільки послідовності з низьким рівнем розбіжності не випадкові, а детерміновані, квазі-Монте-Карло метод може розглядатися як детермінований алгоритм або дерандомізований алгоритм. В даному випадку, у нас є тільки межа (наприклад, ε ≤ (Ф) Г_Н) похибки, і похибку важко оцінити. Для того, щоб уможливити аналіз та оцінку дисперсії, ми можемо рандомізувати метод (див. рандомізації для загального випадку). В результаті отримаємо рандомізований метод квазі-Монте-Карло, який також можна розглядати як зменшення варіації для стандартного методу Монте-Карло.[5] Серед декількох методів, найпростіша процедура перетворень - це через випадкові зміщення. Нехай {х₁,...,х_п} точка встановлена на послідовності з низькою розбіжністю. Оберемо випадковий s-вимірний  вектор U і змішаємо його з {х₁,...,х_п}. Тобто, для кожного x_J, створюємо

${\displaystyle y_{j}=x_{j}+U{\pmod {1}}}$

і використовуємо послідовність ${\displaystyle (y_{j})}$ замість ${\displaystyle (x_{j})}$. Якщо ми маємо R повторів за методом Монте-Карло, оберемо випадковий s-вимірний вектор U для кожної реплікації. Рандомізація дозволяє дати оцінку дисперсії, при цьому використовуючи квазі-випадкові послідовності. Порівняно з чисто методом квазі-Монте Карло, кількість зразків квазі-випадкової послідовності буде ділитись на R, рівноцінну за обчислювальних витрат, що зменшує теоретичну швидкість збіжності. У порівнянні зі стандартним методом Монте-Карло, дисперсії та обчислення швидкості є дещо кращі, ніж експериментальні результати у Туффина (2008) [6]

• Метод Монте-Карло
  

1. Søren Asmussen and Peter W. Glynn, Stochastic Simulation: Algorithms and Analysis, Springer, 2007, 476 pages
2. William J. Morokoff and Russel E. Caflisch, Quasi-Monte Carlo integration, J. Comput. Phys. 122 (1995), no. 2, 218--230. (At CiteSeer: )
3. Rudolf Schürer, A comparison between (quasi-)Monte Carlo and cubature rule based methods for solving high-dimensional integration problems, Mathematics and Computers in Simulation, Volume 62, Issues 3–6, 3 March 2003, 509–517
4. Christiane Lemieux, Monte Carlo and Quasi-Monte Carlo Sampling, Springer, 2009, ISBN 978-1441926760
5. Moshe Dror, Pierre L’Ecuyer and Ferenc Szidarovszky, Modeling Uncertainty: An Examination of Stochastic Theory, Methods, and Applications, Springer 2002, pp. 419-474
6. Bruno Tuffin, Randomization of Quasi-Monte Carlo Methods for Error Estimation: Survey and Normal Approximation, Monte Carlo Methods and Applications mcma.

• 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 (At CiteSeer:)
• 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

• The MCQMC Wiki page contains a lot of free online material on Monte Carlo and quasi-Monte Carlo methods
• A very intuitive and comprehensive introduction to Quasi-Monte Carlo methods

Статтю перекладено за ініціативи студентів факультету прикладної математики та інформатики ЛНУ ім. Франка http://www.lnu.edu.ua

Лінки не містять посилання на інші статті, допущено орфографічні помилки.