Численное интегрирование - Numerical integration

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

В анализ, численное интегрирование включает в себя широкую семью алгоритмы для вычисления числового значения определенного интеграл, и, в более широком смысле, этот термин также иногда используется для описания численное решение дифференциальных уравнений. Эта статья посвящена вычислению определенных интегралов. Период, термин числовая квадратура (часто сокращенно квадратура ) является более или менее синонимом численное интегрирование, особенно применительно к одномерным интегралам. Некоторые авторы называют численное интегрирование по более чем одному измерению кубатура;[1] другие берут квадратура включить многомерную интеграцию.

Основная проблема численного интегрирования - вычислить приближенное решение определенного интеграла

с заданной степенью точности. Если f (x) является гладкой функцией, интегрированной по небольшому количеству измерений, а область интегрирования ограничена, существует множество методов аппроксимации интеграла с желаемой точностью.

История

Термин «численное интегрирование» впервые появился в 1915 г. в публикации Курс интерполяции и числовой интеграции для математической лаборатории от Дэвид Гибб.[2]

Квадратура - исторический математический термин, обозначающий расчет площади. Квадратурные задачи служили одним из основных источников математический анализ. Математики Древней Греции, согласно Пифагорейский доктрина, понятный расчет площадь как процесс геометрического построения квадрат одинаковой площади (возведение в квадрат). Поэтому процесс получил название квадратура. Например, квадратура круга, Луна Гиппократа, Квадратура параболы. Это строительство должно выполняться только с помощью компас и линейка.

Древние вавилоняне использовали трапеция интегрировать движение Юпитер вдоль эклиптика.[3]

Античный способ найти Среднее геометрическое

Для квадратуры прямоугольника со сторонами а и б необходимо построить квадрат со стороной Среднее геометрическое из а и б). Для этого можно использовать следующий факт: если нарисовать круг с суммой а и б как диаметр, то высота BH (от точки их соединения до пересечения с окружностью) равна их среднему геометрическому. Подобная геометрическая конструкция решает задачу о квадратуре параллелограмма и треугольника.

Площадь отрезка параболы

Задачи квадратуры для криволинейных фигур намного сложнее. В квадратура круга с циркулем и линейкой было доказано в 19 веке, что это невозможно. Тем не менее, для некоторых цифр (например, Луна Гиппократа ) квадратура может быть выполнена. Квадратуры поверхности шара и сегмент параболы сделано Архимед стало высшим достижением античного анализа.

  • Площадь поверхности шара в четыре раза больше площади большой круг этой сферы.
  • Площадь сегмента парабола отрезанный от него прямой линией составляет 4/3 площади вписанного в этот отрезок треугольника.

Для доказательства результатов Архимед использовал Метод истощения из Евдокс.

В средневековой Европе квадратура означала расчет площади любым методом. Чаще Метод неделимых было использовано; он был менее строгим, но более простым и мощным. С его помощью Галилео Галилей и Жиль де Роберваль нашел площадь циклоида арка Грегуар де Сент-Винсент исследовал территорию под гипербола (Opus Geometricum, 1647), и Альфонс Антонио де Сараса, ученик де Сент-Винсент и комментатор, отметил связь этой области с логарифмы.

Джон Уоллис Алгебрировал этот метод: он писал в своем Arithmetica Infinitorum (1656), которую мы теперь называем определенный интеграл, и он рассчитал их значения. Исаак Барроу и Джеймс Грегори добился дальнейшего прогресса: квадратуры для некоторых алгебраические кривые и спирали. Кристиан Гюйгенс успешно выполнил квадратуру некоторых Тела революции.

Квадратура гиперболы Сен-Винсента и де Сарасы дала новый функция, то натуральный логарифм, критическое значение.

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

Причины численного интегрирования

