ГЛАВА IX. СПЕЦИАЛИЗИРОВАННЫЕ МАШИНЫ ДЛЯ РЕШЕНИЯ ЗАДАЧ ПО МЕТОДУ МОНТЕ-КАРЛО

§ 31. Особенности краевых задач, упрощающие машинную реализацию

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

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

Эти черты особенно ярко проявляются при использовании специализированных машин, предназначенных для решения того или иного класса задач по методу

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

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

Рис. 12.

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

Рассмотрим алгоритм решения задачи Дирихле для уравнения эллиптического типа, описанный в главе V. На рис. 12 показана схема решения задачи Дирихле для уравнения эллиптического типа (с переменными коэффициентами).

Регистр координат РК содержит координаты начального положения частицы. Эти координаты поступают в накапливающий сумматор 2, где они складываются с числами поступающими из датчика случайных чисел ДСЧ. Вероятности, с которыми выдаются на сумматор значения ±1, зависят, как это указано на схеме, от числа, стрящего в сумматоре. Координаты частицы из

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

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

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

Задача сводится к нахождению решения двумерного уравнения Лапласа

в полуплоскости удовлетворяющего условиям при при На линиях раздела вместо уравнения (9.1) имеют место равенства следующего типа (коэффициенты при производных считаются положительными):

Решение ищется лишь в одной дочке на оси или в, серии точек на этой оси.

На границе полуплоскости нормальная производная обращается в нуль

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

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

Эти цифры нам понадобятся при оценке времени решения. Точность решения должна иметь порядок нескольких процентов. Большая точность в задачах такого рода бессмысленна.

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

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

Таким образом, задача сводится к отысканию функции в прямоугольной с вырезом области (рис. 13), принимающей на границе области заданные значения и удовлетворяющей внутри области уравнению (9.1), а на линиях — условиям (9.2). Теперь будем считать, что в область О вписана квадратная решетка со стороной На оси находятся узлы решетки отточки до точки на оси — узлы в точках от до Размеры внутреннего контура границы можно взять примерно Линии содержат дополнительные узлы, не входящие в общее

количество внутренних узлов решетки. Вместо функции можно рассматривать функцию определенную в узлах решетки.

Рис. 13.

Эта функция должна удовлетворять следующим условиям:

а) в граничных узлах решетки принимает те же краевые значения, что и функция т. е. на внешнем контуре на внутреннем прямоугольнике С;

б) для внутренних узлов решетки Р иглеет место равенство

где — четыре узла, соседние с Р (рис. 14);

в) если узел Р принадлежит прямой (соответственно или ) то

Последнее условие получается, если соответствующее равенство (9.2) заменить конечноразностным соотношением

и выразить отсюда

Рис. 14.

Предположим теперь, что ищется значение функции в некотором внутреннем узле Рассмотрим «случайную» точку которая движется в дискретные моменты временй по следующим правилам:

а) в начальный момент точка находится в узле

б) если в данный момент точка находится в узле Р, то в следующий момент времени точка с одинаковой вероятностью, равной 74, может оказаться в любом из соседних узлов;

в) если точка попала на границу области то она там и останется;

г) если точка попала в узел принадлежащий одной из особых линий (соответственно ) то она с вероятностью

попадет в левую соседнюю точку Р и с вероятностью попадет в следующий момент в правую соседнюю точку Р.

Можно показать, что с вероятностью единица за конечное число шагов точка попадет на границу области, и блуждание заканчивается.

Теперь рассмотрим случайную величину равную значению в том граничном узле, куда в конце концов попадает точка вышедшая из в процессе случайного блуждания. Аналогично тому, как это сделано для обычной задачи Дирихле, можно показать, что математическое ожидание этой величины удовлетворяет для внутренних узлов решетки уравнению (9.3), для узлов на особых линиях—Соотношениям типа (9.4) и принимает на границе области те же значения, что и искомая функция

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

