Правило Симпсона

Чтобы узнать о правиле голосования Симпсона, см. Minimax Condorcet . О правилах военно-морской архитектуры см. Правила Симпсона (остойчивость корабля) .

Правило Симпсона можно получить путем аппроксимации подынтегральной функции f ( x ) (синим цветом) квадратичным интерполянтом P ( x ) (красным цветом) .

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

Анимация, показывающая, как аппроксимация правила Симпсона улучшается при увеличении количества подразделений.

В численном интегрировании правила Симпсона представляют собой несколько приближений для определенных интегралов , названных в честь Томаса Симпсона (1710–1761).

Самое основное из этих правил, называемое правилом Симпсона 1/3 или просто правилом Симпсона , гласит: $$\int _{a}^{b}f(x)\,dx\approx {\frac {b-a}{6}}\left[f(a)+4f\left({\frac {a+b}{2}}\right)+f(b)\right].$$

На немецком и некоторых других языках оно названо в честь Иоганна Кеплера , который вывел его в 1615 году после того, как увидел, что оно используется для изготовления винных бочек (правило бочек, Keplersche Fassregel ). Приблизительное равенство в правиле становится точным, если f является многочленом до 3-й степени включительно.

Если правило 1/3 применяется к n равным подразделениям диапазона интегрирования [ a , b ], получается составное правило 1/3 Симпсона . Точкам внутри диапазона интегрирования присваиваются чередующиеся веса 4/3 и 2/3.

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

Если правило 3/8 применяется к n равным подразделениям диапазона интегрирования [ a , b ], получается составное правило Симпсона 3/8 .

Правила Симпсона 1/3 и 3/8 представляют собой два частных случая замкнутых формул Ньютона–Котеса .

В военно-морской архитектуре и оценке устойчивости корабля также существует третье правило Симпсона , не имеющее особого значения в общем численном анализе, см. Правила Симпсона (остойчивость корабля) .

Правило Симпсона 1/3

Правило Симпсона 1/3, также называемое просто правилом Симпсона, представляет собой метод численного интегрирования, предложенный Томасом Симпсоном. Оно основано на квадратичной интерполяции и представляет собой составное правило 1/3 Симпсона, рассчитанное для $n=2$. Правило Симпсона 1/3 выглядит следующим образом: $${\begin{aligned}\int _{a}^{b}f(x)\,dx&\approx {\frac {b-a}{6}}\left[f(a)+4f\left({\frac {a+b}{2}}\right)+f(b)\right]\\&={\frac {1}{3}}h\left[f(a)+4f\left(a+h\right)+f(b)\right],\end{aligned}}$$ где $h=(b-a)/n$ размер шага для $n=2$.

Ошибка аппроксимации интеграла по правилу Симпсона для $n=2$ является $$-{\frac {1}{90}}h^{5}f^{(4)}(\xi )=-{\frac {(b-a)^{5}}{2880}}f^{(4)}(\xi ),$$ где $\xi$ ( греческая буква xi ) — некоторое число между $a$ и $b$.

Ошибка асимптотически пропорциональна $(b-a)^{5}$. Однако приведенные выше выводы предполагают ошибку, пропорциональную $(b-a)^{4}$. Правило Симпсона приобретает дополнительный порядок, поскольку точки, в которых вычисляется подынтегральная функция, распределены симметрично на интервале $[a,\ b]$.

Поскольку член ошибки пропорционален четвертой производной $f$ в $\xi$, это показывает, что правило Симпсона дает точные результаты для любого полинома $f$ степени три или меньше, поскольку четвертая производная такого многочлена равна нулю во всех точках. Другой способ увидеть этот результат — отметить, что любой интерполяционный кубический многочлен может быть выражен как сумма уникального интерполяционного квадратичного многочлена плюс кубического многочлена произвольного масштаба, который обращается в нуль во всех трех точках интервала, а интеграл от этого второго члена обращается в нуль. потому что это нечетно в пределах интервала.

Если вторая производная $f''$ существует и выпукло в интервале $(a,\ b)$, затем $$(b-a)f\left({\frac {a+b}{2}}\right)+{\frac {1}{3}}\left({\frac {b-a}{2}}\right)^{3}f''\left({\frac {a+b}{2}}\right)\leq \int _{a}^{b}f(x)\,dx\leq {\frac {b-a}{6}}\left[f(a)+4f\left({\frac {a+b}{2}}\right)+f(b)\right].$$

Выводы

Квадратичная интерполяция

