4 Метод статистичних випробувань Метод статистичних випробувань


Скачати 2.04 Mb.
Назва 4 Метод статистичних випробувань Метод статистичних випробувань
Сторінка 8/31
Дата 08.04.2013
Розмір 2.04 Mb.
Тип Лекция
bibl.com.ua > Інформатика > Лекция
1   ...   4   5   6   7   8   9   10   11   ...   31

Интегрирование методом Монте-Карло


http://upload.wikimedia.org/wikipedia/commons/thumb/0/03/regular_integration.jpg/250px-regular_integration.jpg

Рисунок 2. Численное интегрирование функции детерминистическим методом

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

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

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


Предположим, требуется вычислить определённый интеграл \int\limits_{a}^{b}f(x)\,dx

Рассмотрим случайную величину ~u, равномерно распределённую на отрезке интегрирования ~[a,b]. Тогда ~f(u)также будет случайной величиной, причём её математическое ожидание выражается как
\mathbb{e}f(u)=\int\limits_a^b f(x)\phi(x)\,dx, где ~\phi(x) — плотность распределения случайной величины ~u, равная \frac{1}{b-a}на участке ~[a,b].

Таким образом, искомый интеграл выражается как
\int\limits_{a}^{b}f(x)\,dx = (b-a)\mathbb{e}f(u).

Но матожидание случайной величины ~f(u)можно легко оценить, смоделировав эту случайную величину и посчитав выборочное среднее.

Итак, бросаем ~nточек, равномерно распределённых на ~[a,b], для каждой точки ~u_iвычисляем ~f(u_i). Затем вычисляем выборочное среднее: \frac{1}{n}\sum^{n}_{i=1}f(u_i).

В итоге получаем оценку интеграла: \int\limits_{a}^{b}f(x)\,dx\approx\frac{b-a}{n}\sum^{n}_{i=1}f(u_i)

Точность оценки зависит только от количества точек ~n.

Этот метод имеет и геометрическую интерпретацию. Он очень похож на описанный выше детерминистический метод, с той разницей, что вместо равномерного разделения области интегрирования на маленькие интервалы и суммирования площадей получившихся «столбиков» мы забрасываем область интегрирования случайными точками, на каждой из которых строим такой же «столбик», определяя его ширину как \frac{b-a}{n}, и суммируем их площади.

Геометрический алгоритм Монте-Карло интегрирования


http://upload.wikimedia.org/wikipedia/commons/thumb/a/a5/mc_integration.jpg/250px-mc_integration.jpg

http://bits.wikimedia.org/static-1.21wmf5/skins/common/images/magnify-clip.png

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

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

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

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

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

  • площадь области, ограниченной функцией и осями координат, sдаётся выражением s = s_{par}\frac{k}{n}

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

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


При том же количестве случайных точек, точность вычислений можно увеличить, приблизив область, ограничивающую искомую функцию, к самой функции. Для этого необходимо использовать случайные величины с распределением, форма которого максимально близка к форме интегрируемой функции. На этом основан один из методов улучшения сходимости в вычислениях методом Монте-Карло: выборка по значимости.
1   ...   4   5   6   7   8   9   10   11   ...   31

Схожі:

Тема: Предмет, структура, завдання й методи досліджень в юридичній психології
Юридична психологія, метод спостереження (інтроспекція), метод бесіди, метод експерименту (законодавчий, природний, лабораторний,...
Урок розвитку мовлення в 11 класі Підготовка до написання твору роздуму...
Методи: метод випереджального навчання, метод наукового дослідження, метод дискусії, активний метод навчання — робота в малих групах,...
Список абітурієнтів, які подали ОРИГІНАЛИ ДОКУМЕНТІВ на напрям 050502
Сума балів вступних випробувань, творчих конкурсів, та вступних випробувань з фізичної підготовки
«УЗАГАЛЬНЕНИЙ МЕТОД НАЙМЕНШИХ КВАДРАТІВ (метод ЕЙТКЕНА)»
Узагальнений метод найменших квадратів (метод Ейткена) оцінка параметрів лінійної економетричної моделі з гетероскедастиними заліками....
МетодичнІ матеріали до ВСТУПНИХ ВИПРОБУВАНЬ
Методичні матеріали до вступних випробувань на навчання для осіб, які здобули освітньо-кваліфікаційний рівень молодшого спеціаліста...
УРОК 58 Тема уроку: Розв'язування логарифмічних рівнянь
Мета уроку: формування умінь учнів розв'язувати логарифмічні рівняння різними методами: зведення логарифміч­ного рівняння до алгебраїчного;...
ЗМІСТ Вступ 3 Змістовна програма вступних випробувань 3 Критерії оцінювання 7 Література 9 Вступ
Методичні матеріали до вступних випробувань з Історії України на навчання до Дніпропетровського університету імені Альфреда Нобеля...
ЗМІСТ Вступ 3 Змістовна програма вступних випробувань 3 Критерії оцінювання 7 Література 9 Вступ
Методичні матеріали до вступних випробувань з Історії України на навчання до Дніпропетровського університету імені Альфреда Нобеля...
ЗМІСТ Вступ 3 Змістовна програма вступних випробувань 3 Критерії оцінювання 7 Література 9 Вступ
Методичні матеріали до вступних випробувань з Історії України на навчання до Дніпропетровського університету імені Альфреда Нобеля...
Тема: Введення в хімію високомолекулярних сполук
Опишіть методики визначення молекулярних мас полімерів (кріоскопія, ебуліоскопія, осмометрія, метод кінцевих груп, ультрацентрифугування,...
Додайте кнопку на своєму сайті:
Портал навчання


При копіюванні матеріалу обов'язкове зазначення активного посилання © 2013
звернутися до адміністрації
bibl.com.ua
Головна сторінка