[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

An improved Gregory-like method for 1-D quadrature

  • Published:
Numerische Mathematik Aims and scope Submit manuscript

Abstract

The quadrature formulas described by James Gregory (1638–1675) improve the accuracy of the trapezoidal rule by adjusting the weights near the ends of the integration interval. In contrast to the Newton–Cotes formulas, their weights are constant across the main part of the interval. However, for both of these approaches, the polynomial Runge phenomenon limits the orders of accuracy that are practical. For the algorithm presented here, this limitation is greatly reduced. In particular, quadrature formulas on equispaced 1-D node sets can be of high order (tested here up through order 20) without featuring any negative weights.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9

Similar content being viewed by others

Notes

  1. Gregory’s letter of 1670 (to John Collins, written mostly in English) indeed begins with “I suppose these series I send you here enclosed, may have some affinity with those inventions you advertise me that Mr. Newton have discovered.” Only extracts of the letter are preserved. These do not include Gregory’s derivation.

References

  1. Advanpix: Multiprecision computing toolbox for MATLAB. Advanpix LLC, Yokohama, Japan. http://www.advanpix.com/. Accessed 8 Aug 2018

  2. Bailey, D.H., Borwein, J.M.: High-precision numerical integration: progress and challenges. J. Symb. Comput. 46, 741–754 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  3. Bayona, V., Flyer, N., Fornberg, B., Barnett, G.A.: On the role of polynomials in RBF-FD approximations: II. Numerical solution of elliptic PDEs. J. Comput. Phys. 332, 257–273 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  4. Bocher, P., De Meyer, H., Berghe, G.: On Gregory- and modified Gregory-type corrections to Newton–Cotes quadrature. J. Comput. Appl. Math. 50, 145–158 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  5. Brunner, H., van der Houwen, P.J.: The Numerical Solution of Volterra equations. CWI Monographs. Elsevier, Amsterdam (1986)

    Google Scholar 

  6. De Swardt, S.A., De Villiers, J.M.: Gregory type quadrature based on quadratic nodal spline interpolation. Numer. Math. 85, 129–153 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  7. De Villiers, J.: Mathematics of Approximation. Atlantis Press, Amsterdam (2012)

    Book  MATH  Google Scholar 

  8. De Villiers, J.M.: A nodal spline interpolant for the Gregory rule of even order. Numer. Math. 66, 123–137 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  9. Fornberg, B.: A Practical Guide to Pseudospectral Methods. Cambridge University Press, Cambridge (1996)

    Book  MATH  Google Scholar 

  10. Fornberg, B., Flyer, N.: A Primer on Radial Basis Functions with Applications to the Geosciences. SIAM, Philadelphia (2015)

    Book  MATH  Google Scholar 

  11. Fornberg, B., Flyer, N.: Solving PDEs with radial basis functions. Acta Numer. 24, 215–258 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  12. Fraser, D.C.: Newton’s interpolation formulas. Further notes. J. Inst. Actuar. 52(274), 117–135 (1920)

    Article  Google Scholar 

  13. Gregory, J.: Letter to J. Collins, 23 November 1670, pp. 203–212. In: Rigaud: Correspondence of Scientific Men. Oxford University Press (1841)

  14. Javed, M., Trefethen, L.N.: Euler–Maclaurin and Gregory interpolants. Numer. Math. 132, 201–216 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  15. Jordan, C.: Calculus of Finite Differences, 2nd edn. Chelsea, New York (1950)

    MATH  Google Scholar 

  16. Phillips, G.M.: Gregory’s method for numerical integration. Am. Math. Mon. 79(3), 270–274 (1972)

    Article  MathSciNet  MATH  Google Scholar 

  17. Pólya, G.: Über die Konvergenz von Quadraturverfahren. Math. Zeitschrift. 37, 264–286 (1933)

    Article  MathSciNet  MATH  Google Scholar 

  18. Reeger, J.A., Fornberg, B.: Numerical quadrature over smooth surfaces with boundaries. J. Comput. Phys. 355, 176–190 (2018)

    Article  MathSciNet  MATH  Google Scholar 

  19. Romberg, W.: Vereinfachte numerische Integration. Det Kongelige Norske Videnskabers Selskab Forhandlinger 28(7), 30–36 (1955)

    MathSciNet  MATH  Google Scholar 

  20. Takahasi, H., Mori, M.: Double exponential formulas for numerical integration. Res. Inst. Math. Sci. 9, 721–741 (1974)

    Article  MathSciNet  MATH  Google Scholar 

  21. Trefethen, L.N.: Approximation Theory and Approximation Practice. SIAM, Philadelphia (2013)

    MATH  Google Scholar 

  22. Trefethen, L.N., Weideman, J.A.C.: The exponentially convergent trapezoidal rule. SIAM Rev. 56, 384–458 (2014)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Applied Mathematics, University of Colorado, Boulder, CO, 80309, USA

    Bengt Fornberg

  2. Department of Mathematics, United States Naval Academy, Holloway Road, Chauvenet Hall, Annapolis, MD, 21402-5002, USA

    Jonah A. Reeger

Authors
  1. Bengt Fornberg
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jonah A. Reeger
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Bengt Fornberg.

Additional information

Support received from Department of Defense, the Office of Naval Research (Atmospheric Propagation Sciences of High Energy Lasers) and the Air Force Office of Scientific Research (Radial Basis Functions for Numerical Simulation). The views expressed in this article are those of the authors and do not reflect the official policy or position of the United States Navy, Department of Defense, or U.S. Government.

Appendix: Derivations of the alternate matrix formulation

Appendix: Derivations of the alternate matrix formulation

1.1 Derivation based on Eq. (10)

Changing variable \(z=-\log (1-w)\) in (10) gives

$$\begin{aligned} -\left( \frac{1}{\log (1-w)}+\frac{1}{w}\right)&=\sum _{k=0}^{\infty }d_{k}e^{k\log (1-w)}\\&=\sum _{k=0}^{\infty }d_{k}(1-w)^{k}=\sum _{k=0}^{\infty }d_{k}\left( \sum _{i=0}^{k}\left( {\begin{array}{c}k\\ i\end{array}}\right) \right) (-1)^{i}w^{i}\\&=\sum _{i=0}^{\infty }(-1)^{i}w^{i}\left( \sum _{k=i}^{\infty }d_{k}\left( {\begin{array}{c}k\\ i\end{array}}\right) \right) . \end{aligned}$$

By (5), the LHS above equals \(\sum _{i=0}^{\infty }(-1)^{i}b_{i}\). Equating coefficients gives (13).

1.2 Derivation based on matrix algebra

There are numerous exact relations for Vandermonde matrices, especially in equi-spaced cases. Starting by LU-factorizing it, it transpires that the linear system (12) can be rewritten as

$$\begin{aligned} \begin{array}{l} \left[ \begin{array}{cccccccc} 1 &{} 1 &{} 1 &{} 1 &{} 1 &{} \cdots &{} \cdots &{} \cdots \\ &{} 1 &{} 2 &{} 3 &{} 4 &{} \cdots &{} \{\text {Pascal's} &{} \cdots \\ &{} &{} 1 &{} 3 &{} 6 &{} \cdots &{} \text {triangle}\} &{} \cdots \\ &{} &{} &{} 1 &{} 4 &{} \cdots &{} \cdots &{} \cdots \\ &{} &{} &{} &{} 1 &{} \cdots &{} \cdots &{} \cdots \\ &{} &{} &{} &{} &{} \ddots &{} \cdots &{} \cdots \end{array}\right] \left[ \begin{array}{c} d_{0}\\ d_{1}\\ \vdots \\ d_{n}\\ \vdots \\ d_{N} \end{array}\right] =\\ =\left[ \begin{array}{ccccc} \frac{1}{0!}\\ &{} \frac{1}{1!}\\ &{} &{} \frac{1}{2!}\\ &{} &{} &{} \ddots \\ &{} &{} &{} &{} \frac{1}{n!} \end{array}\right] \left[ \begin{array}{cccccc} 1\\ &{} 1\\ &{} -1 &{} 1\\ &{} 2 &{} -3 &{} 1\\ &{} -6 &{} 11 &{} -6 &{} 1\\ &{} \vdots &{} \vdots &{} \vdots &{} \vdots &{} \ddots \end{array}\right] \left[ \begin{array}{c} -1/2\\ 1/12\\ 0\\ -1/120\\ 0\\ \vdots \end{array}\right] . \end{array} \end{aligned}$$
(18)

The entries in the second matrix in the RHS are the first order Stirling numbers \(S(i,j),\;i,j=0,1,2,\ldots \), with generating function

$$\begin{aligned} \prod _{j=0}^{i-1}(x-j)=\sum _{j=0}^{i}S(i,j)\,x^{j}. \end{aligned}$$
(19)

These numbers are readily calculated by the ’Pascal-like’ recursion \(s(i,j)=s(i-1,j-1)-(i-1)s(i-1,j)\), initiated by the trivial values when \(i=0\) and \(j=0\). By the identity

$$\begin{aligned} \sum _{j=1}^{i+1}S(i,j-1)\frac{B_{j}}{j}=-\frac{1}{i+1} \sum _{j=0}^{i+1}S(i+1,j)\,\frac{1}{j+1} \end{aligned}$$

([15]; combine (7), p. 147 with (5), p. 249), the RHS of (18) simplifies to

$$\begin{aligned} -\left[ \begin{array}{ccccc} \frac{1}{1!}\\ &{} \frac{1}{2!}\\ &{} &{} \frac{1}{3!}\\ &{} &{} &{} \ddots \\ &{} &{} &{} &{} \frac{1}{(n+1)!} \end{array}\right] \left[ \begin{array}{cccccc} 1\\ -1 &{} 1\\ 2 &{} -3 &{} 1\\ -6 &{} 11 &{} -6 &{} 1\\ 24 &{} -50 &{} 35 &{} -10 &{} 1\\ \vdots &{} \vdots &{} \vdots &{} \vdots &{} \vdots &{} \ddots \end{array}\right] \left[ \begin{array}{c} 1/2\\ 1/3\\ 1/4\\ 1/5\\ 1/6\\ \vdots \end{array}\right] . \end{aligned}$$
(20)

There is now a leading minus sign, both matrices have been shifted one step up and left, and the RHS vector has become much simplified. The result

$$\begin{aligned} \left[ \begin{array}{cccccccc} 1 &{} 1 &{} 1 &{} 1 &{} 1 &{} \cdots &{} \cdots &{} \cdots \\ &{} 1 &{} 2 &{} 3 &{} 4 &{} \cdots &{} \{\text {Pascal's} &{} \cdots \\ &{} &{} 1 &{} 3 &{} 6 &{} \cdots &{} \text {triangle}\} &{} \cdots \\ &{} &{} &{} 1 &{} 4 &{} \cdots &{} \cdots &{} \cdots \\ &{} &{} &{} &{} 1 &{} \cdots &{} \cdots &{} \cdots \\ &{} &{} &{} &{} &{} \ddots &{} \cdots &{} \cdots \end{array}\right] _{(n+1)\times (N+1)}\left[ \begin{array}{c} d_{0}\\ d_{1}\\ \vdots \\ d_{n}\\ \vdots \\ d_{N} \end{array}\right] _{N+1}=\left[ \begin{array}{c} b_{0}\\ b_{1}\\ \vdots \\ \vdots \\ b_{n} \end{array}\right] _{n+1} \end{aligned}$$
(21)

now follows from combining (7) and (19) with the additional observation that integration in x of the monomials \(x,\,x^{2},\,x^{3},\,\ldots \). produce the factors \(\frac{1}{2},\,\frac{1}{3},\frac{1}{4},\,\ldots \) , matching the RHS vector in (20). The equality of the right hand sides of (18) and (21) can alternatively be deduced from equation (8) in [16].

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Fornberg, B., Reeger, J.A. An improved Gregory-like method for 1-D quadrature. Numer. Math. 141, 1–19 (2019). https://doi.org/10.1007/s00211-018-0992-0

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00211-018-0992-0

Mathematics Subject Classification

Search

Navigation