26 Numerical Quadrature
Approximating \(I = \int_a^b f(x)\,dx\) via weighted sums: \(\sum_{i=1}^n w_i f(x_i)\).
26.1 Newton-Cotes Rules
Uses equally-spaced nodes. Higher-order rules are prone to Runge’s phenomenon.
On \(n\) panels of width \(h = (b-a)/n\): \[ \begin{align} T_n = h \left[ \frac{f(a) + f(b)}{2} + \sum_{i=1}^{n-1} f(a + ih) \right]. \end{align} \] Error Bound: \(E = O(h^2)\). Doubling \(n\) reduces error \(4\times\).
Requires \(n\) to be even. Uses piecewise quadratic interpolation: \[ \begin{align} S_n = \frac{h}{3} \left[ f(a) + f(b) + 4\sum_{\text{odd}\;i} f(x_i) + 2\sum_{\text{even}\;i} f(x_i) \right]. \end{align} \] Error Bound: \(E = O(h^4)\). Exact for polynomials of degree \(\leq 3\).
26.2 Gaussian Quadrature
Optimizes both nodes and weights to achieve the highest possible degree of exactness.
Integrating over \([-1, 1]\) with \(p\) points: \[ \begin{align} \int_{-1}^1 f(x)\,dx \approx \sum_{i=1}^p w_i f(x_i). \end{align} \] Optimality: Exact for all polynomials of degree \(\leq 2p-1\). Nodes: Roots of the degree-\(p\) Legendre polynomial \(P_p(x)\).
Efficiency: \(p\) Gauss points are as accurate as \(2p\) Newton-Cotes points. Always prefer Gaussian quadrature for smooth, non-periodic functions.
26.3 Richardson Extrapolation and Romberg Integration
Given an \(O(h^2)\) estimate \(A(h)\), build an \(O(h^4)\) estimate by: \[ \begin{align} A_{new} = \frac{4A(h/2) - A(h)}{3}. \end{align} \]
Let \(A(h)\) be an \(O(h^2)\) approximation of the true value \(I\). Using a Taylor expansion in \(h\): \[ \begin{align} A(h) = I + C_1 h^2 + C_2 h^4 + O(h^6). \end{align} \] Halving the step size gives: \[ \begin{align} A(h/2) &= I + C_1 (h/2)^2 + C_2 (h/2)^4 + O(h^6) \\ &= I + \frac{1}{4} C_1 h^2 + \frac{1}{16} C_2 h^4 + O(h^6). \end{align} \] To eliminate the \(O(h^2)\) error term, multiply \(A(h/2)\) by 4 and subtract \(A(h)\): \[ \begin{align} 4A(h/2) - A(h) &= (4I + C_1 h^2 + \frac{1}{4} C_2 h^4) - (I + C_1 h^2 + C_2 h^4) + O(h^6) \\ &= 3I - \frac{3}{4} C_2 h^4 + O(h^6). \end{align} \] Dividing by 3 yields the \(O(h^4)\) estimate: \[ \begin{align} I = \frac{4A(h/2) - A(h)}{3} + O(h^4). \end{align} \]
Iterative application of Richardson extrapolation to the trapezoidal rule. Performance: Error decreases as \(O(h^{2k+2})\) for smooth \(f\), converging rapidly.
26.4 Adaptive Quadrature
Design Goal: Automatically focus function evaluations where \(f\) is “difficult” (steep gradients, oscillations) and use large steps where \(f\) is smooth. Mechanism: Compare quadrature on one large panel vs. two small panels. If the difference is above tolerance \(\varepsilon\), recurse.
26.5 Periodic Functions and Spectral Accuracy
Spectral Accuracy on Periodic Domains. For smooth, periodic functions on \([0, 2\pi]\), the Trapezoidal Rule is the optimal choice. It achieves Spectral Accuracy (exponential convergence) because error terms in the Euler-Maclaurin expansion vanish at endpoints.
26.6 Exercises
Doubling nodes in Trapezoidal rule reduces error by \(4\times\). How much does Simpson reduce it?
Derive the \(p=2\) Gauss points for \([-1, 1]\). (Hint: roots of \(3x^2 - 1\)).
Use Richardson extrapolation to improve \(T(h)\) and \(T(h/2)\) to get Simpson’s rule.
Integration of \(\sin(x)\) on \([0, 2\pi]\) with \(n=4\) nodes. Is the error \(0\)? Why?