Отсюда возникает способ решения задачи по методу Монте-Карло, состоящий в следующем. Моделируется описанный процесс случайного блуждания. Именно, берутся координаты исходного узла и с вероятностью выбирается один из четырех векторов или который и прибавляется к вектору Таким образом, получаются координаты узла, в который точка попадает в следующий момент времени. Этот процесс случайного изменения одной из координат

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

Для реализации случайного процесса нужно иметь запас случайных чисел. Удобнее всего в данном случае иметь дело со случайными числами, равномерно распределенными на отрезке (0,1). Тогда переход в соседний узел к внутреннему узлу может быть осуществлен путем выбора случайного числа указанного вида. Теперь, если мы из узла переходим в узел то в узел и, наконец, если то точка переходит в узел . Если узел принадлежал особой линии то, выбирая мы определяем, имеет ли место неравенство

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

Одно из наиболее важных обстоятельств при решении связано с тем, что точность зависит от количества

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

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

Для оценки нужно оценить дисперсию Известно, что Пусть со — вероятность того, что точка вышедшая из узла закончит блуждание на внутреннем контуре Г. Тогда если максимальное значение на контуре Г равно и то

так как значения на внешнем контуре равны нулю.

Поскольку вблизи внутреннего контура значения имеют тот же порядок, что и им, то ошибку в определении можно оценивать в долях величины им. Если потребовать, чтобы ошибка в определении не превосходила с вероятностью, большей 0,99, то из неравенства (9.5) получаем соотношение

отсюда

для чего достаточно, чтобы было

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

Теперь оценим множитель в равенстве (9.6). Обозначим вероятность того, что процесс случайного блуждания, начатый в узле Р, закончится ровно через шагов. Нетрудно видеть, что для внутреннего узла Р

где соседние узлы. Для точки рис. 14) на особой линии (соответственно ) имеем:

Наконец, для граничных точек Математическое ожидание количества шагов, необходимых для окончания блуждания точки, вышедшей в начальный момент из узла Р,

Подставляя в выражение для из (9.8), имеем для внутренних узлов Р:

или

Для всех граничных узлов

Для точек на особой линии (и аналогично на других особых линиях) можно из (9.9) получить соотношения

или Чтобы можно было свести вычисление к классической задаче, примем,

что на прохождение особой линии не тратится дополнительного времени. Это можно сделать, так как количество узлов на особых линиях, пройденных точкой в среднем мало по сравнению с полным количеством проходимых узлов. Тогда равенство (9.9) заменится на

откуда

Это в свою очередь даст

Соотношения (9.12) и (9.16) вместе с граничными условиями (9.13) представляют собой конечноразностные уравнения для дифференциального уравнения вида

с условиями на особых линиях вида

и с граничными условиями

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

Для простоты рассмотрим случай, когда значения равны, т. е. классическую задачу Пуассона. Положим и подставим это выражение в (9.17). Получаем

а на границе имеем

Так как решение уравнения Лапласа (9.18) принимает максимальное значение на границе, то для всех внутренних точек

Величина достигает максимального значения в начале координат и при Поэтому

Сопоставляя оценку (9.19) с ранее полученной оценкой (9.07), имеем для полного времени решения

Если принять время на один шаг (что, как мы увидим, соответствует времени на две-три арифметические операции над малоразрядными числами) сек., то получим, что в самом худшем случае

В действительности же эта оценка сильно завышена. В самом деле, множитель уменьшает время решения по крайней мере в два раза. Далее, величина становится в интересующей нас области примерно в полтора - два раза меньше. Наконец, точность решения в 0,01 им не является обязательной, а переход к точности хотя бы в 0,02 им уменьшает время решения вчетверо. Уже только за счет указанных факторов время решения оказывается порядка полутора часов. В общем можно считать, что, как правило, решение задачи для одного варианта будет составлять от 10 мин. до 1 часа.