9.5: Інтеграція Монте-Карло

Last updated

Oct 27, 2022
Save as PDF
- 9.4: Квадратури Гауса
- 10: Чисельне інтегрування ОДУ

$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$

$\newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$

$\newcommand{\id}{\mathrm{id}}$

$\newcommand{\Span}{\mathrm{span}}$

$\newcommand{\kernel}{\mathrm{null}\,}$

$\newcommand{\range}{\mathrm{range}\,}$

$\newcommand{\RealPart}{\mathrm{Re}}$

$\newcommand{\ImaginaryPart}{\mathrm{Im}}$

$\newcommand{\Argument}{\mathrm{Arg}}$

$\newcommand{\norm}[1]{\| #1 \|}$

$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$

$\newcommand{\Span}{\mathrm{span}}$

$\newcommand{\id}{\mathrm{id}}$

$\newcommand{\Span}{\mathrm{span}}$

$\newcommand{\kernel}{\mathrm{null}\,}$

$\newcommand{\range}{\mathrm{range}\,}$

$\newcommand{\RealPart}{\mathrm{Re}}$

$\newcommand{\ImaginaryPart}{\mathrm{Im}}$

$\newcommand{\Argument}{\mathrm{Arg}}$

$\newcommand{\norm}[1]{\| #1 \|}$

$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$

$\newcommand{\Span}{\mathrm{span}}$

Остаточна схема числового інтеграції, яку ми обговоримо, - інтеграція Монте-Карло, і вона концептуально повністю відрізняється від попередніх схем. Замість призначення набору точок дискретизації (або явно, як у правилах середньої точки/трапеції/Сімпсона, або за допомогою процедури машинної оптимізації, як у методі адаптивної квадратури), цей метод випадковим чином вибірки точок в області інтеграції. Якщо точки вибірки незалежні і їх досить велика кількість, інтеграл можна оцінити, взявши середньозважене ціле по точках вибірки.

Якщо бути точним, розглянемо 1D інтеграл над доменом $x \in [a,b]$ . Нехай кожна точка вибірки буде намальована незалежно від розподілу $p(x)$ . Це означає, що ймовірність нанесення зразка $x_{n}$ в діапазоні $x_n \in [x, x + dx]$ є $p(x) dx$ . Розподіл нормалізується, так що

$\int_a^b p(x) \; dx = 1.$

Візьмемо $N$ зразки і оцінимо цілісність в цих точках: це дає нам набір чисел $\{f(x_n)\}$ . Потім обчислюємо кількість

$\mathcal{I}^{\mathrm{mc}} = \frac{1}{N} \sum_{n=0}^{N-1} \frac{f(x_n)}{p(x_n)}.$

На відміну від оцінювачів, які ми раніше вивчали, $\mathcal{I}^{\mathrm{mc}}$ є випадковим числом (тому що $\{x_n\}$ базові величини всі випадкові). Що найважливіше, його середнє значення дорівнює потрібному інтегралу:

$\begin{align} \left\langle\mathcal{I}^{\mathrm{mc}}\right\rangle &= \frac{1}{N} \sum_{n=0}^{N-1} \left\langle \frac{f(x_n)}{p(x_n)}\right\rangle \\ & = \left\langle \frac{f(x_n)}{p(x_n)}\right\rangle \qquad\mathrm{for}\;\mathrm{each}\; n \\ & = \int_a^b p(x) \, \left[\frac{f(x)}{p(x)}\right]\, dx \\ & = \int_a^b f(x)\, dx \end{align}$

Для низьковимірних інтегралів зазвичай немає підстав використовувати метод інтеграції Монте-Карло. Це вимагає набагато більшої кількості зразків, щоб досягти рівня числової точності, порівнянної з іншими методами числового інтегрування. (Для 1D інтегралів інтеграція Монте-Карло зазвичай вимагає мільйонів зразків, тоді як правило Сімпсона вимагає лише сотні або тисячі точок дискретизації.) Однак інтеграція Монте-Карло перевершує схеми інтеграції на основі дискретизації, коли розмірність інтеграції стає надзвичайно великою. Такі інтеграли зустрічаються, наприклад, при квантово-механічних розрахунках за участю систем багатьох тіл, де розмірність гільбертового простору масштабується експоненціально з кількістю частинок.