MATH2070: LAB 10: Quadrature

Introduction	Exercise 1
Matlab hint	Exercise 2
The Midpoint Method	Exercise 3
Precision	Exercise 4
The Trapezoid Method	Exercise 5
Singular Integrals	Exercise 6
Newton-Cotes Rules	Exercise 7
Gauss Quadrature	Exercise 8
Adaptive quadrature	Exercise 9
	Exercise 10
	Exercise 11
	Exercise 12
	Exercise 13
	Exercise 14

Introduction

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 $f(x)$ 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 three dimensional cell.

We first discuss 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 precision 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:

• ``Degree of precision:'' the largest value of n so that all polynomials of degree n and below are integrated exactly. (Degree of a polynomial is the highest power of x appearing in it.)
• ``Order of accuracy:'' the value of n so that the error is $O(h^n)$, where $h$ measures the subinterval size.
• ``Index:'' a number distinguishing one of a collection of rules from another.

These can be related to one another, but are not the same thing.

This lab will take four sessions. If you print this lab, you may prefer to use the pdf version.

Matlab hint

Matlab provides the capability of defining functions ``in line'' instead 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. The way to do this is to use the inline function. (The full help description is available from the command line using help inline, from the help facility on your PC, or from the Mathworks on-line reference.) Suppose, for example, you want to define a function sq(x)=x^2. You could do this by writing

  sq=inline('x.^2')

(Letters such as x are understood to mean independent variables.) or, less ambiguously, by writing

  sq=inline('x.^2','x')

You could then use sq(x) later, just as if you had defined it in an m-file. Alternatively, you could use it where a function name is needed. In the next section you will be writing an integration function named midpoint that requires a function name as its first argument. If you wanted to apply it to the integral $\int_0^1x^2dx$, you might write

  q=midpointquad(inline('x.^2','x'),0,1,11)

There is a nice way to use inline to streamline a sequence of calculations computing the integrals of ever higher degree polynomials in order to find the degree of precision of a quadrature rule. The following statement

  q=midpointquad(inline('5*x.^4','x'),0,1,11);1-q

first computes $\int_0^1 5x^4dx$ using the midpoint rule, and then prints the error (=1-q because the exact answer is 1). You would only have to change '5*x.^4' into '4*x.^3' to check the error in $\int_0^1 4x^3dx$, and you can make that change with judicious use of the arrow keys.

A second remark is that errors should be reported in scientific notation (like 1.234e-3, not .0012). This is particularly important if you want to visually estimate ratios of errors. In this lab, I would much prefer that you use full-precision values when you compute ratios of errros. 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/err40

will yield a ratio of errors without loss of accuracy due to reading numbers off the computer screen.

The Midpoint Method

In general, numerical quadrature involves breaking an interval $[a,b]$ 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 (Atkinson, p. 269). This method is based on interpolation of the integrand $f(x)$ by the constant $f(\frac{a+b}2)$ and multiplying by the width of the interval. The result is a form of Riemann sum that you probably learned in elementary calculus when you first studied integration.

Break the interval $[a,b]$ into $N-1$ subintervals with endpoints $x_1,x_2,\ldots,x_{N-1},x_N$ (there is one more endpoint than intervals, of course). Then the midpoint rule can be written as

$$=\sum_{k=1}^{N-1} (x_{k+1}-x_k)f(\frac{x_k+x_{k+1}}2).$$ (1)

In the exercise that follows, you will be writing a Matlab function to implement the midpoint rule.

Exercise 1:

1. Write a function m-file called midpointquad.m with signature

   function quad = midpointquad( f, a, b, n)
   % comments
   
   % your name and the date
   

   where 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 );
   

2. Test your midpointquad routine by computing $\int_0^1 2xdx=1$. Even if you use only one interval (i.e. n=2) you should get the exact answer because the midpoint rule integrates linear functions exactly.
3. Use your midpoint routine to estimate the integral of our friend, the Runge function, $f(x)=1/(1+x^2)$, over the interval $[-5,5]$. (If you do not have a copy of the Runge function handy, you can download my version of runge.m.) The exact answer is 2*atan(5). Fill in the following table, using scientific notation for the error values so you can see the pattern.

        n  h      Midpoint Result     Error
   
       11  1.0   _________________   __________________
      101  0.1   _________________   __________________
     1001  0.01  _________________   __________________
    10001  0.001 _________________   __________________
   

4. Estimate the order of accuracy (an integer power of h) by examining the behavior of the error when h is divided by 10. (In previous labs, we have estimated such orders by repeatedly doubling the number of subintervals. Here, we multiply by ten. The idea is the same.)