Один вывод заменяет подынтегральную функцию $f(x)$ квадратичным полиномом (т.е. параболой) $P(x)$ который принимает те же значения, что и $f(x)$ в конечных точках $a$ и $b$ и середина $m=(a+b)/2$. Можно использовать интерполяцию полинома Лагранжа , чтобы найти выражение для этого многочлена: $$P(x)=f(a){\frac {(x-m)(x-b)}{(a-m)(a-b)}}+f(m){\frac {(x-a)(x-b)}{(m-a)(m-b)}}+f(b){\frac {(x-a)(x-m)}{(b-a)(b-m)}}.$$ Интегрируя заменой , можно показать, что $$\int _{a}^{b}P(x)\,dx={\frac {b-a}{6}}\left[f(a)+4f\left({\frac {a+b}{2}}\right)+f(b)\right].$$ Представляем размер шага $h=(b-a)/2$, это также обычно пишется как $$\int _{a}^{b}P(x)\,dx={\frac {1}{3}}h\left[f(a)+4f\left(a+h\right)+f(b)\right].$$ Из-за $1/3$ фактор, правило Симпсона также называют «правилом Симпсона 1/3» (обобщение см. ниже).

Усреднение средней точки и правила трапеций

Другой вывод строит правило Симпсона из двух более простых приближений: правила средней точки. $$M=(b-a)f\left({\frac {a+b}{2}}\right)$$ и правило трапеций $$T={\frac {1}{2}}(b-a){\big (}f(a)+f(b){\big )}.$$

Ошибки в этих приближениях $${\frac {1}{24}}(b-a)^{3}f''(a)+O{\big (}(b-a)^{4}{\big )}$$ и $$-{\frac {1}{12}}(b-a)^{3}f''(a)+O{\big (}(b-a)^{4}{\big )}$$ соответственно, где $O{\big (}(b-a)^{4}{\big )}$ обозначает член, асимптотически пропорциональный $(b-a)^{4}$. два $O{\big (}(b-a)^{4}{\big )}$ условия не равны; см . в обозначении Big O. более подробную информацию Из приведенных выше формул для ошибок средней точки и правила трапеций следует, что главный член ошибки исчезает, если взять средневзвешенное значение ${\frac {2M+T}{3}}.$ Это средневзвешенное значение в точности соответствует правилу Симпсона.

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

Неопределенные коэффициенты

Третий вывод начинается с анзаца. $${\frac {1}{b-a}}\int _{a}^{b}f(x)\,dx\approx \alpha f(a)+\beta f\left({\frac {a+b}{2}}\right)+\gamma f(b).$$

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

Составное правило 1/3 Симпсона

Если интервал интегрирования $[a,b]$ в некотором смысле «маленький», то правило Симпсона с $n=2$ подинтервалы обеспечат адекватное приближение к точному интегралу. Под «малым» мы подразумеваем, что интегрируемая функция относительно гладкая на интервале $[a,b]$. Для такой функции хорошие результаты даст гладкий квадратичный интерполянт, подобный тому, который используется в правиле Симпсона.

Однако часто бывает, что функция, которую мы пытаемся интегрировать, не является гладкой на интервале. Обычно это означает, что либо функция сильно колебательна, либо не имеет производных в определенных точках. В этих случаях правило Симпсона может дать очень плохие результаты. Один из распространенных способов решения этой проблемы — разбить интервал $[a,b]$ в $n>2$ небольшие подинтервалы. Затем правило Симпсона применяется к каждому подинтервалу, при этом результаты суммируются для получения аппроксимации интеграла по всему интервалу. Такой подход называется составным правилом Симпсона 1/3 или просто составным правилом Симпсона .

Предположим, что интервал $[a,b]$ разделен на $n$ подинтервалы, с $n$ четное число. Тогда составное правило Симпсона имеет вид

Деление интервала $[a,b]$ в $n$ подинтервалы длины $h=(b-a)/n$ и ознакомление с точками $x_{i}=a+ih$ для $0\leq i\leq n$ (в частности, $x_{0}=a$ и $x_{n}=b$), у нас есть $${\begin{aligned}\int _{a}^{b}f(x)\,dx&\approx {\frac {1}{3}}h\sum _{i=1}^{n/2}{\big [}f(x_{2i-2})+4f(x_{2i-1})+f(x_{2i}){\big ]}\\&={\frac {1}{3}}h{\big [}f(x_{0})+4f(x_{1})+2f(x_{2})+4f(x_{3})+2f(x_{4})+\dots +2f(x_{n-2})+4f(x_{n-1})+f(x_{n}){\big ]}\\&={\frac {1}{3}}h\left[f(x_{0})+4\sum _{i=1}^{n/2}f(x_{2i-1})+2\sum _{i=1}^{n/2-1}f(x_{2i})+f(x_{n})\right].\end{aligned}}$$ Это составное правило с $n=2$ соответствует обычному правилу Симпсона из предыдущего раздела.

