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

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

Общая схема

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

1. процедура интегрирования ( f, a, b, τ )2.
3.
4. если ε > τ , то ${\displaystyle Q\approx \int _{a}^{b}f(x)\,\mathrm {d} x}$ ${\displaystyle \varepsilon \approx \left|Q-\int _{a}^{b}f(x)\,\mathrm {d} x\right|}$  5. м = (а + б) / 26. Q = интегрировать(f, a, m, τ/2) + интегрировать (f, m, b, τ/2)7. конецесли
8. возврат Q

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

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

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

оценка погрешности

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Оценка погрешности

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

Видеть:

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

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

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

Смотрите также

• Адаптивная численная дифференциация
• Адаптивный размер шага в ОДУ
• Метод адаптивного Симпсона для примера адаптивной квадратуры
• QUADPACK , библиотека FORTRAN, которая использует глобальную адаптивную квадратуру

Примечания

Ссылки

• McKeeman, William (декабрь 1962 г.). Gotlieb, Calvin (ред.). «Алгоритм 145: Адаптивное численное интегрирование по правилу Симпсона». Communications of the ACM (Periodical). 5 (12). Нью-Йорк : ACM : 604–605. doi : 10.1145/355580.369102 . eISSN  1557-7317. ISSN  0001-0782. OCLC  1011805770.
• Джон Р. Райс. Металгоритм для адаптивной квадратуры. Журнал ACM 22(1) стр. 61-82 (январь 1975 г.).
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), «Раздел 4.7. Адаптивная квадратура», Numerical Recipes: The Art of Scientific Computing (3-е изд.), Нью-Йорк: Cambridge University Press, ISBN 978-0-521-88068-8