Precision

If a quadrature rule can compute exactly the integral of any polynomial up to some specific degree, we will call this its degree of precision. Thus a rule that can correctly integrate any cubic, but not quartics, has precision 3. (Atkinson, page 266.)

To determine the degree of precision of a rule, we might look at the approximations of the integrals

$$\int_0^1 1dx = [x]_0^1$$

$$\int_0^1 2xdx = [x^2]_0^1$$

$$\int_0^1 3x^2dx = [x^3]_0^1$$

$$\vdots$$

$$\int_0^1 (k+1)x^kdx = [x^{k+1}]_0^1$$

The exact value of each one of these integrals is 1.

Exercise 2:

1. To study the degree of precision of the midpoint method, use a single interval (i.e. n = 2), and estimate the integrals of the test functions over [0,1]. The exact answer is 1 each time.

        f    Midpoint Result        Error
   
     1       ___________________    ___________________
     2 * x   ___________________    ___________________
     3 * x^2 ___________________    ___________________
     4 * x^3 ___________________    ___________________
   

2. So what is the degree of precision of the midpoint rule?
3. What is the relation between the degree of precision of the midpoint rule and the order of accuracy you computed in Exercise 1?

The Trapezoid Method

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

$$=\sum_{k=1}^{N-1} (x_{k+1}-x_k)\frac{f(x_k)+f(x_{k+1})}2$$ (2)

If you compare the midpoint rule (1) and the trapezoid rule, you will see that the midpoint rule takes $f$ at the midpoint of the subinterval and the trapezoid takes the average of $f$ at the endpoints. In the previous lab, we used this rule in the case of equal length subintervals. If each of the subintervals has length $h$, then the trapezoid rule becomes

$$\frac{h}{2}f(x_1) + \frac{h}{2}f(x_{N}) + h\sum_{k=2}^{N-1}f(x_k).$$ (3)

To apply the trapezoid rule, we need to generate $N$ points and evaluate the function at each of them. Then, apply either (2) or (3) as appropriate.

Exercise 3:

1. Use your midpointquad.m m-file as a model and write a function m-file called trapezoidquad.m to evaluate the trapezoid rule. The signature of your m-file should be

   function quad = trapezoidquad( f, a, b, n )
   % comments
   
   % your name and the date
   

   You may use either form of the trapezoid rule.
2. To test your routine and to study the precision of the trapezoid rule, use a single interval (n = 2), and estimate the integrals of the same test functions used for the midpoint rule over [0,1]. The exact answer should be 1 each time.

        f    Trapezoid Result       Error
   
     1       ___________________    ___________________
     2 * x   ___________________    ___________________
     3 * x^2 ___________________    ___________________
     4 * x^3 ___________________    ___________________
   

3. What is the degree of precision of the trapezoid rule?
4. Use the trapezoid method to estimate the integral of the Runge function over $[-5,5]$, using the given values of n, and record the error using scientific notation.

        n  h     Trapezoid Result    Error
   
       11  1.0   _________________   __________________
      101  0.1   _________________   __________________
     1001  0.01  _________________   __________________
    10001  0.001 _________________   __________________
   

5. Estimate the rate at which the error decreases as $h$ decreases. (Find the power of $h$ that best fits the error behavior.) This is the order of accuracy of the rule.
6. Are the degree of precision and order of accuracy of the trapezoid rule related in the same way as for the midpoint rule?

Singular Integrals

The midpoint and trapezoid rules seem to have the same precision 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. Atkinson discusses 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

$$I=\int_0^1 \sqrt{-\log(x)} dx = \sqrt{\pi}/2,$$

where the natural logarithm is used. (See Atkinson, p. 307.) Note that the integrand ``is infinite'' at the left endpoint, so you could not use the trapezoid rule to evaluate it. The midpoint rule, conveniently, does not need the endpoint values.

Exercise 4: Apply the midpoint rule to the above integral, and fill in the following table.

     n  h      Midpoint Result     Error

    11  0.1    _________________   __________________
   101  0.01   _________________   __________________
  1001  0.001  _________________   __________________
 10001  0.0001 _________________   __________________

Estimate the rate of convergence (power of $h$) as $h\rightarrow0$. You should see that the singularity causes a loss in the rate of convergence.

Newton-Cotes Rules

Look at the trapezoid rule for a minute. One way of interpreting that rule is to say that if the function $f$ is roughly linear over the subinterval $[x_{k},x_{k+1}]$, then the integral of $f$ is the integral of the linear function that agrees with $f$ (i.e., interpolates $f$) over that 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 $f$ 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, then you can approximate the integral of that function with the integral of the polynomial interpolant. The polynomial interpolant in this case being taken on a uniformly distributed set of points, including the end points. Atkinson defines the ``index'' of a Newton-Cotes rule as one fewer than the number of points it uses.

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

