Трапецеидальная линейка - Trapezoidal rule

Эта статья посвящена квадратурному правилу аппроксимации интегралов. Для неявного правила трапеции для решения задач начального значения см. Правило трапеции (дифференциальные уравнения). Для явного правила трапеции для решения задач начального значения см. Метод Хойна.

Функция ж(Икс) (синим цветом) аппроксимируется линейной функцией (красным цветом).

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

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

Правило трапеции работает, аппроксимируя область под графиком функции${\displaystyle f(x)}$ как трапеция и расчет его площади. Следует, что

${\displaystyle \int _{a}^{b}f(x)\,dx\approx (b-a)\cdot {\tfrac {f(a)+f(b)}{2}}}$.

Правило трапеции можно рассматривать как результат, полученный путем усреднения оставили и верно Суммы Римана, и иногда определяется так. Еще лучше интеграл можно аппроксимировать следующим образом: разбиение интервала интегрирования, применяя правило трапеций к каждому подынтервалу и суммируя результаты. На практике это «сцепленное» (или «составное») правило трапеции обычно подразумевается под «интеграцией с правилом трапеции». Позволять ${\displaystyle \{x_{k}\}}$ быть разделом ${\displaystyle [a,b]}$ такой, что ${\displaystyle a=x_{0}<x_{1}<\cdots <x_{N-1}<x_{N}=b}$ и ${\displaystyle \Delta x_{k}}$ быть длиной ${\displaystyle k}$-й подынтервал (то есть ${\displaystyle \Delta x_{k}=x_{k}-x_{k-1}}$), тогда

${\displaystyle \int _{a}^{b}f(x)\,dx\approx \sum _{k=1}^{N}{\frac {f(x_{k-1})+f(x_{k})}{2}}\Delta x_{k}={\tfrac {\Delta x}{2}}\left(f(x_{0})+2f(x_{1})+2f(x_{2})+2f(x_{3})+2f(x_{4})+\cdots +2f(x_{N-1})+f(x_{N})\right)}$.

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

Иллюстрация «цепной трапециевидной линейки», используемой на неравномерном разбиении ${\displaystyle [a,b]}$.