Есть несколько причин для проведения численного интегрирования.

  1. Подынтегральное выражение ж(Икс) могут быть известны только в определенных точках, например, полученных отбор проб. Немного встроенные системы по этой причине может потребоваться численное интегрирование для других компьютерных приложений.
  2. Формула для подынтегрального выражения может быть известна, но может быть трудно или невозможно найти первообразный это элементарная функция. Пример такого подынтегрального выражения: ж(Икс) = ехр (-Икс2), первообразная которого ( функция ошибки, умноженное на константу) не может быть записано в элементарная форма.
  3. Может быть возможно найти первообразную символически, но может быть проще вычислить численное приближение, чем вычислить первообразную. Это может иметь место, если первообразная дана как бесконечная серия или произведение, или если ее оценка требует специальная функция это недоступно.

Методы одномерных интегралов

Методы численного интегрирования обычно можно описать как объединение оценок подынтегрального выражения для получения приближения к интегралу. Подынтегральное выражение вычисляется в конечном наборе точек, называемых точки интеграции и взвешенная сумма этих значений используется для аппроксимации интеграла. Точки интегрирования и веса зависят от конкретного используемого метода и требуемой точности аппроксимации.

Важной частью анализа любого метода численного интегрирования является изучение поведения ошибки аппроксимации в зависимости от числа вычислений подынтегрального выражения. Метод, который дает небольшую ошибку для небольшого числа вычислений, обычно считается лучшим. количество вычислений подынтегральной функции уменьшает количество задействованных арифметических операций и, следовательно, уменьшает общую ошибка округления Кроме того, каждое вычисление требует времени, и подынтегральное выражение может быть произвольно сложным.

Численное интегрирование типа "грубой силы" может быть выполнено, если подынтегральное выражение имеет достаточно хорошее поведение (т.е. кусочно непрерывный и из ограниченная вариация ), оценивая подынтегральное выражение с очень маленькими приращениями.

Квадратурные правила на основе интерполирующих функций

Большой класс квадратурных правил можно получить, построив интерполирующий функции, которые легко интегрировать. Обычно эти интерполирующие функции многочлены. На практике, поскольку многочлены очень высокой степени имеют тенденцию сильно колебаться, используются только многочлены низкой степени, обычно линейные и квадратичные.

Иллюстрация правила прямоугольника.

Самый простой метод этого типа - сделать интерполирующую функцию постоянной функцией (полином нулевой степени), проходящей через точку . Это называется правило средней точки или правило прямоугольника

Иллюстрация трапециевидной линейки.

Интерполирующая функция может быть прямой линией ( аффинная функция, т. е. многочлен степени 1), проходящий через точки и Это называется трапеция

Иллюстрация правила Симпсона.

Для любого из этих правил мы можем сделать более точное приближение, разбив интервал в какое-то число подинтервалов, вычисляя приближение для каждого подынтервала, а затем суммируя все результаты. Это называется составное правило, расширенное правило, или повторяющееся правило. Например, составное правило трапеций можно сформулировать как

где подынтервалы имеют вид с и Здесь мы использовали подынтервалы одинаковой длины но можно также использовать интервалы различной длины .

Интерполяция с многочленами, вычисленными в равноотстоящих точках в дает Формулы Ньютона – Котеса, примерами которых являются линейка прямоугольников и линейка трапеций. Правило Симпсона, который основан на полиноме порядка 2, также является формулой Ньютона – Котеса.

Квадратурные правила с равноотстоящими точками обладают очень удобным свойством: гнездование. Соответствующее правило с каждым разделенным интервалом включает все текущие точки, поэтому эти значения подынтегральной функции можно использовать повторно.

Если мы позволим интервалу между точками интерполяции изменяться, мы найдем другую группу квадратурных формул, таких как Квадратура Гаусса формулы. Квадратурное правило Гаусса обычно более точное, чем правило Ньютона – Котеса, которое требует того же количества вычислений функции, если подынтегральное выражение равно гладкий; плавный (т.е. если она достаточно дифференцируема). Другие квадратурные методы с различными интервалами включают Квадратура Кленшоу – Кертиса (также называемые квадратурами Фейера), которые вкладываются.

Квадратурные правила Гаусса не вложены, но связанные Квадратурные формулы Гаусса – Кронрода. делать.

Обобщенная формула правила средней точки

Формула обобщенного правила средней точки дается формулой

или

где обозначает -я производная. Например, подставив и

