|Matlab hint||Exercise 2|
|The Midpoint Method||Exercise 3|
|Reporting Errors||Exercise 4|
|The Trapezoid Method||Exercise 6|
|Singular Integrals||Exercise 7|
|Newton-Cotes Rules||Exercise 8|
|Gauss Quadrature||Exercise 9|
|Adaptive quadrature||Exercise 10|
|Integration by Monte Carlo methods (Extra)||Exercise 11|
The term ``numerical quadrature'' refers to the estimation of an area, or, more generally, any integral. (You might hear the term ``cubature'' referring to estimating a volume in three dimensions, but most people use the term ``quadrature.'') We might want to integrate some function or a set of tabulated data. The domain might be a finite or infinite interval, it might be a rectangle or irregular shape, it might be a multi-dimensional volume.
We first discuss the ``degree of exactness'' (sometimes called the ``degree of precision'') of a quadrature rule, and its relation to the ``order of accuracy.'' We consider some simple tests to measure the degree of exactness and the order of accuracy of a rule, and then describe (simple versions of) the midpoint and trapezoidal rules. Then we consider the Newton-Cotes and Gauss-Legendre families of rules, and discuss how to get more accurate approximations by either increasing the order of the rule or subdividing the interval. Finally, we will consider a way of adapting the details of the integration method to meet a desired error estimate. In the majority of the exercises below, we will be more interested in the error (difference between calculated and known value) than in the calculated value itself.
A word of caution. We discuss three similar-sounding concepts:
This lab will take four sessions. If you print this lab, you may prefer to use the pdf version.
As you recall, Matlab provides the capability of defining ``anonymous'' functions, using
of writing m-files to do it. This feature is most convenient when the
function to be defined is very simple-a line of code, say-or when
you have a function that requires several arguments but you only
are interested in varying one of them.
You can find out about anonymous functions on on-line reference for
Suppose, for example, you want to define a function
You could do this by writing the following:
sq=@(x) x.^2; % define a function using @You could then use sq(x) later, just as if you had defined it in an m-file. sq is a ``function handle'' and can be used wherever a function handle is used, such as in a call from another function. Remember, though, that another
@should not appear before the name. In the next section you will be writing an integration function named midpoint that requires a function handle as its first argument. If you wanted to apply it to the integral , you might write
q=midpointquad(sq,0,1,11)or you could write it without giving the function a name as
There is a nice way to use this form to streamline a sequence of calculations computing the integrals of ever higher degree polynomials in order to find the degree of exactness of a quadrature rule. The following statement
q=midpointquad(@(x) 5*x.^4,0,1,11);1-qfirst computes using the midpoint rule, and then prints the error (=1-q because the exact answer is 1). You would only have to change
4*x.^3to check the error in , and you can make the change with judicious use of the arrow keys.
Errors should be reported in scientific notation (like 1.234e-3, not .0012). You can force Matlab to display numbers in this format using the command format short e (or format long e for 15 decimal places). This is particularly important if you want to visually estimate ratios of errors.
Computing ratios of errors should always be done using full precision, not the value printed on the screen. For example, you might use code like
err20=midpointquad(@runge,-5,5,20)-2*atan(5); err40=midpointquad(@runge,-5,5,40)-2*atan(5); ratio=err20/err40to get a ratio of errors without loss of accuracy due to reading numbers off the computer screen.
When I compute ratios of this nature, I find it easier to compute them as ``larger divided by smaller,'' yielding ratios larger than 1. It is easier to recognize that 15 is nearly (=16) than to recognize that .0667 is nearly (=0.0625).
In general, numerical quadrature involves breaking an interval into subintervals, estimating or modelling the function on each subinterval and integrating it there, then adding up the partial integrals.
Perhaps the simplest method of numerical integration is the midpoint method presented by Atkinson, p. 269. This method is based on interpolation of the integrand by the constant and multiplying by the width of the interval. The result is a form of Riemann sum that you probably saw in elementary calculus when you first studied integration.
Break the interval into subintervals with endpoints (there is one more endpoint than intervals, of course). Then the midpoint rule can be written as
function quad = midpointquad( func, a, b, N) % quad = midpointquad( func, a, b, N) % comments % your name and the datewhere f indicates the name of a function, a and b are the lower and upper limits of integration, and n is the number of points, not the number of intervals. The code for your m-file might look like the following:
xpts = linspace( ??? ) ; h = ??? ; % length of subintervals xmidpts = 0.5 * ( xpts(1:N-1) + xpts(2:N) ); fmidpts = ??? quad = h * sum ( fmidpts );
N h Midpoint Result Error 11 1.0 _________________ __________________ 101 0.1 _________________ __________________ 1001 0.01 _________________ __________________ 10001 0.001 _________________ __________________
If a quadrature rule can compute exactly the integral of any polynomial up to some specific degree, we will call this its degree of exactness. Thus a rule that can correctly integrate any cubic, but not quartics, has exactness 3. See Atkinson, page 266.
To determine the degree of exactness of a rule, we might look at
the approximations of the integrals
func Midpoint Result Error 1 ___________________ ___________________ 2 * x ___________________ ___________________ 3 * x^2 ___________________ ___________________ 4 * x^3 ___________________ ___________________
The trapezoid rule breaks [a,b] into subintervals, approximates the integral on each subinterval as the product of its width times the average function value, and then adds up all the subinterval results, much like the midpoint rule. The difference is in how the function is approximated. The trapezoid rule can be written as
To apply the trapezoid rule, we need to generate points and evaluate the function at each of them. Then, apply either (2) or (3) as appropriate.
function quad = trapezoidquad( func, a, b, N ) % quad = trapezoidquad( func, a, b, N ) % more comments % your name and the dateYou may use either form of the trapezoid rule.
func Trapezoid Result Error 1 ___________________ ___________________ 2 * x ___________________ ___________________ 3 * x^2 ___________________ ___________________ 4 * x^3 ___________________ ___________________
N h Trapezoid Result Error 11 1.0 _________________ __________________ 101 0.1 _________________ __________________ 1001 0.01 _________________ __________________ 10001 0.001 _________________ __________________
The midpoint and trapezoid rules seem to have the same exactness and about the same accuracy. There is a difference between them, though. Some integrals have perfectly well-defined values even though the integrand has some sort of mild singularity. There are some sophisticated ways to perform these integrals, but there is a simple way that can be adequate for the case that the singularity appears at the endpoint of an interval. Something is lost, however.
Consider the integral
n h Midpoint Result Error 11 0.1 _________________ __________________ 101 0.01 _________________ __________________ 1001 0.001 _________________ __________________ 10001 0.0001 _________________ __________________Estimate the rate of convergence (power of ) as . You should see that the singularity causes a loss in the rate of convergence.
Look at the trapezoid rule for a minute. One way of interpreting that rule is to say that if the function is roughly linear over the subinterval , then the integral of is the integral of the linear function that agrees with (i.e., interpolates ) at the endpoints of the interval. What about trying higher order methods? It turns out that Simpson's rule can be derived by picking triples of points, interpolating the integrand by a quadratic polynomial, and integrating the quadratic. The trapezoid rule and Simpson's rule are Newton-Cotes rules of index one and index two, respectively. In general, a Newton-Cotes formula uses the idea that if you approximate a function by a polynomial interpolant on uniformly-spaced points in each subinterval, then you can approximate the integral of that function with the integral of the polynomial interpolant. This idea does not usually work for derivatives. The polynomial interpolant in this case being taken on a uniformly distributed set of points, including the end points. The number of points used in a Newton-Cotes rule is a fundamental parameter, and can be used to characterize the rule. The ``index'' of a Newton-Cotes rule is commonly defined as one fewer than the number of points it uses, although this common usage is not universal.
We applied the trapezoid rule to an interval by breaking it into subintervals and repeatedly applying a simple formula for the integral on a single subinterval. Similarly, we will be constructing higher-order rules by repeatedly applying Newton-Cotes rules over subintervals. But Newton-Cotes formulæ are not so simple as the trapezoid rule, so we will first write a helper function to apply the rule on a single subinterval.
Over a single interval, all (closed) Newton-Cotes formulæ can be written as
Remark: There are also open Newton-Cotes formulæ that do not require values at endpoints, but there is not time to consider them in this lab.
function quad = nc_single ( func, a, b, N ) % quad = nc_single ( func, a, b, N ) % more comments % your name and the dateThere are no subintervals in this case. The coding might look like something like this:
xvec = linspace ( a, b, N ); wvec = nc_weight ( N ); fvec = ??? quad = (b-a) * sum(wvec .* fvec);
func Error Error Error N=4 N=5 N=6 4 * x^3 __________ __________ ___________ 5 * x^4 __________ __________ ___________ 6 * x^5 __________ __________ ___________ 7 * x^6 __________ __________ ___________ Degree ___ ___ ___
The objective of numerical quadrature rules is to accurately approximate integrals. We have already seen that polynomial interpolation on uniformly spaced points does not always converge, so it should be no surprise that increasing the order of Newton-Cotes integration might not produce accurate quadratures.
index nc_single Result Error 3 _________________ __________________ 7 _________________ __________________ 11 _________________ __________________ 15 _________________ __________________
The results of Exercise 6 should have convinced you that you need a composite Newton-Cotes rule in order to accurately do numerical integration. In the following exercise you will use nc_single as a helper function for a composite Newton-Cotes routine.
function quad = nc_quad( func, a, b, N, numSubintervals) % quad = nc_quad( func, a, b, N, numSubintervals) % comments % your name and the dateThis function will perform these steps: (1) break the interval into numSubintervals subintervals; (2) use nc_single to integrate over each subinterval; and, (3) add them up.
nc_quad(@runge, -5, 5, 4, 10) = 2.74533025
Subin- nc_quad tervals N Error Err ratio 10 2 _____________ __________ 20 2 _____________ __________ 40 2 _____________ __________ 80 2 _____________ __________ 160 2 _____________ __________ 320 2 _____________ 10 3 _____________ __________ 20 3 _____________ __________ 40 3 _____________ __________ 80 3 _____________ __________ 160 3 _____________ __________ 320 3 _____________ 10 4 _____________ __________ 20 4 _____________ __________ 40 4 _____________ __________ 80 4 _____________ __________ 160 4 _____________ __________ 320 4 _____________
In the previous exercise, the table served to illustrate the behavior of the integration routine. Suppose, on the other hand, that you had an integration routine and you wanted to be sure it had no errors. It is not good enough to just see that you can get ``good'' answers. In addition, it must converge at the correct rate. Tables such as the previous one are one of the most powerful debugging and verification tools a researcher has.
Like Newton-Cotes quadrature, Gauss-Legendre quadrature interpolates the integrand by a polynomial and integrates the polynomial. Instead of uniformly spaced points, Gauss-Legendre uses optimally-spaced points. Furthermore, Gauss-Legendre converges as degree gets large, unlike Newton-Cotes, as we saw above. Of course, in real applications, one does not use higher and higher degrees of quadrature-one uses more and more subintervals, each with some given degree of quadrature.
The disadvantage of Gauss-Legendre quadrature is that there is no easy way to compute the node points and weights. Instead, the values are tabulated (see, for example, Table 5.10 in Atkinson, page 276). We will be using a Matlab function to serve as a table of node points and weights. Atkinson discusses Gauss-Legendre quadrature in Section 5.3, giving expressions for the node point locations and weights.
One way to compute the node points and weights is described in Algorithm 125 in the collected algorithms from the ACM, appearing in The Communications of the ACM, 5, no. 10 (October 1962), pp. 510-511, and is available as a Fortran program TOMS125.
Normally, Gauss-Legendre quadrature is characterized by the number of integration points. We speak of three-point Gauss, etc.
The following two exercises involve writing m-files analogous to nc_single.m and nc_quad.m.
function quad = gl_single ( func, a, b, N ) % quad = gl_single ( func, a, b, N ) % comments % your name and the dateAs with nc_single there are no subintervals in this case. Your coding might look like something like this:
[xvec, wvec] = gl_weight ( a, b, N ); fvec = ??? quad = sum( wvec .* fvec );
f Error Error N=2 N=3 3 * x^2 __________ ___________ 4 * x^3 __________ ___________ 5 * x^4 __________ ___________ 6 * x^5 __________ ___________ 7 * x^6 __________ ___________ Degree ___ ___
index gl_single Result Error 3 _________________ __________________ 7 _________________ __________________ 11 _________________ __________________ 15 _________________ __________________
You might be surprised at how much better Gauss-Legendre integration is than Newton-Cotes, using a single interval. There is a similar advantage for composite integration, but it is hard to see for small N. When Gauss-Legendre integration is used in a computer program, it is generally in the form of a composite formulation because it is difficult to compute the weights and integration points accurately for high order Gauss-Legendre integration. The efficiency of Gauss-Legendre integration is compounded in multiple dimensions, and essentially all computer programs that use the finite element method use composite Gauss-Legendre integration rules to compute the coefficient matrices.
function quad = gl_quad( f, a, b, N, numSubintervals) % quad = gl_quad( f, a, b, N, numSubintervals) % comments % your name and the dateThis function will perform two steps: (1) break the interval into numSubintervals subintervals; (2) use gl_single to integrate over each subinterval; and, (3) add them up.
gl_quad(@runge, -5, 5, 4, 10) = 2.7468113
Subin- gl_quad tervals N Error Err ratio 10 1 ____________ __________ 20 1 ____________ __________ 40 1 ____________ __________ 80 1 ____________ __________ 160 1 ____________ __________ 320 1 ____________ 10 2 ____________ __________ 20 2 ____________ __________ 40 2 ____________ __________ 80 2 ____________ __________ 160 2 ____________ __________ 320 2 ____________ 45 3 ____________ __________ 90 3 ____________ 46 3 ____________ __________ 92 3 ____________ 47 3 ____________ __________ 94 3 ____________ 48 3 ____________ __________ 96 3 ____________ 49 3 ____________ __________ 98 3 ____________
The proofs you have seen about convergence of Gauss quadrature rely on bounds on higher derivatives of the function. When bounds are not available, higher-order convergence might not be observed.
log(x) Subin- gl_quad tervals N Error Err ratio 10 1 ____________ __________ 20 1 ____________ __________ 40 1 ____________ __________ 80 1 ____________What is the order of accuracy of the method using N=1?
log(x) Subin- gl_quad tervals N Error Err ratio 10 2 ____________ __________ 20 2 ____________ __________ 40 2 ____________ __________ 80 2 ____________What is the order of accuracy of the method using N=2?
log(x) Subin- gl_quad tervals N Error Err ratio 10 3 ____________ __________ 20 3 ____________ __________ 40 3 ____________ __________ 80 3 ____________What is the order of accuracy of the method using N=3?
It is instructive to see how to compute integrals over infinite intervals. Basically, the best way to do that is to make a change of variables to make the interval finite. There are other ways, such as multiplying the integrand by a weighting function and then using an integration method based on weighted integrals, but you will see how a change of variables works in thee following exercise.
Use any of the integration functions to evaluate this integral to an accuracy of Explain why you chose the method you used and how you determined the number of intervals necessary to achieve the specified accuracy.
Remark: There is no easy way to tell in advance which method to use to achieve a particular accuracy. You can pick a method by trial-and-error, switching methods when you cannot achieve the desired error in the time you are willing to wait.
Our final task will consider ``adaptive quadrature.'' Adaptive quadrature employs non-uniform division of the interval of integration into subintervals of non-equal length. It uses smaller subintervals where the integrand is changing rapidly and larger subintervals where it is flatter. The advantage of this approach is that it minimizes the work necessary to compute a given integral. Adaptive quadrature is discussed by Atkinson starting on page 300. In this section, you will investigate a recursive algorithm for adaptively computing quadratures.
Numerical integration is used often with integrands that are very complicated and take a long time to compute. Although this section will use simple integrands for illustrative purposes, you should think of each evaluation of the integrand (``function call'') to take a long time. Thus, the objective is to reach a given accuracy with a minimum number of function calls. A good strategy for achieving a specified accuracy efficiently is to attempt to uniformly distribute the error over each subinterval. If no interval is particularly bad, there is no obvious place to improve the estimate and if no interval is particularly good, no work has been wasted.
Recall that, if an integration method has degree of exactness , then the local error on an integration interval of length satisfies an expression involving a constant and a point located somewhere in th interval. Assuming the derivative of the function are roughly constant in the interval, then can be estimated by dividing the interval into two subintervals of length each, estimating the error in the interval as the sum of the errors on the two subintervals, and then equating the two expressions. Denote by the integral over the interval of length , then
The basic structure of one simple adaptive algorithm depends on using the error estimate (6) over each integration subinterval. If the error is acceptably small over each interval, the process stops, and, if not, continues recursively. In the following exercise, you will write a recursive function to implement this procedure.
function [Q,errEst,x,recursions]= ... adaptquad(func,x0,x1,tol,recursions) % [Q,errEst,x,recursions]= % adaptquad(func,x0,x1,tol,recursions) % adaptive quadrature % input parameters % func = function to integrate % x0 = left end point % x1 = right end point % tol = desired accuracy % recursions = number of allowable recursions left % % output parameters % Q = estimate of the value of the integral % errEst = estimate of error in Q % x = all intermediate integration points % recursions = minimum number of recursions remaining % after convergence % Add a mid-point and re-estimate integral xmid=(x0+x1)/2; % Qleft and Qright are integrals over two halves N=3; Qboth=gl_single(func,x0,x1,N); Qleft=gl_single(func,x0,xmid,N); Qright=gl_single( ??? ); % p=degree of exactness of Gauss-Legendre p=2*N-1; errEst= ??? ; if errEst<tol | recursions<=0 %vertical bar means "or" % either ran out of recursions or converged Q= ??? ; x=[x0 xmid x1]; else % not converged -- do it again [Qleft,estLeft,xleft,recursLeft]=adaptquad(func, ... x0,xmid,tol/2,recursions-1); [Qright,estRight,xright,recursRight]=adaptquad(func, ... ??? ); % recursive work is all done, return answers % don't want xmid to appear twice in x x=[xleft xright(2:length(xright))]; Q= ??? ; errEst= ??? ; recursions=min(recursLeft,recursRight); endNote: The input and output parameter recursions is not theoretically necessary, but is used to guard against infinite recursion. The output vector x is not necessary, either, but will be used to show the effect of the adaptation.
adaptquad for Runge tol est. error exact error 1.e-3 __________ __________ 1.e-6 __________ __________ 1.e-9 __________ __________You should find that the estimated and exact errors are close in size, and smaller than tol. For the two more accurate cases, the estimated error is slightly larger than the exact error. As you can see, the estimated error is not so good for the case that tol=1.e-3.
The next few exercises will help you look a little more closely at the results of this recursive adaptive algorithm. Some of the points that will be made are listed below.
In the following exercises, you will examine two functions that are more difficult to integrate. The first is a scaled version of the Runge function, , where The value of the integral on [-1,1] of the scaled Runge function is
The second function is , and the value of its integral over the interval [-1,1] is
A third function that is difficult to integrate is . This function has an integrable singularity at that is close to being nonintegrable.
[Q,estErr,x,recursions]=adaptquad(@srunge,-1,1,1.e-10,50);What are the estimated and true errors? Is recursions larger than zero?
xave=(x(2:end)+x(1:end-1))/2; dx= x(2:end)-x(1:end-1); semilogy(xave,dx,'*')A semilog plot is appropriate here because of the wide range of interval sizes. Please include this plot with your summary.
xave=(x(2:end)+x(1:end-1))/2; dx= x(2:end)-x(1:end-1); semilogy(xave,dx,'*')where x is replaced by the variable name you used. A semilog plot is appropriate here because of the wide range of interval sizes. Please include this plot with your summary.
In the following exercise you will apply adaptquad to a function that is almost not integrable. You will see the benefit of the recursions variable, whose reduction to 0 indicates that convergence was not achieved.
There is another approach to approximating integrals, one that can be used even when the integrand is not smooth or piecewise smooth, when the integral is taken over a region that is not easily characterized or when its dimension, is high. This versatility comes at a cost: the method is probabalistic and also slowly convergent. It is called the ``Monte Carlo'' method.
The basic idea behind the Monte Carlo method is that the formula for computing the average value of a function over a region
The Monte Carlo method is discussed
in many places on
the web. You can find a very clear description, with considerable
Eric Weisstein has an article in MathWorld,
http://mathworld.wolfram.com/MonteCarloIntegration.html that states, for and
As an example, consider the problem of computing the area of the unit ball in . In this case, is simply the characteristic function of the ball
The following code, using x and y to denote and will estimate the area of the ball
CHUNK=10000; % chosen for efficiency NUM_CHUNKS=100; VOLUME=4; % outer square is 2 X 2 totalPoints=0; insidePoints=0; for k=1:NUM_CHUNKS x=(2*rand(CHUNK,1)-1); y=(2*rand(CHUNK,1)-1); phi=( (x.^2+y.^2) <= 1 ); % 1 for "true" and 0 for "false" % just like characteristic function insidePoints=insidePoints+sum(phi); totalPoints=totalPoints+CHUNK; end average=insidePoints/totalPoints; a=VOLUME*average; disp(strcat('approx area=',num2str(a), ... ' with true error=',num2str(pi-a), ... ' and estimated error=', ... num2str(VOLUME*sqrt((average-average^2)/totalPoints))));
Remark: This code uses a programming trick. In Matlab, the value 0 represents ``false'' and the value 1 represents ``true''. As a consequence, the characteristic function of the unit ball can easily be calculated by using a logical expression describing the interior of the ball.
Remark: Note that the points are divided into chunks of 10,000 points each. Then the function evaluation is done using vectors whose lengths are the chunk size. Working with these long vectors, Matlab will do the calculations efficiently. You don't, however, want to do all 1,000,000 points at once, because such large vectors can take a while just for the memory to be allocated. That is why the problem is first divided into chunks and then repeated a number of times.
Back to MATH2070 page.