CS3414 Afterclass Notes --- 13 June, 2002
Numerical Integration (Chapter 5)
- 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 xi, for i = 0,...,n).
The error is often called the remainder term
- Two ways to evaluate the accuracy of a quadrature rule:
- How fast does the remainder term go to zero as the number
of nodes (n) increases? (Example: goes to zero like
O(h4), where h = O(1/n).
- For what space of polynomials is the quadrature rule exact?
(Example: exact on polynomials of degree 3).
- Two types of numerical integration problems:
- Sometimes a set of data points is just given.
- 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 x0, ..., xn
(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.
- Simple quadrature rules: see handout