§ 21. Оценка времени решения краевой задачи

Определим, сколько всего понадобится операций на решение рассмотренной в § 20 краевой задачи.

Число операций определяется тем, сколько «пьяному» нужно пройти перекрестков, чтобы выйти на границу.

Пусть число пройденных узлов при блуждании равно Тогда время решения Т определится так:

где — время одного перехода в соседний узел, полное число блужданий, которое надо промоделировать, чтобы достичь нужной точности решения. Величина определяется из закона больших чисел обычным способом и равна

где — погрешность решения, - дисперсия величины берется по всем граничным узлам решетки.

Число узлов, проходимых «пьяным» за одно блуждание, есть тоже случайная величина. Поэтому сумма этих величин приближенно равна математическому ожиданию величины, умноженной на Таким образом, время решения равно

Среднее число шагов при блуждании зависит от формы решетки и от шага Оказывается, что число блужданий зависит только от линейных размеров решетки, если принять, как выше, Если — радиус области то как это показано в конце параграфа. Вообще говоря, время решения задачи имеет порядок

Точность решения зависит еще и от того, насколько мелкой выбрана решетка. Например, если мы хотим получить решение с точностью от максимального значения тогда и 108.

Если считать, что вычисления ведутся на электронной цифровой вычислительной машине, где один шаг можно выполнить за время 100 мксек, то полное время решения оказывается равным

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

Время вычисления значения в одном узле практически не зависит от размерности решетки. Если необходимо вычислить значения во всех узлах, то время решения возрастает. Но часто бывает вовсе не нужно находить значение функции во всех узлах, а лишь в некоторых критических узлах..

На этой задаче также проявляется основная особенность метода Монте-Карло — приспособленность к многомерным задачам.

Оценим теперь среднее время блуждания при решении задачи Дирихле. Обозначим через вероятность того, что процесс блуждания закончится через шагов, т. е. «пьяный» свалится в ров, пройдя ровно кварталов.

Попадание «пьяного» в ров из перекрестка равносильно тому, что «пьяный» попадет в ров из одного из соседних перекрестков пройдя при этом квартал. Следовательно, вероятность удовлетворяет соотношению

Математическое ожидание количества кварталов, пройденных «пьяным», равно

Подставим в правую часть (5.8) выражение (5.7) для Получаем

В правой части равенства (5.9) суммы в первой скобке равны а суммы во второй скобке равны каждая единице, так как выражают вероятность того, что «пьяный», пройдя конечное число кварталов, попадет в ров. Следовательно, из (5.9) получаем

Для граничных точек очевидно,

Уравнение (5.10) есть конечноразностное уравнение для уравнения Пуассона

Нетрудно проверить, что для решетки любой размерности математическое ожидание количества узлов, проходимых до выхода на границу, удовлетворяет конечноразностному уравнению Пуассона. Чтобы оценить мы фактически оценим решение уравнения (5.10) с граничными условиями (5.11) для решетки квадратной формы со стороной

Обозначим независимые переменные через и будем решать уравнение (5.10) в -мерном кубе

Совершим подстановку

Ясно, что

откуда

На границе максимальное значение и равно

Стало быть, всюду внутри области

Отсюда следует оценка

Таким образом, время блуждания допускает оценку, не зависящую от размерности решетки.