Ошибка, допущенная составным правилом Симпсона, равна $$-{\frac {1}{180}}h^{4}(b-a)f^{(4)}(\xi ),$$ где $\xi$ какое-то число между $a$ и $b$, и $h=(b-a)/n$ это «длина шага». Ошибка ограничена (по абсолютной величине) величиной $${\frac {1}{180}}h^{4}(b-a)\max _{\xi \in [a,b]}\left|f^{(4)}(\xi )\right|.$$

Эта формулировка разбивает интервал $[a,b]$ в подинтервалах равной длины. На практике часто бывает выгодно использовать подинтервалы разной длины и концентрировать усилия на тех местах, где подынтегральная функция ведет себя менее хорошо. Это приводит к адаптивному методу Симпсона .

Правило Симпсона 3/8

Правило Симпсона 3/8, также называемое вторым правилом Симпсона, — это еще один метод численного интегрирования, предложенный Томасом Симпсоном. Он основан на кубической интерполяции, а не на квадратичной интерполяции. Правило Симпсона 3/8 выглядит следующим образом: $${\begin{aligned}\int _{a}^{b}f(x)\,dx&\approx {\frac {b-a}{8}}\left[f(a)+3f\left({\frac {2a+b}{3}}\right)+3f\left({\frac {a+2b}{3}}\right)+f(b)\right]\\&={\frac {3}{8}}h\left[f(a)+3f\left(a+h\right)+3f\left(a+2h\right)+f(b)\right],\end{aligned}}$$ где $h=(b-a)/3$ это размер шага.

Ошибка этого метода заключается в том, что $$-{\frac {3}{80}}h^{5}f^{(4)}(\xi )=-{\frac {(b-a)^{5}}{6480}}f^{(4)}(\xi ),$$ где $\xi$ какое-то число между $a$ и $b$. Таким образом, правило 3/8 примерно в два раза точнее стандартного метода, но использует еще одно значение функции. Также существует составное правило 3/8, аналогично приведенному выше.

Дальнейшим обобщением этой концепции для интерполяции полиномами произвольной степени являются формулы Ньютона–Котеса .

Составное правило Симпсона 3/8

Деление интервала $[a,b]$ в $n$ подинтервалы длины $h=(b-a)/n$ и ознакомление с точками $x_{i}=a+ih$ для $0\leq i\leq n$ (в частности, $x_{0}=a$ и $x_{n}=b$), у нас есть $${\begin{aligned}\int _{a}^{b}f(x)\,dx&\approx {\frac {3}{8}}h\sum _{i=1}^{n/3}{\big [}f(x_{3i-3})+3f(x_{3i-2})+3f(x_{3i-1})+f(x_{3i}){\big ]}\\&={\frac {3}{8}}h{\big [}f(x_{0})+3f(x_{1})+3f(x_{2})+2f(x_{3})+3f(x_{4})+3f(x_{5})+2f(x_{6})+\dots +2f(x_{n-3})+3f(x_{n-2})+3f(x_{n-1})+f(x_{n}){\big ]}\\&={\frac {3}{8}}h\left[f(x_{0})+3\sum _{i=1,\ 3\nmid i}^{n-1}f(x_{i})+2\sum _{i=1}^{n/3-1}f(x_{3i})+f(x_{n})\right].\end{aligned}}$$

Остаток правила отображается как $-{\frac {1}{80}}h^{4}(b-a)f^{(4)}(\xi ),$ мы можем использовать это только в том случае, если $n$ кратно трем. Правило 1/3 можно использовать для оставшихся подинтервалов без изменения порядка ошибки (и наоборот, правило 3/8 можно использовать с составным правилом 1/3 для подинтервалов с нечетными номерами).

Альтернативное расширенное правило Симпсона

Это еще одна формулировка составного правила Симпсона: вместо применения правила Симпсона к непересекающимся сегментам аппроксимируемого интеграла правило Симпсона применяется к перекрывающимся сегментам, что дает $$\int _{a}^{b}f(x)\,dx\approx {\frac {1}{48}}h\left[17f(x_{0})+59f(x_{1})+43f(x_{2})+49f(x_{3})+48\sum _{i=4}^{n-4}f(x_{i})+49f(x_{n-3})+43f(x_{n-2})+59f(x_{n-1})+17f(x_{n})\right].$$

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

Правила Симпсона в случае узких пиков