Приближение становится более точным с увеличением разрешения разбиения (т. Е. Для большего ${\displaystyle N}$, ${\displaystyle \Delta x_{k}}$ Если разделение имеет регулярный интервал, как это часто бывает, формулу можно упростить для повышения эффективности вычислений.

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

История

В документе 2016 года сообщается, что правило трапеции использовалось в Вавилон до 50 г. до н.э. для интегрирования скорости Юпитер вдоль эклиптика.^[1]

Численная реализация

Неравномерная сетка

Когда шаг сетки неравномерен, можно использовать формулу

${\displaystyle \int _{a}^{b}f(x)\,dx\approx \sum _{k=1}^{N}{\frac {f(x_{k-1})+f(x_{k})}{2}}\Delta x_{k}}$

Равномерная сетка

Для области, дискретизированной на ${\displaystyle N}$ панели, расположенные на одинаковом расстоянии друг от друга, можно значительно упростить. Позволять

${\displaystyle \Delta x_{k}=\Delta x={\frac {b-a}{N}}}$

приближение к интегралу принимает вид

${\displaystyle \int _{a}^{b}f(x)\,dx\approx {\frac {\Delta x}{2}}\sum _{k=1}^{N}\left(f(x_{k-1})+f(x_{k})\right)}$

${\displaystyle {}={\frac {\Delta x}{2}}(f(x_{0})+2f(x_{1})+2f(x_{2})+2f(x_{3})+\dotsb +2f(x_{N-1})+f(x_{N}))}$

${\displaystyle {}={\frac {\Delta x}{2}}\left(f(x_{0})+f(x_{N})+2\sum _{k=1}^{N-1}f(x_{k})\right)}$

${\displaystyle {}=\Delta x\left(\sum _{k=1}^{N-1}f(x_{k})+{\frac {f(x_{N})+f(x_{0})}{2}}\right)}$

что требует меньшего количества вычислений функции для вычисления.

Анализ ошибок

Анимация, показывающая, как улучшается приближение трапециевидного правила с увеличением количества полос для интервала с ${\displaystyle a=2}$ и ${\displaystyle b=8}$. Как количество интервалов ${\displaystyle N}$ увеличивается, так же как и точность результата.

Ошибка составной трапециевидной линейки - это разница между значением интеграла и численным результатом:

${\displaystyle {\text{error}}=\int _{a}^{b}f(x)\,dx-{\frac {b-a}{N}}\left[{f(a)+f(b) \over 2}+\sum _{k=1}^{N-1}f\left(a+k{\frac {b-a}{N}}\right)\right]}$

Есть номер ξ между а и б, так что^[2]

${\displaystyle {\text{error}}=-{\frac {(b-a)^{3}}{12N^{2}}}f''(\xi )}$

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

Оценка асимптотической погрешности для N → ∞ задается формулой

${\displaystyle {\text{error}}=-{\frac {(b-a)^{2}}{12N^{2}}}{\big [}f'(b)-f'(a){\big ]}+O(N^{-3}).}$

Дополнительные члены в этой оценке погрешности даются формулой суммирования Эйлера – Маклорена.

Для анализа ошибки можно использовать несколько методов, в том числе:^[3]

1. Ряд Фурье
2. Остаточный камень
3. Формула суммирования Эйлера – Маклорена^[4][5]
4. Полиномиальная интерполяция^[6]

Утверждается, что скорость сходимости трапециевидной линейки отражает и может использоваться как определение классов гладкости функций.^[7]

Доказательство

Сначала предположим, что ${\displaystyle h={\frac {b-a}{N}}}$ и ${\displaystyle a_{k}=a+(k-1)h}$. Позволять ${\displaystyle g_{k}(t)={\frac {1}{2}}t[f(a_{k})+f(a_{k}+t)]-\int _{a_{k}}^{a_{k}+t}f(x)dx}$ - функция такая, что ${\displaystyle |g_{k}(h)|}$ - погрешность трапециевидной линейки на одном из отрезков, ${\displaystyle [a_{k},a_{k}+h]}$. потом

${\displaystyle {dg_{k} \over dt}={1 \over 2}[f(a_{k})+f(a_{k}+t)]+{1 \over 2}t\cdot f'(a_{k}+t)-f(a_{k}+t),}$

и

${\displaystyle {d^{2}g_{k} \over dt^{2}}={1 \over 2}t\cdot f''(a_{k}+t).}$

Теперь предположим, что ${\displaystyle \left\vert f''(x)\right\vert \leq f''(\xi ),}$ что имеет место, если ${\displaystyle f}$ достаточно гладкая. Отсюда следует, что

${\displaystyle \left\vert f''(a_{k}+t)\right\vert \leq f''(\xi )}$

что эквивалентно${\displaystyle -f''(\xi )\leq f''(a_{k}+t)\leq f''(\xi )}$, или же ${\displaystyle -{\frac {f''(\xi )t}{2}}\leq g_{k}''(t)\leq {\frac {f''(\xi )t}{2}}.}$

С ${\displaystyle g_{k}'(0)=0}$ и ${\displaystyle g_{k}(0)=0}$,

${\displaystyle \int _{0}^{t}g_{k}''(x)dx=g_{k}'(t)}$ и ${\displaystyle \int _{0}^{t}g_{k}'(x)dx=g_{k}(t).}$

Используя эти результаты, находим

${\displaystyle -{\frac {f''(\xi )t^{2}}{4}}\leq g_{k}'(t)\leq {\frac {f''(\xi )t^{2}}{4}}}$

и

${\displaystyle -{\frac {f''(\xi )t^{3}}{12}}\leq g_{k}(t)\leq {\frac {f''(\xi )t^{3}}{12}}}$

Сдача ${\displaystyle t=h}$ мы нашли

${\displaystyle -{\frac {f''(\xi )h^{3}}{12}}\leq g_{k}(h)\leq {\frac {f''(\xi )h^{3}}{12}}.}$

Суммируя все члены локальной ошибки, мы находим

${\displaystyle \sum _{k=1}^{N}g_{k}(h)={\frac {b-a}{N}}\left[{f(a)+f(b) \over 2}+\sum _{k=1}^{N-1}f\left(a+k{\frac {b-a}{N}}\right)\right]-\int _{a}^{b}f(x)dx.}$

Но у нас также есть

${\displaystyle -\sum _{k=1}^{N}{\frac {f''(\xi )h^{3}}{12}}\leq \sum _{k=1}^{N}g_{k}(h)\leq \sum _{k=1}^{N}{\frac {f''(\xi )h^{3}}{12}}}$

и

${\displaystyle \sum _{k=1}^{N}{\frac {f''(\xi )h^{3}}{12}}={\frac {f''(\xi )h^{3}N}{12}},}$

так что

${\displaystyle -{\frac {f''(\xi )h^{3}N}{12}}\leq {\frac {b-a}{N}}\left[{f(a)+f(b) \over 2}+\sum _{k=1}^{N-1}f\left(a+k{\frac {b-a}{N}}\right)\right]-\int _{a}^{b}f(x)dx\leq {\frac {f''(\xi )h^{3}N}{12}}.}$

Следовательно, общая ошибка ограничена

${\displaystyle {\text{error}}=\int _{a}^{b}f(x)dx-{\frac {b-a}{N}}\left[{f(a)+f(b) \over 2}+\sum _{k=1}^{N-1}f\left(a+k{\frac {b-a}{N}}\right)\right]={\frac {f''(\xi )h^{3}N}{12}}={\frac {f''(\xi )(b-a)^{3}}{12N^{2}}}.}$

Периодические и пиковые функции

Правило трапеций быстро сходится для периодических функций. Это простое следствие формулы суммирования Эйлера-Маклорена, которая гласит: ${\displaystyle f}$ является ${\displaystyle p}$ время, непрерывно дифференцируемое с периодом ${\displaystyle T}$

${\displaystyle \sum _{k=0}^{N-1}f(kh)h=\int _{0}^{T}f(x)\,dx+\sum _{k=1}^{\lfloor p/2\rfloor }{\frac {B_{2k}}{(2k)!}}(f^{(2k-1)}(T)-f^{(2k-1)}(0))-(-1)^{p}h^{p}\int _{0}^{T}{\tilde {B}}_{p}(x/T)f^{(p)}(x)\,\mathrm {d} x}$

куда ${\displaystyle h:=T/N}$ и ${\displaystyle {\tilde {B}}_{p}}$ является периодическим продолжением ${\displaystyle p}$й многочлен Бернулли.^[8] Из-за периодичности производные в конечной точке сокращаются, и мы видим, что ошибка равна ${\displaystyle O(h^{p})}$.

Аналогичный эффект доступен для пиковых функций, таких как Гауссовский, Экспоненциально модифицированный гауссовский и другие функции с производными в пределах интегрирования, которыми можно пренебречь.^[9] Оценка полного интеграла функции Гаусса по правилу трапеций с точностью 1% может быть произведена с использованием всего 4 точек.^[10] Правило Симпсона требуется в 1,8 раза больше точек для достижения той же точности.^[10][11]

Хотя были предприняты некоторые усилия по распространению формулы суммирования Эйлера-Маклорена на более высокие измерения,^[12] Самое прямое доказательство быстрой сходимости правила трапеций в высших измерениях - свести проблему к проблеме сходимости рядов Фурье. Это рассуждение показывает, что если ${\displaystyle f}$ периодичен на ${\displaystyle n}$-мерное пространство с ${\displaystyle p}$ непрерывные производные, скорость сходимости ${\displaystyle O(h^{p/d})}$. Для очень большого измерения, как видно, интеграция методом Монте-Карло, скорее всего, является лучшим выбором, но для 2-х и 3-х измерений эффективна равномерная выборка. Это используется в вычислительной физике твердого тела, где равномерная выборка по примитивным ячейкам в обратной решетке известна как Интеграция Monkhorst-Pack.^[13]

«Грубые» функции

Для функций, которых нет в C², граница ошибки, указанная выше, не применима. Тем не менее, границы ошибок для таких грубых функций могут быть получены, которые обычно показывают более медленную сходимость с количеством вычислений функции. ${\displaystyle N}$ чем ${\displaystyle O(N^{-2})}$ поведение, указанное выше. Интересно, что в этом случае правило трапеций часто имеет более точные границы, чем Правило Симпсона для того же количества оценок функций.^[14]

Применимость и альтернативы

Правило трапеции - это одна из семейства формул для численное интегрирование называется Формулы Ньютона – Котеса, из которых правило средней точки похоже на правило трапеции. Правило Симпсона является другим членом того же семейства и в целом имеет более быструю сходимость, чем правило трапеций для функций, которые дважды непрерывно дифференцируемы, хотя и не во всех конкретных случаях. Однако для различных классов более грубых функций (с более слабыми условиями гладкости) правило трапеций имеет более быструю сходимость, чем правило Симпсона.^[14]

Более того, правило трапеции становится очень точным, когда периодические функции интегрированы по своим периодам, которые могут быть проанализированы различными способами.^[7][11] Аналогичный эффект доступен для пиковых функций.^[10][11]

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

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

• Квадратура Гаусса
• Формулы Ньютона – Котеса
• Прямоугольный метод
• Метод Ромберга
• Правило Симпсона
• Интегральное уравнение Вольтерра # Численное решение с использованием правила трапеции

Примечания

1. Оссендрейвер, Матье (29 января 2016 г.). «Древние вавилонские астрономы вычислили положение Юпитера на основе графика времени-скорости». Наука. 351 (6272): 482–484. Дои:10.1126 / science.aad8085. PMID  26823423. S2CID  206644971.
2. Аткинсон (1989, уравнение (5.1.7))
3. (Weideman 2002, п. 23, раздел 2)
4. Аткинсон (1989, уравнение (5.1.9))
5. Аткинсон (1989, п. 285)
6. Бремя и ярмарки (2011), п. 194) Ошибка harvtxt: нет цели: CITEREFBurdenFaires2011 (помощь)
7. (Рахман и Шмайссер, 1990 г. )
8. Кресс, Райнер (1998). Численный анализ, том 181 выпускных текстов по математике. Springer-Verlag.
9. Гудвин, Э. Т. (1949). «Оценка интегралов формы». Математические труды Кембриджского философского общества. 45 (2): 241–245. Дои:10.1017 / S0305004100024786. ISSN  1469-8064.
10. Каламбет, Юрий; Козьмин Юрий; Самохин, Андрей (2018). «Сравнение правил интегрирования в случае очень узких хроматографических пиков». Хемометрия и интеллектуальные лабораторные системы. 179: 22–30. Дои:10.1016 / j.chemolab.2018.06.001. ISSN  0169-7439.
11. (Weideman 2002 )
12. "Формула суммирования Эйлера-Маклорена для кратных сумм". math.stackexchange.com.
13. Томпсон, Ник. «Численное интегрирование по зонам Бриллюэна». bandgap.io. Получено 19 декабря 2017.
14. (Круз-Урибе и Нойгебауэр, 2002 г. )

Рекомендации

• Аткинсон, Кендалл Э. (1989), Введение в численный анализ (2-е изд.), Нью-Йорк: Джон Уайли и сыновья, ISBN  978-0-471-50023-0
• Rahman, Qazi I .; Шмайссер, Герхард (декабрь 1990 г.), "Характеристика скорости сходимости трапециевидной линейки", Numerische Mathematik, 57 (1): 123–138, Дои:10.1007 / BF01386402, ISSN  0945-3245, S2CID  122245944
• Бэрден, Ричард Л .; Фэрс, Дж. Дуглас (2000), Числовой анализ (7-е изд.), Брукс / Коул, ISBN  978-0-534-38216-2
• Вайдеман, Дж. А. С. (январь 2002 г.), "Численное интегрирование периодических функций: несколько примеров", Американский математический ежемесячник, 109 (1): 21–36, Дои:10.2307/2695765, JSTOR  2695765
• Cruz-Uribe, D .; Нойгебауэр, К. Дж. (2002), «Границы точных ошибок для правила трапеции и правила Симпсона» (PDF), Журнал неравенств в чистой и прикладной математике, 3 (4)

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

• Формула трапеции. И. Мысовских, Энциклопедия математики, изд. М. Хазевинкель
• Замечания о сходимости квадратуры по правилу трапеций
• Реализация трапециевидной квадратуры, предоставленная Boost.Math