TOPICS
Search

Newton-Cotes Formulas


The Newton-Cotes formulas are an extremely useful and straightforward family of numerical integration techniques.

To integrate a function f(x) over some interval [a,b], divide it into n equal parts such that f_n=f(x_n) and h=(b-a)/n. Then find polynomials which approximate the tabulated function, and integrate them to approximate the area under the curve. To find the fitting polynomials, use Lagrange interpolating polynomials. The resulting formulas are called Newton-Cotes formulas, or quadrature formulas.

Newton-Cotes formulas may be "closed" if the interval [x_1,x_n] is included in the fit, "open" if the points [x_2,x_(n-1)] are used, or a variation of these two. If the formula uses n points (closed or open), the coefficients of terms sum to n-1.

If the function f(x) is given explicitly instead of simply being tabulated at the values x_i, the best numerical method of integration is called Gaussian quadrature. By picking the intervals at which to sample the function, this procedure produces more accurate approximations (but is significantly more complicated to implement).

TrapezoidalRule

The 2-point closed Newton-Cotes formula is called the trapezoidal rule because it approximates the area under a curve by a trapezoid with horizontal base and sloped top (connecting the endpoints x_1 and x_2). If the first point is x_1, then the other endpoint will be located at

x_2=x_1+h,
(1)

and the Lagrange interpolating polynomial through the points (x_1,f_1) and (x_2,f_2) is

P_2(x)=(x-x_2)/(x_1-x_2)f_1+(x-x_1)/(x_2-x_1)f_2
(2)
=(x-x_1-h)/(-h)f_1+(x-x_1)/hf_2
(3)
=x/h(f_2-f_1)+(f_1+(x_1)/hf_1-(x_1)/hf_2).
(4)

Integrating over the interval (i.e., finding the area of the trapezoid) then gives

int_(x_1)^(x_2)f(x)dx=int_(x_1)^(x_1+h)P_2(x)dx
(5)
=1/(2h)(f_2-f_1)[x^2]_(x_1)^(x_2)+(f_1+(x_1)/hf_1-(x_1)/hf_2)[x]_(x_1)^(x_2)
(6)
=1/(2h)(f_2-f_1)(x_2+x_1)(x_2-x_1)+(x_2-x_1)(f_1+(x_1)/hf_1-(x_1)/hf_2)
(7)
=1/2(f_2-f_1)(2x_1+h)+f_1h+x_1(f_1-f_2)
(8)
=x_1(f_2-f_1)+1/2h(f_2-f_1)+hf_1-x_1(f_2-f_1)
(9)
=1/2h(f_1+f_2)-1/(12)h^3f^('')(xi).
(10)

This is the trapezoidal rule (Ueberhuber 1997, p. 100), with the final term giving the amount of error (which, since x_1<=xi<=x_2, is no worse than the maximum value of f^('')(xi) in this range).

The 3-point rule is known as Simpson's rule. The abscissas are

x_2=x_1+h
(11)
x_3=x_1+2h
(12)

and the Lagrange interpolating polynomial is

P_3(x)=((x-x_2)(x-x_3))/((x_1-x_2)(x_1-x_3))f_1+((x-x_1)(x-x_3))/((x_2-x_1)(x_2-x_3))f_2+((x-x_1)(x-x_2))/((x_3-x_1)(x_3-x_2))f_3
(13)
=(x^2-x(x_2+x_3)+x_2x_3)/(h(2h))f_1+(x^2-x(x_1+x_3)+x_1x_3)/(h(-h))f_2+(x^2-x(x_1+x_2)+x_1x_2)/(2h(h))f_3
(14)
=1/(h^2){x^2(1/2f_1-f_2+1/2f_3)+x[-1/2(2x_1+3h)f_1+(2x_1+2h)f_2-1/2(2x_1+h)f_3]+[1/2(x_1+h)(x_1+2h)f_1-x_1(x_1+2h)f_2+1/2x_1(x_1+h)f_3]}.
(15)

Integrating and simplifying gives

 int_(x_1)^(x_3)f(x)dx=int_(x_1)^(x_1+2h)P_3(x)dx=1/3h(f_1+4f_2+f_3)-1/(90)h^5f^((4))(xi)
(16)

(Ueberhuber 1997, p. 100).