В задаче оценки полной площади узких пикообразных функций правила Симпсона гораздо менее эффективны, чем правило трапеций . А именно, составное правило 1/3 Симпсона требует в 1,8 раза больше точек для достижения той же точности, что и правило трапеций. Композитное правило Симпсона 3/8 еще менее точно. Интегрирование по правилу Симпсона 1/3 можно представить как средневзвешенное значение, где 2/3 значения получается в результате интегрирования по правилу трапеций с шагом h и 1/3 значения, полученного в результате интегрирования по правилу прямоугольника с шагом 2 h . Точность определяется вторым членом (шаг 2 часа ). Усреднение составных сумм по правилу Симпсона 1/3 с правильно сдвинутыми рамками дает следующие правила: $$\int _{a}^{b}f(x)\,dx\approx {\frac {1}{24}}h\left[-f(x_{-1})+12f(x_{0})+25f(x_{1})+24\sum _{i=2}^{n-2}f(x_{i})+25f(x_{n-1})+12f(x_{n})-f(x_{n+1})\right],$$ где эксплуатируются две точки за пределами интегрированного региона, и $$\int _{a}^{b}f(x)\,dx\approx {\frac {1}{24}}h\left[9f(x_{0})+28f(x_{1})+23f(x_{2})+24\sum _{i=3}^{n-3}f(x_{i})+23f(x_{n-2})+28f(x_{n-1})+9f(x_{n})\right],$$ где используются только точки внутри области интеграции. Применение второго правила к области 3 баллов порождает правило 1/3 Симпсона, 4 балла – правило 3/8.

Эти правила очень похожи на альтернативное расширенное правило Симпсона. Коэффициенты внутри большей части интегрируемой области едины, а неединичные коэффициенты есть только по краям. Эти два правила можно связать с формулой Эйлера – Маклорена с первым производным и назвать первого порядка правилами интегрирования Эйлера – Маклорена . Два представленных выше правила отличаются только способом расчета первой производной на конце региона. Член первой производной в правилах интегрирования Эйлера – Маклорена учитывает интеграл от второй производной, который равен разности первых производных на краях области интегрирования. Можно сгенерировать правила Эйлера-Маклорена более высокого порядка, добавляя разность 3-й, 5-й и т. д. производных с коэффициентами, как это определено формулой Эйлера-Маклорена .

Составное правило Симпсона для неравномерно расположенных данных

Для некоторых приложений интервал интегрирования $I=[a,b]$ необходимо разделить на неравные интервалы – возможно, из-за неравномерной выборки данных или отсутствия или повреждения точек данных. Предположим, мы разделили интервал $I$ в четное число $N$ подинтервалов ширины $h_{k}$. Тогда составное правило Симпсона имеет вид $$\int _{a}^{b}f(x)\,dx\approx \sum _{i=0}^{N/2-1}{\frac {h_{2i}+h_{2i+1}}{6}}\left[\left(2-{\frac {h_{2i+1}}{h_{2i}}}\right)f_{2i}+{\frac {(h_{2i}+h_{2i+1})^{2}}{h_{2i}h_{2i+1}}}f_{2i+1}+\left(2-{\frac {h_{2i}}{h_{2i+1}}}\right)f_{2i+2}\right],$$ где $$f_{k}=f\left(a+\sum _{i=0}^{k-1}h_{i}\right)$$ значения функции в $k$-я точка отбора проб на интервале $I$.

В случае нечетного числа $N$ подинтервалов приведенная выше формула используется до предпоследнего интервала, а последний интервал обрабатывается отдельно, добавляя к результату следующее: $$\alpha f_{N}+\beta f_{N-1}-\eta f_{N-2},$$ где $${\begin{aligned}\alpha &={\frac {2h_{N-1}^{2}+3h_{N-1}h_{N-2}}{6(h_{N-2}+h_{N-1})}},\\[1ex]\beta &={\frac {h_{N-1}^{2}+3h_{N-1}h_{N-2}}{6h_{N-2}}},\\[1ex]\eta &={\frac {h_{N-1}^{3}}{6h_{N-2}(h_{N-2}+h_{N-1})}}.\end{aligned}}$$

показывать Пример реализации на Python

from collections.abc import Sequence

