Namespaces
Variants
Actions

Difference between revisions of "Gregory formula"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (→‎Comments: links)
m (tex encoded by computer)
 
Line 1: Line 1:
''for the approximate integration of a function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045120/g0451201.png" />''
+
<!--
 +
g0451201.png
 +
$#A+1 = 39 n = 0
 +
$#C+1 = 39 : ~/encyclopedia/old_files/data/G045/G.0405120 Gregory formula
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
 +
 
 +
{{TEX|auto}}
 +
{{TEX|done}}
 +
 
 +
''for the approximate integration of a function  $  f $''
  
 
The formula
 
The formula
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045120/g0451202.png" /></td> </tr></table>
+
$$
 +
{
 +
\frac{1}{h}
 +
}
 +
\int\limits _ { a } ^ { {a }  + nh } f ( x)  dx  = \
 +
{
 +
\frac{1}{2}
 +
} y _ {0} +
 +
y _ {1} + \dots +
 +
y _ {n - 1 }  + {
 +
\frac{1}{2}
 +
} y _ {n} +
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045120/g0451203.png" /></td> </tr></table>
+
$$
 +
+
 +
A _ {2} ( \Delta  ^ {1} y _ {n - 1 }  - \Delta  ^ {1} y _ {0} ) -
 +
A _ {3} ( \Delta  ^ {2} y _ {n - 2 }  - \Delta  ^ {2} y _ {0} ) +
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045120/g0451204.png" /></td> </tr></table>
+
$$
 +
+
 +
A _ {4} ( \Delta  ^ {3} y _ {n - 3 }  - \Delta  ^ {3} y _ {0} ) - A _ {5} ( \Delta  ^ {4} y _ {n - 4 }  + \Delta  ^ {4} y _ {0} ) + \dots + R,
 +
$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045120/g0451205.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045120/g0451206.png" /> are the differences of the function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045120/g0451207.png" /> of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045120/g0451208.png" /> at the points <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045120/g0451209.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045120/g04512010.png" /> and
+
where $  y _ {j} = f ( a + jh) $,  
 +
and $  \Delta  ^ {l} y _ {j} $
 +
are the differences of the function $  y $
 +
of order $  l = 1, 2 \dots $
 +
at the points $  a + jh $,
 +
$  j = 0 \dots n, $
 +
and
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045120/g04512011.png" /></td> </tr></table>
+
$$
 +
A _ {k}  = \
 +
\int\limits _ { 0 } ^ { 1 }
 +
 
 +
\frac{t ( t - 1) \dots ( t - k + 1) }{( k!) }
 +
  dt,\ \
 +
k = 2, 3 ,\dots .
 +
$$
  
 
In particular,
 
In particular,
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045120/g04512012.png" /></td> </tr></table>
+
$$
 +
A _ {2}  = - {
 +
\frac{1}{12}
 +
} ,\ \
 +
A _ {3}  = {
 +
\frac{1}{24}
 +
} ,
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045120/g04512013.png" /></td> </tr></table>
+
$$
 +
A _ {4}  = - {
 +
\frac{19}{720}
 +
} ,\  A _ {5}  = {
 +
\frac{3}{160}
 +
} ,\dots .
 +
$$
  
Gregory's formula is obtained by the integration of the interpolation polynomial with nodes at <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045120/g04512014.png" />. Gregory's formula with differences of orders up to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045120/g04512015.png" /> inclusive can be obtained from the [[Newton–Cotes quadrature formula|Newton–Cotes quadrature formula]] of closed type (cf. [[Cotes formulas|Cotes formulas]]), and for this reason the residual terms of the two formulas are identical. The simplest variant of Gregory's formula was proposed by J. Gregory in 1668.
+
Gregory's formula is obtained by the integration of the interpolation polynomial with nodes at $  a, a + h \dots a + nh $.  
 +
Gregory's formula with differences of orders up to $  n $
 +
inclusive can be obtained from the [[Newton–Cotes quadrature formula|Newton–Cotes quadrature formula]] of closed type (cf. [[Cotes formulas|Cotes formulas]]), and for this reason the residual terms of the two formulas are identical. The simplest variant of Gregory's formula was proposed by J. Gregory in 1668.
  
 
====References====
 
