1 Error Analysis of Simple Rules for Numerical Integration

1 Cs412: introduction to Numerical analysis11/16/10 Lecture 19: Numerical Integration IIInstructor: Professor Amos RonScribes: Mark Cowlishaw, Nathanael Fillmore1 Error Analysis of Simple Rules for Numerical IntegrationLast time we discussed approximating the definite integralI(f) = baf(t)dtThe general approach introduced last time was to interpolate functionfusing some polyno-mialp(t), choosing interpolation points according to some rulerand compute the integral of thepolynomial, bap(t)dtas the approximation. LetX={t0, t1, , tn}be the interpolating node can write the integral ofp(t) using Lagrange polynomials:Ir(f) = bap(t)dt= ba(f(t0)`0(t) +f(t1)`1(t) + +f(tn)`n(t))dt= ban i=0f(ti)`i(t)dt=n i=0f(ti) ba`i(t)dt wiSince the Lagrange polynomials`i(t) depend only on the interpolation points and not the corre-sponding function values, we can rewrite this approximation as a Simple weighted sum of functionvalues:Ir(f) =n i=0f(ti)wiLast time we presented four Rules that used this scheme to approximate a definite integral.

2 Rectangle RuleThe rectangle rule uses node setX={a}, the left endpoint of the interval [a, b] to interpolatef|[a,b]using a constant polynomial (p(t) =f(a)). The corresponding estimate of the definiteintegral is given by:IR=f(a)(b a)1 Midpoint RuleThe midpoint rule uses node setX={a+b2}, the midpoint of the interval [a, b] to interpolatef|[a,b]using a constant polynomial (p(t) =f(a+b2)). The corresponding estimate of the definiteintegral is given by:IM=f(a+b2)(b a)Trapezoid RuleThe trapezoid rule uses node setX={a, b}, the left and right endpoints of the interval [a, b]to interpolatef|[a,b]using a polynomial of degree at most 1 (p(t) =f(a)t ba b+f(b)t ab a).

3 Thecorresponding estimate of the definite integral is given by:IT= (f(a) +f(b))b a2 Simpson s RuleSimpson s rule uses node setX={a,a+b2, b}, the left endpoint, midpoint, and right endpointof the interval [a, b] to interpolatef|[a,b]using a polynomial of degree at most 2 (p(t) =f(a)(t b)(t m)(a b)(a m)+f(m)(t a)(t b)(m a)(m b)+f(b)(t a)(t m)(b a)(b m), wheremis the midpoint of [a, b]). Thecorresponding estimate of the definite integral is given by:IS=(f(a) + 4f(a+b2)+f(b))b a6In last lecture s example, we estimated ln( ) using the four Rules and obtained the followingresults:IR= IT= IS= Error AnalysisRecall that last time we showed that the Error of approximating a definite integral using polynomialinterpolation overT={t0, t1.}

4 , tn}is given by:Er(f) = ba[f(t) p(t)]dt= ba f(n+1))(c)(n+ 1)!n i=0(t ti) (t) dtWe split the Error Analysis into two cases:2 Case1: (t)|[a,b]is always nonnegative, or always non-positiveIn this case, we can calculate the Error as:Er(f) =f(n+1)(c)(n+ 1)! ba (t)dtThe Rectangle and Trapezoid rule fit this case, and last time we showed that the Error foreach can be written as:ER(f) =f (c)2(b a)2ET(f) =f (c)12(b a)3 Case2: ba (t)dt= 0It is easy to see that the midpoint rule falls into this case, since: ba M(t)dt= ba(t a+b2)dt=[t (a+b)/2]22 ba= 0and Simpson s rule behaves similarly.

5 An interesting property of Rules that fall into case2 is that adding another interpolation point does not change the integral of the polynomialinterpolant. This is easy to see, since (t) is the next Newton polynomial and since its integralis 0, the weight of the corresponding function valuewn+1will be Error Analysis of Midpoint RuleSince the midpoint rule fits into case 2 of our Error Analysis , that is: ba (t)dt=[t (a+b)/2]22 ba= 0as shown in Figure 1, we can add an interpolation point without affecting the area of the interpolatedpolynomial, leaving the Error unchanged. We can therefore do our Error Analysis of the midpointrule with any single point added - since addinganypoint in [a, b] does not affect the area, we simplydouble the midpoint, so thatX={(a+b)/2,(a+b)/2}.

