[Intermediate] — Quadrature. Computing when there’s no antiderivative, and why Gaussian rules are twice as good as they look.
Why
Most integrals have no elementary antiderivative. , , — none of them.
And in practice is often not a formula at all — it’s a table of measurements, or the output of a simulation you can only evaluate pointwise.
Where it appears here:
- FEM — every element stiffness matrix is a quadrature. This is the single biggest consumer
- Probability — expectations, normalising constants, Bayesian evidence → Probability
- ODE solvers — each step integrates the derivative
- Areas, volumes, centroids, moments of inertia
- Rendering — the rendering equation is an integral over incoming light
Newton–Cotes rules
Interpolate at equally-spaced points, integrate the interpolant exactly. That’s the whole derivation — it’s interpolation with an integral on top.
Rectangle (midpoint): — error
Trapezoid: — error
Simpson’s 1/3: — error . Fits a parabola through each group of three points, so it needs an even number of intervals.
Simpson’s 3/8: — also . Fits a cubic through each group of four points, so it needs a multiple of three intervals. It is slightly less accurate per evaluation than the 1/3 rule, and exists mainly to mop up the leftover intervals when your count is not even — combine one 3/8 panel with the rest as 1/3 panels.
Simpson’s is free accuracy. Same number of function evaluations as the trapezoid rule, two orders better. Halving cuts the error by 16× instead of 4×.
And a pleasing detail: Simpson’s fits a quadratic through three points but integrates cubics exactly. The odd-order error terms cancel by symmetry — you get one degree more than you paid for. The same cancellation is why the midpoint rule matches the trapezoid rule despite using one point instead of two.
Don’t use high-order Newton–Cotes. Above about degree 8 the weights go negative and the rule becomes unstable — Runge’s phenomenon again, in integral form. Use composite low-order rules or Gaussian quadrature instead.
Gaussian quadrature
The insight: don’t use equally-spaced points. Choose the points too.
With points you have free parameters ( nodes and weights), so you can make the rule exact for polynomials up to degree .
An -point Gaussian rule is exact for degree , versus degree for Newton–Cotes with the same count. Twice the accuracy for the same number of evaluations — and function evaluations are usually the entire cost.
The nodes are the roots of the Legendre polynomial . Tabulated, or computed via the Golub–Welsch algorithm (an eigenvalue problem — note 05 again).
Two points integrates cubics exactly. Three points integrates quintics exactly.
This is why FEM uses Gauss points. A quadratic element’s stiffness integrand is degree 4-ish, so 2×2 Gauss points suffice in 2D — and that’s exactly what FEM codes use. → FEM
Variants for awkward integrands: Gauss–Chebyshev, Gauss–Laguerre (infinite range with weight), Gauss–Hermite ( weight — used for Gaussian expectations in ML and in the unscented Kalman filter).
Gauss–Kronrod extends an -point Gauss rule with more points, reusing the originals, giving a higher-order estimate and therefore an error estimate for free. This is what adaptive quadrature routines are built on — scipy.integrate.quad is QUADPACK, which is Gauss–Kronrod.
Adaptive quadrature
Put the effort where the function is difficult.
integrate(f, a, b, tol):
coarse = rule(f, a, b)
m = (a+b)/2
fine = rule(f, a, m) + rule(f, m, b)
if |fine - coarse| < tol:
return fine
else:
return integrate(f,a,m,tol/2) + integrate(f,m,b,tol/2)
Recursively subdivide where the estimate disagrees. A function that’s smooth over most of its range and sharp in one place gets refined only where it matters.
This is what you should call. scipy.integrate.quad handles subdivision, error estimation, singularities and infinite ranges. Writing your own is an exercise, not a plan.
Watch the recursion depth — a genuine singularity subdivides forever. Cap it and return a status.
Special cases
Singularities — converges but the integrand is unbounded. Fixes: substitution to remove it ( here), a rule that avoids the endpoint (Gauss doesn’t evaluate at endpoints — a real advantage), or tanh-sinh (double exponential) quadrature, which handles endpoint singularities remarkably well.
Infinite ranges — substitute (), or use Gauss–Laguerre/Hermite, or truncate where the integrand is negligible and bound the tail.
Oscillatory integrands — standard rules need many points per oscillation and get expensive. Filon-type methods and Levin’s method handle high frequency specifically.
Periodic functions — the trapezoid rule is spectrally accurate on a full period. Error decays faster than any power of . This is genuinely surprising and it’s why FFT-based spectral methods are so effective on periodic domains.
Monte Carlo
When dimension defeats everything else.
Error is — slow, and independent of dimension.
That independence is the entire point. A grid method in dimensions costs — it degrades exponentially with dimension. Monte Carlo doesn’t care.
Crossover is around –8. Below that, use quadrature. Above it, Monte Carlo is the only option — which is why it dominates in finance (high-dimensional payoffs), rendering (light paths), and Bayesian inference (posterior integrals over many parameters).
Variance reduction is where the practical work is, since means 100× the samples for 10× the accuracy:
Importance sampling — sample where is large, reweight. The biggest win available.
Stratified sampling — subdivide the domain and sample each region.
Control variates — subtract a correlated function you can integrate exactly.
Quasi-Monte Carlo — low-discrepancy sequences (Sobol, Halton) instead of random points. Error approaches for smooth integrands. Used heavily in finance and rendering.
MCMC for sampling from a distribution you can only evaluate up to a constant — Metropolis–Hastings, HMC, NUTS. The foundation of practical Bayesian inference. → Probability
Numerical differentiation, briefly
The opposite operation, and it’s worth contrasting because the error behaviour is reversed.
Integration is well-conditioned; differentiation is not. Integration averages, which smooths noise. Differentiation amplifies it — noise of size produces derivative error .
So there’s an optimal balancing truncation against rounding — around for central differences — and you cannot do better. → The error U-curve
The better options when you need derivatives:
Automatic differentiation — exact to machine precision, no step size. This is what every ML framework does, and it’s why gradients in PyTorch are trustworthy in a way finite differences aren’t. → Deep Learning
Complex-step differentiation — . No subtraction, so no cancellation, and you can take . Requires to accept complex input, and it’s a genuinely elegant trick worth knowing.
Symbolic differentiation — SymPy, when the expression is manageable.
Practical notes
Use scipy.integrate.quad for 1-D. It’s QUADPACK, it’s adaptive, and it returns an error estimate. Read that estimate — it’s the whole point.
Check the error estimate, don’t just take the value.
Transform away singularities and infinite ranges before integrating, or use a routine that handles them (quad accepts np.inf).
Exploit smoothness. Gaussian quadrature converges spectacularly on smooth integrands and no better than anything else on rough ones. If has a kink, split the interval at the kink — one line of code, and it recovers the full convergence rate.
Above ~4 dimensions, switch to Monte Carlo and invest in variance reduction rather than raw sample count.
Test on something you know. Integrate a polynomial your rule should handle exactly and confirm you get the exact answer to machine precision. It catches implementation errors immediately.
Related
- Interpolation — quadrature rules are integrated interpolants
- ODEs — integration in time
- FEM — the biggest consumer of Gauss points
- Numerical methods map
Software engineering
Infrastructure & security
Computer science
Hardware & engineering