2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

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

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

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



Начать новую тему Ответить на тему
 
 Вычисление площади методом Монте-Карло
Сообщение08.07.2012, 20:29 


04/09/11
149
Здравствуйте. Поставлена следующая задача: задан некоторый набор прямоугольников, их объединение погружают в большой прямоугольник - и бросают в него N точек. Из них n попадут в объединение заданных прямоугольников - и мы приблизительно вычисляем площадь этого объединения, умножим число n/N на площадь большого прямоугольника.

Вопрос возник следующий. Можно ли как-то оценить точность вычисления на основе количества точек или количества бросаний? Видимо, точность будет означать вероятность того, что найденная величина соответствует настоящей площади. Интуитивно понятно, что если проводить бросание не один раз, а, например, сто, и усреднить полученные значения, то скорее всего это значение будет ближе к настоящему, чем значение, полученное после первого броска. Также, кажется, что если бросать не десять точек, а опять, например, сто, то найденное число больше должно соответствовать действительности, чем в случае десяти точек.

Есть ли какая-то формула для оценки точности или какой-то метод или что-то ещё? Заранее спасибо.

 Профиль  
                  
 
 Re: Вычисление площади методом Монте-Карло
Сообщение08.07.2012, 20:41 
Заслуженный участник
Аватара пользователя


18/05/06
13435
с Территории
Ну Вы же можете найти распределение возможных n при данном N, его сигму и всё такое прочее?

 Профиль  
                  
 
 Re: Вычисление площади методом Монте-Карло
Сообщение08.07.2012, 21:58 
Заслуженный участник


11/05/08
32166
Asker Tasker в сообщении #593588 писал(а):
Есть ли какая-то формула для оценки точности

Эта стандартная статистическая задача вот какого сорта (кстати, прямоугольность внутренней области тут совершенно не при чём -- ровно с тем же успехом можно задавать область вообще любой системой неравенств).

Известно, что мы имеем дело со схемой Бернулли с некоторым неизвестным параметром $p$, который и надо, собственно, оценить по большой выборке; а также оценить и погрешность (говоря конкретнее -- дисперсию оценки по данной выборке).

Формально -- задачка занудна. Но практически (учитывая, что ожидаемое $p$ при разумной постановке задачи не слишком мало и не слишком близко к единице, при том что количество отсчётов велико) -- все оценки практически сводятся центральной предельной теоремой к соотв. оценкам для того нормального распределения, к которому сводится той теоремой усреднённое по многим отсчётам распределение Бернулли.

 Профиль  
                  
 
 Re: Вычисление площади методом Монте-Карло
Сообщение09.07.2012, 06:26 


02/11/08
1187
http://projecteuler.net/problem=212 напомнило ассоцитиативно...

 Профиль  
                  
 
 Re: Вычисление площади методом Монте-Карло
Сообщение09.07.2012, 08:46 
Заслуженный участник


09/09/10
3729
Если мы считаем интеграл $I=\int\limits_0^1 f(x)dx$, кидая $n$ точек на отрезок $[0,1]$, то погрешность будет меньше $\varepsilon$ при $n>\dfrac{9\max^2|f(x)|}{\varepsilon^2}$. При выводе, правда, используется правило трех сигм.

 Профиль  
                  
 
 Re: Вычисление площади методом Монте-Карло
Сообщение10.07.2012, 02:50 


04/09/11
149
Всем спасибо.
Но с теорией вероятностей я дело имел лишь косвенно и отдалённо, так что "пошёл читать про центральную предельную теорему".

Joker_vD в сообщении #593702 писал(а):
Если мы считаем интеграл $I=\int\limits_0^1 f(x)dx$, кидая $n$ точек на отрезок $[0,1]$, то погрешность будет меньше $\varepsilon$ при $n>\dfrac{9\max^2|f(x)|}{\varepsilon^2}$. При выводе, правда, используется правило трех сигм.

А можно чуть подробнее, как мы оценку для n получаем?

ewert в сообщении #593623 писал(а):
Эта стандартная статистическая задача вот какого сорта (кстати, прямоугольность внутренней области тут совершенно не при чём -- ровно с тем же успехом можно задавать область вообще любой системой неравенств).

Я понимаю, но задача была поставлена именно в таком виде, как я написал, поэтому решил ничего не менять - и спрашивать как есть.

Yu_K в сообщении #593677 писал(а):
http://projecteuler.net/problem=212 напомнило ассоцитиативно...

Спасибо за ссылку. Не слышал раньше об этом проекте. Вроде бы интересно.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 6 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group