Метод квазі-Монте-Карло () — метод чисельного інтегрування та розв'язування деяких інших задач з використанням послідовностей з низьким рівнем невідповідності (так-звані квазі-випадкові послідовності або суб-випадкові послідовності). Це на противагу звичайному методу Монте-Карло, який заснований на послідовності псевдовипадкових чисел.
На відміну від випадкових вибірок, квазі-послідовності забезпечують більш рівномірне заповнення області визначення інтеграла, що дає змогу суттєво прискорити збіжність методу.
Методи Монте-Карло і квазі-Монте-Карло викладені аналогічним чином. Проблема полягає в тому, щоб апроксимувати інтеграл від функції f як середнє значення функції, обчисленої в наборі точок х1, …, хп:
Оскільки ми інтегруємо по х-вимірному одиничному кубі, кожен хi є вектором s елементів. Різниця між методами квазі-Монте-Карло і Монте-Карло — це спосіб вибору хi. Квазі-Монте-Карло використовує послідовності з низьким рівнем невідповідності, такі як послідовності Халтон, Соболеві послідовності, або послідовності Фора (з англ. Faure), в той час як метод Монте-Карло використовує псевдовипадкові послідовності. Перевага використання послідовностей з низьким рівнем невідповідності — швидкість збіжності. Метод квазі-Монте-Карло має оцінку збіжності О(1/n), тоді як у випадку методу Монте-Карло вона становить О(N−0.5).Søren Asmussen and Peter W. Glynn, Stochastic Simulation: Algorithms and Analysis, Springer, 2007, 476 pages
Метод квазі-Монте-Карло останнім часом став популярним в області математичних фінансів і фінансових обчислень. В цих областях багатовимірні числові інтеграли, де значення інтеграла повинне бути оцінене в межах порогового значення ε, трапляються часто. Методи Монте-Карло і квазі-Монте-Карло корисні в таких випадках.
Огляд Метод квазі-Монте-Карло — чисельний метод для обчислення багатовимірних інтегралів, у якому точки інтегрування вибирають не випадково, а як детерміновану множину з високою рівномірністю заповнення (послідовність низької розбіжності).
Після зведення задачі до інтеграла на одиничному гіперкубі
оцінку будують як середнє значення:
де — точки низькорозбіжної послідовності (наприклад, Соболя, Гальтона тощо).
На відміну від стандартного методу Монте-Карло, QMC використовує «квазі-випадкові» (детерміновані) точки, що часто дає меншу похибку для багатьох практичних інтегралів за тієї самої кількості викликів .
Послідовності низької розбіжності
Розбіжність (discrepancy) і «рівномірність» Якість QMC-точок описують через розбіжність (), яка вимірює відхилення емпіричного розподілу точок від рівномірного у .
Поширена характеристика — зіркова розбіжність , що контролює найбільше відхилення частки точок у прямокутниках вигляду від їхнього об'єму .
Приклади побудов До класичних послідовностей/множин низької розбіжності належать: послідовність Гальтона (); послідовність Соболя () та її реалізації для високих розмірностей; послідовності Фора/Нідеррайтера та інші цифрові (t,m,s)-сітки й (t,s)-послідовності (); ґраткові правила () для інтегрування у функціональних просторах зі «зваженою» важливістю координат.
Теорія збіжності і оцінка похибки
Порівняння з Монте-Карло Для стандартного Монте-Карло середньоквадратична похибка типово спадає як і практично не залежить від розмірності (за умови скінченної дисперсії).
Для QMC існує класична оцінка похибки через нерівність Коксма—Главки (Koksma–Hlawka):
де — варіація інтегранда у сенсі Гарді—Краузе (Hardy–Krause).
Для багатьох конструкцій низької розбіжності відомо, що
тобто теоретично можливе зближення порядку приблизно для функцій з обмеженою варіацією.
Практичні застереження Фактор і вимога обмеженої варіації показують, що оцінки QMC у «гіршому випадку» швидко погіршуються зі зростанням . На практиці QMC найчастіше ефективний тоді, коли інтегранд має низьку ефективну розмірність або сильну анізотропію важливості координат (наприклад, після відповідного перетворення змінних).
Рандомізований квазі-Монте-Карло (RQMC) Детермінований QMC не дає «природної» оцінки статистичної похибки на кшталт довірчого інтервалу. Щоб поєднати рівномірність QMC з можливістю оцінювати похибку, застосовують рандомізований QMC ().
Випадковий зсув (Cranley–Patterson) Один із базових прийомів: випадковий зсув за модулем 1:
де . Повторюючи рандомізацію разів, можна оцінити дисперсію/стандартну похибку за вибіркою з незалежних оцінок.
Скремблювання (Owen scrambling) Для цифрових сіток/послідовностей (зокрема Соболя) застосовують скремблювання Овена — рандомізацію, що зберігає рівномірність і часто суттєво зменшує дисперсію порівняно з MC.
Переваги Порівняно з (псевдо)випадковим Монте-Карло, QMC/RQMC часто мають такі переваги: Швидше зближення для багатьох гладких інтеграндів і задач з низькою ефективною розмірністю. Краще «покриття» простору: точки менш схильні утворювати кластери й великі порожні області. Відтворюваність (для детермінованого QMC) та стабільніша залежність результату від . Сумісність з прийомами зменшення дисперсії (перенумерація змінних, перетворення Броунівського мосту, стратифікації тощо). Для RQMC можна отримувати оцінку похибки за повторними рандомізаціями, як у MC.
Застосування Методи QMC/RQMC застосовують у задачах, де потрібно багаторазово оцінювати багатовимірні інтеграли або математичні сподівання.
Фінансова математика (оцінювання похідних інструментів, моделі з багатьма часовими кроками) — одна з найвідоміших областей практичного успіху QMC, зокрема після зменшення ефективної розмірності (наприклад, «Броунівський міст»). Статистичне моделювання та байєсівські методи (як частина або альтернатива стандартним MC-процедурам у деяких підзадачах). Комп'ютерна графіка/рендеринг: використання низькорозбіжних вибірок для інтегрування освітлення (image synthesis).
Приклад Розглянемо інтеграл у двох вимірах:
Для QMC-оцінки беремо точок з послідовності низької розбіжності (наприклад, Соболя) й обчислюємо
Щоб отримати оцінку похибки, можна використати RQMC (наприклад, випадковий зсув або скремблювання) та виконати незалежних рандомізацій, після чого оцінити стандартну похибку за вибірковою дисперсією результатів.
Оцінка похибки апроксимації методу квазі-Монте-Карло Апроксимаційна похибка методу квазі-Монте-Карло обмежена значенням, пропорційним невідповідності комплекту х1, …, хn. Зокрема, з нерівності Koksma-Hlawka маємо, що похибка
є обмеженою
,
де V(F) є варіацією Харді-Краузе для функції f (див. Morokoff і Кафлиш (1995) для детального визначення). Dn — це так звана головна розбіжність набору (х1,…,xn) і визначається як
,
де Q — прямокутна [0,1]s фігура зі сторонами, паралельними осям координат. Нерівність може бути використана, щоб показати, що похибка апроксимації методом квазі-Монте-Карло метод рівна , у той час як метод Монте-Карло має імовірнісну похибку . Хоча ми можемо тільки констатувати верхню межу похибки апроксимації, збіжність розрахунку методу квазі-Монте-Карло на практиці, як правило, набагато швидша за його теоретичну межу. Отже, в загальному випадку, точність методу квазі-Монте-Карло збільшується швидше, ніж збіжність методу Монте-Карло. Однак, ця перевага забезпечується тільки якщо N досить велике і якщо варіація скінченна.
Методи Монте-Карло та Квазі-Монте-Карло для багатовимірних інтегрувань Для одновимірного інтегрування, квадратурні методи, такі як методи трапецій, Сімпсона, або формула Ньютона–Котеса, відомі як ефективні, якщо функція є гладкою. Ці підходи можуть бути також використані для багатовимірної інтеграції, повторюючи одновимірні інтегрування за кількома вимірами. Однак кількість обчислень функції зростає експоненціально з числом вимірів s. Отже, щоб подолати це прокляття розмірності слід використовувати для багатовимірних інтегралів дещо інший метод. Стандартний метод Монте-Карло часто використовується, коли квадратурні методи складно або дорого реалізувати.William J. Morokoff and Russel E. Caflisch, Quasi-Monte Carlo integration, J. Comput. Phys. 122 (1995), no. 2, 218—230. (At CiteSeer: ) Методи Монте-Карло і квазі-Монте-Карло точні і відносно швидкі, коли розмірність сягає 300 і вище.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
Мороков і Кафлиша вивчали продуктивність методів Монте-Карло і квазі-Монте-Карло у інтегруванні. У статті, Халтон, Соболь, і Фор послідовності для квазі-Монте-Карло порівнюють із стандартним методом Монте-Карло з використанням псевдовипадкових послідовностей. Вони виявили, що метод з Халтон послідовністю найбільш ефективний для розмірностей до приблизно 6; метод з Соболевими послідовністями працює краще для більш високих розмірностей; і метод з Фор послідовностями, хоч і є гіршим за вказані дві інші послідновності, досі працює краще, ніж псевдовипадкові послідовності.
Однак, Мороков і Кафлиша навели приклади, де перевага методу квазі-Монте-Карло менша, ніж очікувалося теоретично. Ще, в прикладах вивчені Мороковим і Кафлишею, метод квазі-Монте-Карло не дає більш точний результат, ніж метод Монте-Карло з однаковою кількістю очок. Мороков і Кафлиша зауважили, що перевага методу квазі-Монте-Карло є значною, якщо підінтегральний вираз є гладкою функцією, і кількість вимірів s інтеграла мала.
Недоліки методу квазі-Монте-Карло Лем'є виділив недоліки методу квазі-Монте-Карло:Christiane Lemieux, Monte Carlo and Quasi-Monte Carlo Sampling, Springer, 2009,
Для того щоб оцінка була меншою за , повинне бути достатньо малим і повинне бути великим (наприклад, ). Для багатьох функцій, що виникають на практиці, . Ми знаємо тільки верхню межу похибки (тобто ε ≤ V(f) DN), і важко обчислити і .
Для того, щоб подолати деякі з цих недоліків, можна використати рандомізований метод квазі-Монте-Карло.
Рандомізування методу квазі-Монте-Карло Оскільки послідовності з низьким рівнем розбіжності не випадкові, а детерміновані, квазі-Монте-Карло метод може розглядатися як детермінований алгоритм або дерандомізований алгоритм. В даному випадку, у нас є тільки межа (наприклад, ε ≤ (Ф) ГН) похибки, і похибку важко оцінити. Для того, щоб уможливити аналіз та оцінку дисперсії, ми можемо рандомізувати метод (див. рандомізації для загального випадку). В результаті отримаємо рандомізований метод квазі-Монте-Карло, який також можна розглядати як зменшення варіації для стандартного методу Монте-Карло.Moshe Dror, Pierre L'Ecuyer and Ferenc Szidarovszky, Modeling Uncertainty: An Examination of Stochastic Theory, Methods, and Applications, Springer 2002, pp. 419—474 Серед декількох методів, найпростіша процедура перетворень — це через випадкові зміщення. Нехай {х1,…,хп} точка встановлена на послідовності з низькою розбіжністю. Оберемо випадковий s-вимірний вектор U і змішаємо його з {х1,…,хп}. Тобто, для кожного xJ, створюємо
і використовуємо послідовність замість . Якщо ми маємо R повторів за методом Монте-Карло, оберемо випадковий s-вимірний вектор U для кожної реплікації. Рандомізація дозволяє дати оцінку дисперсії, при цьому використовуючи квазі-випадкові послідовності. Порівняно з чисто методом квазі-Монте-Карло, кількість зразків квазі-випадкової послідовності буде ділитись на R, рівноцінну за обчислювальних витрат, що зменшує теоретичну швидкість збіжності. У порівнянні зі стандартним методом Монте-Карло, дисперсії та обчислення швидкості є дещо кращі, ніж експериментальні результати у Туффіна (2008)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.