Gaussian quadrature

Gaussian quadrature is a quadrature rule that chooses both sample locations and coefficients to achieve unusually high polynomial exactness. For a finite interval $[a,b]$ with $a<b$, assume the integration weight $w$ is integrable and positive almost everywhere. DefineLet $p_n$ be the monic orthogonal polynomial of polynomial degree $n$ for the inner product $⟨u,v{⟩}_w={\int }_a^{b}u(x)v(x)w(x)dx$: it satisfies $⟨p_n,q{⟩}_w=0$ for every polynomial $q$ of polynomial degree below $n$. The polynomial roots of $p_n$ are distinct and inside $(a,b)$; take them as the nodes $x_i$. Integrate the Lagrange cardinal polynomials ${\ell }_i$ to obtain $A_i=I_w({\ell }_i)$. These coefficients are positive, andThe integration weight $w(x)$ and the discrete coefficients $A_i$ play different roles: $w$ specifies the integral being approximated, while $A_i$ tell us how much each sample contributes.^[ref]

A proof outline explains the gain over simply integrating an arbitrary polynomial interpolation. Use polynomial division to write $f=p_{n}q+r$, with $\mathrm{deg}q\le n-1$ and $\mathrm{deg}r\le n-1$. Orthogonality makes $I_w(p_{n}q)=0$, and sampling at the polynomial roots of $p_n$ makes $Q_n(p_{n}q)=0$. The Lagrange cardinal polynomials recover $r$ exactly, so both expressions agree. Also $A_i=Q_n({\ell }_i^2)=I_w({\ell }_i^2)>0$, since ${\ell }_i^2$ has polynomial degree $2n-2$. This is the mechanism behind positive weights of Gaussian quadrature.

For a concrete two-node example, set $w=1$ on $[-1,1]$. The Legendre polynomial $P_2(x)=(3x^2-1)/2$ has polynomial roots $x=\pm 1/\sqrt{3}$. Its monic polynomial version $p_2=x^2-1/3$ has zero integral against both $1$ and $x$, as required. Symmetry and exactness for the constant polynomial give $A_1=A_2=1$. Thus the Gauss–Legendre instance of Gaussian quadrature isDirect evaluation on $1,x,x^2,x^3$ gives $2,0,2/3,0$, exactly their integrals. For the polynomial $f(x)=1+x+x^2+x^3$, two samples therefore give $8/3$ exactly. But for $x^4$ the rule gives $2/9$, whereas the integral is $2/5$: the error $I_1-Q_2$ is $8/45$.

The ceiling $2n-1$ is sharp for $n$ distinct real nodes under the positive-weight assumptions. Their squared nodal polynomial ${\prod }_i(x-x_i{)}^2$ has polynomial degree $2n$, is zero at every sample, and has a strictly positive weighted integral. Thus no such quadrature rule integrates every polynomial of polynomial degree $2n$ exactly. Nor does Gaussian quadrature integrate every nonpolynomial function exactly: the same two-node example gives $Q_2(|x|)=2/\sqrt{3}$, while $I_1(|x|)=1$.

Gaussian quadrature is useful when evaluations are costly and a modest polynomial captures the integrand well. More precisely, for a continuous function $f$ and any polynomial $r$ of polynomial degree at most $2n-1$, positivity and constant exactness giveThe uniform norm on $[a,b]$ measures the approximation between samples. This bound connects quadrature rule accuracy to uniform approximation, rather than promising an error from sample count alone. Corners, sharp unresolved features and roundoff error require their own assessment; the absolute value function example already shows why polynomial exactness is a qualified guarantee.

For positive quadrature weights summing to the total mass $M$, a quadrature rule exact on polynomials through polynomial degree $d$ satisfies $|I(f)-Q(f)|\le 2M\Vert f-p_d{\Vert }_{\infty }$ for every such polynomial $p_d$. This follows by subtracting the exactly integrated $p_d$ and applying the triangle inequality to the integral and weighted sum. For Gauss-Legendre quadrature with $n+1$ nodes, $M=2$ and $d=2n+1$. Exponentially decaying Chebyshev series coefficients therefore yield a bound proportional to $e^{-2Kn}$ when $|c_j|\le e^{-Kj}$.

