 |
П.3. Решение одномерной ЗНО.
|
|
|
|
Нам необходимо найти минимум некоторой функции f (одной переменной) на интервале [a,b]. Будем считать, что f на данном интервале имеет ровно один минимум.
Простейший метод нахождения точки минимума – метод сечений:
Разобьем участок [a,b] на n интервалов и
рассмотрим 
. Предположим
минимум достигается при 
, тогда
новый участок поиска будет [ 
]
его снова разбиваем на новые участки
(критерий как в МПД, т.е. 
).
Рассмотрим вариант n=3 (ежу понятно,
что делить меньше чем на 3 интервала
бессмысленно).
() (*)
На самом же деле выгоднее делить интервал не таким образом, а по методу золотого сечения.
Пропорции деления (они сохраняются) были подобраны таким образом, что при переходе к новому интервалу нам необходимо вычислять значения f не в 2х новых точках, а в 1-ой, хотя при этом интервал поиска сокращается не в два раза (как было на предложенной схеме (*)), а чуть меньше, следовательно, этот вариант оказывается выгоднее, т.к. для достижения заданной точности нам придётся меньше раз вычислять значение f. 4 точки на первом шаге и по 1-ой новой точке на каждом последующем шаге, а не в 2х.
Найдём пропорции золотого сечения:
Итак, в алгебре метода золотого сечения заложены пропорции: 0,382; 0,236; 0,382.
Тема 9: Метод Монте-Карло.
П.1.Особенности метода Монте-Карло.
Главная особенностью метода Монте-Карло – то, что он в отличие от всех остальных методов вероятностный. Т.е., если во всех остальных методах мы знали, с вероятностью равной 1, что достигли заданной точности, то в методе Монте-Карло мы можем только лишь утверждать, что P – близка к единице, т.е. вероятность ошибиться, мала, но есть.
Причём, всякий раз при новом запуске метода, результат будет другим, т.к. он носит вероятностный характер. Наша основная цель научиться оценить вероятность того, что найденное значение Х, отличается от точного не более чем на 
(
).
|
|
|
Методом Монте-Карло можно решать многие задачи вычислительной математики: СЛАУ, ДУ, ЧИ и т.д.
Мы рассмотрим простейший пример применения метода Монте-Карло.
П.2.Метод Монте-Карло в ЧИ.
Обычные (невероятностные) методы ЧИ хорошо работают только лишь при интегрировании функций небольшого количества переменных. При росте количества переменных, число узлов интегрирования стремительно растёт (экспоненциально).
Например, пусть необходимо найти интеграл 10-ти переменных с шагом h=0,1 по каждому измерению:
итого 
измерений – в подобном случае применяют метод Монте-Карло.
Рассмотрим первый вариант метода Монте-Карло:
{среднему значению на кубе 
, как известно из мат. анализа среднее значение функции равно 
, следовательно, для функций многих переменных 
}.
В то же время, как известно из теории вероятности, среднее эмпирическое значение при увеличении количества испытаний стремится к точному значению.
В нашем случае эмпирическое среднее (для N испытаний)
, таким образом, для нахождения 
мы N раз находим значение функции f в N точках 
, каждая из которых имеет n координат, при этом, каждая координата – случайное число на отрезке [0,1]. Итак, random нам потребуется вызвать n*N раз.
При каждом запуске метода Монте-Карло мы будем получать новые значения , но все они 
П.2. Второй вариант метода Монте-Карло (интегрирование не по n-мерному кубу, а по некоторой произвольной n-мерной области D).
Необходимо найти:
где П – прямоугольный параллелепипед ограничивающий область D.
П= 
= 
Чтобы получить равномерное распределение на 
, берем random* 
- все остальные вычисления аналогичны случаю n-мерного куба.
Недостатки:
Основная проблема, что в предложенном выше методе мы не можем достоверно оценить вероятность отклонения от 
, мы знаем только лишь, что M()= , т.е. при бесконечном количестве испытаний = . А оценить разброс от мы не можем, т.к. не знаем дисперсию.
|
|
|
Оценить вероятность отклонения случайной величины от её мат. ожидания, можно с помощью неравенства Чебышева 
(9.1)
С ростом числа испытаний N, 
, а именно, если мы проведём N испытаний, то 
(9.2)
Если в (9.1) подставить формулу (9.2), то получим 
-не зависит от N и , зависит от g и области интегрирования D.
можно оценить, используя различные способы, например, найти эмпирическое значение дисперсии.
|
|
|