6 We can now examine the value of thenext Newton polynomial, (t) for the modified rule: (t) =(t a+b2)(t a+b2)3a(a + b)/2 b0 Figure 1: (t) in the Midpoint rule over [a, b]Clearly, (t)|[a,b] 0, so that this new rule can be analyzed using case 1, this yields:EM(f) =f (c)2 ba(t a+b2)2dt=f (c)2(t a+b2)33 ba=f (c)2(b a2)3 (a b2)33=f (c)22(b a)324=f (c)24(b a)3 Note that this Error is a constant factor of two smaller than the Error for the trapezoid Error Analysis of Simpson s RuleSince Simpson s rule also fits into case 2 of our Error Analysis , that is: ba (t)dt= 0as shown in Figure 2, we can add an interpolation point without affecting the area of the interpolatedpolynomial, leaving the Error unchanged.

7 We can therefore do our Error Analysis of Simpson s rulewith any single point added - since addinganypoint in [a, b] does not affect the area, we simplydouble the midpoint, so that our node setX={a,(a+b)/2,(a+b)/2, b}. We can now examinethe value of the next Newton polynomial, (t) for the modified rule: (t) = (t a)(t a+b2)2(t b)4a (a + b)/2 b 0 Figure 2: (t) in Simpson s rule over [a, b]Clearly, (t)|[a,b] 0, so that this new rule can be analyzed using case 1, this yields:EM(f) =f(4)(c)24 ba(t a)(t a+b2)2(t b)dt= f(4)(c)2880(b a)52 Composite RulesNotice that the Error formula for each of the Simple Rules depends on a high power of the size ofthe intervalb a, so that a small interval makes for a smaller Error .

8 This motivates the followinggeneral idea for creating composite Rules for Numerical the interval [a, b] intoNsubintervals, equidistant by default, with widthh=b aNStep2 Apply a Simple approximation rulerto each subinterval [xi, xi+1] and use the areaIras theapproximation of the integral for that subinterval: xi+1xif(t)dt Ir[xi,xi+1](f)Note that in this application, the appearance of each of the piecewise polynomials is unim-portant, we are only interested in their approximation of the definite up the approximation of the area over each subinterval to obtain the approximation overthe entire interval [a, b]:I[a,b](f) n 1 i=0Ir[xi,xi+1](f) illustrate, consider applying the composite rectangle rule to an interval[a, b], asshown in Figure 4.

9 In each subinterval, the left endpoint gets weighth. Thus every point exceptthe last one in our partition has weight 1; the last point has weight 0. This yields the followingestimate of the definite integral:ICR=h f(a) +h f(a+h) +h f(a+ 2h) + +h f(b h) 3: Function Value Weights in the Composite Rectangle another illustration, consider applying the composite trapezoid rule to an interval[a, b], as shown in Figure 4. In each subinterval, the endpoints get weighth/2. Since each of theinterior points is included in two subintervals, this yields the following estimate of the definiteintegral:ICT=h2[f(a) + 2 f(a+h) + 2 f(a+ 2h) + + 2 f(b h) +f(b)] , consider applying composite Simpson s rule to an interval[a, b]as shown inFigure 5.

10 For each subinterval[xi, xi+1], the endpoints get weight1/6and the midpoint gets weight4/6. Since each interior endpoint (all nodes exceptaandb) is counted twice, this yields the followingestimate of the definite integral:ICS=h6[f(a) + 4 f(a+h2) + 2 f(a+h) + 4 f(a+3h2) + 2 f(a+ 2h) +..+2 f(b h) + 4 f(b h2) +f(b)] 4: Function Value Weights in the Composite Trapezoid 5: Function Value Weights in Composite Simpson s Error Analysis for Composite Simpson s RuleIn a composite rule, we are making use of the fact that a definite integral over an interval [a, b] issimply the sum of the definite integrals of the subintervals.