Геометрический алгоритм Монте-Карло интегрирования
Рисунок 3. Численное интегрирование функции методом Монте-Карло
Для определения площади под графиком функции можно использовать следующий стохастический алгоритм:
§ ограничим функцию прямоугольником (n-мерным параллелепипедом в случае многих измерений), площадь которого можно легко вычислить;
§ «набросаем» в этот прямоугольник (параллелепипед) некоторое количество точек ( штук), координаты которых будем выбирать случайным образом;
§ определим число точек ( штук), которые попадут под график функции;
§ площадь области, ограниченной функцией и осями координат, даётся выражением
Для малого числа измерений интегрируемой функции производительность Монте-Карло интегрирования гораздо ниже, чем производительность детерминированных методов. Тем не менее, в некоторых случаях, когда функция задана неявно, а необходимо определить область, заданную в виде сложных неравенств, стохастический метод может оказаться более предпочтительным.
Использование выборки по значимости
При том же количестве случайных точек, точность вычислений можно увеличить, приблизив область, ограничивающую искомую функцию, к самой функции. Для этого необходимо использовать случайные величины с распределением, форма которого максимально близка к форме интегрируемой функции. На этом основан один из методов улучшения сходимости в вычислениях методом Монте-Карло: выборка по значимости.
Оптимизация
Применение в физике
Компьютерное моделирование играет в современной физике важную роль и метод Монте-Карло является одним из самых распространённых во многих областях от квантовой физики до физики твёрдого тела, физики плазмы и астрофизики.
Построение кривой по точкам. Интерполяционный полином Лагранжа. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.
Интерполяцио́нныймногочле́нЛагра́нжа — многочлен минимальной степени, принимающий данные значения в данном наборе точек. Для пар чисел
, где все
различны, существует единственный многочлен
степени не более
, для которого
.
В простейшем случае ( ) — это линейный многочлен, график которого — прямая, проходящая через две заданные точки.
Определение
Этот пример показывает интерполяционный многочлен Лагранжа для четырёх точек (-9,5), (-4,2), (-1,-2) и(7,9), а также полиномы yi li(x), каждый из которых проходит через одну из выделенных точек, и принимает нулевое значение в остальных xj
Лагранж предложил способ вычисления таких многочленов:
где базисные полиномы определяются по формуле:
обладают следующими свойствами:
§ являются многочленами степени
§
§ при
Отсюда следует, что , как линейная комбинация
, может иметь степень не больше
, и
, Q.E.D.
Применения
Полиномы Лагранжа используются для интерполяции, а также для численного интегрирования.
Пусть для функции известны значения
в некоторых точках. Тогда мы можем интерполировать эту функцию как
В частности,
Значения интегралов от не зависят от
, и их можно вычислить заранее, зная последовательность
.