в формуле обобщенного правила средней точки мы получаем уравнение обратной касательной

где является мнимая единица и

Поскольку при каждом нечетном числитель подынтегрального выражения принимает вид , формулу обобщенного правила средней точки можно преобразовать как

В следующем примере кода Mathematica создается график, показывающий разницу между арктангенсом и его приближением, усеченным на и :

ж[theta_,Икс_]:=тета/(1+тета^2*Икс^2);загар[theta_,M_,nMax_]:=2*Сумма[(Функция[Икс,Оценить[D[ж[тета,Икс],{Икс,2*п}]]][(м-1/2)/M])/((2*п+1)!*(2*M)^(2*п+1)),{м,1,M},{п,0,nMax}];участок[{АркТан[тета]-загар[тета,5,10]},{тета,-Пи,Пи},PlotRange->Все]

Для функции определяется в интервале , его интеграл равен

Следовательно, мы можем применить приведенную выше обобщенную формулу интегрирования средней точки, предполагая, что .

Адаптивные алгоритмы

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

def Calcul_definite_integral_of_f(ж, initial_step_size):    """    Этот алгоритм вычисляет определенный интеграл функции    от 0 до 1 адаптивно, выбирая меньшие шаги около    проблемные точки.    """    Икс = 0.0    час = initial_step_size    аккумулятор = 0.0    в то время как Икс < 1.0:        если Икс + час > 1.0:            час = 1.0 - Икс  # В конце единичного интервала настройте последний шаг так, чтобы он закончился на 1.        если error_too_big_in_quadrature_of_f_over_range(ж, [Икс, Икс + час]):            час = make_h_smaller(час)        еще:            аккумулятор += квадратурная_ф_фур_диапазона(ж, [Икс, Икс + час])            Икс += час            если error_too_small_in_quadrature_of_over_range(ж, [Икс, Икс + час]):                час = make_h_larger(час)  # Не тратьте время на крошечные шаги.    вернуть аккумулятор

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

Эвристика адаптивной квадратурности обсуждается Forsythe et al. (Раздел 5.4).

Методы экстраполяции

Точность квадратурного правила Ньютон-Котес Тип, как правило, является функцией количества оценочных баллов. Результат обычно более точен по мере увеличения количества оценочных баллов или, что то же самое, по мере уменьшения ширины шага между точками. Естественно спросить, какой результат было бы, если бы размер шага приближался к нулю. На это можно ответить, экстраполируя результат из двух или более ненулевых размеров шага, используя серийное ускорение такие методы как Экстраполяция Ричардсона.Функция экстраполяции может быть многочлен или рациональная функция Методы экстраполяции более подробно описаны Стоером и Булиршем (раздел 3.4) и реализованы во многих подпрограммах в КВАДПАК библиотека.

Консервативная (априорная) оценка погрешности

Позволять имеют ограниченную первую производную по т.е. В теорема о среднем значении за где дает

для некоторых в зависимости от .

Если мы интегрируем в из к с обеих сторон и возьмем абсолютные значения, получим

Мы можем дополнительно аппроксимировать интеграл в правой части, добавив абсолютное значение к подынтегральному выражению и заменив член в по верхней границе

 

 

 

 

(1)

где супремум использовался для приближения.

Следовательно, если аппроксимировать интеграл посредством квадратурное правило наша ошибка не больше, чем правая часть 1. Мы можем преобразовать это в анализ ошибок для Сумма Римана (*), что дает верхнюю оценку

для погрешности этого конкретного приближения. (Обратите внимание, что это именно та ошибка, которую мы рассчитали для примера .) Используя больше производных и настраивая квадратуру, мы можем провести аналогичный анализ ошибок, используя Серия Тейлор (с использованием частичной суммы с остаточным членом) для ж. Этот анализ ошибок дает строгую верхнюю границу ошибки, если производные от ж доступны.

Этот метод интеграции можно комбинировать с интервальная арифметика производить компьютерные доказательства и проверено расчеты.

Интегралы по бесконечным интервалам