def simpson_nonuniform(x: Sequence[float], f: Sequence[float]) -> float:
    """
    Simpson rule for irregularly spaced data.

    :param x: Sampling points for the function values
    :param f: Function values at the sampling points

    :return: approximation for the integral

    See ``scipy.integrate.simpson`` and the underlying ``_basic_simpson``
    for a more performant implementation utilizing numpy's broadcast.
    """
    N = len(x) - 1
    h = [x[i + 1] - x[i] for i in range(0, N)]
    assert N > 0

    result = 0.0
    for i in range(1, N, 2):
        h0, h1 = h[i - 1], h[i]
        hph, hdh, hmh = h1 + h0, h1 / h0, h1 * h0
        result += (hph / 6) * (
            (2 - hdh) * f[i - 1] + (hph**2 / hmh) * f[i] + (2 - 1 / hdh) * f[i + 1]
        )

    if N % 2 == 1:
        h0, h1 = h[N - 2], h[N - 1]
        result += f[N]     * (2 * h1 ** 2 + 3 * h0 * h1) / (6 * (h0 + h1))
        result += f[N - 1] * (h1 ** 2 + 3 * h1 * h0)     / (6 * h0)
        result -= f[N - 2] * h1 ** 3                     / (6 * h0 * (h0 + h1))
    return result

показывать Пример реализации в R

SimpsonInt <- function(fx, dx) {
  n <- length(dx)
  h <- diff(dx)
  stopifnot(exprs = {
    length(fx) == n
    all(h >= 0)
  })
  res <- 0
  for (i in seq(1L, n - 2L, 2L)) {
    hph <- h[i] + h[i + 1L]
    hdh <- h[i + 1L] / h[i]
    res <- res + hph / 6 *
      ((2 - hdh) * fx[i] +
         hph ^ 2 / (h[i] * h[i + 1L]) * fx[i + 1L] +
         (2 - 1 / hdh) * fx[i + 2L])
  }

  if (n %% 2 == 0) {
    hph <- h[n - 1L] + h[n - 2L]
    threehth <- 3 * h[n - 1L] * h[n - 2L]
    sixh2 <- 6 * h[n - 2L]
    h1sq <- h[n - 1L] ^ 2
    res <- res +
      (2 * h1sq + threehth) / (6 * hph) * fx[n] +
      (h1sq + threehth) / sixh2 * fx[n - 1L] -
      (h1sq * h[n - 1L]) / (sixh2 * hph) * fx[n - 2L]
  }
  res
}

См. также

• Формулы Ньютона–Котеса
• Гауссова квадратура

Ссылки

• Аткинсон, Кендалл Э. (1989). Введение в численный анализ (2-е изд.). Джон Уайли и сыновья. ISBN  0-471-50023-2 .
• Берден, Ричард Л.; Фейрес, Дж. Дуглас (2000). Численный анализ (7-е изд.). Брукс/Коул. ISBN  0-534-38216-9 .
• Картрайт, Кеннет В. (сентябрь 2017 г.). «Кумулятивная интеграция по правилу Симпсона с MS Excel и нерегулярно расположенными данными» (PDF) . Журнал математических наук и математического образования . 12 (2): 1–9 . Проверено 18 декабря 2022 г.
• Каламбет, Юрий; Козьмин Юрий; Самохин, Андрей (2018). «Сравнение правил интегрирования в случае очень узких хроматографических пиков». Хемометрика и интеллектуальные лабораторные системы . 179 : 22–30. doi : 10.1016/j.chemolab.2018.06.001 . ISSN   0169-7439 .
• Мэтьюз, Джон Х. (2004). «Правило Симпсона 3/8 для численного интегрирования» . Численный анализ — Проект численных методов . Калифорнийский государственный университет, Фуллертон. Архивировано из оригинала 4 декабря 2008 года . Проверено 11 ноября 2008 г.
• Шклов Н. (декабрь 1960 г.). «Правило Симпсона для неравноотстоящих ординат». Американский математический ежемесячник . 67 (10): 1022–1023. дои : 10.2307/2309244 . JSTOR   2309244 .
• Сюли, Эндре; Майерс, Дэвид (2003). Введение в численный анализ . Издательство Кембриджского университета. ISBN  0-521-00794-1 .
• Вайсштейн, Эрик В. «Формулы Ньютона-Котеса» . Математический мир . Проверено 14 декабря 2022 г.

Внешние ссылки

• «Формула Симпсона» . Энциклопедия математики . ЭМС Пресс . 2001 [1994].
• Вайсштейн, Эрик В. «Правило Симпсона» . Математический мир .
• Правило интеграции 1/3 Симпсона — Notes, PPT, Mathcad, Matlab, Mathematica, Maple и численные методы для студентов STEM
• Подробное описание компьютерной реализации дано Дораем Ситарамом в книге Teach Yourself Scheme in Fixnum Days , Приложение C.

Эта статья включает в себя материал из Кодекса для правила Симпсона на PlanetMath , который распространяется по лицензии Creative Commons Attribution/Share-Alike License .