Адаптивная квадратура

Адаптивная квадратура — это метод численного интегрирования , в котором интеграл от функции $f(x)$ аппроксимируется с использованием правил статических квадратур на адаптивно уточненных подинтервалах области интегрирования. Как правило, адаптивные алгоритмы так же эффективны и действенны, как и традиционные алгоритмы для подынтегральных выражений с «хорошим поведением», но также эффективны для подынтегральных выражений с «плохим поведением», для которых традиционные алгоритмы могут дать сбой.

Общая схема

Адаптивная квадратура следует общей схеме.

1. procedure integrate ( f, a, b, τ )
2.      $Q\approx \int _{a}^{b}f(x)\,\mathrm {d} x$ 
3.      $\varepsilon \approx \left|Q-\int _{a}^{b}f(x)\,\mathrm {d} x\right|$ 
4.     if ε > τ then
5.         m = (a + b) / 2
6.         Q = integrate(f, a, m, τ/2) + integrate(f, m, b, τ/2)
7.     endif
8.     return Q

Приближение $Q$ к интегралу $f(x)$ за интервал $[a,b]$ вычисляется (строка 2), а также оценка ошибки $\varepsilon$ (строка 3). Если предполагаемая погрешность превышает требуемый допуск $\tau$ (строка 4), интервал подразделяется (строка 5) и квадратура наносится на обе половины отдельно (строка 6). Возвращается либо первоначальная оценка, либо сумма рекурсивно вычисленных половин (строка 7).

Важными компонентами являются квадратур само правило .

Q\approx \int _{a}^{b}f(x)\,\mathrm {d} x,

оценщик ошибок

\varepsilon \approx \left|Q-\int _{a}^{b}f(x)\,\mathrm {d} x\right|,

и логика принятия решения о том, какой интервал разделить и когда завершить.

Существует несколько вариантов этой схемы. Самые распространенные будут рассмотрены позже.

Основные правила

Правила квадратур обычно имеют вид

Q_{n}\quad =\quad \sum _{i=0}^{n}w_{i}f(x_{i})\quad \approx \quad \int _{a}^{b}f(x)\,\mathrm {d} x

где узлы $x_{i}$ и веса $w_{i}$ обычно рассчитываются заранее.

В простейшем случае формулы Ньютона–Котеса четной степени, где узлы используются $x_{i}$ расположены равномерно в интервале:

x_{i}=a+{\frac {b-a}{n}}i.

При использовании таких правил точки, в которых $f(x)$ было оценено, может быть повторно использовано при рекурсии:

Аналогичная стратегия используется с квадратурой Кленшоу – Кертиса , где узлы выбираются как

x_{i}=\cos \left({\frac {2i}{n}}\pi \right).

Или, когда квадратура Фейера используется ,

x_{i}=\cos \left({\frac {2(i+0.5)}{n+1}}\pi \right).

Также могут использоваться другие правила квадратуры, такие как квадратура Гаусса или квадратура Гаусса-Кронрода .

Алгоритм может решить использовать разные квадратурные методы на разных подинтервалах, например, используя метод высокого порядка только там, где подынтегральная функция является гладкой.

Оценка ошибки

Некоторые квадратурные алгоритмы генерируют последовательность результатов, которая должна приближаться к правильному значению. В противном случае можно использовать «нулевое правило», которое имеет форму приведенного выше правила квадратур, но значение которого будет равно нулю для простого подынтегрального выражения (например, если подынтегральное выражение было многочленом соответствующей степени).

Видеть:

Экстраполяция Ричардсона (см. также метод Ромберга )
Нулевые правила
Алгоритм Эпсилон

Логика подразделения

«Локальная» адаптивная квадратура делает допустимую ошибку для данного интервала пропорциональной длине этого интервала. Этому критерию может быть трудно удовлетворить, если подынтегральные выражения плохо ведут себя только в нескольких точках, например, с разрывами в несколько шагов. В качестве альтернативы можно потребовать только того, чтобы сумма ошибок на каждом из подинтервалов была меньше, чем требует пользователь. Это будет «глобальная» адаптивная квадратура. Глобальная адаптивная квадратура может быть более эффективной (с использованием меньшего количества вычислений подынтегральной функции), но, как правило, ее сложнее программировать и может потребоваться больше рабочего пространства для записи информации о текущем наборе интервалов.

См. также

Адаптивное числовое дифференцирование
Адаптивный размер шага в ODE
Адаптивный метод Симпсона на примере адаптивной квадратуры
QUADPACK — библиотека FORTRAN, использующая глобальную адаптивную квадратуру.

Примечания

Ссылки

Маккиман, Уильям (декабрь 1962 г.). Готлиб, Кальвин (ред.). «Алгоритм 145: Адаптивное численное интегрирование по правилу Симпсона» . Сообщения ACM (периодическое издание). 5 (12). Нью-Йорк : ACM : 604–605. дои : 10.1145/355580.369102 . eISSN 1557-7317 . ISSN 0001-0782 . OCLC 1011805770 .
Джон Р. Райс. Металгоритм для адаптивной квадратуры. Журнал ACM 22 (1), стр. 61–82 (январь 1975 г.).
Пресс, WH; Теукольский, С.А.; Феттерлинг, WT; Фланнери, BP (2007), «Раздел 4.7. Адаптивная квадратура» , Численные рецепты: искусство научных вычислений (3-е изд.), Нью-Йорк: Cambridge University Press, ISBN 978-0-521-88068-8