Вычисление площади сложной фигуры методом имитационного моделирования

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

Государственное образовательное  учреждение высшего профессионального  образования

АМУРСКИЙ ГОСУДАРСТВЕННЫЙ  УНИВЕРСИТЕТ

(ГОУВПО «АмГУ»)

 

 

 

Факультет Математики и информатики

Кафедра Общей математики и информатики

Специальность 160802 - Космические летательные аппараты и разгонные блоки

 

 

 

 

КУРСОВАЯ РАБОТА

 

 

на тему: Вычисление площади сложной фигуры методом имитационного моделирования

по дисциплине «Математический  анализ»

 

 

Исполнитель

студент группы 911 к     _____________________________ В.В. Шевелев

 

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

доцент, к.п.н.                   _____________________________ Н.Н. Двоерядкина

 

Нормоконтроль

доцент, к.п.н.                   _____________________________ Т.А. Макарчук

 

 

 

 

 

 

Благовещенск 2010

 

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

Государственное образовательное  учреждение высшего профессионального  образования

АМУРСКИЙ   ГОСУДАРСТВЕННЫЙ   УНИВЕРСИТЕТ

(ГОУВПО «АмГУ»)

 

Факультет__________________________________________________________

 

Кафедра ____________________________________________________________

 

 

З А Д А  Н И Е

 

К курсовой работе (проекту) студента ___________________________________________

____________________________________________________________________________

 

1. Тема курсовой работы (проекта):______________________________________________

_____________________________________________________________________________

2. Срок сдачи студентом  законченной работы (проекта)_____________________________

 

3. Исходные данные к  курсовой работе (проекту):__________________________________

_____________________________________________________________________________

_____________________________________________________________________________

_____________________________________________________________________________

_____________________________________________________________________________

 

4. Содержание курсовой  работы (проекта) (перечень подлежащих  разработке  вопросов):

_____________________________________________________________________________

_____________________________________________________________________________

 

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

_____________________________________________________________________________

_____________________________________________________________________________

 

6 Дата выдачи  задания_________________________________________________________

 

Руководитель курсовой работы (проекта)_________________________________

                                                                                                           ^{(фамилия, имя, отчество, должность, ученая степень, ученое звание)}

_____________________________________________________________________________

Задание принял к исполнению (дата):_____________________________________________

                                                             _________________                                               ^{(подпись студента)}

 

 СОДЕРЖАНИЕ

 

 

 

 

 

 

 

 

 

 

 

 

 

ТЕХНИЧЕСКОЕ ЗАДАНИЕ

1. Изучить вычисление площади сложной фигуры методом имитационного моделирования. Метод Монте-Карло.
2. Рассмотреть пример вычисление площади методом Монте-Карло.
3. Дата выдачи задания:_______________________________________
4. Срок готовности задания:____________________________________
5. Дата защиты курсовой:______________________________________

 

Принял к  исполнению_________________________________  В.В. Шевелев

 

ВВЕДЕНИЕ

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

·   Дорого или невозможно экспериментировать на реальном объекте.

·   Невозможно построить аналитическую модель: в системе есть время, причинные связи, последствие, нелинейности, стохастические (случайные) переменные.

·   Необходимо сымитировать поведение системы во времени.

Цель  имитационного моделирования состоит в воспроизведении поведения исследуемой системы на основе результатов анализа наиболее существенных взаимосвязей между ее элементами или другими словами – разработке симулятора (английский термин – simulation, modeling) исследуемой предметной области для проведения различных экспериментов.

Имитационное  моделирование позволяет имитировать  поведение системы, во времени. Причём плюсом является то, что временем в  модели можно управлять: замедлять  в случае с быстропротекающими процессами и ускорять для моделирования систем с медленной изменчивостью. Можно имитировать поведение тех объектов, реальные эксперименты с которыми дороги, невозможны или опасны. Имитация, как метод решения нетривиальных задач, получила начальное развитие в связи с созданием ЭВМ в 1950х — 1960х годах. Одним из методов имитационного моделирования является метод статистических испытаний или метод Монте-Карло. Рассмотрим использование этого метода для вычисления S плоских фигур.

 

1.ОБЩЕЕ ПРЕДСТАВЛЕНИЕ О МЕТОДЕ

1.1. Происхождение метода Монте-Карло.

  Датой рождения метода Монте-Карло  принято считать 1949 год, когда  появилась статья под названием  “The Monte Carlo method”. Создателями этого  метода считают американских  математиков Дж. Неймана и С.  Улама. В Советском Союзе первые статьи о методе Монте-Карло были опубликованы в 1955-1956 годах.

