Stable Newton-Cotes Formulas (Open Type)

Few years ago I have published some ideas on how to improve numerical stability of the Newton-Cotes formulas of closed type. Today I want to apply the same ideas to so-called “open” NC-formulas when boundary points are not used for integral approximation.

Just to remind the basic facts and ideas. Newton-Cotes rules use polynomial interpolation to approximate the function under integral sign. Then integral of the function is assumed to be equal to the integral of the approximating polynomial (which can be computed explicitly).

Idea is simple enough, but it has one serious drawback.

Although polynomials are easy to work with, they are very unpredictable/problematic beasts. Enough to say that even such simple task as root finding of polynomials is inherently ill-conditioned (e.g. Wilkinson’s polynomial).

Similar issues with stability arise when we use polynomial interpolation over equidistant nodes (used by Newton-Cotes). The classic example of why this is a bad idea is Runge’s phenomenon.

Because of the issues, Gauss-family quadrature are usually used instead of Newton-Cotes. However in some applications we stuck with uniform sampling and have no other choice but to improve the Newton-Cotes.

One of the most obvious ways of doing that is to use least-squares approximation instead of interpolation. Another useful tool is studying properties of the formulas in spectral domain.

There is additional information in my older posts (1, 2, etc.) – here I just provide resulting formulas for “stable” Newton-Cotes rules of open type.

Task

We consider the problem of numerical approximation of integral of a function $f(x)$ on $x\in[a,b]$ :

$\label{eq:integral} I(f)=\int_a^b f(x)\,\mathrm{d}x$

having only discrete values ${f_i=f(x_i)}$ sampled at equidistant points $x_i$ with step $h$ :

$\begin{align*} x_i &= a+i\,h,\,\,\,\,i=0,\dots,N-1\\ h &=\frac{b-a}{N-1} \end{align*}$

Our goal here is to use only interior nodes for approximation (ignoring $f_0$ and $f_{N-1}$ ).
Closed rules (when all nodes are used) were derived here.

Least-squares Newton-Cotes formulas (open type)

$O(h^5)$ :

$\begin{tabular}{|r|c|l|} \hline $N$& Classic (Open) Newton-Cotes Formulas of $O(\displaystyle{{h}^{5}\,f^{(4)}})$& Error Term\\ \hline &&\\ 5&$\displaystyle{\frac{4}{3}\,h \left( 2\,f_{{1}}-f_{{2}}+2\,f_{{3}} \right)}$&$\displaystyle{{\frac{14}{45}}{{h}^{5}}\,f^{(4)}(\xi)}$\\ &&\\ 6&$\displaystyle{{\frac {5}{24}}\,h \left( 11\,f_{{1}}+f_{{2}}+f_{{3}}+11\,f_{{4}} \right)}$&$\displaystyle{{\frac{95}{144}}{{h}^{5}}\,f^{(4)}(\xi)}$\\ &&\\ \hline $N$& Least-Squares (Open) Newton-Cotes Formulas of $O(\displaystyle{{h}^{5}\,f^{(4)}})$& Error Term\\ \hline &&\\ 7&$\displaystyle{{\frac {3}{35}}\,h \left( 24\,f_{{1}}+9\,f_{{2}}+4\,f_{{3}}+9\,f_{{4}}+24\,f_{{5}} \right)} \right)}$&$\displaystyle{{\frac{87}{70}}{{h}^{5}}\,f^{(4)}(\xi)}$\\ &&\\ 8&$\displaystyle{{\frac {7}{48}}\,h \left( 13\,f_{{1}}+7\,f_{{2}}+4\,f_{{3}}+4\,f_{{4}}+7\,f_{{5}}+13\,f_{{6}} \right)}$&$\displaystyle{{\frac{1547}{720}}{{h}^{5}}\,f^{(4)}(\xi)}$\\ &&\\ 9&$\displaystyle{{\frac {8}{63}}\,h \left( 14\,f_{{1}}+6\,f_{{3}}+5\,f_{{4}}+6\,f_{{5}}+14\,f_{{7}}+9\,f_{{2}}+9\,f_{{6}} \right)} \right)}$&$\displaystyle{{\frac{1096}{315}}{{h}^{5}}\,f^{(4)}(\xi)}$\\ &&\\ \hline \end{tabular}$

