Соболь И.М. Численные методы Монте-Карло (1973) (1186217), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

Основная причина этого — чисто техническая: внутренний накопитель всех современных ЭВМ сравн!ггельно мал н большая таблица туда не помещается; а обращение к внешним запоьншающим устройствам'сильно замедляет счет. Вторая причина — ограниченность объема существующих таблиц,— по-видимому, играет второстепенную роль: можно заготовить таблицу любого объема, если это по!Рсбустся. 1.4. Датчики случайных чисел. Генераторами или датчиками случайных величин называют различные технические устройства, вырабатывающие случайные величины.

Чаще всего для построения датчика используют «шумящие» радиоэлектронные приборы (диоды, тира- троны, газотропы и др.). Не вдаваясь в технические подробности, рассмотрим один из возможных способов построения датчика, вырабатывающего случайные двоичные цифры а. Нетрудно представить себе счетчик, который подсчитывает количество у флуктуаций напряжения шумящего Яф~М~4КФЯ дг л! Рас. 2.

прибора, превышаю!цих заданный уровень Е, за фиксированное время Л1 (рис. 2). Еще проще устроить счетчик, который выдавал бы число у (гпод 2), т. е. 0 при четном у и 1 прн нечетном у. Если вероятности появления 0 и 1 в таком процессе равны между собой, то можно считать, что устройс!во вырабатывзет случайную последовательность двоц шых цифр. [е получение случапных Велп'>ин нл эвм [Гл ! Если вероятность появления нуля отлична от половины Р[0) =)>Ф0,5, то можно ввести какую-нибудь схему стабилизации вероятности. Например, можно группировать цифры парами и выдавать 0 нрн получении пары 01 и 1 — при получении пары 10, а пары 00 и 11 просто опускать.

Так кан Р(01)=Р(!0)=>з11 — р), то в результате получим последовательное>ь нулей и единиц с равнымп вероятностями "), Обычно датчики случайных чисел содержат пт генераторов описанного тнпа, работающих независимо, так что датчиком выдается приближенное случайное число т=0, а! ... а„, записанное в форме т-разрядно!) двоичной дроби. Для случайных чисел отведена специальная ячейка в накопителе, и скорость генерирования их столь велика, что на кагкдом такте работы ЭВМ в этой ячейке получается новое случайное число.

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

Во-вторых, приходится содержать и эксплуатировать дополнительное устройство, которое требует ухода и регулярной проверки «качества» вырабатываемых чисел с помошью специальных тестов. Основные области применения датчиков — системы автоматического регулирования и аналоговые вычислительные машины, а не методы Монте-Карло. 1.5. Метод псевдослучайных чисел. Мы видели, что пригодность случайных чисел определяется в конечном счете не процессом их получения, а тем, удовлетворяют «) К со>калеки!о возможен также случай, когда вероятность р меняется во времени или зависит от предшествуьощих цифр, и тогда простые схемы стабилизации ье спасают положения.

«") Можно, конечно, запомнить все выработанные числа, но тогда мы фактически будем ясгользопать таблицу. 4 П три спосовд получшп!я слу')дпных Величин )7 лп они некоторым принятым тестам. Но в таком случае совершенно безразлично, как эти числа получены, оин могут быть да>хе сосчитаны по какой-нибудь формуле, лишь бы онн удовлетворяли тестам! Такая точка зрения иногда вызывает возражения, ибо, вычисляя числа по формуле, мы тем самым сразу отказываемся от их «случайности». Любопытно, что такого рода возражения чаще высказывают нематематики, хотя, казалось бы, математики должны более решительно протестовать против нестрогости.

Дело в том, ч!о ма!ематики лучше понимают, что слово «случайность», взятое выше в кавычки, использовано там не в математическом, а скорее в обыденном смысле. С точки зрения математика равномерно распределенная случайная величина т — зто абстрактное понятие; и только опыт может убедить пас в том, что какая-либо конкретнап последовательность чисел т!, тз, ..., т„ обладает и!Иересующими пас свойствами независимых случайных чисел т. Числа 7!, те, ..., Т, котоРые вычислЯютсЯ по какой- либо заданной формуле и могут быть использованы вместо случайных чисел при решении некоторых задач, называются псевдослучайными числами, Нередко счптзют, что тесты, прпведеячые ниже в $3, обеспечивзют возможность использования проверенных случайных пля псевдослучзйпых чисел в любых зздзчзх.

