TheoremComplete

Gaussian Quadrature Optimality Theorem

Theorem4.1Optimality of Gaussian Quadrature

Let w:(a,b)R>0w: (a, b) \to \mathbb{R}_{>0} be a positive weight function with finite moments. Among all quadrature rules abw(x)f(x)dxi=1nwif(xi)\int_a^b w(x) f(x)\, dx \approx \sum_{i=1}^n w_i f(x_i) with nn nodes, the maximum degree of exactness is 2n12n - 1. This maximum is achieved if and only if the nodes x1,,xnx_1, \ldots, x_n are the roots of the nn-th degree orthogonal polynomial with respect to ww, and the weights are uniquely determined by wi=abw(x)jixxjxixjdxw_i = \int_a^b w(x) \prod_{j \neq i} \frac{x - x_j}{x_i - x_j}\, dx.


Proof

Proof

Upper bound: A quadrature rule with nn nodes has 2n2n free parameters (nodes and weights). Since a polynomial of degree 2n2n has 2n+12n + 1 coefficients, one cannot expect exactness beyond degree 2n12n - 1 in general.

Existence and characterization: Let p0,p1,p_0, p_1, \ldots be the orthonormal polynomials with respect to f,g=abw(x)f(x)g(x)dx\langle f, g \rangle = \int_a^b w(x) f(x) g(x)\, dx. Suppose the nodes x1,,xnx_1, \ldots, x_n are the roots of pn(x)p_n(x).

For any polynomial ff of degree 2n1\leq 2n - 1, divide by pnp_n: f(x)=q(x)pn(x)+r(x)f(x) = q(x) p_n(x) + r(x) where degqn1\deg q \leq n - 1 and degrn1\deg r \leq n - 1.

Since degqn1\deg q \leq n - 1 and pnpkp_n \perp p_k for k<nk < n: abw(x)q(x)pn(x)dx=0\int_a^b w(x) q(x) p_n(x)\, dx = 0.

Therefore abw(x)f(x)dx=abw(x)r(x)dx\int_a^b w(x) f(x)\, dx = \int_a^b w(x) r(x)\, dx.

Since pn(xi)=0p_n(x_i) = 0 for all ii, we have f(xi)=r(xi)f(x_i) = r(x_i), so i=1nwif(xi)=i=1nwir(xi)\sum_{i=1}^n w_i f(x_i) = \sum_{i=1}^n w_i r(x_i).

The weights are chosen so that the quadrature is exact for all polynomials of degree n1\leq n - 1 (which is possible since the Lagrange interpolation weights provide the unique such choice). Since degrn1\deg r \leq n - 1: i=1nwir(xi)=abw(x)r(x)dx\sum_{i=1}^n w_i r(x_i) = \int_a^b w(x) r(x)\, dx.

Hence i=1nwif(xi)=abw(x)f(x)dx\sum_{i=1}^n w_i f(x_i) = \int_a^b w(x) f(x)\, dx for all ff with degf2n1\deg f \leq 2n - 1.

Uniqueness of nodes: If x1,,xnx_1, \ldots, x_n achieve degree of exactness 2n12n - 1, define ω(x)=i=1n(xxi)\omega(x) = \prod_{i=1}^n (x - x_i). For any polynomial qq with degqn1\deg q \leq n - 1: abw(x)q(x)ω(x)dx=i=1nwiq(xi)ω(xi)=0\int_a^b w(x) q(x)\omega(x)\, dx = \sum_{i=1}^n w_i q(x_i)\omega(x_i) = 0 since ω(xi)=0\omega(x_i) = 0. Thus ω\omega \perp all polynomials of lower degree, so ω\omega is (up to scaling) the orthogonal polynomial pnp_n. \square


Consequences

RemarkPositivity of Gaussian Weights

All Gaussian weights are positive: wi=abw(x)[i(x)]2dx>0w_i = \int_a^b w(x) [\ell_i(x)]^2\, dx > 0 where i\ell_i is the ii-th Lagrange basis polynomial. This guarantees numerical stability, as the condition number wi/wi=1\sum|w_i| / |\sum w_i| = 1. In contrast, high-order Newton-Cotes formulas have negative weights, leading to potential cancellation errors.

ExampleThree-Point Gauss-Legendre

For n=3n = 3 on [1,1][-1,1]: the roots of P3(x)=12(5x33x)P_3(x) = \frac{1}{2}(5x^3 - 3x) are x1=3/5x_1 = -\sqrt{3/5}, x2=0x_2 = 0, x3=3/5x_3 = \sqrt{3/5}, with weights w1=w3=5/9w_1 = w_3 = 5/9, w2=8/9w_2 = 8/9. This integrates polynomials of degree 5\leq 5 exactly. Applied to 11exdx\int_{-1}^1 e^x\, dx: 59e3/5+89e0+59e3/52.3504024\frac{5}{9}e^{-\sqrt{3/5}} + \frac{8}{9}e^0 + \frac{5}{9}e^{\sqrt{3/5}} \approx 2.3504024 vs. exact ee12.3504024e - e^{-1} \approx 2.3504024 (error <107< 10^{-7}).