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

Метод квазі-Монте-Карло (англ. Quasi-Monte Carlo Method) — метод чисельного інтегрування та розв'язування деяких інших задач з використанням послідовностей з низьким рівнем невідповідності (так-звані квазі-випадкові послідовності або суб-випадкові послідовності). Це на противагу звичайному методу Монте-Карло, який заснований на послідовності псевдовипадкових чисел.

[Псевдовипадкова послідовність]

[Соболева послідовність - послідовність із малою розбіжністю]

256 точок з джерела псевдовипадкових чисел, послідовність Хальтона та Соболева послідовність (Червоні=1,..,10, Сині=11,..,100, Зелені=101,..,256). Точки Соболевої послідовності є більш рівномірно розподіленими.

Методи Монте-Карло і квазі-Монте-Карло викладені аналогічним чином. Проблема полягає  в тому, щоб апроксимувати інтеграл від функції f як середнє значення функції, обчисленої в наборі точок х₁, …, х_п:

${\displaystyle \int _{[0,1]^{s}}f(u)\,{\rm {d}}u\approx {\frac {1}{N}}\,\sum _{i=1}^{N}f(x_{i}).}$

Оскільки ми інтегруємо по х-вимірному одиничному кубі, кожен х_i є вектором s елементів. Різниця між методами квазі-Монте-Карло і Монте-Карло — це спосіб вибору х_i.  Квазі-Монте-Карло використовує послідовності з низьким рівнем невідповідності, такі як послідовності Халтон, Соболеві послідовності, або послідовності Фора (з англ. Faure), в той час як метод Монте-Карло використовує псевдовипадкові послідовності. Перевага використання послідовностей з низьким рівнем невідповідності — швидкість збіжності. Метод квазі-Монте-Карло має оцінку збіжності  О(1/n), тоді як у випадку методу Монте-Карло вона становить О(N^−0.5).

Метод квазі-Монте-Карло останнім часом став популярним в області математичних фінансів і фінансових обчислень. В цих областях багатовимірні числові інтеграли, де значення інтегралу повинне бути оцінене в межах порогового значення ε, трапляються часто. Методи Монте-Карло і квазі-Монте-Карло корисні в таких випадках.

Оцінка похибки апроксимації методу квазі-Монте-Карло

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

${\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. Отже, щоб подолати це прокляття розмірності слід використовувати для багатовимірних інтегралів дещо інший метод. Стандартний метод Монте-Карло часто використовується, коли квадратурні методи складно або дорого реалізувати. Методи Монте-Карло і квазі-Монте-Карло точні і відносно швидкі, коли розмірність сягає 300 і вище.

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

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

Недоліку методу квазі-Монте-Карло

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

• Для того щоб оцінка ${\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)}$.

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

Рандомізування методу квазі-Монте-Карло

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

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

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

Див. також

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

Примітки

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: [1] [ 7 Січня 2008 у Wayback Machine.])
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,
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,
• Michael Drmota and Robert F. Tichy, Sequences, discrepancies and applications, Lecture Notes in Math., 1651, , Berlin, 1997,
• 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: [2] [ 15 Березня 2006 у Wayback Machine.])
• Harald Niederreiter. Random Number Generation and Quasi-Monte Carlo Methods. Society for Industrial and Applied Mathematics, 1992.
• 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,

Посилання

• The MCQMC Wiki page contains a lot of free online material on Monte Carlo and quasi-Monte Carlo methods [ 28 червня 2018 у Wayback Machine.]

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

Коментарі

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