Любопытно, что теоретическая основа метода была известна уже давно. Более  того, некоторые задачи статистики рассчитывались иногда с помощью  случайных выборок, то есть фактически методом Монте-Карло. Однако до появления электронных вычислительных машин (ЭВМ) этот метод не мог найти сколько-нибудь широкого применения, ибо моделировать случайные величины вручную - очень трудоемкая работа. Таким образом, возникновение метода Монте-Карло как весьма универсального численного метода стало возможным только благодаря появлению ЭВМ. Само название «Монте-Карло» происходит от города Монте-Карло в княжестве Монако, знаменитого своим игорным домом. Дело в том, что одним из простейших механических приборов для получения случайных величин является... рулетка. Стоит ответить на часто задаваемый вопрос: «Помогает ли метод Монте-Карло выигрывать в рулетку?» Нет, не помогает. И даже не занимается этим.

  1.2. Пример.

 Для начала рассмотрим весьма простой пример. Предположим, что нам нужно вычислить площадь плоской фигуры S. Это может быть совсем произвольная фигура с криволинейной границей, заданная графически или аналитически, связная или состоящая из нескольких кусков. Пусть это будет фигура, изображенная на рис. 1, и предположим, что она вся расположена внутри единичного квадрата. Выберем в квадрате N случайных точек. Обозначим через N' число точек, попавших при этом внутрь S. Геометрически очевидно, что площадь S приближенно равна отношению N'/N. Чем больше будет N, тем больше будет точность этой оценки. В примере, изображенном на рис. 1, выбраны N = 40 точек. Из них N' = 12 точек оказались внутри S. Отношение N'/N = 12/40=0,30, в то время как истинная площадь S равна 0,35 ¹.

Рисунок 1-пример случайных координат.

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

1.3. Две особенности метода Монте-Карло.

Первая особенность метода - простая  структура вычислительного алгоритма. Как правило, составляется программа  для осуществления одного случайного испытания (в примере из п. 1.2 надо выбрать случайную точку в квадрате и проверить, принадлежит ли она S). Затем это испытание повторяется N раз, причем каждый опыт не зависит от всех остальных, и результаты всех опытов усредняются. Поэтому иногда метод Монте-Карло называют методом статистических испытаний.

Вторая особенность метода: ошибка вычислений, как правило, пропорциональна , где D - некоторая постоянная, а N - число испытаний. Из этой формулы видно, что для того, чтобы уменьшить ошибку в 10 раз (иначе говоря, чтобы получить в ответе еще один верный десятичный знак), нужно увеличить N (то есть объем работы) в 100 раз. Ясно, что добиться высокой точности на таком пути невозможно. Поэтому обычно говорят, что метод Монте-Карло особенно эффективен при решении тех задач, в которых результат нужен с небольшой точностью (5-10 %).

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

1.4. Задачи, решаемые методом Монте-Карло.

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

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

Вернемся к примеру из п. 1.2. Для расчета нам нужно было выбирать случайные точки в единичном квадрате. Как это сделать физически? Представим такой эксперимент. Рис. 1 (в увеличенном масштабе) с фигурой S и квадратом повешен на стену в качестве мишени. Стрелок, находящийся на некотором расстоянии от стены, стреляет N раз, целясь в центр квадрата. Конечно, все пули не будут ложиться точно в центр: они пробьют на мишени N случайных точек³. Можно ли по этим точкам оценить площадь S? Результат такого опыта изображен на рис. 2. В этом опыте N=40, N' = 24 и отношение N'/N=0,60, что превышает истинное значение площади (0,35) почти в два раза. Впрочем, и так ясно, что при очень высокой квалификации стрелка результат опыта будет очень плохим, так как почти все пули будут ложиться вблизи центра и попадут в S.

Рисунок 2-пример физического вычисления.

Нетрудно сообразить, что наш  метод вычисления площади будет  справедлив только тогда, когда случайные  точки будут не «просто случайными», а еще и «равномерно разбросанными» по всему квадрату.

 

2. ОБЫЧНЫЙ АЛГОРИТМ МОНТЕ-КАРЛО ИНТЕГРИРОВАНИЯ

Рисунок 3-численное интегрирование функции методом Монте-Карло.

 

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

Обычный алгоритм Монте-Карло интегрирования

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

ограничим функцию прямоугольником (n-мерным параллелепипедом в случае многих измерений), площадь которого Spar можно легко вычислить;

«набросаем» в этот прямоугольник (параллелепипед) некоторое количество точек (N штук), координаты которых будем  выбирать случайным образом;

определим число точек (K штук), которые  попадут под график функции;

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

                                                                                   (1)

Использование выборки по значимости.

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ЗАКЛЮЧЕНИЕ

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1. Башарин Г.П. Модели информационно-вычислительных систем. - М.: Наука, 1993. – 156с.
2. Соболь И.М. Метод Монте-Карло. – М: Наука, 2005 г., 64с.

 

 

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

² В иностранной литературе теперь чаще пишут о методах Монте-Карло (во множественном числе), имея в виду, что одну и ту же задачу можно считать при помощи моделирования различных случайных величин.

³ Мы предполагаем, что стрелок не является чемпионом мира и удалён на достаточно большое расстояние от мишени.