Пред.
След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике ВВЕДЕНИЕОсновные пути развития вычислительной математики в последние годы можно охарактеризовать следующими взаимосвязанными явлениями: широкое использование цифровых вычислительных машин высокой производительности, реализация вычислительных алгоритмов с большим объемом арифметических операций и разработка новых классов алгоритмов, приспособленных к реализации на цифровых вычислительных машинах. Метод статистических испытаний, известный в литературе также под названием метода Монте-Карло, дает возможность конструировать для ряда важных задач алгоритмы, хорошо приспособленные к реализации на цифровых вычислительных машинах. Настоящая книга посвящена описанию ряда алгоритмов, основанных на методе статистических испытаний, и изложению основных приемов реализации таких алгоритмов с помощью вычислительных машин. Основная идея метода статистических испытаний — связь между вероятностными характеристиками различных случайных процессов (вероятностями случайных событий или математическими ожиданиями случайных величин) и величинами, являющимися решениями задач математического анализа (значениями интегралов, решениями дифференциальных уравнений и т. п.). Первый нетривиальный пример такой связи это из вестное соотношение между процессом случайных блужданий и дифференциальным уравнением, описывающим изменение концентрации диффундирующего вещества, открытое в работах Эйнштейна и Смолуховского. Классическая ситуация состояла в том, что изучение случайного процесса считалось в какой-то мере исчерпывающим, если определение характеристик этого случайного процесса сводилось к решению аналитической задачи. При этом считалось, что решение аналитической задачи (независимо от его трудоемкости) составляет следующий независимый этап исследования. Однако существенное обстоятельство, на которое, по-видимому, впервые было обращено внимание в работе [31], состоит в том, что эту классическую ситуацию можно обратить. Именно, вместо решения аналитической задачи можно моделировать случайный процесс и использовать статистические оценки вероятностей или математических ожиданий для приближенного решения данной аналитической задачи. Таким образом, метод статистических испытаний состоит в использовании связи между вероятностными характеристиками и аналитическими вычислительными задачами. Оказывается, что вместо вычисления ряда сложных аналитических выражений можно экспериментально определить значения соответствующих вероятностей или математических ожиданий. Этот метод получил широкое развитие в связи с новыми возможностями, которые дают быстродействующие электронные цифровые вычислительные машины. Йсторически первым примером применения метода статистических испытаний является так называемая задача Бюффона. Пусть на плоскости изображена последовательность равноотстоящих параллельных прямых и на плоскость сверху бросается игла. Какова вероятность пересечения иглой одной из прямых? Оказывается, что эта вероятность равна
Можно ли отсюда определить число
где бросаний, при которых игла пересекала одну из прямых. Из соотношения (0.1) и определяется число Чтобы привести пример реальной вычислительной задачи, рассмотрим задачу вычисления интеграла
Будем считать, что значения функции Надо найти (рис. 1) площадь
Рис. 1. Нужно заметить, что ограничение на функцию Пусть в квадрат Эта точка Итак, пусть имеется какой-то способ получения независимых равномерных величин
Если это условие выполнено, то выбранная случайная точка Величина Выясним теперь, как оценивать точность метода статистических испытаний. Это очень важно для определения области применения последнего. Пусть моделируется событие Обозначим через
где Мы ограничиваемся схемой независимых испытаний. Частота появления события А равна и является величиной, распределенной почти по закону Гаусса с математическим ожиданием
и дисперсией
Поэтому с вероятностью 0,997 (при достаточно больших N) величина
Правая часть формулы (0.3) является оценкой для ошибки метода статистических испытаний при вычислении вероятности события Из формулы (0.3) видно, что уменьшение ошибки связано с увеличением числа испытаний, т. е. времени вычислений. Приравнивая правую часть (0.3) величине погрешности
т. е. увеличение точности, например, в десять раз приводит к стократному удлинению времени решения задачи. Поэтому метод статистических испытаний не может дать решение с очень большой точностью. В практических задачах метод статистических испытаний (если не применяются специальные приемы ускорения) дает точность порядка Как будет видно из дальнейшего, метод статистических испытаний хорошо приспособлен к многомерным задачам. Обычно эти задачи и не требуют больших точностей, поэтому отмеченный недостаток метода не столь существен, как это могло бы показаться с первого взгляда. Предположим теперь, что метод Монте-Карло состоит в моделировании случайной величины Пусть
также распределена почти по закону Гаусса. Ее параметры равны соответственно
Поэтому имеет место оценка (с надежностью 0,997)
Таким образом, и в этом случае время решения связано обратной квадратичной зависимостью с достигаемой точностью
При решении конкретных задач для оценки ошибки можно в правую часть (0.6) подставлять вместо теоретического значения
получаемую в процессе моделирования значений
Таким образом, точность, достигаемая в методе статистических испытаний, может быть хорошо оценена только в процессе решения. Этот факт аналогичен тому, что точность физического эксперимента может быть надежно определена только по результатам этого эксперимента. Необходимо отметить еще одну особенность метода Монте-Карло, состоящую в том, что оценка погрешности вычислений имеет вероятностный характер. При этом методе нельзя утверждать, что ошибка не превысит какого-либо значения. Можно только указать границы, за которые ошибка не выйдет с вероятностью, близкой к единице. В частности, в оценках (0.3) и (0.5) эта вероятность равнялась 0,997. При использовании электронных вычислительных машин в каком-то смысле сглаживается это принципиальное отличие метода Монте-Карло от остальных методов, так как в любом методе возникает вероятность ошибки из-за сбоя машины. Кроме того, значительная часть оценок погрешности, используемых в вычислительных методах, справедлива не для всех случаев, а, так сказать, для практически возможных случаев, т. е. в сущности имеет вероятностный смысл, хотя и более замаскированный. Общую схему вычислений по методу статистических испытаний можно рассматривать как реализацию некоторого марковского процесса. Рассмотрим марковский процесс с конечным числом состояний и дискретным временем. Такой процесс представляет систему (в дальнейшем обозначаемую нами через Пусть состояния
т. е.
Кроме того, для всякого не особого состояния существует положительная вероятность попасть через некоторое время в одно из особых состояний. Известно, что при этих условиях система системы Докажем последнее утверждение. По предположению, для каждого неособого состояния
Тогда вероятность того, что через
Отсюда следует, что среднее время «жизни» системы не превосходит величины
Излагаемая схема метода статистических испытаний может быть описана следующим образом. Пусть марковский процесс указанного выше вида находится в на: чальный момент в состоянии
Рассмотрим случайную величину
связанную с рассматриваемым марковским процессом и являющуюся функцией от истории процесса. Полученное значение этой случайной величины мы зафиксируем. После этого мы возвратим систему
будет мало отличаться от среднего значения Кроме изложенной выше, мыслима и другая схема метода статистических испытаний. Рассмотрим такой марковский процесс, в котором вероятность перехода системы Тогда (см. [8]) среднее арифметическое возникающих значений случайной величины
стремится при
Средним значением величины
Для некоторых задач, в частности для задачи блужданий с полным отражением на границе (гл. VII), искомая величина представима именно в виде математического ожидания в указанном только что смысле. Предыдущие рассмотрения показывают, что метод статистических испытаний применим для задач, связанных с марковскими процессами и требующих ограниченной точности решения. Ряд таких задач описан в настоящей книге. Эти задачи можно разделить (как и всякая классификация, это деление в большой степени является условным) на задачи, допускающие простую аналитическую формулировку, и на задачи, формулируемые в терминах случайных процессов. Для задач первого типа значительная часть трудностей заключается в формулировке теоретико - вероятностной аналогии. Для задач второго типа трудность состоит часто в переходе от исходного вероятностного процесса к аппроксимирующей его марковской цепи, допускающей удобную реализацию на вычислительной машине. Эта марковская цепь должна обладать не слишком большим количеством состояний (ограничение — объем машинной памяти) и не слишком большим средним временем перехода в особые состояния (ограничение — быстродействие машины). Примерами задач первого типа являются: решение систем линейных уравнений, решение краевых задач для эллиптических уравнений, решение задачи Коши с граничными условиями для параболических уравнений, нахождение собственных значений для эллиптических дифференциальных операторов, вычисление многомерных интегралов. Примерами задач второго типа являются задачи о рассеянии нейтронов, задача расчета атомных реакторов, задачи исследования процессов массового обслуживания, задачи исследования систем управления со случайными воздействиями на входах, задачи моделирования различных самообучаемых систем (такого рода задачи решались в применении к моделям биологических систем образования сложных навыков). Надо отметить, что область применения метода статистических испытаний может в дальнейшем существенно расширяться. Так, например, описываемая В данной книге модель случайных блужданий принципиально применима только к линейным дифференциальным уравнениям параболического и эллиптического типов. Изучение этой модели дозволило не только получить методы решения таких уравнений, но и результаты о существовании и характере этих решений. Очень естественно ожидать появления вероятностных схем, связанных с уравнениями более общих типов, в частности нелинейных, связанных с описанием непрерывных сред (уравнения газовой динамики, магнитодинамики и т. п.). Более того, быть может, ряд трудностей, связанных с изучением дифференциальных уравнений непрерывных сред (в частности, гидродинамики), обусловлен тем, что классический аппарат дифференциальных уравнений неадэкватно описывает физические явления. Таким образом, можно предполагать развитие такого прямого вероятностного способа описания непрерывных сред, который позволит и выполнять качественное исследование задачи, и строить достаточно хорошо аппроксимирующие процесс марковские цепи, допускающие удобную реализацию на существующих и перспективных вычислительных машинах. Возможно, в частности, что такого рода прямым способом описания явится при дальнейшем развитии метод так называемых континуальных интегралов [4], используемых при описании задач квантовой механики и статистической физики. Моделирование марковских цепей в вычислительных машинах приводит, как показано ниже, к необходимости оперирования в машине с так называемыми случайными числами. В главе I рассматриваются различные методы образования случайных чисел. Однако это изложение отнюдь не претендует на полноту, а ставит целью указать лишь основные используемые здесь приемы. В частности, в книге не рассматриваются развитые за последние годы полезные приемы образования систем псевдослучайных чисел, основанные на теоретико - числовых методах. Нам представляется, что основное в методе статистических испытаний — это совокупность приемов, позволяющих от реальной вычислительной задачи переходить к удобно реализуемой в вычислительной машине марковской цепи. В этом аспекте нам кажется, что метод статистических испытаний приобрел бы замкнутую форму, если бы были найдены общие приемы перехода от достаточно общего описания алгоритмов к конструкции аппроксимирующих марковских цепей, позволяющих установить возможность и эффективность такого перехода.
|
1 |
Оглавление
|