Let ${\varphi }_0,\dots ,{\varphi }_n$ be orthonormal polynomials for a positive weight, and let $x_i,w_i$ define its $(n+1)$-point Gaussian quadrature. Put $A_{ij}={\varphi }_{j-1}(x_{i-1})$ and $W=\mathrm{diag}(w_0,\dots ,w_n)$. Exactness through polynomial degree $2n+1$ gives $A^{T}WA=I$. Positivity of the quadrature weights makes $W^{1/2}A$ a square orthogonal matrix, so $A{A}^T=W^{-1}$ also. Thus the unweighted row inner products of the evaluation matrix are ${\delta }_{ij}/w_{i-1}$.

Gauss-Legendre quadrature approximates an integral on a finite interval using nodes obtained from roots of a Legendre polynomial. With $n$ nodes it integrates every polynomial of degree at most $2n-1$ exactly.

An $(n+1)$-node quadrature exact on degree $n$ is exact through degree $2n+1$ precisely when its node polynomial $p={\prod }_i(x-x_i)$ is orthogonal to every degree-$n$ polynomial for the integration weight. Necessity applies the rule to $pr$. Sufficiency divides an arbitrary degree-$2n+1$ polynomial as $pq+r$, with both $q,r$ of degree at most $n$; the integral and quadrature of $pq$ vanish while both agree on $r$.

The even weight $1-x^2$ has moments $m_0=4/3$ and $m_2=4/15$. Its monic quadratic orthogonal polynomial is $x^2-1/5$, so the two Gaussian quadrature nodes are $\pm 1/\sqrt{5}$. Symmetry and constant exactness give weights $2/3$ each. These nodes and weights integrate every polynomial of degree at most three exactly. Degree four fails: the true integral is $4/35$, whereas the rule gives $4/75$.

The first-kind rule approximates ${\int }_{-1}^{1}f(x)(1-x^2{)}^{-1/2}dx$ at the zeros of the Chebyshev polynomial $T_n$. It integrates all polynomials of degree at most $2n-1$ exactly. The weights follow by integrating the Lagrange interpolation polynomial at those nodes. Orthogonality kills the quotient when a degree-$2n-1$ polynomial is divided by $T_n$; its remainder is recovered by interpolation. No $n$-node rule can integrate every degree-$2n$ polynomial, since the squared nodal polynomial has zero quadrature sum and strictly positive weighted integral.

// Target: probability-and-statistics.bigb

For the weight $e^{-x}$ on $[0,\infty )$, use the zeros of a degree-$n$ Laguerre polynomial as quadrature nodes. Divide a polynomial of degree at most $2n-1$ by that polynomial. The quotient term integrates to zero by orthogonality and vanishes at every node; interpolation of the remainder proves exactness. The two-node rule has nodes $2\pm \sqrt{2}$ and corresponding weights $(2\pm \sqrt{2})/4$, with the larger weight at the smaller node.

For weight $w(x)=x$ on $[0,1]$, the two-node Gaussian quadrature nodes are roots of $x^2-6x/5+3/10$, the monic quadratic orthogonal to all linear polynomials. Its weights come from integrating the Lagrange interpolation cardinal functions. Orthogonality gives exactness on cubic polynomials and positive weights.

For integration against $\sin x$ on $[0,\pi ]$, the monic quadratic orthogonal polynomial is $x^2-\pi x+2$. Its two roots are the Gaussian quadrature nodes $c_{1,2}=\pi /2\mp \sqrt{{\pi }^2/4-2}$, with weights one. The rule integrates every cubic exactly: divide it by the orthogonal quadratic and integrate the degree-one remainder.

For an $n$-node Gaussian quadrature rule exact through degree $2n-1$, the cardinal Lagrange interpolation polynomial ${\ell }_j$ has square of degree $2n-2$. Exactness gives $A_j=\int {\ell }_j^2>0$ for a positive integration weight. This proof turns polynomial exactness directly into positivity.

Gauss-Hermite quadrature uses the roots of a degree-$N$ Hermite polynomial as nodes for an integral with Gaussian weight. Its positive interpolation weights make it exact for every polynomial of degree at most $2N-1$.