Основы численных методов курсовая работа

Федеральное агентство по образованию

Национальный Исследовательский  Технологический Университет «МИСиС»

 

 

Институт информационных технологий и автоматизированных систем управления

 

 

Кафедра инженерной кибернетики

 

 

Курс:

Основы численных методов

 

Курсовая работа:

Метод Монте-Карло.

Применение метода для решения задач интегрирования

 

 

Исполнитель:

Сенченко Роман Владимирович,

студент группы ММ-09-01

Руководитель:

Гопенгауз Владимир Израилевич

 

 

 

 

 

 

 

 

 

Москва, 2012 г. 

Оглавление

Введение 3

§1. Моделирование случайных  величин 4

1.1. Генерация стандартной  случайной величины 4

1.2. Статистическая  проверка генератора 5

Длина апериодичности 5

Критерий Пирсона 6

Частотный тест 7

Тест серий 8

§2. Применение метода Монте-Карло для вычисления интегралов 9

2.1. Общий метод 9

Оценка математического  ожидания 9

Погрешность метода 9

2.2. Простейший метод  Монте-Карло 10

Одномерный определенный интеграл 11

2.3. Простейший метод  с повышенной скоростью сходимости 12

Двумерный определенный интеграл 17

Выводы 20

Список литературы 21

Приложения и листинги 22

Приложение 1. Листинг  генератора Д.Лемера 22

Приложение 2. Листинг  статистических функций 24

Приложение 3. Листинг  основной части программы 27

 

Введение

Методами Монте-Карло называется семейство методов решения численных  задач, основанных на моделирование  различных случайных величин. Главная  идея методов Монте-Карло заключается  в следующем: пусть поставлена некая  задача и скалярная величина является ее решением (это может быть решение СЛАУ или же значение интеграла , и т.д.). Постараемся придумать такую случайную величину , чтобы . Если это удастся сделать, то естественно ожидать, что решение поставленной задачи можно получить как при достаточно большом .

 

 

§1. Моделирование  случайных величин

1.1. Генерация стандартной случайной величины

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

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

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

Не вдаваясь в дальнейшие подробности, укажем сразу простую и достаточно хорошую функцию, предложенную Д.Лемером:

,

 и  - параметры функции. Указанная выше запись не удобна, т.к. приходится работать с дробными числами. Однако, если представимо в виде несократимой дроби , а и взаимнопросты, то функцию Д.Лемера можно записать иначе.

 

 

А именно:

Тройка чисел  являются параметрами функции. Генератор стандартной случайной величины, основанный на этой функции носит название генератор Д.Лемера.

1.2. Статистическая проверка  генератора

Разумеется, не для всех параметров генератор Д.Лемера, также называемый линейным конгруэнтным генератором, генерирует последовательности, обладающие хорошими свойствами. Обстоятельные исследования по этому поводу приводятся в [2]. Мы же лишь воспользуемся рекомендациями, данными в [1] для проверки качества генерируемой последовательности при уже выбранных параметрах генератора.

Длина апериодичности

Прежде, чем приступать к каким-либо проверкам получаемой последовательности, следует определить длину отрезка  апериодичности. Как легко видеть из самой формулировки алгоритма  Д.Лемера:

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

Ясно, что использовать числа, полученные алгоритмом Д.Лемера при  , не имеет смысла.

Критерий Пирсона

Рассмотрим произвольную случайную  величину , которая может быть одномерной или многомерной, дискретной или непрерывной. Обозначим через множество всевозможных значений . Фиксируем какое-нибудь разбиение множества на попарно непересекающихся множеств таких, что при .

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

В качестве меры отклонения «истинных» значений от «теоретических» удобно выбрать величину

Согласно теореме Пирсона, каковы бы ни были исходная величина и (такое, что все ), при каждом

,

Где плотность  , называется плотностью распределения с степенями свободы (аналитическую формулу для можно найти в [3]).

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

Строим величину для конкретной гипотезы (меняется разбиение и соответствующие вероятности ), вычисляем значение теоретической величины . Если , то принимаем гипотезу о законе распределения; иначе – отвергаем.

 

Для удобства проверки гипотезы о  стандартности чисел, генерируемых алгоритмом Д.Лемера, возьмем аппроксимацию  Голдштейна из [3]:

Частотный тест

Пусть первые десятичные разряды всех чисел, генерируемых генератором Д.Лемера на всем промежутке апериодичности .

Во-первых, если распределены равномерно, то частоты встречи цирф будут примерно равны. Аналогично, примерно равны будут и частоты независмых пар

Сосчитаем матрицу частот при : - частота встречи пары ; а также сосчитаем вектора , и . По этим данным посчитаем величины

1. с 9-ю степенями свободы – тест проверки частот (frequency test)
2. с 99-ю степенями свободы – тест проверки пар (serail test)

И проверим гипотезу о равномерности  распределения с помощью критерия .

Тест серий

Числа образуют серию длины , если . Пусть - это количество серий длины , а - количество всех остальных серий выборки . Общее количество серий обозначим через . Величина с степенями свободы вычисляется по формуле

,

 и 

 

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

 

Замечание 2: эмпирически удалось подобрать параметры генератора Д.Лемера, при которых длина отрезка апериодичности составляет и чиста обладают хорошими случайными свойствами.

 

§2. Применение метода Монте-Карло для вычисления интегралов

2.1. Общий метод

Оценка математического ожидания

Рассмотрим произвольную случайную  величину , у которой существует конечное математическое ожидание . Чтобы оценить величину , выберем независимых реализаций случайной величины и вычислим математическое ожидание этой выборки:

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

Более того, при достаточно больших  можно положить приближенное равенство

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

Погрешность метода

Предположим, дополнительно к 2.1., что  у случайной величины существует еще и конечная дисперсия. Тогда

И по центральной предельной теореме (а величина подчиняется ей, коль скоро ) имеем:

,

Положим, что  . Тогда из последнего соотношения получим, что

Следовательно, при достаточно больших  значениях 

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

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

2.2. Простейший метод Монте-Карло

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

.

Рассмотрим задачу о приближенном вычислении интеграла

.

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

.

Но, согласно оценки из пункта 2.1, и действительна оценка точности вычисления из пункта 2.2.

Одномерный определенный интеграл

Построим метод Монте-Карло на основе простейшего, позволяющий брать  интегралы вида

,

который всегда можно представить  в виде

,

где - плотность равномерно распределенной случайной величины на отрезке .

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

при достаточно больших  .

 

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

 

Численный пример 1 Пусть требуется взять интеграл График подынтегральной функции   При , имеем При , имеем При , и выбранный генератор Д.Лемера не способен сгенерироваьт такую выборку.