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

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

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

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

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

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

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

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

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

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

Оптимизация

Применение в физике

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

Построение кривой по точкам. Интерполяционный полином Лагранжа. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.

Интерполяцио́нныймногочле́нЛагра́нжа — многочлен минимальной степени, принимающий данные значения в данном наборе точек. Для пар чисел , где все различны, существует единственный многочлен степени не более , для которого .

В простейшем случае ( ) — это линейный многочлен, график которого — прямая, проходящая через две заданные точки.

Определение

Этот пример показывает интерполяционный многочлен Лагранжа для четырёх точек (-9,5), (-4,2), (-1,-2) и(7,9), а также полиномы y_i l_i(x), каждый из которых проходит через одну из выделенных точек, и принимает нулевое значение в остальных x_j

Лагранж предложил способ вычисления таких многочленов:

где базисные полиномы определяются по формуле:

обладают следующими свойствами:

§ являются многочленами степени

§

§ при

Отсюда следует, что , как линейная комбинация , может иметь степень не больше , и , Q.E.D.

Применения

Полиномы Лагранжа используются для интерполяции, а также для численного интегрирования.

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

В частности,

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