Методы парабол (Симпсона) и более высоких степеней (Ньютона - Котеса)
Материал из MachineLearning.
Строка 103: | Строка 103: | ||
::<tex>\int_a^b{f(x)dx} = \sum_{i=0}^K{\int_{a_i}^{b_i}{f(x)dx}},</tex> | ::<tex>\int_a^b{f(x)dx} = \sum_{i=0}^K{\int_{a_i}^{b_i}{f(x)dx}},</tex> | ||
- | а на каждом из отрезков приближенное значение интеграла вычисляется при помощи квадратурных формул. | + | а на каждом из ''частичных отрезков'' <tex>[a_i,b_i]</tex> приближенное значение интеграла вычисляется при помощи квадратурных формул. |
=== Примеры квадратурных формул === | === Примеры квадратурных формул === | ||
Строка 148: | Строка 148: | ||
== Рекомендации программисту == | == Рекомендации программисту == | ||
+ | |||
+ | === Автоматический выбор шага интегрирования с помощью апостериорной оценки погрешности методом Рунге === | ||
+ | |||
+ | Величина погрешности численного интегрирования зависит как от шага сетки <tex>h</tex>, так и от гладкости подынтегральной функции <tex>f(x)</tex>. В величину погрешности, кроме <tex>h</tex> входит также величина <tex>f^{(p)}(\xi)</tex>, которая может сильно меняться на отрезке <tex>[a,b]</tex> и заранее неизвестна. Для уменьшения величины погрешности, можно измельчить сетку на заданном отрезке. Но при этом необходимо апостериорно оценивать погрешность. Такую оценку погрешности можно осуществить ''методом Рунге''. Рассмотрим применение какой-то квадратурной формулы на частичном отрезке <tex>[x_{i-1},x_i]</tex>. Обозначим за <tex>I</tex> значение интеграла на всем отреpке, за <tex>I_i</tex> значение интеграла на <tex>i</tex>-ом частичном отрезке, за <tex>I_h</tex> приближенное значение интеграла на всем отрезке, полученное при помощи заданной квадратурной формулы и равномерном сетки с шагом <tex>h</tex>, а за <tex>I_{h,i}</tex> приближенное значение интеграла на <tex>i</tex>-ом частичном отрезке. Пусть данная квадратурная формула на данном частичном отрезке имеет порядок точности <tex>m</tex>, то есть | ||
+ | |||
+ | ::<tex>I_i-I_{h,i} \approx ch^m,</tex> | ||
+ | |||
+ | где с <tex>c</tex> - некоторая константа. Тогда | ||
+ | |||
+ | ::<tex>I_i-I_{ \frac{h}{2},i} \approx c( \frac{h}{2} )^m,</tex> | ||
+ | |||
+ | откуда получаем | ||
+ | |||
+ | ::<tex>I_i-I_{h,i} \approx 2^m(I_i-I_{ \frac{h}{2},i})</tex> | ||
+ | |||
+ | {{ eqno | 8 }} | ||
+ | ::<tex>I_i-I_{ \frac{h}{2},i} \approx \frac {I_{ \frac{h}{2},i} - I_{h,i}} {2^m-1}.</tex> | ||
+ | |||
+ | Пусть используется составная квадратурная формула | ||
+ | |||
+ | ::<tex>I \approx I_h=\sum_{i=1}^N{I_{h,i}},</tex> | ||
+ | |||
+ | причем на всех частичных отрезках используются квадратурные формулы с одним и тем же порядком точности (или же,в частности, одна и та же формула). Проведем на каждом частичном отрезке <tex>[x_{i-1},x_i]</tex> вычисления дважды - один раз с шагом <tex>h_i</tex>, второй раз с шагом <tex>\frac{h_i}{2}</tex> и апостериорно оценим погрешность по правилу Рунге {{ eqref | 8 }}. Если для заданного <tex>\varepsilon >0</tex> при <tex>i=1,2, \ldots N</tex> будут выполняться неравенства | ||
+ | |||
+ | {{eqno | 9 }} | ||
+ | ::<tex>|I_i-I_{ \frac{h}{2},i}| \approx \frac {|I_{ \frac{h}{2},i} - I_{h,i}|} {2^m-1} \le \frac {\varepsilon h_i} {b-a},</tex> | ||
+ | |||
+ | то получим | ||
+ | |||
+ | ::<tex>|I-I_{\frac{h}{2}}| \le \frac {\varepsilon}{b-a} \sum_{i=1}^N{h_i} \le \varepsilon,</tex> | ||
+ | |||
+ | то есть будет достигнута заданная точность <tex>\varepsilon</tex>. | ||
+ | |||
+ | Если же на каком-то из частичных отрезков оценка {{ eqref | 9 }} не будет выполняться, то шаг на этом отрезке надо измельчить еще в два раза и снова оценить погрешность. Измельчение сетки на данном отрезке следует проводить до тех пор, пока не будет достигнута оценка вида {{ eqref | 9 }}. Заметим, что для некоторой функции <tex>f(x)</tex> такое измельчение может продолжаться слишком долго. Поэтому в соответствующей программе следует предусмотреть ограничение сверху на число измельчений. | ||
+ | |||
+ | Таким образом, автоматический выбор шага интегрирования приводит к тому, что интегрирование ведется с крупным шагом на участках плавного изменения функции <tex>f(x)</tex> и с мелким шагом - на участках быстрого изменения <tex>f(x)</tex>. Это позволяет при заданной точности <tex>\epsilon</tex> уменьшить количество вычислений значений <tex>f(x)</tex> по сравнению с расчетом на сетке с постоянным шагом. Подчеркнем, что для нахождения сумм <tex>I_{ \frac{h}{2},i}</tex> не надо пересчитывать значения <tex>f(x)</tex> во всех узлах, достаточно вычислять <tex>f(x)</tex> только в новых узлах. | ||
== Заключение == | == Заключение == |
Версия 17:09, 18 октября 2008
Содержание |
Введение
Постановка математической задачи
Задача численного интегрирования состоит в нахождении приближенного значения интеграла
где - заданная и интегрируемая на отрезке функция. На отрезке вводится сетка и в качестве приближенного значения интеграла рассматривается число
где - значения функции в узлах , где - весовые множители, зависящие только от узлов, но не зависящие от выбора . Формула (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