Существует несколько методов приближенного интегрирования по неограниченным интервалам. Стандартный метод включает специально выведенные квадратурные правила, такие как Квадратура Гаусса-Эрмита для интегралов по всей действительной прямой и Квадратура Гаусса-Лагерра для интегралов от положительных действительных чисел.[4] Также можно использовать методы Монте-Карло или замену переменных на конечный интервал; например, для всей строки можно использовать

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

как возможные трансформации.

Многомерные интегралы

Все рассмотренные квадратурные правила предназначены для вычисления одномерных интегралов. Чтобы вычислить интегралы в нескольких измерениях, один из подходов состоит в том, чтобы сформулировать кратный интеграл как повторяющиеся одномерные интегралы, применив Теорема Фубини (правило тензорного произведения). Этот подход требует, чтобы оценки функций расти экспоненциально по мере увеличения количества измерений. Известно три метода преодоления этого так называемого проклятие размерности.

Множество дополнительных приемов формирования правил многомерного кубатурного интегрирования для различных весовых функций дано в монографии Страуда.[5]

Монте-Карло

Методы Монте-Карло и квази-Монте-Карло методы легко применяются к многомерным интегралам. Они могут дать большую точность для того же количества вычислений функций, чем повторные интеграции с использованием одномерных методов.[нужна цитата ]

Большой класс полезных методов Монте-Карло - это так называемые Цепь Маркова Монте-Карло алгоритмы, которые включают Алгоритм Метрополиса-Гастингса и Выборка Гиббса.

Редкие сетки

Редкие сетки были первоначально разработаны Смоляком для квадратур многомерных функций. Метод всегда основан на одномерном квадратурном правиле, но выполняет более сложную комбинацию одномерных результатов. Однако, в то время как правило тензорного произведения гарантирует, что веса всех кубатурных точек будут положительными, если веса квадратурных точек будут положительными, правило Смоляка не гарантирует, что все веса будут положительными.

Байесовская квадратура

Байесовская квадратура представляет собой статистический подход к численной проблеме вычисления интегралов и относится к области вероятностных чисел. Он может обеспечить полную обработку неопределенности решения интеграла, выраженного как Гауссовский процесс апостериорная дисперсия. Также известно, что он обеспечивает очень высокую скорость сходимости, которая может быть экспоненциальной по количеству квадратных точек n.[6]

Связь с дифференциальными уравнениями

Проблема вычисления интеграла

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

Методы, разработанные для обыкновенных дифференциальных уравнений, таких как Методы Рунге – Кутты, можно применить к переформулированной задаче и, таким образом, использовать для вычисления интеграла.Например, стандартный метод Рунге – Кутты четвертого порядка, примененный к дифференциальному уравнению, дает правило Симпсона сверху.

Дифференциальное уравнение имеет специальный вид: правая часть содержит только независимую переменную (здесь ), а не зависимой переменной (здесь ). Это значительно упрощает теорию и алгоритмы. Таким образом, проблема вычисления интегралов лучше всего изучена сама по себе.

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

использованная литература

  1. ^ Вайсштейн, Эрик В. "Кубатура". MathWorld.
  2. ^ «Самые ранние известные варианты использования некоторых слов математики (Q)». jeff560.tripod.com. Получено 31 марта 2018.
  3. ^ Матье Оссендрейвер (29 января, 2016). «Древние вавилонские астрономы вычислили положение Юпитера на основе графика времени-скорости». Наука. 351 (6272): 482–484. Bibcode:2016Научный ... 351..482O. Дои:10.1126 / science.aad8085. PMID  26823423.
  4. ^ Лидер Джеффри Дж. (2004). Численный анализ и научные вычисления. Эддисон Уэсли. ISBN  978-0-201-73499-7.
  5. ^ Страуд, А. Х. (1971). Приближенное вычисление кратных интегралов.. Клиффс, Нью-Джерси: Prentice-Hall Inc.
  6. ^ Бриоль, Франсуа-Ксавье; Оутс, Крис Дж .; Джиролами, Марк; Осборн, Майкл А. (2015-06-08). "Байесовская квадратура Франка-Вульфа: вероятностная интеграция с теоретическими гарантиями". arXiv:1506.02681 [stat.ML ].

внешняя ссылка