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

Численное интегрирование используется для расчета численной аппроксимации значения $S$, площадь под кривой, определяемая формулой $f(x)$.

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

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

$\int _{a}^{b}f(x)\,dx$

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

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

Мотивация и потребность

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

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

История

Основная статья: Квадратура (математика)

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

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

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

Античный метод нахождения среднего геометрического

Для квадратуры прямоугольника со сторонами a и b необходимо построить квадрат со стороной $x={\sqrt {ab}}$ ( среднее геометрическое a b и ) . Для этого можно воспользоваться следующим фактом: если нарисовать окружность, диаметр которой равен сумме a и b , то высота BH (от точки их соединения до пересечения с окружностью) равна их среднему геометрическому. Подобная геометрическая конструкция решает задачу квадратуры для параллелограмма и треугольника.

Площадь сегмента параболы

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

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

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

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

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

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

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

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

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

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

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

Квадратурные правила, основанные на ступенчатых функциях

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

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

Этот простейший метод аппроксимирует функцию ступенчатой ​​функцией (кусочно-постоянной функцией или сегментированным полиномом нулевой степени), проходящей через точку ${\textstyle \left({\frac {a+b}{2}},f\left({\frac {a+b}{2}}\right)\right)}$. Это называется правилом средней точки или правилом прямоугольника. $$\int _{a}^{b}f(x)\,dx\approx (b-a)f\left({\frac {a+b}{2}}\right).$$

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

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

Иллюстрация правила трапеций.

Интерполирующая функция может быть прямой линией ( аффинная функция , т.е. многочлен степени 1)проходя через точки $\left(a,f(a)\right)$ и $\left(b,f(b)\right)$.Это называется правилом трапеций $$\int _{a}^{b}f(x)\,dx\approx (b-a)\left({\frac {f(a)+f(b)}{2}}\right).$$

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

Для любого из этих правил мы можем сделать более точное приближение, разбив интервал $[a,b]$ в какое-то число $n$ подинтервалов, вычисляя приближение для каждого подинтервала, а затем суммируя все результаты. Это называется составным правилом , расширенным правилом или повторяющимся правилом . Например, составное правило трапеций можно сформулировать как $$\int _{a}^{b}f(x)\,dx\approx {\frac {b-a}{n}}\left({f(a) \over 2}+\sum _{k=1}^{n-1}\left(f\left(a+k{\frac {b-a}{n}}\right)\right)+{f(b) \over 2}\right),$$

где подинтервалы имеют вид $[a+kh,a+(k+1)h]\subset [a,b],$ с ${\textstyle h={\frac {b-a}{n}}}$ и $k=0,\ldots ,n-1.$ Здесь мы использовали подинтервалы одинаковой длины $h$ но можно также использовать интервалы различной длины $\left(h_{k}\right)_{k}$.

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

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

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

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

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

Этот раздел представляет собой отрывок из книги «Адаптивная квадратура» . [ редактировать ]

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

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

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

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

Позволять $f$ иметь ограниченную первую производную по $[a,b],$ то есть $f\in C^{1}([a,b]).$ Теорема о среднем значении для $f,$ где $x\in [a,b),$ дает $$(x-a)f'(\xi _{x})=f(x)-f(a),$$для некоторых $\xi _{x}\in (a,x]$ в зависимости от $x$.

Если мы интегрируемся в $x$ от $a$ к $b$ с обеих сторон и приняв абсолютные значения, получим $$\left|\int _{a}^{b}f(x)\,dx-(b-a)f(a)\right|=\left|\int _{a}^{b}(x-a)f'(\xi _{x})\,dx\right|.$$

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

$\left|\int _{a}^{b}f(x)\,dx-(b-a)f(a)\right|\leq {(b-a)^{2} \over 2}\sup _{a\leq x\leq b}\left|f'(x)\right|,$

( 1 )

где супремум использовался для аппроксимации.

Следовательно, если аппроксимировать интеграл ${\textstyle \int _{a}^{b}f(x)\,dx}$ по правилу квадратур $(b-a)f(a)$ наша ошибка не превышает правую часть 1 . Мы можем преобразовать это в анализ ошибок суммы Римана , дав верхнюю границу $${\frac {n^{-1}}{2}}\sup _{0\leq x\leq 1}\left|f'(x)\right|$$для ошибки этого конкретного приближения. (Обратите внимание, что именно эту ошибку мы рассчитали для примера $f(x)=x$.) Используя больше производных и корректируя квадратуру, мы можем провести аналогичный анализ ошибок, используя ряд Тейлора (используя частичную сумму с остаточным членом) для f . Этот анализ ошибок дает строгую верхнюю границу ошибки, если производные f доступны .

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

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

Существует несколько методов приближенного интегрирования по неограниченным интервалам. Стандартный метод включает в себя специально выведенные квадратурные правила, такие как квадратура Гаусса-Эрмита для интегралов на всей действительной прямой и квадратура Гаусса-Лагерра для интегралов на положительных действительных числах. Также можно использовать методы Монте-Карло или замену переменных на конечный интервал; например, для всей строки можно использовать $$\int _{-\infty }^{\infty }f(x)\,dx=\int _{-1}^{+1}f\left({\frac {t}{1-t^{2}}}\right){\frac {1+t^{2}}{\left(1-t^{2}\right)^{2}}}\,dt,$$а для полубесконечных интервалов можно использовать $${\begin{aligned}\int _{a}^{\infty }f(x)\,dx&=\int _{0}^{1}f\left(a+{\frac {t}{1-t}}\right){\frac {dt}{(1-t)^{2}}},\\\int _{-\infty }^{a}f(x)\,dx&=\int _{0}^{1}f\left(a-{\frac {1-t}{t}}\right){\frac {dt}{t^{2}}},\end{aligned}}$$как возможные трансформации.

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

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

Множество дополнительных приемов формирования многомерных кубатурных правил интегрирования для различных весовых функций дано в монографии Страуда. Интеграция в этой сфере была рассмотрена Гессе и др. (2015).

Монте-Карло

Основная статья: Интеграция Монте-Карло

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

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

Разреженные сетки

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

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

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

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

Задача о вычислении определенного интеграла

$F(x)=\int _{a}^{x}f(u)\,du$

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

${\frac {dF(x)}{dx}}=f(x),\quad F(a)=0.$

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

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

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

См. также

• Ошибка усечения (численное интегрирование)
• Квадратура Кленшоу – Кертиса
• Квадратура Гаусса-Кронрода
• Сумма Римана или интеграл Римана
• Правило трапеции
• метод Ромберга
• Тан-квадратура рождения
• Неэлементарные интегралы

Ссылки

• Филип Дж. Дэвис и Филип Рабиновиц , Методы численного интегрирования .
• Джордж Э. Форсайт , Майкл А. Малкольм и Клив Б. Молер , Компьютерные методы математических вычислений . Энглвуд Клиффс, Нью-Джерси: Прентис-Холл, 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