11 16 10 cs412 introduction to numerical analysis Lecture 19 Numerical Integration II Instructor Professor Amos Ron 1 Scribes Mark Cowlishaw Nathanael Fillmore Error Analysis of Simple Rules for Numerical Integration Last time we discussed approximating the definite integral Z b I f f t dt a The general approach introduced last time was to interpolate function f using some polynomial p t choosing interpolation points according to some rule r and compute the integral of the Rb polynomial a p t dt as the approximation Let X t0 t1 tn be the interpolating node set We can write the integral of p t using Lagrange polynomials Z b Ir f p t dt a Z b f t0 0 t f t1 1 t f tn n t dt a Z bX n a i 0 n X f ti i t dt Z f ti i 0 b i t dt a z wi Since the Lagrange polynomials i t depend only on the interpolation points and not the corresponding function values we can rewrite this approximation as a simple weighted sum of function values Ir f n X f ti wi i 0 Last time we presented four rules that used this scheme to approximate a definite integral Rectangle Rule The rectangle rule uses node set X a the left endpoint of the interval a b to interpolate f a b using a constant polynomial p t f a The corresponding estimate of the definite integral is given by IR f a b a 1 Midpoint Rule The midpoint rule uses node set X a b the midpoint of the interval a b to interpolate 2 f a b using a constant polynomial p t f a b 2 The corresponding estimate of the definite integral is given by a b b a IM f 2 Trapezoid Rule The trapezoid rule uses node set X a b the left and right endpoints of the interval a b t b t a to interpolate f a b using a polynomial of degree at most 1 p t f a a b f b b a The corresponding estimate of the definite integral is given by IT f a f b b a 2 Simpson s Rule Simpson s rule uses node set X a a b 2 b the left endpoint midpoint and right endpoint of the interval a b to interpolate f a b using a polynomial of degree at most 2 p t t a t b t a t m t b t m f m m a m b f b b a b m where m is the midpoint of a b The f a a b a m corresponding estimate of the definite integral is given by b a a b f b IS f a 4f 2 6 In last lecture s example we estimated ln 1 2 using the four rules and obtained the following results IR 0 2 IM 0 181818 IT 0 183333 IS 0 182323 1 1 Error Analysis Recall that last time we showed that the error of approximating a definite integral using polynomial interpolation over T t0 t1 tn is given by Z b Er f f t p t dt a Z b n 1 n f c Y dt t t i a n 1 i 0 z t We split the error analysis into two cases 2 Case 1 t a b is always nonnegative or always non positive In this case we can calculate the error as Er f f n 1 c n 1 Z b t dt a The Rectangle and Trapezoid rule fit this case and last time we showed that the error for each can be written as ER f ET f Case 2 Rb a f 0 c b a 2 2 f 00 c b a 3 12 t dt 0 It is easy to see that the midpoint rule falls into this case since Z b a Z b a b M t dt t dt 2 a b t a b 2 2 2 a 0 and Simpson s rule behaves similarly An interesting property of rules that fall into case 2 is that adding another interpolation point does not change the integral of the polynomial interpolant This is easy to see since t is the next Newton polynomial and since its integral is 0 the weight of the corresponding function value wn 1 will be 0 1 2 Error Analysis of Midpoint Rule Since the midpoint rule fits into case 2 of our error analysis that is Z a b b t a b 2 2 t dt 2 a 0 as shown in Figure 1 we can add an interpolation point without affecting the area of the interpolated polynomial leaving the error unchanged We can therefore do our error analysis of the midpoint rule with any single point added since adding any point in a b does not affect the area we simply double the midpoint so that X a b 2 a b 2 We can now examine the value of the next Newton polynomial t for the modified rule a b a b t t t 2 2 3 0 a a b 2 b 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 Z b a b 2 t dt 2 a 3 b f 00 c t a b 2 2 3 a b a 3 a b 3 00 2 f c 2 2 3 f 00 c 2 b a 3 2 24 f 00 c b a 3 24 f 00 c 2 EM f Note that this error is a constant factor of two smaller than the error for the trapezoid rule 1 3 Error Analysis of Simpson s Rule Since Simpson s rule also fits into case 2 of our error analysis that is Z b t dt 0 a as shown in Figure 2 we can add an interpolation point without affecting the area of the interpolated polynomial leaving the error unchanged We can therefore do our error analysis of Simpson s rule with any single point added since adding any point in a b does not affect the area we simply double the midpoint so that our node set X a a b 2 a b 2 b We can now examine the value of the next Newton polynomial t for the modified rule a b 2 t t a t t b 2 4 0 a a b 2 b 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 2 Z f 4 c 2880 b a a b 2 t a t t b dt 2 b a 5 Composite Rules Notice that the error formula for each of the simple rules depends on a high power of the size of the interval b …