WikiDer > Метод ходьбы по сферам

В математика, то метод прогулки по сферам (WoS) числовой вероятностный алгоритм, или же Метод Монте-Карло, используемый в основном для аппроксимации решений некоторых конкретных краевая задача за уравнения в частных производных (PDE).^[1][2] Метод WoS был впервые представлен Мервин Э. Мюллер в 1956 году решить Уравнение Лапласа,^[1] и с тех пор был распространен на другие проблемы.

Он полагается на вероятностную интерпретацию PDE и моделирует пути Броуновское движение (или для некоторых более общих вариантов, диффузионные процессы), выбирая только точки выхода из следующих друг за другом сфер, а не моделируя подробно путь процесса. Это часто делает его менее затратным, чем "сеточные" алгоритмы, и сегодня это один из наиболее широко используемых алгоритмов "без сетки" для генерации броуновских путей.

Неформальное описание

Позволять ${ displaystyle Omega}$ быть ограниченным домен в ${ Displaystyle mathbb {R} ^ {d}}$ с достаточно регулярной границей ${ displaystyle Gamma}$, позволять час быть функцией на ${ displaystyle Gamma}$, и разреши ${ displaystyle x}$ быть точкой внутри ${ displaystyle Omega}$.

Рассмотрим Задача Дирихле:

${ Displaystyle { begin {case} Delta u (x) = 0 & { mbox {if}} x in Omega u (x) = h (x) & { mbox {if}} x в Gamma. end {case}}}$

Это легко показать^[а] что когда решение ${ displaystyle u}$ существует, для ${ displaystyle x in Omega}$:

${ Displaystyle и (х) = mathbb {E} _ {x} [час (W _ { tau})]}$

куда W это d-размерный Винеровский процесс, математическое ожидание берется условно на {W₀ = Икс}, и τ время первого выхода из Ω.

Чтобы вычислить решение с использованием этой формулы, нам нужно только смоделировать первую точку выхода независимых броуновских путей, поскольку закон больших чисел:

${ displaystyle mathbb {E} _ {x} [h (W _ { tau})] sim { frac {1} {n}} sum _ {i = 1} ^ {n} h (W_ { tau} ^ {i})}$

Метод WoS обеспечивает эффективный способ выборки первой точки выхода броуновского движения из области, отмечая, что для любого (d − 1)-сфера сосредоточена на Икс, первая точка выхода из W вне сферы имеет равномерное распределение по ее поверхности. Таким образом, он начинается с Икс⁽⁰⁾ равно Икс, и рисует самую большую сферу ${ displaystyle { mathcal {S}} _ {0}}$ сосредоточен на Икс⁽⁰⁾ и содержится внутри домена. Первая точка выхода Икс⁽¹⁾ из ${ displaystyle { mathcal {S}} _ {0}}$ равномерно распределяется по его поверхности. Повторяя этот шаг индуктивно, WoS выдает последовательность (Икс^(п)) позиций броуновского движения.

Согласно интуиции, процесс сведется к первой точке выхода из области. Однако этот алгоритм почти наверняка требует бесконечного количества шагов для завершения. Для вычислительной реализации процесс обычно останавливается, когда он подходит достаточно близко к границе, и возвращает проекцию процесса на границе. Эту процедуру иногда называют введением ${ displaystyle varepsilon}$-оболочка, или ${ displaystyle varepsilon}$-слой.^[4]

Формулировка метода

Иллюстрация запуска алгоритма прогулки по сферам в произвольной области ${ displaystyle Omega}$ с ${ displaystyle varepsilon}$-ракушка

выбирать ${ displaystyle varepsilon> 0}$. Используя те же обозначения, что и выше, алгоритм прогулки по сферам описывается следующим образом:

1. Инициализировать: ${ Displaystyle х ^ {(0)} = х}$
2. Пока ${ Displaystyle d (х ^ {(п)}, Gamma)> varepsilon}$:
   1. Набор ${ displaystyle r_ {n} = d (х ^ {(n)}, Gamma)}$.
   2. Образец ${ displaystyle gamma _ {n}}$ вектор, равномерно распределенный по единичной сфере, независимо от предыдущих.
   3. Набор ${ displaystyle x ^ {(n + 1)}: = x ^ {(n)} + r_ {n} gamma _ {n}}$
3. Когда ${ Displaystyle д (х ^ {(п)}, гамма) leq varepsilon}$:
4. ${ displaystyle x_ {f}: = p _ { Gamma} (x ^ {(n)})}$, ортогональная проекция ${ Displaystyle х ^ {(п)}}$ на ${ displaystyle Gamma}$
5. Возвращаться ${ displaystyle x_ {f}}$

Результат ${ displaystyle x_ {f}}$ оценка первой точки выхода из ${ displaystyle Omega}$ винеровского процесса, начиная с ${ displaystyle x}$в том смысле, что они имеют близкое распределение вероятностей (см. ниже комментарии к ошибке).

Комментарии и практические соображения

Радиус сфер

В некоторых случаях расстояние до границы может быть трудно вычислить, и в этом случае предпочтительнее заменить радиус сферы нижней границей этого расстояния. Затем необходимо убедиться, что радиус сфер остается достаточно большим, чтобы процесс достиг границы.^[1]

Смещение в методе и GFFP

