Conte, de Boor - Elementary Numerical Analysis. An Algorithmic Approach (523140), страница 56
Текст из файла (страница 56)
Thiscoefficient requires, along with other parameters, the evaluation of the integralFind the value of this integral using Simpson’s rule with N = 5, 10, 15, 20 subdivisions.Answer: For N = 5, I2.5286949.7.5 ADAPTIVE QUADRATUREThe composite rules discussed so far are all based on N subintervals ofequal size. Such a choice of subintervals is quite natural, and at times evennecessary, if the integrand is known only at a sequence of equally spacedpoints, e.g., if f(x) is given only in the form of a table of function values.But if f(x) can be evaluated with equal ease for every point in the intervalof integration, it is usually more economical to use subintervals whoselength is determined by the local behavior of the integrand.
In other words,it is usually possible to calculate I(f) to within a prescribed accuracy withfewer function evaluations if the subintervals are of properly chosenunequal size than if one insists on equal-length subintervals.Consider, for example, the general composite trapezoid rulewhere the breakpoints a = x0 <equally spaced. The contribution< xN = b are not necessarilysome η i(xi-1, xi )from the interval (xi-1, xi ) to the overall error depends on both the size off´´(x) on the interval (xi-1, xi ) and the size |xi - xi-l| of the subinterval.Hence, in those parts of the interval of integration (a,b) where |f´´(x)| is“small,” we can take subintervals of “large” size, while in regions where|f´´(x)| is “large,” we have to take “small” subintervals, if we want thecontribution to the overall error from each subinterval to be about equal.It can be shown that such a policy is best if the goal is to minimize thenumber of subintervals, and hence the number of function evaluations,necessary to calculate I(f) to a given accuracy.Integration schemes which adapt the length of subintervals to the localbehavior of the integrand are called adaptive.
The major difficulty suchschemes have to face is lack of knowledge about the derivative appearingin the error term. This means that such schemes have to guess the localbehavior of the integrand from its values at a few points.7.5ADAPTIVE QUADRATURE329We shall describe briefly an adaptive quadrature scheme based on theuse of Simpson’s rule as a basic integration formula. We assume that weare given a function f(x), an interval [a,b] and an error criterion ε. Theobjective is to compute an approximation P to the integral I =so that|P - I| < ε(7.55)and to do this using as small a number of function evaluations as possible.We begin by dividing the interval [a,b] into N subintervals, usually,but not necessarily, equally spaced.
Let xi , xi+1 be the endpoints of onesuch subinterval and let xi+l - xi = h. We now obtain two Simpson ruleapproximations to the integralOne of these, which we denote by S, is based on the use of two panels; theother, denoted by is based on the use of four panels. According to theformula (7.28) these approximations are given by(7.56a)(7.56b)From these two approximations we can estimate the error in the moreaccurate approximation as follows. According to the error term inSimpson’s rule (7.28), we have(7.57a)(7.57b)In (7.57b) the factor 2 comes from the fact that we are integrating over twosubintervals, each of width h/2.
Assuming that the derivative fiv(x) isapproximately constant over the interval [xi , xi+1 ], we can subtract (7.57b)from (7.57a) and simplify to obtainfrom which we find that(7.58)Substituting (7.58) into the right-hand side of (7.57b ) we obtain the error330DIFFERENTIATION AND INTEGRATIONestimate(7.59)In words, the error in the more accurate approximationis approximately1/15 times the difference between the two approximations and Si , aquantity which is easily computable.If the interval [a,b] is covered by N subintervals, and if on each ofthese subintervals we arrange that the error estimate satisfies(7.60)then it can be shown that the approximation to the integral I obtained bysummingwill satisfy the required error criterion (7.55) over the entire interval [a,b].In (7.60) it is important to note that h = xi+1 - xi will change as thesubinterval width changes.Adaptive quadrature essentially consists of applying the formulas(7.56a) and (7.566) to each of the subintervals covering [a,b] until theinequality (7.60) is satisfied.
If the inequality (7.60) is not satisfied on oneor more of the subintervals, then those subintervals must be furthersubdivided and the entire process repeated.Any subroutine based on adaptive quadrature must keep track of allsubintervals to ensure that the interval [a,b] is covered, and it mustproperly select the subinterval widths h needed in formulas (7.56a) ,(7.56b), and (7.60).
The complexity of adaptive quadrature subroutinesarises from the extensive bookkeeping needed to keep track of nestedsubintervals, and on the need for alternative courses of action whendifficulties are encountered. Adaptive subroutines based on Simpson’s rulecan also be made more efficient by noting in the formulas (7.56a) and(7.56b) that the points at which f(x) is evaluated in (7.56a) also occur in(7.56b). Hence these values of f(x) can be saved.
The following examplewill clarify the procedure described here.Example 7.8 Using adaptive quadrature based on Simpson’s rule find an approximationto the integralcorrect to an error ε = 0.0005.The correct answer is easily calculated to be I = 2/3. It is revealing, however, toattempt to solve it by an adaptive Simpson rule procedure. By drawing a graph of thefunction f(x) =the student will observe that the curve is very steep in the vicinity7.5ADAPTIVE QUADRATURE331of the origin [indeed f´(0) =while it is fairly flat as x1.
Hence we would expectto have more difficulty in integrating over an interval near the origin than over aninterval near x = 1.We begin by dividing the interval [0, 1] into two subintervals [0, ½] and [½ , 1]. Weapply the formulas (7.56a) and (7.56b) over the interval [½, 1] first. Here h = ½ andhenceWe use here a slightly different notation to make clear the subinterval being considered.From the error formula (7.60) we haveSince the error criterion is satisfied, we accept the valueand set it aside in aSUM register.
Next we apply the formulas (7.56a) and (7.56b) to the interval [0, ½]. Wefind again with h = 1/2 thatandHere the error test fails so that we must subdivide the interval [0, ½]. On halving thisinterval we obtain the two intervals [0, 1/4] and [l/4, l/2]. Applying formulas (7.56 a )and (7.56b) with h = 1/4, we obtainThe error criterion is clearly satisfied, hence we add the value ofSUM register to obtain the partial approximationto theSUM[¼ , 1] = 0.43096219 + 0.15236814 = 0.58333033.Applying again the basic formulas (7.56) to the interval [0, ¼] with h = 1/4, wefindS [0, ¼] = 0.079758900.08206578D[0, ¼] = (0.0001537922) 0.000125The error test is not satisfied and hence we subdivide the interval [0, ¼] into the twointervals [0, 1/8] and [1/8, 1/4]. Proceeding as above with h = 1/8 we find thatS [1/8 , 1/4] = 0.053866750.05387027E [1/8, 1/4] = 0.0000002346 < 1/8(0.0005) = 0.0000625332DIFFERENTIATION AND INTEGRATIONand thatS [0, 1/8] = 0.028199030.02901464E [0, 1/8] - 0.00005437 < 0.0000625Since the error test is passed on both intervals, we can add these values into the SUMregister to getP = SUM [0, 1] = 0.58331033 + 0.05387027 + 0.02901464= 0.66621524Since the exact value of I is .66666666 we see that the approximation P to I satisfies therequired error criterion|P - I| = 0.00045142 < 0.0005over the entire interval [0, 1].As this example shows, adaptive quadrature schemes use large spacings where the curve f(x) is changing slowly; where the curve is changingrapidly, e.g., near sharp peaks or near points of singularity, the intervalspacing will have to be much finer to achieve a required accuracy.We do not include here a subroutine based on adaptive quadrature.
Asalready noted, such a subroutine is certain to be very complex if it is tohandle large classes of functions. There are some excellent adaptivequadrature routines available on most modern computers.EXERCISES7.5-l Using a pocket calculator verify the results given in Example 7.8 forand7.5-2 Change the error criterion in Example 7.8 to ε = 0.0001. Which of the interval estimatesalready obtained will satisfy the required error criterion and which will not? Subdivide theinterval [0, 1/8] and compute the integral as in the example until the new error criterion issatisfied.7.5-3 Using adaptive Simpson-rule-based quadrature, find an approximation to the integralcorrect to three decimal places.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
