Numerical Integration: Overview
Quadrature rules approximate a definite integral as a weighted sum of function values, chosen to be exact for polynomials up to some degree.
Approximating the area under a curve
Most integrals have no closed form, so numerical integration, or quadrature, estimates the value of a definite integral from function samples. A quadrature rule is a weighted sum sum(w_i f(x_i)); the nodes x_i and weights w_i define the rule. Rules are designed to integrate polynomials up to a certain degree exactly.
Two design philosophies
- Newton-Cotes rules use equally spaced nodes: the trapezoidal rule, Simpson's rule, and their higher-order relatives.
- Gaussian quadrature chooses both nodes and weights optimally, integrating polynomials of degree 2n-1 exactly with only n points.
- Composite rules split the interval into panels and apply a simple rule on each, controlling error by panel width.
- Adaptive rules refine only where the integrand is difficult.
Degree of exactness and error
A rule's degree of exactness is the highest polynomial degree it integrates without error. Higher degree usually means faster convergence for smooth integrands. The error of composite rules typically falls as a power of the panel width h; Simpson's rule, for instance, has error proportional to h^4.
Practical concerns
Singularities, sharp peaks, and oscillation defeat naive rules. Remedies include variable transformations to tame endpoint singularities, adaptive subdivision to concentrate effort, and specialized rules for oscillatory or infinite-range integrals. Multidimensional integration often turns to Monte Carlo methods, whose error is independent of dimension.
Quadrature is ubiquitous in physics: integrating reaction rates over energy, computing moments of distributions, and assembling finite-element matrices, all of which appear in the breeder Hyperion modeling pipeline.