The 4-point closed rule is Simpson's 3/8 rule,

 int_(x_1)^(x_4)f(x)dx=3/8h(f_1+3f_2+3f_3+f_4)-3/(80)h^5f^((4))(xi)
(17)

(Ueberhuber 1997, p. 100). The 5-point closed rule is Boole's rule,

 int_(x_1)^(x_5)f(x)dx=2/(45)h(7f_1+32f_2+12f_3+32f_4+7f_5)-8/(945)h^7f^((6))(xi)
(18)

(Abramowitz and Stegun 1972, p. 886). Higher order rules include the 6-point

 int_(x_1)^(x_6)f(x)dx=5/(288)h(19f_1+75f_2+50f_3+50f_4+75f_5+19f_6)-(275)/(12096)h^7f^((6))(xi),
(19)

7-point

 int_(x_1)^(x_7)f(x)dx=1/(140)h(41f_1+216f_2+27f_3+272f_4 
 +27f_5+216f_6+41f_7)-9/(1400)h^9f^((8))(xi),
(20)

8-point

 int_(x_1)^(x_8)f(x)dx=7/(17280)h(751f_1+3577f_2+1323f_3+2989f_4+2989f_5+1323f_6+3577f_7+751f_8)-(8183)/(518400)h^9f^((8))(xi),
(21)

9-point

 int_(x_1)^(x_9)f(x)dx=4/(14175)h(989f_1+5888f_2-928f_3+10496f_4-4540f_5+10496f_6-928f_7+5888f_8+989f_9)-(2368)/(467775)h^(11)f^((10))(xi)
(22)

(Ueberhuber 1997, p. 100), 10-point

 int_(x_1)^(x_(10))f(x)dx=9/(89600)h[2857(f_1+f_(10))+15741(f_2+f_9)+1080(f_3+f_8)+19344(f_4+f_7)+5778(f_5+f_6)]-(173)/(14620)h^(11)f^((10))(xi),
(23)

and 11-point

 int_(x_1)^(x_(11))f(x)dx=5/(299376)h[16067(f_1+f_(11))+106300(f_2+f_(10))-48525(f_3+f_9)+272400(f_4+f_8)-260550(f_5+f_7)+427368f_6]-(1346350)/(326918592)h^(13)f^((12))(xi)
(24)

rules.

In general, the n-point rule is given by the analytic expression

 int_(x_1)^(x_n)f(x)dx=hsum_(i=1)^nH_(n,i)f_i,
(25)

where

 H_(n,r+1)=((-1)^(n-r))/(r!(n-r)!)int_0^nt(t-1)...(t-r+1)(t-r-1)...(t-n)dt
(26)

(Whittaker and Robinson 1967, p. 154). This gives the triangle of coefficients shown in the following table (OEIS A093735 and A093736).

n\r012345
11/21/2
21/34/31/3
33/89/89/83/8
4(14)/(45)(64)/(45)8/(15)(64)/(45)(14)/(45)
5(95)/(288)(125)/(96)(125)/(144)(125)/(144)(125)/(96)(95)/(288)

Note that

 sum_(r=0)^nH_(n,r+1)=n,
(27)

Closed "extended" rules use multiple copies of lower order closed rules to build up higher order rules. By appropriately tailoring this process, rules with particularly nice properties can be constructed. For n tabulated points, using the trapezoidal rule (n-1) times and adding the results gives

 int_(x_1)^(x_n)f(x)dx=(int_(x_1)^(x_2)+int_(x_2)^(x_3)+...+int_(x_(n-1))^(x_n))f(x)dx 
=1/2h[(f_1+f_2)+(f_2+f_3)+...+(f_(n-2)+f_(n-1))+(f_(n-1)+f_n)] 
=h(1/2f_1+f_2+f_3+...+f_(n-2)+f_(n-1)+1/2f_n)-1/(12)nh^3f^('')(xi)
(28)

(Ueberhuber 1997, p. 107). Using a series of refinements on the extended trapezoidal rule gives the method known as Romberg integration. A 3-point extended rule for odd n is

 int_(x_1)^(x_n)f(x)dx=h[(1/3f_1+4/3f_2+1/3f_3)+(1/3f_3+4/3f_4+1/3f_5)+...+(1/3f_(n-4)+4/3f_(n-3)+1/3f_(n-2))+(1/3f_(n-2)+4/3f_(n-1)+1/3f_n)] 
