#### CS3414 Afterclass Notes --- 17 June, 2002

Numerical Integration (Chapter 5)

1. Midpoint rule: see handout

2. Trapezoid rule: see handout

3. Simpson's rule: see handout

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

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

• Recall that the remainder term for Simpson looks like this: Rn = c*h4 + O(h5).

• So under reasonable assumptions, the remainder term with twice as many points is
R2n = (c*h4)/16 + O(h5)

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

• And with a little more algebra, R2n = (S2n - Sn)/15.

• Remarks
• So (S2n - Sn)/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(h4) to O(h5) accuracy. In this case, the appropriate formula is (16 S2n - Sn)/15, which is O(h5) accurate.