Методы парабол (Симпсона) и более высоких степеней (Ньютона - Котеса)
Материал из MachineLearning.
Содержание |
Введение
Постановка математической задачи
Задача численного интегрирования состоит в нахождении приближенного значения интеграла
где - заданная и интегрируемая на отрезке функция. На отрезке вводится сетка и в качестве приближенного значения интеграла рассматривается число
где - значения функции в узлах , где - весовые множители, зависящие только от узлов, но не зависящие от выбора . Формула (2) называется квадратурной формулой. Задача численного интегрирования при помощи квадратур состоит в отыскании таких узлов и таких весов , чтобы погрешность квадратурной формулы
была минимальной по модулю для функции из заданного класса (величина зависит от гладкости ). Погрешность зависит как от расположения узлов, так и от выбора весовых коэффициентов. Введем на равномерную сетку с шагом , т.е. множество точек , и представим интеграл (1) в виде суммы интегралов по частичным отрезкам:
Для построения формулы численного интегрирования на всм отрезке достаточно построить квадратурную формулу для интеграла
на частичном отрезке и воспользоваться свойством (3).
Построение квадратурных формул
В силу вышеизложенного выше, вычисление приближенного значения интеграла производится при помощи квадратурной формулы
Данную формулу при помощи замены можно привести к стандартному виду
В общем случае узлы и веса неизвестны и подлежат определению.
Рассмотрим случай, когда узлы заданы и требуется найти веса квадратурной формулы . Будем пользоваться требованием: формула (5) должна быть точной для любого полинома степени . Для того чтобы полином степени удовлетворял данному требованию, достаточно потребовать, чтобы квадратурная формула была точной для любого одночлена степени . Учитывая, что , получаем уравнение
Эта система имеет единственное решение, так как ее определителем является определитель Вандермонда, отличный от нуля если нет совпадающих узлов, .
Так, полагая , имеем систему , решением которой являются веса формулы Симпсона: . Таким образом, формула Симпсона является точной для полинома второй степени. Однако, в силу симметрии, она является точной и для всех полиномов третьей степени:
так как она точна для :
Формулы треугольника и трапеции точны для линейной функции,т.е. для полинома первой степени, в чем легко убедиться непосредственно. В общем случае в качестве можно выбрать интерполяционный полином Лагранжа
где - интерполяционный коэффициент Лагранжа. Из равенства
видно, что формула (5) верна для полинома степени , если весовые коэффициенты определяются по формуле
Формулы такого типа называют квадратурными формулами Котеса.
Изложение метода
Применение квадратурных формул
Вернемся к рассмотрению интеграла (1). Как было показано выше, данный интеграл заменой сводится к интегралу на единичном отрезке , а следовательно легко обобщить формулы для приближенного вычисления интеграла на единичном отрезке на произвольный. Применим аппарат квадратурных формул. Пусть задано равномерное разбиение отрезка с шагом , где обозначим . Пусть также выбрана некоторая квадратурная формула Ньютона-Котеса (то есть выбрана степень полинома , а следовательно каждый полином строится по точке сетки). Мы также считаем, что данный набор из точки можно разбить на поднаборы по точек с совпадающими крайним, то есть
- где
Тогда, суммируя значения квадратур на каждом поднаборе, получим приближенное значение искомого интеграла. Если обозначить весовые множители то приближенное значение интеграла можно записать в виде двойной суммы
Данный алгоритм естественным образом обобщается на случай, когда , где , а на каждом отрезке задана равномерная сетка. Тогда искомый интеграл равен
а на каждом из частичных отрезков приближенное значение интеграла вычисляется при помощи квадратурных формул.
Примеры квадратурных формул
Приведем примеры квадратурных формул Котеса на равномерной сетке с шагом , где обозначим :
- для 3 точек(метод Симпсона),
- для 4 точек,
- для 5 точек,
- для 6 точек,
- для 7 точек,
- для 8 точек,
- для 9 точек,
- для 10 точек,
Анализ метода
Числовой пример
Рекомендации программисту
Автоматический выбор шага интегрирования с помощью апостериорной оценки погрешности методом Рунге
Величина погрешности численного интегрирования зависит как от шага сетки , так и от гладкости подынтегральной функции . В величину погрешности, кроме входит также величина , которая может сильно меняться на отрезке и заранее неизвестна. Для уменьшения величины погрешности, можно измельчить сетку на заданном отрезке. Но при этом необходимо апостериорно оценивать погрешность. Такую оценку погрешности можно осуществить методом Рунге. Рассмотрим применение какой-то квадратурной формулы на частичном отрезке . Обозначим за значение интеграла на всем отреpке, за значение интеграла на -ом частичном отрезке, за приближенное значение интеграла на всем отрезке, полученное при помощи заданной квадратурной формулы и равномерном сетки с шагом , а за приближенное значение интеграла на -ом частичном отрезке. Пусть данная квадратурная формула на данном частичном отрезке имеет порядок точности , то есть
где с - некоторая константа. Тогда
откуда получаем
Пусть используется составная квадратурная формула
причем на всех частичных отрезках используются квадратурные формулы с одним и тем же порядком точности (или же,в частности, одна и та же формула). Проведем на каждом частичном отрезке вычисления дважды - один раз с шагом , второй раз с шагом и апостериорно оценим погрешность по правилу Рунге ( 8 ). Если для заданного при будут выполняться неравенства
то получим
то есть будет достигнута заданная точность .
Если же на каком-то из частичных отрезков оценка ( 9 ) не будет выполняться, то шаг на этом отрезке надо измельчить еще в два раза и снова оценить погрешность. Измельчение сетки на данном отрезке следует проводить до тех пор, пока не будет достигнута оценка вида ( 9 ). Заметим, что для некоторой функции такое измельчение может продолжаться слишком долго. Поэтому в соответствующей программе следует предусмотреть ограничение сверху на число измельчений.
Таким образом, автоматический выбор шага интегрирования приводит к тому, что интегрирование ведется с крупным шагом на участках плавного изменения функции и с мелким шагом - на участках быстрого изменения . Это позволяет при заданной точности уменьшить количество вычислений значений по сравнению с расчетом на сетке с постоянным шагом. Подчеркнем, что для нахождения сумм не надо пересчитывать значения во всех узлах, достаточно вычислять только в новых узлах.
Заключение
Список литературы
- А.А.Самарский, А.В.Гулин. Численные методы М.: Наука, 1989.
- А.А.Самарский. Введение в численные методы М.: Наука, 1982.
- http://mathworld.wolfram.com/Newton-CotesFormulas.html