Пред.
След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике § 21. Оценка времени решения краевой задачиОпределим, сколько всего понадобится операций на решение рассмотренной в § 20 краевой задачи. Число операций определяется тем, сколько «пьяному» нужно пройти перекрестков, чтобы выйти на границу. Пусть число пройденных узлов при
где
где Число узлов, проходимых «пьяным» за одно блуждание, есть тоже случайная величина. Поэтому сумма этих величин приближенно равна математическому ожиданию величины, умноженной на
Среднее число шагов при блуждании
Точность решения зависит еще и от того, насколько мелкой выбрана решетка. Например, если мы хотим получить решение с точностью Если считать, что вычисления ведутся на электронной цифровой вычислительной машине, где один шаг можно выполнить за время 100 мксек, то полное время решения оказывается равным
Существенно также, что при решении нужно помнить малое число промежуточных результатов (только величины Время вычисления значения На этой задаче также проявляется основная особенность метода Монте-Карло — приспособленность к многомерным задачам. Оценим теперь среднее время блуждания при решении задачи Дирихле. Обозначим через Попадание «пьяного» в ров из перекрестка
Математическое ожидание количества кварталов, пройденных «пьяным», равно
Подставим в правую часть (5.8) выражение (5.7) для
В правой части равенства (5.9) суммы в первой скобке равны
Для граничных точек
Уравнение (5.10) есть конечноразностное уравнение для уравнения Пуассона
Нетрудно проверить, что для решетки любой размерности математическое ожидание количества узлов, проходимых до выхода на границу, удовлетворяет конечноразностному уравнению Пуассона. Чтобы оценить Обозначим независимые переменные через
Совершим подстановку
Ясно, что
откуда
На границе максимальное значение и равно
Стало быть, всюду внутри области
Отсюда следует оценка
Таким образом, время блуждания допускает оценку, не зависящую от размерности решетки.
|
1 |
Оглавление
|