$$\int_a^b f(x) dx \approx Q_n(f)=\sum_{k=0}^n w_{k,n}f(x_k)$$

where $f$ is a function and $x_k$ are $n+1$ evenly-spaced points between $a$ and $b$. The weights $w_{k,n}$ can be computed from the Lagrange interpolation polynomials $\ell_{k,n}$ as

$$w_{k,n}=(b-a)\int_0^1\ell_{k,n}(\xi)d\xi.$$

(The Lagrange interpolation polynomials arise because we are doing a polynomial interpolation.) These two equations appear in Atkinson as (5.2.2) and (5.2.3) on page 263. The weights do not depend on $f$, and on $a$ and $b$ in a simple manner, so they are often tabulated for the unit interval. In the exercise below, I will provide them through a function.

Exercise 5:

1. Download nc_weight.m.
2. Write a routine called nc_single.m with the signature

   function quad = nc_single ( f, a, b, index )
   % comments
   
   % your name and the date
   

   There are no subintervals in this case. The coding might look like something like this:

   xvec = linspace ( a, b, index+1 );
   wvec = nc_weight ( index );
   fvec = ???
   quad = (b-a) * dot(wvec , fvec);
   

3. Test your function by showing its precision is at least 1 for index 1: $\int_0^1 2xdx=1$ exactly.
4. Fill in the following table by computing the integrals over [0,1] of the indicated integrands using nc_single. Atkinson (p. 266) indicates that the degree of precision is equal to the index when the index is odd and the degree of precision is one more than the index when the index is even. Your results should agree, further confirming that your function is correct. (Hint: You can use inline to simplify your work.)

        f     Error         Error        Error
              index=3       index=4      index=5
     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.

Exercise 6: Attempt to get accurate estimates of the integral of the Runge function over the interval [-5,5]. Recall that the exact answer is 2*atan(5). Fill in the following table

  index  nc_single Result    Error

      3  _________________   __________________
      7  _________________   __________________
     11  _________________   __________________
     15  _________________   __________________

The results of the previous exercise 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.

Exercise 7:

1. Write a function m-file called nc_quad.m to perform a composite Newton-Cotes integration. Use the following signature.

   function quad = nc_quad( f, a, b, index, numSubintervals)
   % comments
   

   This 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.
2. The most elementary test to make when you write this kind of routine is to check that you get the same answer when numSubintervals=1 as you would have obtained using nc_single. Choose at least one line from the table in the previous exercise and make sure you get the same result using nc_quad.
3. Test your routine by checking the following value

     nc_quad('runge', -5, 5, 3, 10) = 2.74533025
   

4. Fill in the following table using the Runge function.

   Subin-
   tervals index  nc_quad        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   ____________   _____________
   

5. Estimate the order of convergence by taking the ratio of the error for N subintervals divided by the error for (2*N) subintervals and estimating the power of two it best approximates.

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. I use tables such as the previous one to convince myself that newly-written code is correct.

Gauss Quadrature

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 simple formula for 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.

Normally, Gauss-Legendre quadrature is characterized by the number of integration points. We speak of three-point Gauss, etc. In this lab, we will regard this as the ``index'' in order to be consistent with Newton-Cotes quadrature and also to distinguish the number of integration points from the number of subintervals in composite Gauss-Legendre quadrature.

The following two exercises involve writing m-files analogous to nc_single.m and nc_quad.m.

Exercise 8:

1. Download the file gl_weight.m. This file returns both the node points and weights for Gauss-Legendre quadrature for index=$n$ points.
2. Write a routine called gl_single.m with the signature

   function quad = gl_single ( f, a, b, index )
   % comments
   

   As with nc_single there are no subintervals in this case. Your coding might look like something like this:

   [xvec, wvec] = gl_weight ( a, b, index );
   fvec = ???
   quad = dot( wvec , fvec );
   

3. Test your function by showing its precision is at least 1 for one interval: $\int_0^1 2xdx=1$ exactly.
4. Fill in the following table by computing the integrals over [0,1] of the indicated integrands using gl_single. Atkinson (page 272) shows that the degree of precision of the method is $2n-1$, where $n$ means index, and your results should agree, further confirming that your function is correct. (Hint: You can use inline to simplify your work.)

        f       Error        Error
               index=2      index=3
     3 * x^2  __________   ___________
     4 * x^3  __________   ___________
     5 * x^4  __________   ___________
     6 * x^5  __________   ___________
     7 * x^6  __________   ___________
     Degree      ___          ___
   

