Численное интегрирование
Дифференциальные уравнения |
---|
Объем |
Классификация |
Решение |
Люди |
В анализе включает численное интегрирование в себя широкое семейство алгоритмов вычисления численного значения определенного интеграла .Термин «числовая квадратура» (часто сокращенно « квадратура ») является более или менее синонимом «численного интегрирования», особенно применительно к одномерным интегралам. Некоторые авторы называют численное интегрирование по более чем одному измерению кубатурой ; [1] другие используют «квадратуру», чтобы включить интеграцию более высоких измерений.
Основная проблема численного интегрирования состоит в вычислении приближенного решения определенного интеграла.
с заданной степенью точности. Если f ( x ) — гладкая функция, интегрированная по небольшому числу измерений, а область интегрирования ограничена, существует множество методов аппроксимации интеграла с желаемой точностью.
Численное интегрирование имеет корни в геометрической задаче нахождения квадрата той же площади, что и заданная плоская фигура ( квадратура или возведение в квадрат ), как и в квадратуре круга .Этот термин также иногда используется для описания численного решения дифференциальных уравнений .
Мотивация и потребность
[ редактировать ]Существует несколько причин для проведения численного интегрирования, в отличие от аналитического интегрирования путем нахождения первообразной :
- Подынтегральная функция f ( x ) может быть известна только в определенных точках, например, полученных путем выборки . По этой причине некоторым встроенным системам и другим компьютерным приложениям может потребоваться численная интеграция.
- Формула подынтегральной функции может быть известна, но может оказаться трудным или невозможным найти первообразную, которая является элементарной функцией . Примером такого подынтегрального выражения является f ( x ) = exp(− x 2 ) , первообразная которой ( функция ошибки , умноженная на константу) не может быть записана в элементарной форме .
- Первообразную можно найти символически, но, возможно, проще вычислить численную аппроксимацию, чем вычислить первообразную. Это может иметь место, если первообразная задана как бесконечный ряд или произведение, или если для ее вычисления требуется специальная функция , которая недоступна.
История
[ редактировать ]Термин «числовое интегрирование» впервые появляется в 1915 году в публикации «Курс интерполяции и числового интегрирования для математической лаборатории» Дэвида Гибба . [2]
«Квадратура» — исторический математический термин, означающий вычисление площади. Квадратурные задачи послужили одним из основных источников математического анализа . Математики Древней Греции , согласно учению Пифагора , понимали под вычислением площади процесс построения геометрически квадрата, имеющего такую же площадь ( возведение в квадрат ). Именно поэтому процесс получил название «квадратура». Например, квадратура круга , Луна Гиппократа , Квадратура Параболы . Это построение необходимо производить только с помощью циркуля и линейки .
Древние вавилоняне использовали правило трапеций для интегрирования движения Юпитера по эклиптике . [3]
Для квадратуры прямоугольника со сторонами a и b необходимо построить квадрат со стороной ( среднее геометрическое a b и ) . Для этого можно воспользоваться следующим фактом: если нарисовать окружность, диаметр которой равен сумме a и b , то высота BH (от точки их соединения до пересечения с окружностью) равна их среднему геометрическому. Подобная геометрическая конструкция решает задачу квадратуры для параллелограмма и треугольника.
Гораздо сложнее задачи квадратуры для криволинейных фигур. В XIX веке было доказано, что квадратура круга с помощью циркуля и линейки невозможна. Тем не менее, для некоторых фигур (например, Луны Гиппократа ) квадратуру можно выполнить. Квадратуры поверхности сферы и отрезок параболы, выполненные Архимедом, стали высшим достижением античного анализа.
- Площадь поверхности сферы равна четырехкратной площади большого круга этой сферы.
- Площадь отрезка параболы, отрезанного от него прямой, равна 4/3 площади вписанного в этот отрезок треугольника.
Для доказательства результатов Архимед использовал исчерпывания Евдокса метод .
В средневековой Европе квадратура означала вычисление площади любым методом. Чаще метод неделимых использовался ; он был менее строгим, но более простым и мощным. С его помощью Галилео Галилей и Жиль де Роберваль нашли площадь циклоидной арки, Грегуар де Сен-Винсент исследовал площадь под гиперболой ( Opus Geometricum , 1647), а Альфонс Антонио де Сараса , ученик и комментатор де Сен-Винсента, отметил отношение этой площади к логарифмам .
Джон Уоллис алгебраизировал этот метод: в своей серии «Arithmetica Infinitorum » (1656 г.) он написал то, что мы теперь называем определенным интегралом , и вычислил их значения. Исаак Барроу и Джеймс Грегори добились дальнейшего прогресса: квадратуры для некоторых алгебраических кривых и спиралей . Христиан Гюйгенс успешно выполнил квадратуру некоторых тел вращения .
Квадратура гиперболы Сен-Винсента и де Сарасы предоставила новую функцию — натуральный логарифм , имеющую решающее значение.
С изобретением интегрального исчисления появился универсальный метод расчета площади. В ответ термин «квадратура» стал традиционным, и вместо него современная фраза « вычисление одномерного определенного интеграла более распространена ».
Методы одномерных интегралов
[ редактировать ]Правило квадратур — это аппроксимация определенного интеграла функции , обычно выражаемого как взвешенная сумма значений функции в определенных точках области интегрирования.
Методы численного интегрирования обычно можно описать как объединение оценок подынтегральной функции для получения приближения к интегралу. Подынтегральная функция оценивается в конечном наборе точек, называемых точками интегрирования , и взвешенная сумма этих значений используется для аппроксимации интеграла. Точки интегрирования и веса зависят от конкретного используемого метода и точности, требуемой от аппроксимации.
Важной частью анализа любого метода численного интегрирования является изучение поведения ошибки аппроксимации в зависимости от количества оценок подынтегральной функции. Метод, который дает небольшую ошибку при небольшом количестве оценок, обычно считается лучшим. Уменьшение количества вычислений подынтегрального выражения уменьшает количество задействованных арифметических операций и, следовательно, уменьшает общую ошибку округления . Кроме того, каждая оценка требует времени, а подынтегральная функция может быть сколь угодно сложной.
Квадратурные правила, основанные на ступенчатых функциях
[ редактировать ]Численное интегрирование «грубой силы» может быть выполнено, если подынтегральное выражение достаточно хорошо ведет себя (т.е. кусочно -непрерывно и имеет ограниченную вариацию ), вычисляя подынтегральное выражение с очень небольшими приращениями.
Этот простейший метод аппроксимирует функцию ступенчатой функцией (кусочно-постоянной функцией или сегментированным полиномом нулевой степени), проходящей через точку . Это называется правилом средней точки или правилом прямоугольника.
Правила квадратур, основанные на интерполирующих функциях
[ редактировать ]Большой класс квадратурных правил можно получить путем построения интерполирующих функций, которые легко интегрировать. Обычно эти интерполирующие функции являются полиномами . На практике, поскольку полиномы очень высокой степени имеют тенденцию к резким колебаниям , используются только полиномы низкой степени, обычно линейные и квадратичные.
Интерполирующая функция может быть прямой линией ( аффинная функция , т.е. многочлен степени 1)проходя через точки и .Это называется правилом трапеций
Для любого из этих правил мы можем сделать более точное приближение, разбив интервал в какое-то число подинтервалов, вычисляя приближение для каждого подинтервала, а затем суммируя все результаты. Это называется составным правилом , расширенным правилом или повторяющимся правилом . Например, составное правило трапеций можно сформулировать как
где подинтервалы имеют вид с и Здесь мы использовали подинтервалы одинаковой длины но можно также использовать интервалы различной длины .
Интерполяция с полиномами, вычисляемыми в равноотстоящих друг от друга точках дает формулы Ньютона-Котеса , примерами которых являются правило прямоугольников и правило трапеций. Правило Симпсона , основанное на полиноме 2-го порядка, также является формулой Ньютона-Котеса.
Правила квадратур с одинаково расположенными точками обладают очень удобным свойством вложенности . Соответствующее правило с каждым разделенным интервалом включает все текущие точки, поэтому эти значения подынтегральной функции можно использовать повторно.
Если мы позволим интервалам между точками интерполяции варьироваться, мы обнаружим другую группу квадратурных формул, таких как квадратурные формулы Гаусса . Правило квадратуры Гаусса обычно более точное, чем правило Ньютона-Котеса, которое использует то же количество оценок функции, если подынтегральная функция гладкая (т. е. если она достаточно дифференцируема). Другие квадратурные методы с различными интервалами включают квадратурные методы Кленшоу – Кертиса (также называемые квадратурами Фейера), которые имеют гнездо.
Квадратурные правила Гаусса не являются вложенными, в отличие от связанных с ними квадратурных формул Гаусса – Кронрода .
Адаптивные алгоритмы
[ редактировать ]Методы экстраполяции
[ редактировать ]Точность квадратурного правила типа Ньютона-Котеса обычно зависит от количества оценочных точек. Результат обычно становится более точным по мере увеличения количества оценочных точек или, что то же самое, по мере уменьшения ширины шага между точками. Естественно задаться вопросом, каким был бы результат, если бы размер шага приблизился к нулю. На этот вопрос можно ответить, экстраполировав результат на основе двух или более ненулевых размеров шага, используя методы последовательного ускорения, такие как экстраполяция Ричардсона . Функция экстраполяции может быть полиномиальной или рациональной функцией . Методы экстраполяции более подробно описаны Стоером и Булиршем (раздел 3.4) и реализованы во многих процедурах библиотеки QUADPACK .
Консервативная (априорная) оценка ошибки
[ редактировать ]Позволять иметь ограниченную первую производную по то есть Теорема о среднем значении для где дает для некоторых в зависимости от .
Если мы интегрируемся в от к с обеих сторон и приняв абсолютные значения, получим
Мы можем дополнительно аппроксимировать интеграл в правой части, введя абсолютное значение в подынтегральную функцию и заменив член в по верхней границе
( 1 ) |
где супремум использовался для аппроксимации.
Следовательно, если аппроксимировать интеграл по правилу квадратур наша ошибка не превышает правую часть 1 . Мы можем преобразовать это в анализ ошибок суммы Римана , дав верхнюю границу для ошибки этого конкретного приближения. (Обратите внимание, что именно эту ошибку мы рассчитали для примера .) Используя больше производных и корректируя квадратуру, мы можем провести аналогичный анализ ошибок, используя ряд Тейлора (используя частичную сумму с остаточным членом) для f . Этот анализ ошибок дает строгую верхнюю границу ошибки, если производные f доступны .
Этот метод интегрирования можно комбинировать с интервальной арифметикой для получения компьютерных доказательств и проверенных вычислений.
Интегралы по бесконечным интервалам
[ редактировать ]Существует несколько методов приближенного интегрирования по неограниченным интервалам. Стандартный метод включает в себя специально выведенные квадратурные правила, такие как квадратура Гаусса-Эрмита для интегралов на всей действительной прямой и квадратура Гаусса-Лагерра для интегралов на положительных действительных числах. [4] Также можно использовать методы Монте-Карло или замену переменных на конечный интервал; например, для всей строки можно использовать а для полубесконечных интервалов можно использовать как возможные трансформации.
Многомерные интегралы
[ редактировать ]Все правила квадратур, обсуждавшиеся до сих пор, предназначены для вычисления одномерных интегралов. Чтобы вычислить интегралы в нескольких измерениях, один из подходов состоит в том, чтобы сформулировать кратный интеграл как повторяющиеся одномерные интегралы, применив теорему Фубини (правило тензорного произведения). Этот подход требует, чтобы оценки функции росли экспоненциально по мере увеличения числа измерений. Известны три метода преодоления этого так называемого проклятия размерности .
Множество дополнительных приемов формирования многомерных кубатурных правил интегрирования для различных весовых функций дано в монографии Страуда. [5] Интеграция в этой сфере была рассмотрена Гессе и др. (2015). [6]
Монте-Карло
[ редактировать ]Методы Монте-Карло и квазиметоды Монте-Карло легко применимы к многомерным интегралам. Они могут дать большую точность при том же количестве оценок функции, чем повторное интегрирование с использованием одномерных методов. [ нужна ссылка ]
Большим классом полезных методов Монте-Карло являются так называемые алгоритмы Монте-Карло на основе цепей Маркова , к которым относятся алгоритм Метрополиса-Гастингса и выборка Гиббса .
Разреженные сетки
[ редактировать ]Разреженные сетки первоначально были разработаны Смоляком для квадратуры многомерных функций. Этот метод всегда основан на одномерном правиле квадратур, но выполняет более сложную комбинацию одномерных результатов. Однако в то время как правило тензорного произведения гарантирует, что веса всех кубатурных точек будут положительными, если веса квадратурных точек были положительными, правило Смоляка не гарантирует, что все веса будут положительными.
Байесовская квадратура
[ редактировать ]Байесовская квадратура представляет собой статистический подход к числовой задаче вычисления интегралов и относится к области вероятностных чисел . Он может обеспечить полную обработку неопределенности решения интеграла, выраженного как апостериорная дисперсия гауссовского процесса .
Связь с дифференциальными уравнениями
[ редактировать ]Задача о вычислении определенного интеграла
может быть сведена к начальной задаче для обыкновенного дифференциального уравнения путем применения первой части основной теоремы исчисления . Дифференцируя обе части вышеизложенного по аргументу x , видно, что функция F удовлетворяет условию
Численные методы для обыкновенных дифференциальных уравнений , такие как методы Рунге-Кутты , могут быть применены к переформулированной задаче и, таким образом, использоваться для вычисления интеграла. Например, стандартный метод Рунге-Кутты четвертого порядка, примененный к дифференциальному уравнению, дает правило Симпсона сверху.
Дифференциальное уравнение имеет особый вид: в правой части находится только независимая переменная (здесь ), а не зависимая переменная (здесь ). Это значительно упрощает теорию и алгоритмы. Таким образом, проблему вычисления интегралов лучше всего изучать отдельно.
И наоборот, термин «квадратура» может также использоваться для решения дифференциальных уравнений: « решение в квадратуре » или « приведение к квадратуре » означает выражение его решения через интегралы .
См. также
[ редактировать ]- Ошибка усечения (численное интегрирование)
- Квадратура Кленшоу – Кертиса
- Квадратура Гаусса-Кронрода
- Сумма Римана или интеграл Римана
- Правило трапеции
- метод Ромберга
- Тан-квадратура рождения
- Неэлементарные интегралы
Ссылки
[ редактировать ]- ^ Вайсштейн, Эрик В. «Кубатура» . Математический мир .
- ^ «Самые ранние известные варианты использования некоторых математических слов (Q)» . jeff560.tripod.com . Проверено 31 марта 2018 г.
- ^ Матье Оссендрийвер (29 января 2016 г.). «Древние вавилонские астрономы рассчитали положение Юпитера по площади под графиком скорости времени». Наука . 351 (6272): 482–484. Бибкод : 2016Sci...351..482O . doi : 10.1126/science.aad8085 . ПМИД 26823423 . S2CID 206644971 .
- ^ Лидер Джеффри Дж. (2004 г.). Численный анализ и научные вычисления . Эддисон Уэсли. ISBN 978-0-201-73499-7 .
- ^ Страуд, А.Х. (1971). Приближенное вычисление кратных интегралов . Prentice-Hall Inc. Клиффс, Нью-Джерси: ISBN 9780130438935 .
- ^ Керстин Гессе, Ян Х. Слоан и Роберт С. Уомерсли: Численное интегрирование на сфере. В W. Freeden et al. (ред.), Справочник по геоматематике, Springer: Берлин, 2015 г., дои : 10.1007/978-3-642-54551-1_40
- Филип Дж. Дэвис и Филип Рабиновиц , Методы численного интегрирования .
- Джордж Э. Форсайт , Майкл А. Малкольм и Клив Б. Молер , Компьютерные методы математических вычислений . Энглвуд Клиффс, Нью-Джерси: Прентис-Холл, 1977. (См. главу 5.)
- Пресс, WH ; Теукольский, С.А. ; Феттерлинг, WT; Фланнери, Б.П. (2007), «Глава 4. Интегрирование функций» , Численные рецепты: искусство научных вычислений (3-е изд.), Нью-Йорк: Cambridge University Press, ISBN 978-0-521-88068-8
- Йозеф Стер и Роланд Булирш , Введение в численный анализ . Нью-Йорк: Springer-Verlag, 1980. (См. главу 3.)
- Бойер, CB , История математики , 2-е изд. обр. Ута К. Мерцбах , Нью-Йорк: Wiley, 1989. ISBN 0-471-09763-2 (1991 PBK изд. ISBN 0-471-54397-7 ).
- Ивс, Ховард , Введение в историю математики , Сондерс, 1990, ISBN 0-03-029558-0 ,
Внешние ссылки
[ редактировать ]- Интеграция: предыстория, моделирование и т. д. в Институте целостных численных методов.
- Квадратура Лобатто из Wolfram Mathworld
- Квадратурная формула Лобатто из Математической энциклопедии
- Реализации многих квадратурных и кубатурных формул в бесплатной библиотеке компонентов Tracker .
- Онлайн-интегратор SageMath