Выбор метода для числовой квадратуры

12

Существует несколько семейств методов для числовой квадратуры. Если у меня есть определенный класс подынтегральных функций, как выбрать идеальный метод?

Какие уместные вопросы следует задать как о подынтегральном выражении (например, является ли оно гладким? Есть ли у него особенности?), Так и о вычислительной проблеме (например, устойчивость к ошибкам, вычислительный бюджет)?

Как ответы на эти вопросы исключают или продвигают различные семейства методов? Для простоты рассмотрим только единичные или низкоразмерные интегралы.

Например, статья в Википедии о QUADPACK гласит, что довольно общая QAGSпроцедура « использует глобальную адаптивную квадратуру, основанную на квадратуре Гаусса-Кронрода из 21 точки в каждом подинтервале, с ускорением по алгоритму Эпсилона Питера Уинна »

Как было принято это решение? Как можно принимать аналогичные решения, когда известно больше?

MRocklin
источник
1
Вероятно, требуется более конкретная информация, чтобы ответить на этот вопрос должным образом. Не существует единого критерия, подходящего для всех, квадратура Гаусса часто хорошо работает для очень гладких задач, тогда как другие квадратуры могут использоваться при наличии умеренных особенностей. Но если вы периодический, то простая трапеция может обрезать его.
Reid.Atcheson
2
@ Reid.Atcheson, я думаю, ты сейчас отвечаешь на вопрос. Я не спрашиваю, какой метод лучше, я спрашиваю, какие вопросы вы бы задали и что бы вам ответили эти ответы? Как подходить к такого рода проблемам в целом?
MRocklin

Ответы:

11

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

Но если вы знаете «форму» или «тип» вашего интеграта, вы можете адаптировать свой метод к тому, что вам нужно, чтобы вычислительные затраты были ограничены для необходимой точности. Итак, что вам нужно посмотреть:

интегрант:

  • Гладкость: может ли она быть аппроксимирована (хорошо) полиномом из семейства ортогональных полиномов (если это так, квадратура Гаусса будет успешной)
  • Особенности: можно ли разбить интеграл на интегралы только с особенностями конечной точки (если так, то правило IMT или двойная экспоненциальная квадратура будут хороши на каждом подинтервале)
  • Вычислительная стоимость для оценки?
  • Можно ли вычислить подынтегральное выражение? Или доступны только ограниченные точечные данные?
  • Высоко колебательный интеграл: ищите методы типа Левина.

|xc|αcα

Интервал интегрирования: конечный, полубесконечный или бесконечный. В случае полубесконечных или бесконечных интервалов, могут ли они быть сведены к конечному интервалу путем преобразования переменной? Если нет, то полиномы Лагерра или Эрмита можно использовать в квадратурном подходе Гаусса.

У меня нет ссылки на реальную блок-схему для квадратуры в целом, но книга QUADPACK (не страницы Netlib, а настоящая книга) содержит блок-схему для выбора соответствующей подпрограммы на основе интеграла, который вы хотите оценить. Книга также описывает выбор алгоритмов, сделанных Piessens et al. для разных процедур.

Для низкоразмерных интегралов обычно используется вложенная одномерная квадратура. В частном случае двумерных интегралов (кубатуры) существуют правила интегрирования для разных случаев областей интегрирования. Р. Кулс собрал большое количество правил в своей энциклопедии кубатурных формул и является основным автором пакета Cubpack . Для больших размерных интегралов обычно прибегают к методам типа Монте-Карло. Однако, как правило, для получения разумной точности требуется очень большое количество оценок подынтегральных функций. Для низкоразмерных интегралов методы приближения, такие как квадратура / кубатура / вложенная квадратура, часто превосходят эти стохастические методы.

Общие интересные ссылки:

  1. Quadpack, Piessens, Роберт; де Донкер-Капенга, Элиз; Überhuber, Кристоф У .; Каханер, Дэвид (1983). QUADPACK: пакет подпрограмм для автоматической интеграции. Springer-Verlag. ISBN 978-3-540-12553-2
  2. Методы численного интегрирования: второе издание, доктор Дэвис и доктор Рабиновиц, 2007, Dover Books по математике, ISBN 978-0486453392
GertVdE
источник
1
Хороший ответ. Почему QUADPACK выбрал 21-точечный метод Гаусса-Кронрода, в частности? Почему магический номер?
MRocklin
@MRocklin: я думаю, что это был хороший компромисс между точностью и эффективностью: вы не хотите перебивать свое квадратурное правило (дорого), но не хотите, чтобы оно было слишком слабым (слишком много подразделений в адаптивной части). ). Для завершения: в процедуре QAG пользователь должен указать квадратурное правило; в QAGS (с экстраполяцией) по умолчанию используется правило из 21 пункта, но это можно отменить, используя расширенную процедуру вызова QAGSE.
GertVdE
1
@GertVdE Очень хороший ответ. Можете ли вы подробнее рассказать об использовании Кленшоу-Кертиса для захвата сингулярных сингулярностей или предоставить ссылки? Я не слышал, чтобы это использовалось таким образом, и не смог найти подробностей из быстрого поиска в Google. Спасибо!
OscarB
3
@OscarB: извините за долгую задержку, был без доступа к сети (ах хорошая жизнь). См. Книгу Quadpack §2.2.3.3 и далее; Branders, Piessens, "Расширение квадратуры Кленшоу-Кертиса", 1975, J.Comp.Appl.Math., 1, 55-65; Piessens, Branders, «Оценка и применение некоторых модифицированных моментов», 1973, BIT, 13, 443-450; Piessens, Branders, "Вычисление осциллирующих интегралов", 1975, J.Comp.Appl.Math., 1, 153-164. Если вы выполните литературный поиск «Роберта Писсенса» где-то между 1972 и 1980 годами, вы найдете много интересных работ.
GertVdE