Пред.
След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике ГЛАВА IX. СПЕЦИАЛИЗИРОВАННЫЕ МАШИНЫ ДЛЯ РЕШЕНИЯ ЗАДАЧ ПО МЕТОДУ МОНТЕ-КАРЛО§ 31. Особенности краевых задач, упрощающие машинную реализациюРазвитие современных быстродействующих вычислительных машин дает возможность решения широкого класса новых задач. Следствием этого явилось бурное развитие различных вычислительных методов, приспособленных к реализации с помощью вычислительных машин. Одним из таких методов, широкое применение которого стало возможным только при развитии вычислительной техники, является метод Монте-Карло. Более того, этот метод обладает целым рядом особенностей, делающим его особенно удобным при использовании вычислительных машин. Это относится как к вычислениям на универсальных машинах, так и к возможности конструирования специализированных вычислительных машин для решения отдельных задач по методу Монте-Карло. Эти особенности сводятся в основном к следующему: сравнительная простота и однородность последовательности операций (в частности, повторение большого числа однородных испытаний), использование сравнительно малого числа промежуточных результатов, небольшая точность результата, позволяющая оперировать с числами малой разрядности. Эти черты особенно ярко проявляются при использовании специализированных машин, предназначенных для решения того или иного класса задач по методу Монте-Карло. В самом деле, такие машины можно проектировать на малую разрядность чисел, использовать в них оперативную память минимального размера и рассчитывать их на короткие и простые циклические программы, т. е. иметь небольшую память для программ, простой состав команд и простую систему управления. Надо здесь же сказать о другой стороне вопроса. Существуют задачи, решение которых вообще возможно только по методу Монте-Карло. Для этих задач специализированная машина оказывается весьма сложной. Преимущество ее по сравнению с универсальной машиной, сконструированной из аналогичных элементов (т. е. имеющей те же скорости выполнения простейших операций), состоит в существенном увеличении производительности при решении определенного класса задач. Конструирование таких машин может оказаться целесообразным при решении трудоемких задач квантовой физики, формулируемых с помощью сложных континуальных интегралов.
Рис. 12. Рассмотрим примеры специализированных машин простой структуры, предназначенных для решения некоторых важных вычислительных задач. Рассмотрим алгоритм решения задачи Дирихле для уравнения эллиптического типа, описанный в главе V. На рис. 12 показана схема решения задачи Дирихле для уравнения эллиптического типа (с переменными коэффициентами). Регистр координат РК содержит координаты начального положения частицы. Эти координаты поступают в накапливающий сумматор 2, где они складываются с числами сумматора каждый раз подаются на схему совпадения Эта схема существенно упрощается, если рассматривать решение аналогичной задачи для уравнения Лапласа. В этом случае отсутствует поток информации из сумматора 2 в датчик случайных чисел Рассмотрим теперь соображения о структуре специализированной машины, предназначенной для решения краевой задачи для уравнения Лапласа в многослойной области со специальными краевыми условиями на границе. Задача сводится к нахождению решения двумерного уравнения Лапласа
в полуплоскости
Решение ищется лишь в одной дочке на оси На границе полуплоскости нормальная производная обращается в нуль
Поэтому можно решать ту же задачу для всей плоскости, полагая для отрицательных
Функция Эти цифры нам понадобятся при оценке времени решения. Точность решения должна иметь порядок нескольких процентов. Большая точность в задачах такого рода бессмысленна. Опишем случайный процесс, который надлежит реализовать для решения задачи по методу Монте-Карло. Для того чтобы выразить особенность в нуле, надо окружить начало координат контуром С, на котором положить значение функции
Таким образом, задача сводится к отысканию функции количество внутренних узлов решетки. Вместо функции
Рис. 13. Эта функция должна удовлетворять следующим условиям: а) в граничных узлах решетки б) для внутренних узлов решетки Р иглеет место равенство
где в) если узел Р принадлежит прямой
Последнее условие получается, если соответствующее равенство (9.2) заменить конечноразностным соотношением
и выразить отсюда
Рис. 14. Предположим теперь, что ищется значение функции а) в начальный момент точка б) если в данный момент точка в) если точка г) если точка попадет в левую соседнюю точку Р и с вероятностью Можно показать, что с вероятностью единица за конечное число шагов точка Теперь рассмотрим случайную величину Поэтому в силу единственности решения задачи математическое ожидание случайной величины Отсюда возникает способ решения задачи по методу Монте-Карло, состоящий в следующем. Моделируется описанный процесс случайного блуждания. Именно, берутся координаты точки Для реализации случайного процесса нужно иметь запас случайных чисел. Удобнее всего в данном случае иметь дело со случайными числами, равномерно распределенными на отрезке (0,1). Тогда переход в соседний узел к внутреннему узлу может быть осуществлен путем выбора случайного числа
и если оно выполнено, то точка Одно из наиболее важных обстоятельств при решении связано с тем, что точность зависит от количества реализаций случайного процесса. Полное время решения можно выразить так:
где Для оценки
так как значения Поскольку вблизи внутреннего контура значения
отсюда
для чего достаточно, чтобы было
Величина Теперь оценим множитель
где
Наконец, для граничных точек
Подставляя в
или
Для всех граничных узлов
Для точек на особой линии
или что на прохождение особой линии не тратится дополнительного времени. Это можно сделать, так как количество узлов на особых линиях, пройденных точкой
откуда
Это в свою очередь даст
Соотношения (9.12) и (9.16) вместе с граничными условиями (9.13) представляют собой конечноразностные уравнения для дифференциального уравнения вида
с условиями на особых линиях вида
и с граничными условиями Так как для более широкой чем
Для простоты рассмотрим случай, когда значения
а на границе имеем Так как решение уравнения Лапласа (9.18) принимает максимальное значение на границе, то для всех внутренних точек
Величина
Сопоставляя оценку (9.19) с ранее полученной оценкой (9.07), имеем для полного времени решения
Если принять время на один шаг (что, как мы увидим, соответствует времени на две-три арифметические операции над малоразрядными числами)
В действительности же эта оценка сильно завышена. В самом деле, множитель
|
1 |
Оглавление
|