=1/3h(f_1+4f_2+2f_3+4f_4+2f_5+...+4f_(n-1)+f_n)-(n-1)/21/(90)h^5f^((4))(xi).
(29)

Applying Simpson's 3/8 rule, then Simpson's rule (3-point) twice, and adding gives

 [int_(x_1)^(x_4)+int_(x_4)^(x_6)+int_(x_6)^(x_8)]f(x)dx 
=h[(3/8f_1+9/8f_2+9/8f_3+3/8f_4)+(1/3f_4+4/3f_5+1/3f_6)+(1/3f_6+4/3f_7+1/3f_8)] 
=h[3/8f_1+9/8f_2+9/8f_3+(3/8+1/3)f_4+4/3f_5+(1/3+1/3)f_6+4/3f_7+1/3f_8] 
=h(3/8f_1+9/8f_2+9/8f_3+(17)/(24)f_4+4/3f_5+2/3f_6+4/3f_7+1/3f_8).
(30)

Taking the next Simpson's 3/8 step then gives

 int_(x_8)^(x_(11))f(x)dx=h(3/8f_8+9/8f_9+9/8f_(10)+3/8f_(11)).
(31)

Combining with the previous result gives

 int_(x_1)^(x_(11))f(x)dx=h[3/8f_1+9/8f_2+9/8f_3+(17)/(24)f_4+4/3f_5+2/3f_6+4/3f_7+(1/3+3/8)f_8+9/8f_9+9/8f_(10)+3/8f_(11)] 
=h(3/8f_1+9/8f_2+9/8f_3+(17)/(24)f_4+4/3f_5+2/3f_6+4/3f_7+(17)/(24)f_8+9/8f_9+9/8f_(10)+3/8f_(11)),
(32)

where terms up to f_(10) have now been completely determined. Continuing gives

 h(3/8f_1+9/8f_2+9/8f_3+(17)/(24)f_4+4/3f_5+2/3f_6+...+2/3f_(n-5)+4/3f_(n-4)+(17)/(24)f_(n-3)+9/8f_(n-2)+9/8f_(n-1)+3/8f_n).
(33)

Now average with the 3-point result

 h(1/3f_1+4/3f_2+2/3f_3+4/3f_4+2/3f_5+4/3f_(n-1)+1/3f_n)
(34)

to obtain

 h[(17)/(48)f_1+(59)/(48)f_2+(43)/(48)f_3+(49)/(48)f_4+(f_5+f_6+...+f_(n-5)+f_(n-4))+(49)/(48)f_(n-3)+(43)/(48)f_(n-2)+(59)/(48)f_(n-1)+(17)/(48)f_n]+O(n^(-4)).
(35)

Note that all the middle terms now have unity coefficients. Similarly, combining a 3-point with the (2+3)-point rule gives

 h(5/(12)f_1+(13)/(12)f_2+f_3+f_4+...+f_(n-3)+f_(n-2)+(13)/(12)f_(n-1)+5/(12)f_n)+O(n^(-3)).
(36)

Other Newton-Cotes rules occasionally encountered include Durand's rule

 int_(x_1)^(x_n)f(x)dx=h(2/5f_1+(11)/(10)f_2+f_3+...+f_(n-2)+(11)/(10)f_(n-1)+2/5f_n)
(37)

(Beyer 1987), Hardy's rule

 int_(x_0-3h)^(x_0+3h)f(x)dx=1/(100)h(28f_(-3)+162f_(-2)+22f_0+162f_2+28f_3) 
 +9/(1400)h^7[2f^((4))(xi_2)-h^2f^((8))(xi_1)],
(38)

and Weddle's rule

 int_(x_1)^(x_7)f(x)dx=3/(10)h(f_1+5f_2+f_3+6f_4+f_5+5f_6+f_7)
(39)

(Beyer 1987).

The open Newton-Cotes rules use points outside the integration interval, yielding the 1-point

 int_(x_0)^(x_2)f(x)dx=2hf_1,
(40)

2-point

int_(x_0)^(x_3)f(x)dx=int_(x_1-h)^(x_1+2h)P_2(x)dx
(41)
=1/(2h)(f_2-f_1)[x^2]_(x_1-h)^(x_1+2h)+(f_1+(x_1)/hf_1-(x_1)/hf_2)[x]_(x_1-h)^(x_1+2h)
(42)
=3/2h(f_1+f_2)+1/4h^3f^('')(xi),
(43)

