INFO.Z-PDF.RU
БИБЛИОТЕКА  БЕСПЛАТНЫХ  МАТЕРИАЛОВ - Интернет документы
 

«Руководитель работы: Люстров Константин Сергеевич Работу выполнили ученики 11 «А» класса ГБОУ «Школы № 777» Галицкий Павел Саад Али Москва, 2017 Оглавление Введение Глава 1. Общие ...»

Государственное бюджетное общеобразовательное учреждениегорода Москвы«Школа № 777имени Героя Советского Союза Е. В. Михайлова»

Исследование точности метода Монте-Карлопри нахождении площадей фигур

Руководитель работы:

Люстров Константин Сергеевич Работу выполнили ученики 11 «А» класса ГБОУ «Школы № 777»

Галицкий Павел

Саад Али

Москва, 2017

Оглавление

Введение

Глава 1. Общие сведения о методе Монте-Карло

1.1 Моделирование

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

Глава 2. Исследование точности метода Монте-Карло

2.1 Вычисление значения числа методом Монте-Карло...............5

2.2 Гипотеза о зависимости точности метода от количества точек..6

2.3 Гипотеза о зависимости точности метода от радиуса круга......8

Глава 3. Практическое применение метода Монте-Карло……….

.............9

3.1. Алгоритм интегрирования Монте-Карло…………

3.2. Зондирование местности с помощью Монте-Карло……….....10

3.3 Алгоритм Ванга-Ландау…………………………………………10

Заключение

Литература

Введение

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



Изучить вероятностную модель метода Монте-Карло.

Построить информационную модель метода Монте-Карло в компьютерной среде программирования Delphi XE6.

Оценить точность метода Монте-Карло.

Исследовать зависимость абсолютной и относительной погрешности от количества точек.

Исследовать зависимость абсолютной и относительной погрешностей от разности площадей фигур.В работе рассматриваются теоретическая и практическая часть метода и две гипотезы с доказательствами.

Глава 1. Общие сведения о методе Монте-Карло

1.1. Моделирование

Для исследования метода Монте-Карло мы прибегли к компьютерному моделированию. Основой моделирования является модель.

Модель – это упрощённое описание некоторого объекта, процесса или явления, сохраняющего все важные свойства исходного объекта в рамках проводимого эксперимента.

Существуют следующие модели:

Материальные модели (физические);

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

Информационные модели.

Моделирование – это процесс создания и исследования модели объекта. (3)

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

Метод Монте-Карло - это метод решения различных задач с помощью генерации случайных последовательностей.

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

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





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

Глава 2. Исследование точностиметода Монте-Карло

2.1 Вычисление значения числа методом Монте-Карло

Для исследования точности метода мы создали модели, позволяющие определить значение числа с помощью метода Монте-Карло.

Создание качественной модели нашего эксперимента:

впишем круг внутрь квадрата

будем генерировать точки со случайными координатами так, чтобы они попадали внутрь квадрата;

будем считать, что отношение числа точек, попавших внутрь круга, к общему числу точек в квадрате приблизительно равно отношению площади круга к площади квадрата

Создание формальной модели эксперимента:

М – количество точек попавших внутрь круга;

N – количество точек со случайными координатами, которые генерируются внутри квадрата.

Отношение точек, попавших внутрь круга, к общему количеству точек примерно соответствует отношению чисел M и N:

SкругаSквадрата~MNИспользуя формулы из курса геометрии, вычисляем площади фигур:

Sкруга=R2Sквадрата=4R2Откуда находим значение числа :

= 4MN

Для оценки точности вычисляем абсолютную и относительную погрешности.

Абсолютная погрешность:

x = |расч - |

где:

расч – значение числа, полученное в ходе эксперимента,

– реальное значение числа

Относительная погрешность:

= x /.

Для проведения такого эксперимента нами было разработано в среде Embarcadero RAD Studio (Delphi XE6) программное обеспечение для операционной системы Windows.

С помощью созданного программного обеспечения мы исследовали:

зависимость точности метода от количества генерируемых точек;

зависимость точности метода от радиуса окружности при неизменных размерах квадрата.

(6, 2)

2.2. Гипотеза о зависимости точности метода от количества точек

Мы выдвинем гипотезу о зависимости точности метода от количества взятых нами точек при значениях радиуса равных стороны квадрата. Пусть сторона квадрата=1000, радиус=500.

По результатам эксперимента нами составлен график зависимости относительной погрешности от количества взятых точек.

Как мы видим, вначале погрешность резко понижается, после постепенно выравнивается.

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

k = 0,05 · x,

где k – необходимое количество точек для эксперимента, x – общее количество точек в квадрате.

Например, в квадрате 4000 точек. Находим по формуле необходимое количество точек для эксперимента, оно равно=200. Теперь мы знаем, какое количество точек нужно высчитывать для использования метода. График будет выглядеть так же, если взять абсолютную погрешность.

2.3 Гипотеза о зависимости точности метода от радиуса круга

Рассмотрим гипотезу о зависимости точности метода от радиуса круга при неизменной стороне квадрата и количества точек внутри квадрата. Докажем это с помощью эксперимента. Будем рассматривать квадрат со стороной 1000 и круг с изменяемым радиусом при сохранении количества расставляемых точек. По результатам эксперимента составим график относительной погрешности.

Получается, что с уменьшением радиуса круга погрешность возрастает, следовательно, точность метода падает с уменьшением радиуса круга.

