Gaussian quadrature
/ GOWSS-ee-un /
Newton-Cotes rules fix the sample points at equal spacing and only get to choose the weights. But why give up half your freedom? If you are allowed to place the sample points wherever you like AND choose their weights, you have twice as many knobs to tune — and with 2n free numbers you can make an n-point rule integrate polynomials up to degree 2n - 1 exactly. Gaussian quadrature is the rule that exploits this full freedom optimally.
The magic is choosing the n nodes to be the roots of a special orthogonal polynomial. For integrals on [-1, 1] with no weighting these are the Legendre polynomials (Gauss-Legendre quadrature); the weights then follow from a simple formula. The deep reason it works: any polynomial of degree up to 2n - 1 can be split as (a degree n orthogonal polynomial) times (a quotient) plus a remainder, and the orthogonality makes the troublesome high-degree part integrate to exactly zero at those nodes. The practical payoff is enormous: a 5-point Gauss-Legendre rule integrates every polynomial up to degree 9 exactly, so for smooth functions it reaches accuracy that a Newton-Cotes rule would need many more points to match. Different weight functions and ranges call for different orthogonal families — Chebyshev for the weight 1/sqrt(1 - x^2), Hermite for e^(-x^2) on the whole line, Laguerre for e^(-x) on the half-line.
Gaussian quadrature is the gold standard for accurately integrating smooth functions you can evaluate at chosen points: it is the workhorse inside finite-element codes and many scientific libraries. The honest caveats: it shines on SMOOTH integrands — for a function with a kink or singularity the high polynomial exactness buys little, and an adaptive method does better. Its classical nodes are not nested, so refining from n to n+1 points reuses none of your old evaluations (Gauss-Kronrod and Clenshaw-Curtis address this). And the nodes and weights, while tabulated or computed once, are irrational numbers, not the tidy fractions of Newton-Cotes.
Two-point Gauss-Legendre on [-1, 1] uses nodes at +-1/sqrt(3) = +-0.57735, each with weight 1. It integrates any cubic exactly. For the integral of x^2 from -1 to 1 (true 2/3): (1/sqrt(3))^2 + (-1/sqrt(3))^2 = 1/3 + 1/3 = 2/3, exact — with just two well-placed samples.
Free both nodes and weights: n points are exact to degree 2n - 1.
Degree-2n-1 exactness is a statement about polynomials; it does NOT mean a smooth integrand is integrated exactly, only that the error scales with how well a high-degree polynomial approximates f. On non-smooth integrands the advantage shrinks, and the non-nested classical nodes make error-controlled refinement awkward — hence Gauss-Kronrod pairs.