3-point

 int_(x_0)^(x_4)f(x)dx=4/3h(2f_1-f_2+2f_3)+(28)/(90)h^5f^((4))(xi),
(44)

4-point

 int_(x_0)^(x_5)f(x)dx=5/(24)h(11f_1+f_2+f_3+11f_4)+(95)/(144)h^5f^((4))(xi),
(45)

5-point

 int_(x_0)^(x_6)f(x)dx=6/(20)h(11f_1-14f_2+26f_3-14f_4+11f_5)-(41)/(140)h^7f^((6))(xi),
(46)

6-point

 int_(x_0)^(x_7)f(x)dx=7/(1440)h(611f_1-453f_2+562f_3+562f_4-453f_5+611f_6)-(5257)/(8640)h^7f^((6))(xi),
(47)

and 7-point

 int_(x_0)^(x_8)f(x)dx=8/(945)h(460f_1-954f_2+2196f_3-2459f_4+2196f_5-954f_6+460f_7)-(3956)/(14175)h^9f^((8))(xi)
(48)

rules.

A 2-point open extended formula is

 int_(x_1)^(x_n)f(x)dx=h[(1/2f_1+f_2+...+f_(n-1)+1/2f_n)+1/(24)(-f_0+f_2+f_(n-1)-f_(n+1))]+(11(n+1))/(720)h^5f^((4))(xi).
(49)

Single interval extrapolative rules estimate the integral in an interval based on the points around it. An example of such a rule is

hf_1+O(h^2f^')
(50)
1/2h(3f_1-f_2)+O(h^3f^(''))
(51)
1/(12)h(23f_1-16f_2+5f_3)+O(h^4f^((3)))
(52)
1/(24)h(55f_1-59f_2+37f_3-9f_4)+O(h^5f^((4))).
(53)

See also

Boole's Rule, Difference Equation, Durand's Rule, Finite Difference, Gaussian Quadrature, Hardy's Rule, Lagrange Interpolating Polynomial, Numerical Integration, Shovelton's Rule, Simpson's Rule, Simpson's 3/8 Rule, Trapezoidal Rule, Weddle's Rule, Woolhouse's Formulas

Explore with Wolfram|Alpha

References

Abramowitz, M. and Stegun, I. A. (Eds.). "Integration." §25.4 in Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables, 9th printing. New York: Dover, pp. 885-887, 1972.Beyer, W. H. (Ed.). CRC Standard Mathematical Tables, 28th ed. Boca Raton, FL: CRC Press, p. 127, 1987.Corbit, D. "Numerical Integration: From Trapezoids to RMS: Object-Oriented Numerical Integration." Dr. Dobb's J., No. 252, 117-120, Oct. 1996.Daniell, P. J. "Remainders in Interpolation and Quadrature Formulae." Math. Gaz. 24, 238, 1940.Fornberg, B. "Calculation of Weights in Finite Difference Formulas." SIAM Rev. 40, 685-691, 1998.Hildebrand, F. B. Introduction to Numerical Analysis. New York: McGraw-Hill, pp. 160-161, 1956.Press, W. H.; Flannery, B. P.; Teukolsky, S. A.; and Vetterling, W. T. "Classical Formulas for Equally Spaced Abscissas." §4.1 in Numerical Recipes in FORTRAN: The Art of Scientific Computing, 2nd ed. Cambridge, England: Cambridge University Press, pp. 124-130, 1992.Sloane, N. J. A. Sequences A093735 and A093736 in "The On-Line Encyclopedia of Integer Sequences."Ueberhuber, C. W. Numerical Computation 2: Methods, Software, and Analysis. Berlin: Springer-Verlag, 1997.Whittaker, E. T. and Robinson, G. "The Newton-Cotes Formulae of Integration." §76 in The Calculus of Observations: A Treatise on Numerical Mathematics, 4th ed. New York: Dover, pp. 152-156, 1967.

Referenced on Wolfram|Alpha

Newton-Cotes Formulas

Cite this as:

Weisstein, Eric W. "Newton-Cotes Formulas." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Newton-CotesFormulas.html

Subject classifications