Math 1B, Lecture 4 Error Bounds for Numerical Methods

Math 1B, lecture 4: Error bounds for numerical methods 14 September 2011 1 Introduction The five numerical methods descried in the previous lecture all operate by the same principle: they approxRb imate the integral a f (x)dx by dividing the interval [a, b] into n slices of equal width, and approximate the area under the curve in each slice by assuming that the curve has a certain shape (flat, linear, or quadratic), and approximating the area by what the area would be in this case. Using any of these numerical methods, it is necessary to understand the error that may result from these assumptions. This lecture presents a method for computing bounds on the error of each numerical method. The objective of this topic is not that you should remember these error bounds after the course; in practice, any time you need to the value of an integral, you will use a machine that implements these methods (or even more sophisticated methods which we do not discuss). Rather, the objective is to familiarize you with how these methods work, so that you will be aware of the basic qualitative aspects of the methods that machines use. Furthermore, we wish to emphasize that an approximation is useless without knowledge of its possible error, so that you will always remember to demand error bounds whenever you use approximate methods. As a secondary objective, we wish to use these methods and their error bounds to illustrate how polynomials are, in some sense, the fundamental functions in calculus; each of these numerical methods has the feature that it is exact for polynomials of a certain degree, and its error can be found by considering polynomials of higher degree. The basic philosophy that a function can be understood by means of the polynomials it resembles is a central feature of calculus, which will be made especially vivid by the development of Taylor series in a couple weeks. The reading for today is Gottlieb §26.2. The homework is to do problems 1, 3, 4, 5 from §26.2, as well as a Topic Outline. 2 Summary of results We first recall the definitions of the five numerical methods discussed last time. We are evaluating the integral: Z b f (x)dx. a In order to do this, divide the interval [a, b] on which the integral is being computed into n pieces (where n can be chosen to be anything), thus dividing the value of the integral into n slices, with endpoints x0 , x1 , . . . , xn , as shown. 1 Z b f (x)dx = a = n X area under the curve in the k th slice k=1 n Z xk X k=1 f (x)dx xk−1 Here we make the following definitions. x0 = a xn = b ∆x = xk (b − a)/n = a + k · ∆x Thus [x0 , x1 ] is the interval corresponding to the first slice, [x1 , x2 ] corresponds to the seconds slice, and in general [xk−1 , xk ] corresponds to the k th slice. Using this notation, the five numerical methods that we consider can be summarized as follows. Left approximation Ln Right approximation Rn Midpoint approximation Mn = = = n X k=1 n X k=1 n X f (xk−1 )∆x f (xk )∆x  f k=1 Trapezoid approximation Tn = = xk−1 + xk 2  ∆x 1 (Ln + Rn ) 2 n X 1 [f (xk−1 ) + f (xk )] ∆x 2 k=1 Simpson’s rule S2n = = 1 2 Mn + Tn 3 3     n X xk−1 + xk 1 f (xk−1 + 4f + f (xk ) ∆x 6 2 k=1 Note that both the trapezoid approximation and Simpson’s rule can be defined either in terms of earlier approximations or directly in terms of values of the function f . Note also that each approximation is a sum of estimates for individual slices, each of which consists of the width of the slice times an estimate for the average value of f on that slice. The estimate for this average value depends on the assumed shape of the function on the slice. The error bounds which we present will include a constant factor determined by the size of some derivative of f (x). We shall use the following notation.1 1 The symbol M is called a “Gothic M,” or a “German M.” It is frequently used by mathematicians in situations where the ordinary letter M would be ambiguous, as it certainly would be here. 2
M1 = max {|f 0 (x)| : x in [a, b]} M2 = M4 = max {|f 00 (x)| : x in [a, b]} n o max |f (4) (x)| : x in [a, b] Using this notation, the error bounds that we shall use are expressed by the following theorem (which will not be proved in class). Rb Theorem 2.1. If the integral a f (x)dx is approximated using the methods above, then the following bounds hold.   Z b 1 1 f (x)dx ≤ M1 (b − a)2 /n = M1 (∆x)2 · n Ln − 2 2 a   Z b 1 1 2 2 f (x)dx ≤ Rn − M1 (b − a) /n = M1 (∆x) · n 2 2 a   Z b 1 1 Mn − f (x)dx ≤ M2 (b − a)3 /n2 = M2 (∆x)3 · n 24 24 a   Z b 1 1 3 2 3 Tn − f (x)dx ≤ M2 (b − a) /n = M2 (∆x) · n 12 12 a   Z b 1 1 M4 (b − a)5 /(2n)4 = M4 (∆x/2)5 · n S2n − f (x)dx ≤ 180 180 a The expressions in parentheses are included simply to show how much each of the n slices contributes to the total error of the approximation. The proof of the first two bounds is not difficult; we will sketch the argument in section 4. The latter three bounds are somewhat more technical, and require the use of integration by parts. The particular forms of these bounds are not important (and you will almost certainly forget them after the exam). However, the following features are important. • The error terms have constant factors coming from the maximum value of some derivative of f (x). The better the approximation, the higher the derivative which governs the error. • The error bound shrinks as n grows. The better the approximation, the faster the error bound will shrink. Theorem 2.1, together with the qualitative descriptions discusses in the last lecture, are summarized in the following table. Remember that the conditions under the columns “overestimates” and “underestimates” must hold at all points in the interval [a, b] in order to conclude whether the method gives an overestimate or underestimate. Method Left Ln Overestimates Underestimates 0 0 f (x) > 0 0 f (x) < 0 Right Rn f (x) > 0 f 0 (x) < 0 Midpoint Mn f 00 (x) < 0 f 00 (x) > 0 00 Trapezoid Tn f (x) > 0 f 00 (x) < 0 Simpson S2n f (4) (x) > 0 f (4) (x) < 0 3 Error bound 1 2 2 M1 (b − a) /n 1 2 2 M1 (b − a) /n 1 3 2 24 M2 (b − a) /n 1 3 2 12 M2 (b − a) /n 1 180 M4 (b − a)5 /(2n)4 3 Examples R2 Example 3.1. How accurate will Simpson’s rule be for n slices be in computing 0 x3 dx? The error bound 1 M4 (b − a)5 /(2n)4 . For this particular function, the fourth derivative is 0, and therefore M4 = 0. is 180 Therefore the error bound is 0, no matter which n is used. So Simpson’s rule should be exactly correct for this integral. This may seem too good to be true, so here is a computation, for n = 1 (i.e. a computation of S2 ). By definition of Simpson’s rule, 1 3 (0 + 4 · 13 + 23 ) · 2 6 1 (0 + 4 + 8) · 2 = 6 = 4. R2 Indeed, the standard calculation shows that 0 x3 dx = 4. Z 2 2 Example 3.2. Consider the integral e−x dx. Determine a sufficient number of slices for the midpoint S4 = 0 approximation to be accurate within 0.001. 1 M2 (b − a)3 /n2 . Since the length of the interval is (b − a) = 2, this is equal The error bound for Mn is 24 1 2 to 3 M2 /n in this case. We need to select an n large enough that this bound is no more that 0.001, i.e. q 1000 such that 31 M2 /n2 ≤ 0.001. Equivalently, n2 ≥ 1000 M , or n ≥ 2 3 3 M2 . So we simply need to find M2 . In fact, it is not necessary to find M2 exactly; an upper bound on M2 will do. To find such an upper bound, begin by computing derivatives of the function (details of the computation are omitted). 2 f (x) = e−x f 0 (x) = (−2x)e−x f 00 (x) = (4x2 − 2)e−x 2 2 It would be a hassle to actually explicitly find the maximum of this second derivative, so simply get 2 an upper bound. For this purpose, observe that for all x, −x2 ≤ 0, hence e−x ≤ e0 = 1. Therefore 2 |f 00 (x)| = |(4x2 − 2)e−x | ≤ |4x2 − 2|. Now, the function 4x2 − 2 is an increasing function on [0, 2], with values ranging from −2 to 14. Thus an upper bound on its size is 14. Taken together, this implies that |f 00 (x)| ≤ 14 on [0, 2], and thus M2 ≤ 14. q Now, since this is an upper bound on M2 , if we can ensure that n ≥ 1000 3 · 14, then we will certainly q q 1000 have that n ≥ 1000 3 M2 , and in turn that the error of Mn is less than 0.001. Now 3 · 14 ≈ 68.3. Thus 69 slices will be sufficient to ensure error of less than 0.001 for the midpoint approximation. R2 Example 3.3. Consider the integral 1 dx x , whose exact value is equal to ln 2. Numerical methods give one way to calculate this value to arbitrary accuracy (better methods will come from the notion of Taylor series). How many slices are needed in order to compute this integral with error at most one millionth (that is, 10−6 ), using the five numerical methods discussed? To begin, we need the maximum values M1 , M2 and M4 , for which we need the derivatives of the function. 4 f (x) 0 = 1/x f (x) = −1/x2 f 00 (x) = f 000 (x) = −6/x4 f (4) (x) = 2/x3 24/x5 Each of these functions decrease in magnitude as x increases, so all of them have maximum absolute value at x = 1. From this we obtain the following values. M1 = 1 M2 = 2 M4 = 24 From this, as well as the fact that the length of the interval is (b − a) = 1, the following bounds for the error of each approximation can be found. |Ln − ln 2| ≤ |Rn − ln 2| ≤ |Mn − ln 2| ≤ |Tn − ln 2| ≤ |S2n − ln 2| ≤ 1 1 M1 (b − a)2 /n = 2 2n 1 1 2 M1 (b − a) /n = 2 2n 1 1 3 2 M2 (b − a) /n = 24 12n2 1 1 M2 (b − a)3 /n2 = 2 12 6n 1 1 5 4 M4 (b − a) /(2n) = 180 120n4 1 Now, observe that 2n ≤ 10−6 ⇔ n ≥ 500, 000, thus 500, 000 slices will ensure that Ln and Rn are both −6 within 10 of the true value. 1 −6 ⇔ n2 ≥ 106 /12 ⇔ n ≥ For the midpoint approximation, 12n 2 ≤ 10 −6 will ensure that Mn is within 10 of the true value. p 106 /12 ≈ 288.7. So 289 slices p 106 /6 ≈ 408.2. So 409 slices will For the trapezoid approximation, 6n1 2 ≤ 10−6 ⇔ n2 ≥ 106 /6 ⇔ n ≥ ensure that Tn is within 10−6 of the true value. 1 −6 For Simpson’s rule, 120n ⇔ n4 ≥ 106 /120 ⇔ n ≥ 4 ≤ 10 S2n is within 10−6 of the true value. p 4 106 /120 ≈ 9.6. So 10 slices will ensure that As this result indicates, the error bounds guarantee much faster convergence for Simpson’s rule than the less sophisticated approximations. In fact, explicit computation reveals that, in order to achieve error of less than one millionth, only 7 slices are needed for Simpson (the bounds ensure that 10 will work), 177 slices are needed for midpoint approximation (the bounds ensure that 289 will work), and 250 slices are needed for trapezoid approximation (the bounds ensure that 409 will work). This illustrates the fact that the error bounds, while obviously not exact, give a good rough idea for how many slices are needed to achieve a desired accuracy of computation. 5 4 Error of Ln and Rn In order to understand the error bound for left and right approximation, we begin by considering the error of these approximations in the special case where f (x) is a linear function, with slope m. That is, f 0 (x) = m for all x, where m is a constant. Then we can see the error of the left approximation Ln in the following picture. The left approximations Ln undershoots the area of each slice by precisely the area of one of the shades triangles. Observe that the base of each triangle is equal to the width of the slice, namely ∆x, and the height must be equal to m∆x (where m is the slope of the function, i.e. the constant value of its first derivative). Therefore the area of each shaded triangle is 12 (∆x)(m∆x) = 12 m(∆x)2 . Since there are n such triangles,
2 2 the total error is precisely n · 21 m(∆x)2 = 12 mn b−a = 12 m (b−a) . Because m is the value of f 0 (x) at every n n 2 . point, |m| is equal to the value M1 , and so in fact the error is precisely equal to the bound 12 M1 (b−a) n Now suppose that f (x) is any function, not necessarily linear. Then although we can no longer view the error as the areas of right triangles, essentially the same technique will apply: since the function never grows at a rate faster than M1 , the error of approximation in each slice is still bounded by the area of a triangle with base ∆x and height M1 ∆x. A complete proof of the error bound can be given by using the mean value theorem; we omit the details. The result is, as stated in section 2, Z b f (x)dx − Ln ≤ a 5 1 M1 (b − a)2 /n. 2 Error of Mn and Tn In this section, we give only a rough sketch of the principles behind the error bounds for Mn and Tn . To give complete details would require somewhat more technical notation than seems appropriate at the moment. Consider the following image, depicting the error of both the midpoint approximation and trapezoid approximation on a single slice. 6 What can make these errors as large as possible? First of all, if f is linear in this slice, then both errors will be 0. So the error is governed by the second derivative. The largest possible error will result when the function begins, at the lest end of the slice, by increasing (respectively, decreasing) very quickly, turns around in the middle, and then decreases (respectively, increases) rapidly to the other endpoint. Such behavior involves a dramatic change in the first derivative, i.e. a large second derivative. Upon formalizing this rough idea and doing some (not entirely trivial) computation, the following result can be obtained. error in a single slice for Mn ≤ error in a single slice for Tn ≤ 1 M2 (∆x)3 24 1 M2 (∆x)3 12 Replacing ∆x by (b − a)/n as usual, and multiplying by n (since there are n slices, each contributing some error) gives the error bounds from section 2. 1 1 and 12 come from, you may evaluate the error in the case The get an idea for where the constants 24 of a quadratic function, where these error bounds are exact. From this it follows (among other things), the classical fact (known to the Greeks by much more elementary methods) that the area of a parabolic segment is equal to 23 of the base times the height. 7