5. Get accurate estimates of the integral of the Runge function over the interval [-5,5]. Recall that the exact answer is 2*atan(5). Fill in the following table

     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 indices. 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.

Exercise 9:

1. Write a function m-file called gl_quad.m to perform a composite Gauss-Legendre integration. Use the following signature.

   function quad = gl_quad( f, a, b, index, numSubintervals)
   % comments
   

   This 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.
2. The most elementary test to make when you write this kind of routine is to check that you get the same answer when numSubintervals=1 as you would have obtained using gl_single. Choose at least one line from the table in the previous exercise and make sure you get the same result using gl_quad.
3. Test your routine by checking the following value

     gl_quad('runge', -5, 5, 4, 10) = 2.7468113
   

4. Fill in the following table.

   Subin-
   tervals index  gl_quad        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   ____________   _____________
   

5. Estimate the order of accuracy by taking the ratio of the error for N subintervals and dividing it by the error for (2*N) subintervals and estimating the power of two it best approximates.

Adaptive quadrature

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. Atkinson discusses adaptive quadrature starting on page 300. There, he expresses it as a recursive algorithm and we will follow his lead here. (This is a case where the potential inefficiency of recursive algorithms is greatly overshadowed by their simplicity. You might want to think how you might recast the recursive function below using loops.)

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.

Recall that, if an integration method has degree of precision $p$, then the local error on an integration interval of length $h$ can be estimated by dividing the interval into two subintervals of length $h/2$ each. Denote by $Q_h$ the integral over the interval of length $h$ and $Q^L_{h/2}$ and $Q^R_{h/2}$ the two estimates of the integral on the left and right subintervals. Then

$$Q_h =Q+Ch^{p+2}f^{(p+1)}(\xi)+$$

$$Q^L_{h/2}+Q^R_{h/2} =Q+C(h/2)^{p+2}(f^{(p+1)}(\xi^L)+f^{(p+1)}(\xi^R)) +$$

(where $C$ is a constant and $\xi$, $\xi^L$, and $\xi^R$ are appropriately chosen). Assuming that $f^{(p+1)}$ is roughly constant, $f^{(p+1)}(\xi)=f^{(p+1)}(\xi^L)= f^{(p+1)}(\xi)=f^{(p+1)}$, and that the higher order terms can be neglected yields

$$Q_h =Q+Ch^{p+2}f^{(p+1)}$$ (4)

$$Q^L_{h/2}+Q^R_{h/2} =Q+C(h/2)^{p+2}(2f^{(p+1)}).$$ (5)

Solving Equation (4) for $Q$, plugging it into Equation (5), and defining the error as $Q^L_{h/2}+Q^R_{h/2}-Q$ yields the expression

$$=\frac{\vert Q^L_{h/2}+Q^R_{h/2}-Q_h\vert}{2^{p+1}-1}$$ (6)

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.

Exercise 10:

1. Create a function m-file named adaptquad.m with the following code, and fill in the places marked ``???''.

   function [Q,errEst,x,recursions]= ...
            adaptquad(f,x0,x1,tol,recursions)
   % [Q,errEst,x,recursions]=
   %        adaptquad(f,x0,x1,tol,recursions)
   % adaptive quadrature
   %     input parameters
   % f          = 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
   INDEX=3;
   Qboth=gl_single(f,x0,x1,INDEX);
   Qleft=gl_single(f,x0,xmid,INDEX);
   Qright=gl_single( ??? );
   
   % p=degree of precision of Gauss-Legendre
   p=2*INDEX-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(f, ...
                    x0,xmid,tol/2,recursions-1);
     [Qright,estRight,xright,recursRight]=adaptquad(f, ...
                     ??? );
     % 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);
   end
   

   Note: 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.

2. Test adaptquad by applying it to the polynomial $f_5(x)=6x^5$ on the interval $[0,1]$, using tol=1.e-5 and recursions=50. Because Gauss-Legendre integration is exact for this polynomial, the integral should equal 1 (i.e. error should be zero or roundoff), and recursions=50, and the values of x should be three equally-spaced points in the interval.

3. Test adaptquad by applying it to the polynomial $f_6(x)=7x^6$ on the interval $[0,1]$, using tol=1.e-5 and recursions=50. Because Gauss-Legendre integration is not exact for this polynomial, the integral should be close to 1. It turns out that a single set of refinements is performed, so recursions=49, and the values of x should be five equally-spaced points in the interval. The estimated and true errors should be extremely close. Please include the estimated error in your summary.