open_nc_h5

$O(h^7)$ :

$\begin{tabular}{|r|c|l|c|} \hline $N$& Classic (Open) Newton-Cotes Formulas of $O(\displaystyle{{h}^{7}\,f^{(6)}})$&Error Term&$||\cdot||_1$\\ \hline &&&\\ 7&$\displaystyle{\frac{3}{10}\,h \left( 11\,f_{{1}}-14\,f_{{2}}+26\,f_{{3}}-14\,f_{{4}}+11\,f_{{5}} \right)}$&$\displaystyle{{\frac{41}{140}}{{h}^{7}}\,f^{(6)}(\xi)}$&$3.8$\\ &&&\\ \hline $N$& Least-Squares (Open) Newton-Cotes Formulas of $O(\displaystyle{{h}^{7}\,f^{(6)}})$&&\\ \hline &&&\\ 8&$\displaystyle{{\frac {7}{1440}}\,h \left( 611\,f_{{1}}-453\,f_{{2}}+562\,f_{{3}}+562\,f_{{4}}-453\,f_{{5}}+611\,f_{{6}} \right)}$&$\displaystyle{{\frac{5257}{8640}}{{h}^{7}}\,f^{(6)}(\xi)}$&$2.3$\\ &&&\\ 9&$\displaystyle{{\frac {8}{3465}}\,h \left( 1181\,f_{{1}}-464\,f_{{2}}+467\,f_{{3}}+1097\,f_{{4}}+467\,f_{{5}}-464\,f_{{6}}+1181\,f_{{7}} \right)} \right)}$&$\displaystyle{{\frac{12136}{10395}}{{h}^{7}}\,f^{(6)}(\xi)}$&$1.5$\\ &&&\\ 10&$\displaystyle{{\frac {9}{3520}}\,h \left( 993\,f_{{1}}-147\,f_{{2}}+203\,f_{{3}}+711\,f_{{4}}+711\,f_{{5}}+203\,f_{{6}}-147\,f_{{7}}+993\,f_{{8}} \right)}$&$\displaystyle{{\frac{10359}{4928}}{{h}^{7}}\,f^{(6)}(\xi)}$&$1.2$\\ &&&\\ 11&$\displaystyle{\frac{5\,h}{2574}\,\left[ \begin{matrix} 1230\,(f_{{1}}+f_{{9}})+40\,(f_{{2}}+f_{{8}})+\\ 185\,(f_{{3}}+f_{{7}})+670\,(f_{{4}}+f_{{6}})+898\,f_{{5}} \end{matrix} \right] }$ & $\displaystyle{\frac {29875}{8316}{{h}^{7}}\,f^{(6)}(\xi)}$&$1$\\ &&&\\ \hline \end{tabular}$

open_nc_h7

Spectral plots show how sensitive every formula to noise (e.g. rounding errors, etc.) in the data. Overall as closer curve to axis X as better the stability of the corresponding rule. In combination with $l_1$ norm it gives us full picture for stability assessment.

Classic rules based on interpolation show strong amplification of rounding errors (or any noise in the data in general) – the red curves.

Not surprisingly we see the substantial improvement when we use least-squares. However to reach the stability we have to use much longer filters. It looks like the “open” case is ill-conditioned in its nature (interpolatory formulas have very high $l_1$ norm right from the onset).

We advise using rule with at least $N=11$ if you consider $O(h^7)$ -family.

(4 votes, average: 3.50)

Stable Newton-Cotes Formulas (Open Type)

Task

Least-squares Newton-Cotes formulas (open type)

Post a Comment