CS3414 Afterclass Notes --- 17 June, 2002

2. Simple quadrature rules

   1. Midpoint rule: see handout

   2. Trapezoid rule: see handout

   3. Simpson's rule: see handout

   4. Gaussian quadrature rules

      • Idea: improve accuracy by choosing quadrature points carefully.

      • Facts: (1) with k equally spaced points, you can get polynomial degree k if k is odd, k-1 if k is even. (2) with k Gauss points, can get polynomial degree 2k-1.

      • Example. Suppose we want , , , such that is exact for all on [-1,1].

        

        So, require

        

        System has a unique solution:

        

      • Remarks:

        • Derivation of Gauss rules for any k involves roots of orthogonal polynomials as the points.

        • Points and weights are tabulated for many standard cases.

        • Points are different for each value of k, but there are combinations of Gauss rules that allow you to reuse function values as points are added.

3. Quadrature algorithms

   • Idea: use error (remainder) estimates to ...
     1. Decide when your approximate solution is good enough (or when you are not making any more progress).
     2. Add function evaluation points only in some areas, but not in others.
     3. Improve the answer even more.

   • Example: adaptive quadrature with Simpson's method

     • Recall that the remainder term for Simpson looks like this: R_n = c*h⁴ + O(h⁵).

     • So under reasonable assumptions, the remainder term with twice as many points is
       R_2n = (c*h⁴)/16 + O(h⁵)

     • By simple algebra, it's easy to show that R_2n is approximately R_n/16.

     • And with a little more algebra, R_2n = (S_2n - S_n)/15.

     • Remarks
       • So (S_2n - S_n)/15 is a reasonable stopping criterion.
       • Note that this error estimate can be done locally, i.e., with respect to any subinterval of [a,b]. This is important because it allows us to decide where to add more points and where the answer is good enough.
       • Note also that we can still use the Richardson extrapolation idea to improve from O(h⁴) to O(h⁵) accuracy. In this case, the appropriate formula is (16 S_2n - S_n)/15, which is O(h⁵) accurate.