Numerical integration (quadrature)

Level UniversityDifficulty ★★★★★Method⌖ Open in the map

What is it?

Approximating $\int_a^b f$ by a weighted sum of samples. Trapezoid ( $O(h^2)$ ), Simpson ( $O(h^4)$ ) and Gaussian quadrature are excellent in one or a few dimensions; in high dimensions Monte Carlo takes over.

Formulas

$\int_a^b f \approx \frac{h}{2}\Big(f_0 + 2f_1 + \dots + 2f_{n-1} + f_n\Big)$
composite trapezoidal rule: $\int_a^b f \approx \frac{h}{3}\Big(f_0 + 4f_1 + 2f_2 + 4f_3 + \dots + f_n\Big)$
composite Simpson rule

Where it shows up in computing

Scientific computing★★★★★fundamentalScientific computing and algorithms
Adaptive quadrature (e.g. scipy.integrate.quad) is a standard tool of scientific software.
Finite element method★★★★★frequentPhysics and simulation
FEM assembles element matrices by Gaussian quadrature on each element.

Where it shows up in AI

Bayesian inference★★★★★frequentAI and machine learning
Low-dimensional posteriors and marginal likelihoods can be computed by quadrature.

Where is it used?

Computing topics reachable from here, through the chain of ideas that leads to them:

This page has the essentials. A fuller treatment (intuition, formal definition, worked example) is on the way.

What is it?

Formulas

Where it shows up in computing

Where it shows up in AI

Where is it used?

λ Scientific computing and algorithms

⚛ Physics and simulation

ℒ AI and machine learning