CS3414 Afterclass Notes --- 13 June, 2002

1. Intro

   • Idea: approximate a definite integral by evaluating the function f(x) at discrete points.

   • Intuition behind most methods: recall from Calculus, the `area-under-the-curve' interpretation of a definite integral.

   • Notation and terminology: a quadrature rule consists of a linear combination of weights (coefficients) and function values (the function evaluated at the n+1 nodes x_i, for i = 0,...,n). The error is often called the remainder term R_n.

   • Two ways to evaluate the accuracy of a quadrature rule:

     1. How fast does the remainder term go to zero as the number of nodes (n) increases? (Example: goes to zero like O(h⁴), where h = O(1/n).

     2. For what space of polynomials is the quadrature rule exact? (Example: exact on polynomials of degree 3).

   • Two types of numerical integration problems:
     1. Sometimes a set of data points is just given.
     2. Sometimes you have the ability to evaluate f(x) at any point x you like; this case is more interesting because there are opportunities to maximize accuracy while minimizing the number of function evaluations.

   • A generic strategy for constructing quadrature rules:
     • Choose points x₀, ..., x_n (or just use the points you are given).
     • Evaluate f(x) at these points.
     • Fit an interpolating polynomial or (better) piecewise polynomial to the data.
     • Integrate that (piecewise) polynomial to get your answer.

2. Simple quadrature rules: see handout