4. Test adaptquad by applying it to the Runge function on the interval [-5,5]. Use recursions=50. Recall that the exact answer is 2*atan(5). Fill in the following table

     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.

Exercise 11: Consider the following situation.

• A quadrature is being attempted with the call

  [Q,estErr,x,recursions]=adaptquad('func',0,1,tol,50);
  

• The estimated error is larger than tol at first, so new calls with tol/2 are made for the intervals $I_{\mbox{left}}=[0,0.5]$ and $I_{\mbox{right}}=[0.5,1]$.
• Assume that the call for the interval $I_{\mbox{left}}$ satisfies the convergence criterion.
• Assume that the call for the interval $I_{\mbox{right}}$ does not satisfy the convergence criterion, thus requiring two more calls to adaptquad. Assume that each of these calls satisfies the convergence criterion.

What are the values of xleft, recursLeft, xright, and recursRight when the work is all done (near the end of the adaptquad function)?

Now you are ready to look a little more closely at the results of this recursive adaptive algorithm. Some of the questions you might ask are listed below.

• What is the advantage? How much work has been saved over using, say, gl_quad?
• What is the pattern of integration points chosen?
• What happens when you try ``harder'' integrands?
• What are the weaknesses of the algorithm?

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, $1/(a+x^2)$, where $a=10^{-5}$ The value of the integral on [-1,1] of the scaled Runge function is

$$\int_{-1}^1 \frac{1}{a+x^2}dx= \frac{2}{\sqrt{a}}\tan^{-1}\frac{1}{\sqrt{a}}.$$

The scaled Runge function has a peak value of $1/a=10^5$, so is much more strongly peaked than the unscaled Runge function.

The second function is $\sqrt{\vert x\vert}$, and the value of its integral over the interval [-1,1] is

$$\int_{-1}^1 \sqrt{\vert x\vert}dx=\frac{4}{3}.$$

This function has a singularity in its derivatives at $x=0$, thus invalidating the proof that the error estimator is reliable.

A third function that is difficult to integrate is $x^{-0.99}$. This function has an integrable singularity at $x=0$ that is close to being nonintegrable.

Exercise 12:

1. Write a function m-file named srunge.m for the scaled Runge function $f(x)=1/(a+x^2)$ with $a=10^{-5}$.
2. Evaluate the integral of srunge on the interval [-1,1] using the following call.

   [Q,estErr,x,recursions]=adaptquad('srunge',-1,1,1.e-10,50);
   

   What are the estimated and true errors?
3. Use gl_quad with index=3 on the scaled Runge function. Use trial-and-error to find the value of numSubintervals that yields an error roughly comparable to estErr from adaptquad. How does this compare with length(x)-1, the number of subintervals that adaptquad used?
4. Plot the sizes of the subintervals that adaptquad used with the following command.

   xave=(x(2:length(x))+x(1:length(x)-1))/2;
   dx= x(2:length(x))-x(1:length(x)-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.

Exercise 13:

1. Approximate the integral of the function $f(x)=\sqrt{\vert x\vert}$ over the interval [-1,1] to a tolerance of 1.e-10. The exact value of this integral is 4/3. What are the estimated and true errors?
2. What is the returned value of recursions? It should be positive, indicating that the subinterval convergence criterion was always reached successfully.
3. Plot the subinterval sizes using the following command

   xave=(x(2:length(x))+x(1:length(x)-1))/2;
   dx= x(2:length(x))-x(1:length(x)-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 the function with an integral singularity in Exercise 4. In this example, you will see the benefit of the recursions variable. This variable takes the value 0 when the convergence test has failed too many times.

Exercise 14:

1. Use adaptquad to approximate the integral
   $$\int_0^1 x^{-0.99}dx=100$$
   to a tolerance of 1.e-10. Use recursions=50. Notice that the integration interval is [0,1]. What is the computed value of the integral? What are the estimated error and the true error? What is the value returned for recursions?
2. Do the same approximation starting with recursions=100. What are the computed value of the integral, the estimated error, the true error, and the returned value of recursions? (You may have to use the command set(0,'RecursionLimit',200) in order that Matlab will allow sufficient recursions.) Warning: This may take more than a minute on the computers in GSCC.
3. If the variable recursions were not used, this recursive function would ``never'' terminate because the convergence test would never be satisfied. (Actually, it would abort because there is a practical limit on the recursion depth.) The reason is that in the presence of the singularity, halving the interval only halves the error, so it never passes the convergence test.

Back to MATH2070 page.