Overlapped Newton-Cotes Quadratures

The goal of this paper is to build numerical integration quadratures for equidistant data which use function values outside interval of integration.

One of the main applications for such formulas is to improve accuracy of compound rules without increase in number of function evaluations. In particular we propose refined composite algorithm which deliver higher precision than Simpson’s 3/8 using the same number of function values.

Reference formulas and their properties are included.

Simpson’s 3/8 composite rule is perhaps the most used method for numerical integration of equally-spaced data.
It has fifth order accuracy and simple computational structure:

$O(h^5)$ :

(1) $\begin{equation*} \int_{x_0}^{x_{3m}} f(x) \mathrm{d}x \approx \frac{3\,h}{8}\sum_{k=1}^{m}\,\left[f_{3k-3}+3\,(f_{3k-2}+f_{3k-1})+f_{3k}\right] \end{equation*}$

Composite scheme divides whole integration interval by non-overlapped $m$ smaller intervals and uses simple Newton-Cotes rule for each of them.
Although this technique gives good results for appropriately chosen $h$ it seems that composite rule doesn’t use full potential of numerous interior function samples. They could contribute more to the overall precision of the algorithm.

Our goal is to improve accuracy of Simpson’s 3/8 composite rule without increase of function evaluations.

With this purpose we have build special quadratures which use function values beyond integration interval. Lets denote total number of nodes in quadrature as $N$ and outer function values as $L$ . Then we have

$\int_{x_L}^{x_{N-1-L}} f(x) \mathrm{d}x \approx \sum_{i=0}^{N-1}c_i\,f_i$

Here are several quadratures of such type for $L=\frac{N}{2}-2$ :

$\begin{tabular}{|r|c|l|c|} \hline $N$& Overlapped Newton-Cotes Quadratures & Error Term & $L_1$ Norm\\ \hline &&&\\ 6&$\displaystyle{\frac{3\,h}{160}\,\left( -f_{{0}}+23\,f_{{1}}+58\,f_{{2}}+58\,f_{{3}}+23\,f_{{4}}-f_{{5}} \right)}$&$\displaystyle{\frac{13\,{h}^{7}}{2240}\,f^{(6)}(\xi)}$&1.03 \\ &&&\\ 8&$\displaystyle{\frac{h}{4480}\, \left[ \begin{matrix} 13\,(f_{{0}}+f_{{7}})-149\,(f_{{1}}+f_{{6}})+\\ 2049\,(f_{{2}}+f_{{5}})+4807\,(f_{{3}}+f_{{4}}) \end{matrix} \right] }$&$\displaystyle{\frac{7\,{h}^{9}}{6400}\,f^{(8)}(\xi)}$&1.04\\ &&&\\ 10&$\displaystyle{\frac{h}{89600}\, \left[ \begin{matrix} -49\,(f_{{0}}+f_{{9}})+603\,(f_{{1}}+f_{{8}})\\ -3960\,(f_{{2}}+f_{{7}})+42352\,(f_{{3}}+f_{{6}})+\\ 95454\,(f_{{4}}+f_{{5}}) \end{matrix} \right] }$&$\displaystyle{\frac{443\,{h}^{11}}{1971200}\,f^{(10)}(\xi)}$&1.06\\ &&&\\ \hline \end{tabular}$

Now, in composite scheme we can apply overlapped quadratures for approximating integral on $k=2,\dots,m-1$ intervals instead of lower-order Simpson’s 3/8 rule.

Composite rules with enhanced precision without increase in function evaluations:

$O(h^7)$ :

(2) $\begin{align*} \int_{x_0}^{x_{3m}} f(x) \mathrm{d}x &\approx \frac{3\,h}{8}\sum_{k=1,\,m}\,\left[f_{3k-3}+3\,(f_{3k-2}+f_{3k-1})+f_{3k}\right]\\ &+\frac{3\,h}{160}\sum_{k=2}^{m-1}\,\left[-f_{3k-4}+23\,f_{3k-3}+58\,f_{3k-2}+58\,f_{3k-1}+23\,f_{3k}-f_{3k+1}\right] \end{align*}$

$O(h^9)$ :

(3) $\begin{align*} \int_{x_0}^{x_{3m}} f(x) \mathrm{d}x &\approx \frac{3\,h}{8}\sum_{k=1,\,m}\,\left[f_{3k-3}+3\,(f_{3k-2}+f_{3k-1})+f_{3k}\right]\\ &+\frac{h}{4480}\sum_{k=2}^{m-1}\,{ \left[ \begin{matrix} 13\,(f_{{3k-5}}+f_{{3k+2}})-149\,(f_{{3k-4}}+f_{{3k+1}})+\\ 2049\,(f_{{3k-3}}+f_{{3k}})+4807\,(f_{{3k-2}}+f_{{3k-1}}) \end{matrix} \right]} \end{align*}$

$O(h^{11})$ :

(4) $\begin{align*} \int_{x_0}^{x_{3m}} f(x) \mathrm{d}x &\approx \frac{3\,h}{8}\sum_{k=1,\,m}\,\left[f_{3k-3}+3\,(f_{3k-2}+f_{3k-1})+f_{3k}\right]\\ &+\frac{h}{89600}\sum_{k=2}^{m-1}\,{ \left[ \begin{matrix} -49\,(f_{{3k-6}}+f_{{3k+3}})+603\,(f_{{3k-5}}+f_{{3k+2}})\\ -3960\,(f_{{3k-4}}+f_{{3k+1}})+42352\,(f_{{3k-3}}+f_{{3k}})+\\ 95454\,(f_{{3k-2}}+f_{{3k-1}}) \end{matrix} \right]} \end{align*}$

Notice that we use extra nodes from neighboring intervals for estimation on every step $k=2,\dots,m-1$ . This allows us to improve precision on interior intervals (first and last intervals still have $O(h^5)$ ). Most importantly, proposed high precision composite rules use the same number of nodes as Simpson’s 3/8 does. They can be plugged in place of Simpson’s 3/8 rules seamlessly in any application.

Special attention should be payed to the stability of the proposed formulas. As you see overlapped quadratures have negative coefficients and $L_1$ norm is bigger than 1.0 as a result. This usually indicates possible instability of the quadratures in some cases. However their magnitude responses show that they are stable:

Noisy high frequencies (usual indicators of instability) are suppressed, there are no other abnormalities. Besides we have tested proposed & Simpson’s 3/8 composite rules on 100+ test functions for integration from [1]. Overlapped quadratures gave more accurate result in 75% of cases without special tuning of the step size $h$ .

This combined with the fact that actually norm is only slightly higher than 1.0 allows us to recommend refined composite schemes for applications.

References

I have used many excellent sources, but only one for the moment:
[1] H. Engels, Numerical Quadrature and Cubature, Academic Press, London, 1980.

(1 votes, average: 5.00)

Loading ...

Print This Page

2 Comments

renato

Posted May 25, 2011 at 5:51 pm | #

Pavel, thank you for replying! As you suggested, I’ll try overlapped formulae also. Just a question : in (2)-(4) is the first summation running for k=0,m or perhaps for k=1,m?
If k=0,m, wouldn’t it require 3 additional evaluations (f(-3),f(-2),f(-1)) ?

thank you,

renato

- Pavel Holoborodko
  
  Posted May 25, 2011 at 6:00 pm | #
  
  Yep, this is mistake – already fixed. Thank you.

Overlapped Newton-Cotes Quadratures

References

2 Comments

Post a Comment