Вывод: метод Монте-Карло является наиболее эффективным для вычисления числа пи при небольшой разности площадей фигур, т.е. при длине радиуса круга близкой к 1/2 стороны квадрата. С увеличением этой разности точность вычислений уменьшается.

Глава 3. Практическое применениеметода Монте-Карло

3.1 Алгоритм интегрирования методом Монте-Карло

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

Для определения этой площади можно воспользоваться одним из обычных численных методов интегрирования: разбить отрезок на подотрезки, подсчитать площадь под графиком функции на каждом из них и сложить. Предположим, что для некоторой функции достаточно разбиения на 25 отрезков и, следовательно, вычисления 25 значений функции. Представим теперь, мы имеем дело с -мерной функцией. Тогда нам необходимо  отрезков и столько же вычислений значения функции. При размерности функции больше 10 задача становится огромной. Поскольку пространства большой размерности встречаются во многих реальных задачах (например, физических), где имеются системы со многими степенями свободы, необходимо иметь метод решения, вычислительная сложность которого бы не столь сильно зависела от размерности. Именно таким свойством обладает метод Монте-Карло.

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

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

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

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

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

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

3.2 Зондирование местности с помощью Монте-Карло

При исследовании снимков со спутников часто возникает потребность в нахождении размера объектов на них. Если с линейными размерами (длина и ширина) все достаточно просто, то в нахождении фигур разной формы могут возникнуть трудности. В данном случае нам может помочь метод Монте-Карло.

Для того, чтобы вычислить площадь какого-либо объекта на снимке, нужно воспользоваться по пиксельным масштабированием. Одному пикселю нужно задать размер. Для этого нужно воспользоваться масштабом снимка и вычислить площадь, которую задает 1 пиксель. Затем выделяем нужную фигуру и вычисляем площадь по формуле S=n·k, где n – количество пикселей, k – площадь одного пикселя.

3.3 Алгоритм Ванга-Ландау

Алгоритм Ванга-Ландау, предложенный Фугао Вангом и Дэвидом Ландау, это метод Монте-Карло, предназначенный для расчета плотности состояний системы. Метод выполняет немарковские случайные переходы для построения плотности состояний, посещая все возможные состояния.

Алгоритм Ванга-Ландау может быть применен к любой системе, которая характеризуется некоторым параметром (энергией, объемом). Он может быть использован для численного интегрирования и моделирования белков.

Заключение

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

Список используемой литературы

Гейн А. Г., Ливчак А. Б., Сенокосов А. И., Юнерман Н. А. Информатика и ИКТ. 10 класс. Учебник для общеобразовательных учреждений. Базовый и профильный уровни. – М.: Просвещение, 2010. – 272 с.

Угринович Н. Д. Информатика и ИКТ. 11 класс. Профильный уровень. – М.: Бином. Лаборатория знаний, 2011.

Тепляков А. Моделируя жизнь. – Hard’n’Soft, № 7, 2001 г.

Культин Н. Основы программирования в Delph XE – СПб., БХВ-Петербург, 2011. – 405 с.

Ермаков С. М. Методы Монте-Карло и смежные вопросы. М.: Наука, 1971г.

Популярные лекции по математике 1968. Выпуск 46. Соболь И.М. Метод Монте-Карло. М.: Наука, 1968. — 64 с.

Похожие работы:

«Пояснительная записка В старшей школе реализовано профильное обучение. В зависимости от выбранного профиля предмет "Информатики и ИКТ" может быть представлен на двух уровнях – базовом или профильном. На предмет, изучаем...»

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное государственное автономное образовательное учреждение высшего образования Новосибирский национальный исследовательский государственный уни...»

«Внеклассная работа по информатике– КВН Информатика и мыЦели: Показать, что информатика является наукой, которая занимается изучением информационных процессов, т.е. сбора, хранения и передачи информации. И что основным инструментом реализации информационных процессов является компьютер. Фор...»

«Муниципальное автономное общеобразовательное учреждение "средняя общеобразовательная школа №96" г.Перми. УТВЕРЖДАЮ Директор МАОУ "СОШ № 96" И.П.Синица"1" августа 2017 годаРАБОЧАЯ ПРОГРАММА Элективного курса "Создание WEB – страниц"...»

«Смоленский техникум железнодорожного транспорта связи и сервисаУТВЕРЖДАЮ Заместитель директора поучебно-производственной работе..................А.В. Прутько".. 28..".....августа....2013 г. РАССМОТРЕНО На заседании комиссии связи...............»

«Смоленский техникум железнодорожного транспорта связи и сервисаУТВЕРЖДАЮ Заместитель директора поучебно-производственной работе..................А.В. Прутько".. 28..".....августа....2013 г. РАССМОТРЕНО На заседании комиссии связи................Л.Е. Кузьмицкая"..28."...августа.. 20...»

«Лекция № 5. Компьютерные сети в системе образования (2 часа) Компьютерная сеть – это совокупность компьютеров и различных устройств, обеспечивающих информационный обмен между компьютерами в сети без использования каких-либо промежуточных носителе...»

«Пояснительная записка Программа по информатике для основной школы составлена в соответствии с федеральным компонентом государственного образовательного стандарта основного общего образования по информатике и ИКТ (2...»

«Лекция 1 Информационные системы и их классификацииОсновные понятия  Система (от греческого systema — целое, составленное из частей соединение) — это совокупность элементов, взаимодействующих друг с другом, образующих определенную целостность, единство. Приведем некоторые понятия, часто испол...»








 
2018-2023 info.z-pdf.ru - Библиотека бесплатных материалов
Поддержка General Software

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 2-3 рабочих дней удалим его.