====References====
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  I.S. Berezin,  N.P. Zhidkov,  "Computing methods" , Pergamon  (1973)  (Translated from Russian)</TD></TR></table>
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  I.S. Berezin,  N.P. Zhidkov,  "Computing methods" , Pergamon  (1973)  (Translated from Russian)</TD></TR></table>
 
 
  
 
====Comments====
 
====Comments====
In [[#References|[1]]] above, the Gregory formulas are derived by means of the [[Fraser diagram|Fraser diagram]] and by integrating the resulting polynomial interpolation formula in each interval <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045120/g04512016.png" />. In this reference it is also observed that they can be derived from the [[Euler–MacLaurin formula|Euler–MacLaurin formula]] by suitable discretization of the  "end corrections" . It turns out that this approach is rather straightforward and yields explicit expressions in terms of [[Stirling numbers]] and [[Bernoulli numbers]] for the coefficients <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045120/g04512017.png" /> (cf. [[#References|[a2]]]). Yet another approach for deriving the Gregory formulas integrates the  "initial-value problem"  <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045120/g04512018.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045120/g04512019.png" /> from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045120/g04512020.png" /> until <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045120/g04512021.png" /> by a numerical integration method with step size <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045120/g04512022.png" />. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045120/g04512023.png" /> denote the numerical approximation obtained for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045120/g04512024.png" />. Since <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045120/g04512025.png" /> equals the integration of the function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045120/g04512026.png" /> over the interval <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045120/g04512027.png" />, one may consider <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045120/g04512028.png" /> as an approximation integration of (or quadrature formula for) the function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045120/g04512029.png" /> over the interval <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045120/g04512030.png" />. If the numerical integration method used for integrating <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045120/g04512031.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045120/g04512032.png" /> is a linear multi-step method generated by polynomials <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045120/g04512033.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045120/g04512034.png" />, then the quadrature formula determined by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045120/g04512035.png" /> is called a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045120/g04512037.png" />-reducible quadrature formula. If the linear multi-step method <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045120/g04512038.png" /> is an Adams–Moulton method (cf. [[Adams method|Adams method]]) with starting values derived from interpolatory quadrature formulas, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045120/g04512039.png" /> is identical with a Gregory formula. The notion of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045120/g04512040.png" />-reducible quadrature formulas was introduced by J. Matthys [[#References|[a4]]]. The general theory of these formulas is due to P.H.M. Wolkenfelt [[#References|[a6]]]. The particular case of the Gregory formulas is discussed in [[#References|[a5]]] and [[#References|[a2]]], and, especially, in [[#References|[a1]]]. These references give expressions for the residual term (or quadrature error) of Gregory formulas with differences of arbitrary orders. Gregory formulas play an important role in the numerical solution of Volterra equations (cf. [[#References|[a5]]], [[#References|[a3]]] and [[#References|[a2]]]).
+
In [[#References|[1]]] above, the Gregory formulas are derived by means of the [[Fraser diagram|Fraser diagram]] and by integrating the resulting polynomial interpolation formula in each interval $  [ a + jh , a + jh + h ] $.  
 +
In this reference it is also observed that they can be derived from the [[Euler–MacLaurin formula|Euler–MacLaurin formula]] by suitable discretization of the  "end corrections" . It turns out that this approach is rather straightforward and yields explicit expressions in terms of [[Stirling numbers]] and [[Bernoulli numbers]] for the coefficients $  A _ {k} $(
 +
cf. [[#References|[a2]]]). Yet another approach for deriving the Gregory formulas integrates the  "initial-value problem"   $  y  ^ \prime  ( x) = f ( x) $,  
 +
$  y ( a) = 0 $
 +
from $  x = a $
 +
until $  x = a + n h $
 +
by a numerical integration method with step size $  h $.  
 +
Let $  Y ( n h ) $
 +
denote the numerical approximation obtained for $  y ( n h ) $.  
 +
Since $  y ( n h ) $
 +
equals the integration of the function $  f $
 +
over the interval $  [ a , a + n h ] $,  
 +
one may consider $  Y ( n h ) $
 +
as an approximation integration of (or quadrature formula for) the function $  f $
 +
over the interval $  [ a , a + n h ] $.  
 +
If the numerical integration method used for integrating $  y  ^  \prime  ( x) = f ( x) $,  
 +
$  y ( a) = 0 $
 +
is a linear multi-step method generated by polynomials $  \rho $
 +
and $  \sigma $,  
 +
then the quadrature formula determined by $  Y ( n h ) $
 +
is called a $  ( \rho , \sigma ) $-
 +
reducible quadrature formula. If the linear multi-step method $  ( \rho , \sigma ) $
 +
is an Adams–Moulton method (cf. [[Adams method|Adams method]]) with starting values derived from interpolatory quadrature formulas, then $  Y ( n h ) $
 +
is identical with a Gregory formula. The notion of $  ( \rho , \sigma ) $-
 +
reducible quadrature formulas was introduced by J. Matthys [[#References|[a4]]]. The general theory of these formulas is due to P.H.M. Wolkenfelt [[#References|[a6]]]. The particular case of the Gregory formulas is discussed in [[#References|[a5]]] and [[#References|[a2]]], and, especially, in [[#References|[a1]]]. These references give expressions for the residual term (or quadrature error) of Gregory formulas with differences of arbitrary orders. Gregory formulas play an important role in the numerical solution of Volterra equations (cf. [[#References|[a5]]], [[#References|[a3]]] and [[#References|[a2]]]).
  
 
====References====
 
====References====
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  H. Brass,  "Quadraturverfahren" , Vandenhoeck &amp; Ruprecht  (1977)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  H. Brunner,  P.J. van der Houwen,  "The numerical solution of Volterra equations" , North-Holland  (1986)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  H. Brunner,  J.D. Lambert,  "Stability of numerical methods for Volterra integro-differential equations"  ''Computing'' , '''12'''  (1974)  pp. 75–89</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  J. Matthys,  "A stable linear multistep method for Volterra integro-differential equations"  ''Numer. Math.'' , '''27'''  (1976)  pp. 85–94</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  J. Steinberg,  "Numerical solution of Volterra integral equations"  ''Numer. Math.'' , '''19'''  (1972)  pp. 212–217</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  P.H.M. Wolkenfelt,  "The construction of reducible quadrature rules for Volterra integral and integro-differential equations"  ''IMA J. Numer. Anal.'' , '''2'''  (1982)  pp. 131–152</TD></TR></table>
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  H. Brass,  "Quadraturverfahren" , Vandenhoeck &amp; Ruprecht  (1977)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  H. Brunner,  P.J. van der Houwen,  "The numerical solution of Volterra equations" , North-Holland  (1986)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  H. Brunner,  J.D. Lambert,  "Stability of numerical methods for Volterra integro-differential equations"  ''Computing'' , '''12'''  (1974)  pp. 75–89</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  J. Matthys,  "A stable linear multistep method for Volterra integro-differential equations"  ''Numer. Math.'' , '''27'''  (1976)  pp. 85–94</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  J. Steinberg,  "Numerical solution of Volterra integral equations"  ''Numer. Math.'' , '''19'''  (1972)  pp. 212–217</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  P.H.M. Wolkenfelt,  "The construction of reducible quadrature rules for Volterra integral and integro-differential equations"  ''IMA J. Numer. Anal.'' , '''2'''  (1982)  pp. 131–152</TD></TR></table>

Latest revision as of 19:42, 5 June 2020


for the approximate integration of a function $ f $

The formula

$$ { \frac{1}{h} } \int\limits _ { a } ^ { {a } + nh } f ( x) dx = \ { \frac{1}{2} } y _ {0} + y _ {1} + \dots + y _ {n - 1 } + { \frac{1}{2} } y _ {n} + $$

$$ + A _ {2} ( \Delta ^ {1} y _ {n - 1 } - \Delta ^ {1} y _ {0} ) - A _ {3} ( \Delta ^ {2} y _ {n - 2 } - \Delta ^ {2} y _ {0} ) + $$

$$ + A _ {4} ( \Delta ^ {3} y _ {n - 3 } - \Delta ^ {3} y _ {0} ) - A _ {5} ( \Delta ^ {4} y _ {n - 4 } + \Delta ^ {4} y _ {0} ) + \dots + R, $$

where $ y _ {j} = f ( a + jh) $, and $ \Delta ^ {l} y _ {j} $ are the differences of the function $ y $ of order $ l = 1, 2 \dots $ at the points $ a + jh $, $ j = 0 \dots n, $ and

$$ A _ {k} = \ \int\limits _ { 0 } ^ { 1 } \frac{t ( t - 1) \dots ( t - k + 1) }{( k!) } dt,\ \ k = 2, 3 ,\dots . $$

In particular,

$$ A _ {2} = - { \frac{1}{12} } ,\ \ A _ {3} = { \frac{1}{24} } , $$

$$ A _ {4} = - { \frac{19}{720} } ,\ A _ {5} = { \frac{3}{160} } ,\dots . $$

Gregory's formula is obtained by the integration of the interpolation polynomial with nodes at $ a, a + h \dots a + nh $. Gregory's formula with differences of orders up to $ n $ inclusive can be obtained from the Newton–Cotes quadrature formula of closed type (cf. Cotes formulas), and for this reason the residual terms of the two formulas are identical. The simplest variant of Gregory's formula was proposed by J. Gregory in 1668.

References

[1] I.S. Berezin, N.P. Zhidkov, "Computing methods" , Pergamon (1973) (Translated from Russian)

Comments

In [1] above, the Gregory formulas are derived by means of the Fraser diagram and by integrating the resulting polynomial interpolation formula in each interval $ [ a + jh , a + jh + h ] $. In this reference it is also observed that they can be derived from the Euler–MacLaurin formula by suitable discretization of the "end corrections" . It turns out that this approach is rather straightforward and yields explicit expressions in terms of Stirling numbers and Bernoulli numbers for the coefficients $ A _ {k} $( cf. [a2]). Yet another approach for deriving the Gregory formulas integrates the "initial-value problem" $ y ^ \prime ( x) = f ( x) $, $ y ( a) = 0 $ from $ x = a $ until $ x = a + n h $ by a numerical integration method with step size $ h $. Let $ Y ( n h ) $ denote the numerical approximation obtained for $ y ( n h ) $. Since $ y ( n h ) $ equals the integration of the function $ f $ over the interval $ [ a , a + n h ] $, one may consider $ Y ( n h ) $ as an approximation integration of (or quadrature formula for) the function $ f $ over the interval $ [ a , a + n h ] $. If the numerical integration method used for integrating $ y ^ \prime ( x) = f ( x) $, $ y ( a) = 0 $ is a linear multi-step method generated by polynomials $ \rho $ and $ \sigma $, then the quadrature formula determined by $ Y ( n h ) $ is called a $ ( \rho , \sigma ) $- reducible quadrature formula. If the linear multi-step method $ ( \rho , \sigma ) $ is an Adams–Moulton method (cf. Adams method) with starting values derived from interpolatory quadrature formulas, then $ Y ( n h ) $ is identical with a Gregory formula. The notion of $ ( \rho , \sigma ) $- reducible quadrature formulas was introduced by J. Matthys [a4]. The general theory of these formulas is due to P.H.M. Wolkenfelt [a6]. The particular case of the Gregory formulas is discussed in [a5] and [a2], and, especially, in [a1]. These references give expressions for the residual term (or quadrature error) of Gregory formulas with differences of arbitrary orders. Gregory formulas play an important role in the numerical solution of Volterra equations (cf. [a5], [a3] and [a2]).

References

[a1] H. Brass, "Quadraturverfahren" , Vandenhoeck & Ruprecht (1977)
[a2] H. Brunner, P.J. van der Houwen, "The numerical solution of Volterra equations" , North-Holland (1986)
[a3] H. Brunner, J.D. Lambert, "Stability of numerical methods for Volterra integro-differential equations" Computing , 12 (1974) pp. 75–89
[a4] J. Matthys, "A stable linear multistep method for Volterra integro-differential equations" Numer. Math. , 27 (1976) pp. 85–94
[a5] J. Steinberg, "Numerical solution of Volterra integral equations" Numer. Math. , 19 (1972) pp. 212–217
[a6] P.H.M. Wolkenfelt, "The construction of reducible quadrature rules for Volterra integral and integro-differential equations" IMA J. Numer. Anal. , 2 (1982) pp. 131–152
How to Cite This Entry:
Gregory formula. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Gregory_formula&oldid=47138
This article was adapted from an original article by L.D. Kudryavtsev (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article