Метод Walk-on-Spheres используется до тех пор, пока процесс не станет ${ displaystyle delta}$-Близко к границе. Затем сфера заменяется ее «пересечением» с границей области.

Поскольку это метод Монте-Карло, погрешность оценки может быть разложена на сумму предвзятость, а статистическая ошибка. Статистическая ошибка уменьшается за счет увеличения количества выбранных путей или использования уменьшение дисперсии методы.

WoS теоретически обеспечивает точное (или беспристрастное) моделирование траекторий броуновского движения. Однако, как здесь сформулировано, ${ displaystyle varepsilon}$-shell, введенный, чтобы гарантировать, что алгоритм завершается, также добавляет ошибку, обычно порядка ${ Displaystyle { mathcal {O}} ( varepsilon)}$.^[4] Эта ошибка была изучена, и ее можно избежать в некоторых геометриях, используя Функции Грина Метод первого прохода:^[5] можно изменить геометрию «сфер», когда они находятся достаточно близко к границе, так что вероятность достижения границы за один шаг становится положительной. Это требует знания функций Грина для конкретных областей. (смотрите также Гармоническая мера)

Когда это возможно, Функция Грина Метод первого прохода (GFFP) обычно предпочтительнее, так как он быстрее и точнее, чем классический WoS.^[4]

Сложность

Можно показать, что количество шагов, сделанных для того, чтобы процесс WoS достиг ${ displaystyle varepsilon}$-оболочка в порядке ${ Displaystyle { mathcal {O}} (| журнал ( varepsilon) |)}$.^[2] Следовательно, можно до некоторой степени повысить точность без значительного увеличения числа шагов.

Как это обычно бывает с методами Монте-Карло, этот алгоритм особенно хорошо работает, когда размерность больше, чем ${ displaystyle 3}$, и нужен только небольшой набор значений. Действительно, вычислительные затраты линейно возрастают с увеличением размера, тогда как стоимость методов, зависящих от сетки, увеличивается экспоненциально с увеличением размера.^[2]

Варианты, расширения

Этот метод широко изучен, обобщен и усовершенствован. Например, сейчас он широко используется для вычисления физических свойств материалов (таких как емкость, внутренняя электростатическая энергия молекул и др.). Некоторые известные расширения включают:

Эллиптические уравнения

Метод WoS может быть изменен для решения более общих задач. В частности, метод был обобщен для решения задач Дирихле для уравнений вида ${ displaystyle Delta u = cu + f}$ ^[6] (которые включают Пуассон и линеаризованный Пуассона-Больцмана уравнений) или для любых эллиптическое уравнение в частных производных с постоянными коэффициентами.^[7]

Также были разработаны более эффективные способы решения линеаризованного уравнения Пуассона – Больцмана, основанные на Фейнман-Кац представления решений.^[8]

Зависимость от времени

Опять же, в пределах достаточно регулярной границы можно использовать метод WoS для решения следующей проблемы:

${ displaystyle { begin {cases} partial _ {t} u (x, t) + { frac {1} {2}} Delta _ {x} u (x, t) = 0 & { mbox { if}} x in Omega { mbox {and}} t$

решение которого можно представить в виде:^[9]

${ Displaystyle и (х, т) = mathbb {E} _ {т, х} (час (X_ {Т клин тау}, Т клин тау))}$,

где ожидание принято условно от ${ displaystyle X_ {t} = x}$

Чтобы использовать WoS по этой формуле, необходимо выбрать время выхода из каждой нарисованной сферы, которая является независимой переменной. ${ displaystyle tau _ {0}}$ с преобразованием Лапласа (для сферы радиуса ${ displaystyle R}$):^[10]

${ displaystyle mathbb {E} ( exp (-s tau _ {0}))) = { frac {R { sqrt {2s}}} { sinh (R { sqrt {2s}}) }}}$

Общее время выхода из домена ${ Displaystyle тау}$ можно вычислить как сумму времен выхода из сфер. Процесс также должен быть остановлен, если он не покинул домен во время ${ displaystyle T}$.

Прочие расширения

Метод WoS был обобщен для оценки решения эллиптических уравнений в частных производных повсюду в области, а не в одной точке.^[11]

Метод WoS также был обобщен для вычисления времени срабатывания для процессов, отличных от броуновских движений. Например, время попадания Бесселевские процессы может быть вычислен с помощью алгоритма под названием «Прогулка по движущимся сферам».^[12] Эта проблема имеет приложения в финансовой математике.

Наконец, WoS может быть адаптирован для решения уравнений Пуассона и Пуассона – Больцмана с условиями потока на границе.^[13]

Смотрите также

• Формула Фейнмана – Каца
• Случайные процессы и краевые задачи
• Метод Эйлера – Маруямы пробовать пути общих диффузионных процессов

Примечания

Рекомендации

дальнейшее чтение

• Сабельфельд, Карл К. (1991). Методы Монте-Карло в краевых задачах. Берлин [и др.]: Springer-Verlag. ISBN 9783540530015.

внешняя ссылка

• Некоторые непрерывные методы Монте-Карло для задачи Дирихле Статья, в которой Марвин Эдгар Мюллер представил метод.
• Броуновское движение Петера Мёртерса и Юваля Переса. См. Главу 3.3 о гармонической мере, функциях Грина и точках выхода.