Это язлпшвпй оптимизм. В действительности каждый тест связзп с кзхпм-то достаточно шпрохям, яо ограниченным классом задач (см. гл. 7, $ 4), в прзвпльпее было бы говорить о таблицах, датчиках пзп псевдослучзйпых числах дзя определенных нлзссов задач «). Конкретная последовательность псевдослучайных чисел сходна с таблицей случайных чисел: ее можно один раз тщательно проверить и затем многократно применять; все числа легко воспроизводятся; н запас чисел в такой последовательности, как мы увидим позднее, тоже ограничен. Однако метод псевдослучайных чисел свободен от главного недостатка таблиц: существуют простые формулы для расчета псевдослучайных чисел, ') Любой реальный объект лишь приближенно описывается мвтемзт!~ческим понятием, в всегда можно указать задачи, в которых д«яязя математическая модель нспрягодяз. Например, хак бы вккуРзтяо яп была начерчена прямзя, прп достаточно большом увелвчеяяя опз превратится в воляпстую язв даже прерывную павию, 3 н.

м. сш! 1в ПОЛУг!ЕНИЕ СЛУЧЛПНЫХ ВЕЛПггип Нл ЭВМ !ГЛ. ! такие, что на получение каждого числа затрачивается всего 3 — 5 команд ЭВМ, а программа расчета занимает в накопителе лишь несколько ячеек. Подавляющее большинство расчетов методами Монте-Карло выполнено с помощью псевдослучайных чисел. 1.6. Сравнение трех способов с практической точки зрения. Попутно с изложением методов получения случайных величин мы рассмотрели некоторые их достоинства и недостатки. Остановимся еще на вопросе о быстроте выработки случайных величин. При решении на ЭВМ большинства задач на получение псевдослучайных чисел затрачивается гораздо меньше времени, чем на расчет самих задач.

В самом деле, практика показывает, что в настоящее время количество псевдослучайных чисел, используемых при решении отдельных задач, как правило*), имеет порядок 104 — 10з и редко. достигает 1О' — 10'. Если на выработку каждого числа затрачивать 5 оперцаий, то на получение всех чисел уйдет не более 5 10г операций. На современных ЭВМ, скорость которых равна 5 10' операций в секунду, это составит не более 100 секунд. Используя датчики, можно организовать «сверхбыструю» выработку случайных чисел, так как, присоединив к ЭВМ й датчиков, мы будем за один такт работы ЭВМ получать А случайных чисел.

Однако выигрыш времени при расчете сложной задачи в указанных выше условиях окажется меньше двух минут. Так что, исходя из интересов методов Монте-Карло, не стоит гнаться за «сверхбыстрой> выработкой случайных величин *). Разумно требовать, чтобы скорость выработки была того же порядка, что скорость счета ЭВМ. Псевдослучайные числа этому требованию удовлетворяют.

В табл. 1 перечислены достоинства и недостатки трех методов по шести признакам. Подчеркнем, что речь идет только об «эксплуатационных» особенностях, а не о «качестве» вырабатываемых чисел, которое должно проверяться во всех трех методах. ') Исключение составляют такие задачи, в которых огромные массивы случайных чисел подвергаются очень простой обработке. Но такие задачи выгоднее решать на специализированных машинах, а не на универсальных ЭВМ. К тому лсе, вероятно, для болынннства таких задач мо>кпо придумать лучшие способы рсшеппя...

ПСЕИДОСЛУЧАИНЫЕ ЧИСЛА Из таблицы видно, что метод псевдослучайных чисел — самый удобный с практической точки зрения. Это подтверждается также всей практикой расчетов методами Монте-Карло. Таблица ! Неаостатаи достоииства Метоа Проверка однократная. Воспроизводить числа можно таблиц Запас чисел яеограничен. Сверхбыстрое аолученнс. Места в накопителе не занимает датчиков псевдослучайных чисел Необходимо, однако, признать, что не все разделяют эту точку зрения. Некоторые авторы отдают предпочтение датчикам, аргументируя тем, что: а) псевдослучайные числа вырабатываются медлен.

нее и занимают место во внутреннем накопителе; б) не стоит расходовать рабочее время большой ЭВаЧ, когда можно использовать время небольшой приставки; в) а все-таки числа, вырабатываемые да~чиком, «случайныеи, а псевдослучайные числа — нет... й 2. Псевдослучайные числа Общей теории псевдослучайных чисел в настоящее время нет. О возможных путях построения такой теории разговор пойдет в гл. 7. Здесь мы ограничимся изложением некоторых фактов, главным образом эмпирического характера.

яе Проверка однократная. Воспроизводить числа ешжно. Быстрое получение. Места в накопителе ванны а ст м ало. Внешние устройства не ну>ням Запас чисел ограничен. Занимает много места в накопителе или медленно вводится. Нужва внешняя память Проверка периодическая. Воспроизводить числа нельзя. Требуется специальпос устройство Запас чисел ограничен 20 ПОЛУЧЕНИЕ СЛУЧАЙНЫХ ВЕЛИЧИН НА ЗВМ !ГЛ ! 2.1. Алгоритмы вида т„+! — Ф(у„).

Характеристики

Список файлов книги