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

Эта статья включает список ссылок , связанных материалов или внешних ссылок , но ее источники остаются неясными, поскольку в ней отсутствуют встроенные цитаты . Пожалуйста, помогите улучшить эту статью, введя более точные цитаты. ( Август 2019 ) ( Узнайте, как и когда удалять это сообщение )

Адаптивная квадратура — это метод численного интегрирования , в котором интеграл функции аппроксимируется с использованием статических квадратурных правил на адаптивно уточненных подынтервалах области интегрирования. Как правило, адаптивные алгоритмы столь же эффективны и действенны , как и традиционные алгоритмы для «хорошо себя ведущих» интегрантов, но также эффективны для «плохо себя ведущих» интегрантов, для которых традиционные алгоритмы могут потерпеть неудачу.${\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 [а,б]}$${\displaystyle \varepsilon}$${\displaystyle \тау}$

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

${\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