Лабораторная работа. LAVR Лаб. раб. № 10. Приближенное вычисление площади фигуры м. Лабораторная работа 4 Приближенное вычисление площади фигуры методом МонтеКарло
 Скачать 0.77 Mb.
|
|
Лабораторная работа № 4 Приближенное вычисление площади фигуры методом Монте-Карло Цель: изучение метода Монте-Карло (метода статистических испытаний) на примере вычисления площади фигуры. Метод Монте-Карло Методы Монте-Карло или методы статистических испытаний – это группа численных методов, основанных на воспроизведении большого числа реализаций случайного процесса. Таким образом, суть метода заключается в статистическом моделировании случайных процессов, численном моделировании реализаций случайных процессов и оценивании параметров по реализациям случайных процессов методами математической статистики. Под численным статистическим моделированием обычно понимают реализацию с помощью компьютера вероятностной модели некоторого объекта с целью оценивания изучаемых интегральных характеристик на основе закона больших чисел. Свое экзотическое название метод получил от города Монте-Карло (княжество Монако), который известен благодаря своему казино, поскольку именно рулетка является одним из самых широко известных генераторов случайных чисел. Станислав Улам пишет в своей автобиографии «Приключения математика», что название было предложено Николасом Метрополисом в честь его дяди, который был азартным игроком. Основоположники метода Монте-Карло Станислав Улам Николас Метрополис Джон фон Нейман Статистическое моделирование широко применяется для решения задач из различных областей человеческого знания. Среди них такие актуальные области как биология, химия, физика, экономика и другие. К задачам, где широко используется этот подход, можно отнести следующие: численное интегрирование, расчеты в системах массового обслуживания, расчеты качества и надежности изделий, расчеты прохождения нейтронов и других частиц через вещество, передача сообщений при наличии помех, задачи теории игр, задачи динамики разреженного газа, задачи дискретной оптимизации, задачи финансовой математики. Алгоритм вычисления площади фигуры Применим метод статических испытаний или метод Монте-Карло к задаче вычисления площади геометрической фигуры на плоскости. Метод заключается в следующем. Поместим данную фигуру в квадрат и будем наугад бросать точки в этот квадрат. Будем исходить из того, что чем больше площадь фигуры, тем чаще в нее будут попадать точки. Таким образом, при большом числе N точек, наугад выбранных внутри квадрата, доля точек, содержащихся в данной фигуре k, приближенно равна отношению площади этой фигуры и площади квадрата: Если площадь квадрата равна и в результате испытаний, из которых при исходах случайные точки оказались внутри фигуры, то площадь фигуры будет определяться выражением Рассмотрим алгоритм решения задачи на конкретном примере. Рассмотрим фигуру, представленную на рис. 1а., площадь которой нам заранее известна и равна . Вообще говоря, фигура может быть любой, но обязательно должны быть известны границы фигуры, в виде аналитического выражения или совокупности таких выражений и логических условий. Рис. 1а Рис. 1б В нашем примере множество точек фигуры определяется следующей системой неравенств: Площадь этой фигуры составляет часть прямоугольника площадью 1. Генерируем случайные числа и равномерно распределенные на отрезке . Это будут координаты случайной точки в квадрате, в которую заключена фигура, площадь которой требуется найти. Полученная точка может как попасть в исследуемую фигуру, так и не не попасть (рис. 1б). 2. Проверяем принадлежность точки к исследуемой фигуре. Если попадания нет, т.е. не выполняется хотя бы одно из неравенств системы, то переходим к пункту 1 и генерируем координаты новой точки. Если попадание есть, то фиксируем это попадание. Значение счетчика числа попаданий увеличиваем на единицу и снова переходим к пункту 1. Заметим, что попадание случайной точки точно на границу фигуры можно отнести как к первому, так и ко второму исходу. Пункты 1 и 2 следует повторить в цикле достаточно большое число N раз. От этого, в конечном итоге, зависит точность вычислений. После проведения N повторов площадь фигуры найдем по формуле: Блок-схема алгоритма приведена на рис. 2. Рис. 2 Пример текста программы на VBA: Функция mk(n) возвращает значение площади фигуры при заданном числе испытаний n. Условия принадлежности случайной точки фигуре заданы в теле подпрограммы-функции. На рабочем листе Excel, использую данную функцию, составим таблицу: N S 10 4,8 0,427484 100 8,96 0,068697 1000 8,272 0,013363 10000 8,3664 0,002104 100000 8,36512 0,002257 1000000 8,37656 0,000892 В столбцах таблицы приведены соответственно число испытаний, найденная площадь и относительная погрешность метода Монте-Карло Задание 1 Составить и отладить программу определения площади фигуры методом Монте- Карло в соответствии с индивидуальным заданием. Задание 2 Вычислить методом Монте-Карло определенный интеграл. Сравните результат со значением, полученным аналитическим путем при значениях N=10, 100, 1000, 10000, 100000, 1000000. Выразите относительную погрешность метода Монте-Карло при каждом значении N. Исходные данные к заданию 1 Условия, ограничивающие область фигуры 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. Контрольные значения площадей фигур по вариантам Вариант 1 6,37517 2 6,94246 3 4,82702 4 6,57343 5 9,39411 6 6,33624 7 9,92969 8 9,64255 9 8,38467 10 9,37331 11 7,13684 12 6,84359 Фигуры, площадь которых необходимо определить методом Монте-Карло Исходные данные к заданию 2 1 2 3 4 5 6 7 8 9 10 11 12 |