Chapter 5 · Numerical Analysis

5.4 Numerical Differentiation and Integration

Derivatives from difference quotients and their error terms; the trapezoidal, Simpson 1/3 and 3/8 rules, simple and composite, with degree of precision; Gauss–Legendre quadrature; and Richardson extrapolation and Romberg integration.

A surprising number of integrals that arise in practice have no elementary antiderivative: the error function $\int_0^x e^{-t^2}dt$ of probability and diffusion, the elliptic integral that gives the length of a planetary orbit, the integral $\int_0^T\sqrt{\dot x^2+\dot y^2}\,dt$ for the length of a robot's path, and every integral of a function known only through measurements: speed readings from a car every ten seconds, the concentration of a drug in blood samples taken every hour, river depths measured at equally spaced points across a channel. The same is true of derivatives: a velocity computed from GPS positions, a heat flux computed from thermometer readings, a slope estimated from a table. In all of these we know $f$ only at finitely many points and must replace the derivative or the integral by a finite combination $\sum w_if(x_i)$.

This section builds the standard formulas and, more importantly, their error terms: why the central difference quotient is better than the forward one, why Simpson's rule (built from parabolas) is exact for cubics, why $n$ cleverly placed points (Gauss) beat $n$ equally spaced ones by a factor of two in degree, and how two crude answers can be combined into a much better one (Richardson and Romberg). CSIR NET asks for precisely these facts: the value of an integral by the trapezoidal or Simpson rule, the order of an error term, the degree of precision of a given rule, the nodes and weights of a Gauss rule, the result of one Richardson step, and Part C statements built from the counterexamples collected in the ⚠️ box. Throughout, the nodes are $x_k=x_0+kh$ with step $h\gt0$, $f_k=f(x_k)$, and $\Delta f_k=f_{k+1}-f_k$, $\nabla f_k=f_k-f_{k-1}$ are the forward and backward differences of §5.3 (Finite Differences and Interpolation).

Numerical Differentiation

The derivative is a limit of difference quotients, so the first idea is to stop before the limit. The question is how much we lose, and the tool that answers it is Taylor's theorem with the Lagrange remainder.

📘 Definition 5.22 — Difference formulas; order of accuracy

For a function $f$ defined near $x_0$ and a step $h\gt0$, the forward, backward and central difference quotients for $f'(x_0)$ and the second central difference quotient for $f''(x_0)$ are

$$D_+(h)=\frac{f(x_0+h)-f(x_0)}{h},\qquad D_-(h)=\frac{f(x_0)-f(x_0-h)}{h},$$ $$D_0(h)=\frac{f(x_0+h)-f(x_0-h)}{2h},\qquad D^2(h)=\frac{f(x_0+h)-2f(x_0)+f(x_0-h)}{h^2}.$$

A formula $D(h)$ for a quantity $A$ has order of accuracy $p$ if its truncation error satisfies $A-D(h)=O(h^p)$ as $h\to0$ for every sufficiently smooth $f$, and not $O(h^{p+1})$ in general. It is exact for polynomials of degree $\le k$ if $D(h)=A$ for every such polynomial and every $h$.

📐 Theorem 5.35 — Error terms of the basic difference formulas

Let $f$ be defined on $[x_0-2h,x_0+2h]$. There are points $\xi$ in the interval spanned by the nodes used such that:

  1. if $f\in C^2$: $\ f'(x_0)=D_+(h)-\dfrac h2f''(\xi)$ (order 1; similarly $f'(x_0)=D_-(h)+\tfrac h2f''(\xi)$);
  2. if $f\in C^3$: $\ f'(x_0)=D_0(h)-\dfrac{h^2}{6}f'''(\xi)$ (order 2);
  3. if $f\in C^4$: $\ f''(x_0)=D^2(h)-\dfrac{h^2}{12}f^{(4)}(\xi)$ (order 2);
  4. if $f\in C^3$: $\ f'(x_0)=\dfrac{-3f_0+4f_1-f_2}{2h}+\dfrac{h^2}{3}f'''(\xi)$ (one-sided, order 2).

Consequently $D_\pm$ are exact for polynomials of degree $\le1$, while $D_0$, $D^2$ and the formula in (4) are exact for degree $\le2$; $D^2$ is even exact for degree $\le3$.

Proof. (1) Taylor's theorem gives $f(x_0+h)=f(x_0)+hf'(x_0)+\tfrac{h^2}{2}f''(\xi)$ with $\xi\in(x_0,x_0+h)$; solve for $f'(x_0)$.

(2) Expand to third order on both sides: $f(x_0\pm h)=f_0\pm hf'_0+\tfrac{h^2}{2}f''_0\pm\tfrac{h^3}{6}f'''(\xi_\pm)$. Subtracting, the even terms cancel: $$f(x_0+h)-f(x_0-h)=2hf'(x_0)+\frac{h^3}{6}\big(f'''(\xi_+)+f'''(\xi_-)\big).$$ The average $\tfrac12(f'''(\xi_+)+f'''(\xi_-))$ lies between the smallest and largest values of the continuous function $f'''$ on $[x_0-h,x_0+h]$, so by the intermediate value theorem it equals $f'''(\xi)$ for some $\xi$. Dividing by $2h$ gives (2).

(3) Expand to fourth order and add: the odd terms cancel and $$f(x_0+h)+f(x_0-h)=2f_0+h^2f''_0+\tfrac{h^4}{24}\big(f^{(4)}(\eta_+)+f^{(4)}(\eta_-)\big);$$ combine the two fourth derivatives as before and divide by $h^2$.

(4) Here the Taylor coefficients of the two remainders have opposite signs ($\tfrac46$ and $-\tfrac86$), so the averaging trick fails; we use interpolation instead. Let $p$ be the quadratic interpolating $f$ at $x_0,x_1,x_2$. By the divided-difference form of the interpolation error (§5.3), $$f(x)-p(x)=f[x_0,x_1,x_2,x]\,w(x),\quad w(x)=(x-x_0)(x-x_1)(x-x_2),$$ where $x\mapsto f[x_0,x_1,x_2,x]$ is continuous and its values are of the form $f'''(\xi)/3!$. Since $w(x_0)=0$, the derivative of the product at $x_0$ is $$f[x_0,x_1,x_2,x_0]\,w'(x_0)=\tfrac{f'''(\xi)}{6}(x_0-x_1)(x_0-x_2)=\tfrac{h^2}{3}f'''(\xi).$$ Finally, differentiating Newton's forward formula $p(x_0+sh)=f_0+s\Delta f_0+\tfrac{s(s-1)}{2}\Delta^2f_0$ at $s=0$ gives $$p'(x_0)=\tfrac{1}{h}\big(\Delta f_0-\tfrac12\Delta^2f_0\big)=\tfrac{-3f_0+4f_1-f_2}{2h}.$$

The exactness statements follow because the error terms involve $f''$, $f'''$ or $f^{(4)}$, which vanish for polynomials of the stated degrees. ∎

The method of the proof is also a method of derivation: to find a formula $\sum c_kf(x_0+kh)$ for $f^{(m)}(x_0)$, expand each $f(x_0+kh)$ in powers of $h$ and choose the $c_k$ so that as many low-order terms as possible cancel (equivalently, make the formula exact for $1,x,x^2,\dots$). Symmetric formulas gain one order for free, because the odd (or even) terms cancel by symmetry. This is the reason why central differences are preferred whenever values on both sides of $x_0$ are available.

When $f$ is given by a table with equal steps, a systematic way to obtain derivatives of any order is to differentiate the interpolating polynomial. In operator language (§5.3) the shift $E$, $Ef(x)=f(x+h)$, satisfies $E=1+\Delta$, and Taylor's theorem says that $E=e^{hD}$ with $D=\tfrac{d}{dx}$; hence formally $hD=\log(1+\Delta)$.

📐 Theorem 5.36 — Derivatives from forward differences

Let $p$ be a polynomial of degree $\le m$ and $p_k=p(x_0+kh)$. Then

$$h\,p'(x_0)=\Delta p_0-\frac{\Delta^2p_0}{2}+\frac{\Delta^3p_0}{3}-\cdots+(-1)^{m+1}\frac{\Delta^mp_0}{m},$$ $$h^2p''(x_0)=\Delta^2p_0-\Delta^3p_0+\frac{11}{12}\Delta^4p_0-\frac56\Delta^5p_0+\cdots,$$

the series being the expansions of $\log(1+\Delta)$ and $\log^2(1+\Delta)$, which terminate after $\Delta^m$. For a smooth function $f$ that is not a polynomial, truncating the first series after the term $\Delta^kf_0$ gives an approximation to $f'(x_0)$ of order $k$: it is the derivative at $x_0$ of the polynomial interpolating $f$ at $x_0,\dots,x_k$. The backward analogue is $h\,f'(x_n)\approx\nabla f_n+\tfrac12\nabla^2f_n+\tfrac13\nabla^3f_n+\cdots$, from $hD=-\log(1-\nabla)$.

Proof. On the space $\mathcal{P}_m$ of polynomials of degree $\le m$ the operators $\Delta$ and $hD$ are nilpotent: each lowers the degree by at least one, so $\Delta^{m+1}=0$ and $(hD)^{m+1}=0$ on $\mathcal{P}_m$. Taylor's formula for a polynomial is exact and finite: $p(x+h)=\sum_{j=0}^m\tfrac{h^j}{j!}p^{(j)}(x)$, that is, $E=e^{hD}$ on $\mathcal{P}_m$ (the exponential series stops at $j=m$). For commuting nilpotent operators the identities of formal power series $\log(e^{u})=u$ and $e^{\log(1+v)}=1+v$ are honest polynomial identities (all terms of degree $\gt m$ vanish). Therefore, on $\mathcal{P}_m$, $$hD=\log E=\log(1+\Delta)=\sum_{j=1}^m\frac{(-1)^{j+1}\Delta^j}{j};$$ applying this to $p$ and evaluating at $x_0$ gives the first formula, and squaring the series gives the second. For general $f$, $q_k(x)=\sum_{j\le k}\binom{s}{j}\Delta^jf_0$ ($x=x_0+sh$) interpolates $f$ at $x_0,\dots,x_k$, and the first $k$ terms of the series are exactly $h\,q_k'(x_0)$ (apply the polynomial case to $q_k$, whose differences of order $\gt k$ at $x_0$ vanish). The error of differentiating an interpolant of degree $k$ at a node is $f^{(k+1)}(\xi)w'(x_0)/(k+1)!$ with $|w'(x_0)|=k!\,h^k$, as in Theorem 5.35(4); this is $O(h^k)$. ∎

✏️ Example 1 — Forward versus central differences
Estimate $f'(0)$ for $f(x)=e^x$ by $D_+(h)$ and $D_0(h)$ with $h=0.1$ and $h=0.05$. How do the errors change when $h$ is halved? Use the two central values to produce a better estimate.
Values The exact value is $f'(0)=1$.
$h$$D_+(h)$error $D_+-1$$D_0(h)$error $D_0-1$
0.11.051709$5.17\times10^{-2}$1.001668$1.67\times10^{-3}$
0.051.025422$2.54\times10^{-2}$1.000417$4.17\times10^{-4}$
Ratios Halving $h$ divides the forward error by $2.03\approx2$ and the central error by $4.00$: orders $1$ and $2$, as Theorem 5.35 predicts. The leading terms agree too: $\tfrac h2f''(0)=0.05$ and $\tfrac{h^2}{6}f'''(0)=0.001667$ for $h=0.1$.
Combine Since $D_0(h)=1+ch^2+O(h^4)$ (the expansion of $D_0$ has only even powers), the combination $$\frac{4D_0(0.05)-D_0(0.1)}{3}=\frac{4(1.0004167)-1.0016675}{3}=0.9999998$$ kills the $h^2$ term; its error is $-2.1\times10^{-7}$. This is Richardson extrapolation, studied in the last subsection.
Lesson For the same two function values per estimate, the central quotient is 30 times more accurate here, and one extrapolation step gains three more digits.
✏️ Example 2 — Derivatives from a table
The table gives $f(x)=e^x$ rounded to four decimals: $x=1.0,1.1,1.2,1.3,1.4$; $f=2.7183,\ 3.0042,\ 3.3201,\ 3.6693,\ 4.0552$. Using forward differences estimate $f'(1.0)$ and $f''(1.0)$; using central differences estimate $f'(1.2)$ and $f''(1.2)$. Compare with the exact values $e=2.71828$ and $e^{1.2}=3.32012$ and explain the discrepancies.
Differences At $x_0=1.0$: $\Delta f_0=0.2859$, $\Delta^2f_0=0.0300$, $\Delta^3f_0=0.0033$, $\Delta^4f_0=0.0001$.
$f'(1.0)$ By Theorem 5.36 with $h=0.1$: $$f'(1.0)\approx\frac{1}{0.1}\Big(0.2859-\frac{0.0300}{2}+\frac{0.0033}{3}-\frac{0.0001}{4}\Big)=2.71975.$$ The error is $+0.0015$. With only two terms we get $2.7090$ (error $-0.0093$), with one term $2.8590$.
$f''(1.0)$ $$f''(1.0)\approx\frac{1}{0.01}\Big(0.0300-0.0033+\frac{11}{12}(0.0001)\Big)=2.679,$$ an error of $-0.039$, much worse.
Central $f'(1.2)\approx\dfrac{3.6693-3.0042}{0.2}=3.3255$ (error $+0.0054$, close to the truncation term $\tfrac{h^2}{6}e^{1.2}=0.0055$) and $f''(1.2)\approx\dfrac{3.6693-2(3.3201)+3.0042}{0.01}=3.33$ (error $+0.010$).
Why The data carry rounding errors up to $5\times10^{-5}$. A formula for $f^{(m)}$ divides by $h^m$, so the rounding errors are amplified by about $1/h$ in $f'$ and $1/h^2=100$ in $f''$: an error of $5\times10^{-5}$ in each of three values can change $D^2$ by up to $4\times5\times10^{-5}/0.01=0.02$. High differences of rounded data ($\Delta^4f_0=0.0001$) are essentially pure noise. Numerical differentiation amplifies data errors — the opposite of integration, which averages them out.

Example 2 shows the second half of the story. The truncation error decreases with $h$, but the rounding error increases: every computed or measured value carries an error, and the formula divides differences of nearly equal numbers by a small $h$.

📐 Theorem 5.37 — Truncation versus rounding: the optimal step

Suppose $f\in C^3$, $|f'''|\le M_3$ near $x_0$, and that the values actually used are $\tilde f(x_0\pm h)=f(x_0\pm h)+\varepsilon_\pm$ with $|\varepsilon_\pm|\le\varepsilon$. Then the computed central quotient $\tilde D_0(h)$ satisfies

$$\big|f'(x_0)-\tilde D_0(h)\big|\le\frac{\varepsilon}{h}+\frac{M_3h^2}{6}.$$

The bound is smallest for $h^*=\left(3\varepsilon/M_3\right)^{1/3}$, where it equals $\tfrac12\left(9\varepsilon^2M_3\right)^{1/3}$; so with data accurate to $\varepsilon$ the best attainable accuracy is of order $\varepsilon^{2/3}$, not $\varepsilon$. For the forward quotient the corresponding bound is $\tfrac{2\varepsilon}{h}+\tfrac{M_2h}{2}$, optimal at $h^*=2\sqrt{\varepsilon/M_2}$ with accuracy of order $\varepsilon^{1/2}$.

Proof. We have $$f'(x_0)-\tilde D_0(h)=\big(f'(x_0)-D_0(h)\big)-\dfrac{\varepsilon_+-\varepsilon_-}{2h}.$$ The first bracket is at most $\tfrac{h^2}{6}M_3$ by Theorem 5.35(2) and the second at most $\tfrac{2\varepsilon}{2h}$. The function $g(h)=\varepsilon/h+M_3h^2/6$ is convex on $(0,\infty)$ and tends to $\infty$ at both ends; $g'(h)=-\varepsilon/h^2+M_3h/3=0$ gives $h^3=3\varepsilon/M_3$. There $\varepsilon/h=M_3h^2/3$, so $g(h^*)=\tfrac12M_3h^{*2}=\tfrac12M_3^{1/3}(3\varepsilon)^{2/3}$. The forward case is identical with $g(h)=2\varepsilon/h+M_2h/2$. ∎

In double-precision arithmetic $\varepsilon\approx10^{-16}|f|$ even for exact data, so the best step for the central quotient is about $10^{-5}$ to $10^{-6}$, not "as small as possible". Interactive 1 shows the characteristic V-shaped error curves.

Interactive 1 — Truncation versus Rounding: The Best Step for a Difference Quotient

Both axes are logarithmic: the error of the forward quotient (order 1), the central quotient (order 2) and the five-point formula $\tfrac{f_{-2}-8f_{-1}+8f_1-f_2}{12h}$ (order 4) is plotted against $h$, computed in the browser's double-precision arithmetic. On the right, truncation dominates and the lines have slopes $1$, $2$, $4$; on the left, rounding takes over and every curve rises like $\varepsilon/h$. The dashed curve is the bound of Theorem 5.37. Add data noise $\varepsilon$ to see the optimal step grow like $\varepsilon^{1/3}$.

—
step h—
forward error—
central error—
five-point error—
best h (central): seen / h*—

Newton–Cotes Rules: Trapezoidal, Simpson 1/3 and 3/8

To integrate, we replace $f$ by a polynomial that agrees with it at chosen nodes and integrate the polynomial. Every such formula has the shape below.

📘 Definition 5.23 — Quadrature rule; degree of precision

A quadrature rule on $[a,b]$ with nodes $x_0,\dots,x_n\in[a,b]$ (distinct) and weights $w_0,\dots,w_n\in\mathbb{R}$ is the approximation

$$\int_a^bf(x)\,dx\approx Q(f)=\sum_{i=0}^nw_if(x_i).$$

Its error is $E(f)=\int_a^bf-Q(f)$. The rule has degree of precision (degree of exactness) $d$ if $E(p)=0$ for every polynomial $p$ of degree $\le d$ but $E(x^{d+1})\ne0$. Since $E$ is linear, it suffices to test the monomials $1,x,\dots,x^{d+1}$ (or $1,(x-c),\dots,(x-c)^{d+1}$ for any convenient $c$). The rule is interpolatory if $w_i=\int_a^b\ell_i(x)\,dx$, where $\ell_i$ are the Lagrange basis polynomials of the nodes, i.e. $Q(f)=\int_a^bp_n$ for the polynomial $p_n$ interpolating $f$ at the nodes.

📐 Theorem 5.38 — Interpolatory rules
For distinct nodes $x_0,\dots,x_n$ there is exactly one choice of weights making the rule exact for all polynomials of degree $\le n$, namely the interpolatory weights $w_i=\int_a^b\ell_i$. In particular every rule with $n+1$ nodes and degree of precision $\ge n$ is interpolatory, and its weights satisfy $\sum_iw_i=b-a$.

Proof. Exactness for $1,x,\dots,x^n$ is the linear system $\sum_iw_ix_i^k=\int_a^bx^k\,dx$ ($0\le k\le n$), whose matrix is the transpose of the Vandermonde matrix of the nodes; it is invertible because the nodes are distinct, so there is exactly one solution. The interpolatory weights are a solution: if $\deg p\le n$, then $p=\sum_ip(x_i)\ell_i$ (interpolation of a polynomial of degree $\le n$ at $n+1$ nodes reproduces it), so $\int p=\sum_ip(x_i)\int\ell_i$. Taking $p\equiv1$ gives $\sum w_i=b-a$. ∎

📘 Definition 5.24 — Newton–Cotes rules

The closed Newton–Cotes rule with $n+1$ nodes is the interpolatory rule with the equally spaced nodes $x_i=a+ih$, $h=(b-a)/n$, $i=0,\dots,n$. The first ones are

$n=1$: trapezoidal rule$\displaystyle\int_a^bf\approx\frac h2\big[f_0+f_1\big]$, $h=b-a$.
$n=2$: Simpson's 1/3 rule$\displaystyle\int_a^bf\approx\frac h3\big[f_0+4f_1+f_2\big]$, $h=\tfrac{b-a}{2}$.
$n=3$: Simpson's 3/8 rule$\displaystyle\int_a^bf\approx\frac{3h}{8}\big[f_0+3f_1+3f_2+f_3\big]$, $h=\tfrac{b-a}{3}$.
$n=4$: Boole's rule$\displaystyle\int_a^bf\approx\frac{2h}{45}\big[7f_0+32f_1+12f_2+32f_3+7f_4\big]$.

Open Newton–Cotes rules use only interior equally spaced nodes; the simplest is the midpoint rule $\int_a^bf\approx(b-a)\,f\!\left(\tfrac{a+b}{2}\right)$.

📐 Theorem 5.39 — Error terms of the basic rules

With $h$ as in Definition 5.24 and some $\xi\in(a,b)$:

$$\text{trapezoidal } (f\in C^2):\quad\int_a^bf-\frac h2(f_0+f_1)=-\frac{h^3}{12}f''(\xi),$$ $$\text{midpoint } (f\in C^2,\ h=b-a):\quad\int_a^bf-h\,f\!\left(\tfrac{a+b}{2}\right)=+\frac{h^3}{24}f''(\xi),$$ $$\text{Simpson 1/3 } (f\in C^4):\quad\int_a^bf-\frac h3(f_0+4f_1+f_2)=-\frac{h^5}{90}f^{(4)}(\xi),$$ $$\text{Simpson 3/8 } (f\in C^4):\quad\int_a^bf-\frac{3h}{8}(f_0+3f_1+3f_2+f_3)=-\frac{3h^5}{80}f^{(4)}(\xi).$$

Hence the trapezoidal and midpoint rules have degree of precision $1$, and both Simpson rules have degree of precision $3$.

Proof. Trapezoidal. Let $p_1$ interpolate $f$ at $a,b$. The interpolation error is $f(x)-p_1(x)=\tfrac12f''(\eta_x)(x-a)(x-b)$, where $x\mapsto f''(\eta_x)=2\,\tfrac{f(x)-p_1(x)}{(x-a)(x-b)}$ is continuous on $(a,b)$ and bounded by $\max|f''|$. Because $(x-a)(x-b)\le0$ does not change sign on $[a,b]$, the mean value theorem for integrals (with a weight of one sign) gives $$\int_a^b(f-p_1)=\frac{f''(\xi)}{2}\int_a^b(x-a)(x-b)\,dx=\frac{f''(\xi)}{2}\cdot\left(-\frac{h^3}{6}\right)=-\frac{h^3}{12}f''(\xi).$$

Midpoint. With $m=\tfrac{a+b}2$, Taylor's theorem gives $$f(x)=f(m)+f'(m)(x-m)+\tfrac12f''(\eta_x)(x-m)^2.$$ The linear term integrates to $0$ by symmetry, and $(x-m)^2\ge0$, so $$\int_a^bf-hf(m)=\tfrac{f''(\xi)}{2}\int_a^b(x-m)^2dx=\tfrac{h^3}{24}f''(\xi).$$

Simpson 1/3. Put $m=x_1$ and, for $0\le t\le h$, $$E(t)=\int_{m-t}^{m+t}f(x)\,dx-\frac t3\big[f(m-t)+4f(m)+f(m+t)\big],$$ so that the error is $E(h)$. Differentiating three times (each step is routine) gives $E(0)=E'(0)=E''(0)=0$ and $$E'''(t)=-\frac t3\big[f'''(m+t)-f'''(m-t)\big]=-\frac{2t^2}{3}\,\frac{f'''(m+t)-f'''(m-t)}{2t}.$$ The last quotient is a continuous function of $t\in(0,h]$ whose values lie between $\min f^{(4)}$ and $\max f^{(4)}$ on $[a,b]$ (mean value theorem). By Taylor's formula with integral remainder, $E(h)=\int_0^h\tfrac{(h-t)^2}{2}E'''(t)\,dt$, and the weight $(h-t)^2t^2$ is $\ge0$, so for some $\xi$ $$E(h)=-\frac{f^{(4)}(\xi)}{3}\int_0^h(h-t)^2t^2\,dt=-\frac{f^{(4)}(\xi)}{3}\cdot\frac{h^5}{30}=-\frac{h^5}{90}f^{(4)}(\xi).$$

Simpson 3/8 (sketch). The same kernel method applies: one shows that the error functional has the form $\int_a^bK(t)f^{(4)}(t)\,dt$ with a kernel $K$ of one sign (the Peano kernel), so it equals $f^{(4)}(\xi)\int K$; testing with $f=x^4$ on $[0,3]$, $h=1$, gives $\int K=E(x^4)/24=\big(\tfrac{243}{5}-\tfrac{99}{2}\big)/24=-\tfrac{3}{80}$.

Degree. The error terms vanish exactly when $f''\equiv0$ (respectively $f^{(4)}\equiv0$), and they are nonzero for $f=x^2$ (respectively $x^4$). ∎

Simpson's rule is built from a parabola, yet it integrates cubics exactly. This is not luck: the cubic $(x-m)^3$ is odd about the midpoint, so its integral and its Simpson value are both $0$. The same symmetry works for every Newton–Cotes rule with an odd number of nodes.

📐 Theorem 5.40 — Degree of precision of Newton–Cotes rules
The closed Newton–Cotes rule with $n+1$ nodes has degree of precision $n$ if $n$ is odd and $n+1$ if $n$ is even. Thus the rules with $2$ and $3$ nodes have degrees $1$ and $3$, those with $4$ and $5$ nodes degrees $3$ and $5$.

Proof. By Theorem 5.38 the rule is exact for degree $\le n$. The nodes and weights are symmetric about $m=\tfrac{a+b}2$: the reflection $x\mapsto a+b-x$ permutes the nodes, and $\ell_{n-i}(x)=\ell_i(a+b-x)$, so $w_{n-i}=w_i$. If $n$ is even, $(x-m)^{n+1}$ is an odd power, so $\int_a^b(x-m)^{n+1}dx=0$, and $\sum_iw_i(x_i-m)^{n+1}=0$ because the terms for $i$ and $n-i$ cancel (and the middle node is $m$ itself). Together with exactness for degree $\le n$ this gives exactness for every polynomial of degree $n+1$. That the degree is not higher follows from the error formulas (for $n=1,2,3$ these are Theorem 5.39; in general the Peano kernel has one sign and the error is a nonzero multiple of $f^{(n+1)}(\xi)$ or $f^{(n+2)}(\xi)$). ∎

A single panel is rarely accurate enough, and raising the number of equally spaced nodes is dangerous (the ⚠️ box). Instead we split $[a,b]$ into many small panels and apply a low-order rule on each.

📐 Theorem 5.41 — Composite rules

Let $h=(b-a)/n$, $x_i=a+ih$, $f_i=f(x_i)$, $I=\int_a^bf$. The composite rules and their errors (for some $\xi\in(a,b)$) are

$$T_n=h\Big[\tfrac12f_0+f_1+\cdots+f_{n-1}+\tfrac12f_n\Big],\qquad I-T_n=-\frac{(b-a)h^2}{12}f''(\xi);$$ $$M_n=h\sum_{i=1}^{n}f\!\left(x_{i-1}+\tfrac h2\right),\qquad I-M_n=+\frac{(b-a)h^2}{24}f''(\xi);$$ $$S_n=\frac h3\Big[f_0+4(f_1+f_3+\cdots+f_{n-1})+2(f_2+f_4+\cdots+f_{n-2})+f_n\Big]\ (n\text{ even}),$$ $$I-S_n=-\frac{(b-a)h^4}{180}f^{(4)}(\xi).$$

So the composite trapezoidal and midpoint rules are of order $2$ and composite Simpson of order $4$: halving $h$ divides the error by about $4$ and $16$ respectively.

Proof. Apply Theorem 5.39 on each panel $[x_{i-1},x_i]$ and add: $I-T_n=-\tfrac{h^3}{12}\sum_{i=1}^nf''(\xi_i)$. The average $\tfrac1n\sum f''(\xi_i)$ lies between $\min f''$ and $\max f''$, so it equals $f''(\xi)$ for some $\xi$ (intermediate value theorem), and $\tfrac{h^3}{12}\,n\,f''(\xi)=\tfrac{(b-a)h^2}{12}f''(\xi)$. The midpoint rule is identical. For Simpson, apply the single rule on the $n/2$ double panels $[x_{2j-2},x_{2j}]$ (half-width $h$): $$I-S_n=-\tfrac{h^5}{90}\sum_{j=1}^{n/2}f^{(4)}(\xi_j)=-\tfrac{h^5}{90}\cdot\tfrac n2f^{(4)}(\xi),$$ which is $-\tfrac{(b-a)h^4}{180}f^{(4)}(\xi)$. ∎

Notice the "loss of one power": a single panel has error $O(h^3)$ (trapezoid) or $O(h^5)$ (Simpson), but there are $n=(b-a)/h$ panels, so the total error is $O(h^2)$ or $O(h^4)$. The same bookkeeping, local error $O(h^{p+1})$ per step and global error $O(h^p)$, reappears for ODE solvers in §5.5.

✏️ Example 3 — The error function: values and a priori step sizes
Approximate $I=\int_0^1e^{-x^2}dx$ by $T_4$ and $S_4$. Then use the error bounds to find the smallest $n$ that guarantees $|I-T_n|\le10^{-6}$, and likewise for $S_n$. (Reference value $I=0.746824133$.)
Data $h=0.25$: $f_0=1$, $f_1=e^{-0.0625}=0.939413$, $f_2=e^{-0.25}=0.778801$, $f_3=e^{-0.5625}=0.569783$, $f_4=e^{-1}=0.367879$.
Rules $T_4=0.25\big[\tfrac12(1+0.367879)+0.939413+0.778801+0.569783\big]=0.742984$ (error $I-T_4=+3.84\times10^{-3}$). $S_4=\tfrac{0.25}{3}\big[1+4(0.939413+0.569783)+2(0.778801)+0.367879\big]=0.746855$ (error $-3.12\times10^{-5}$).
Bounds on derivatives $f''(x)=(4x^2-2)e^{-x^2}$ and $f^{(4)}(x)=(16x^4-48x^2+12)e^{-x^2}$. On $[0,1]$ one checks $|f''|\le2$ and $|f^{(4)}|\le12$, both maxima at $x=0$.
Trapezoidal $|I-T_n|\le\dfrac{1\cdot h^2}{12}\cdot2=\dfrac{1}{6n^2}\le10^{-6}$ needs $n^2\ge166\,667$, i.e. $n\ge409$.
Simpson $|I-S_n|\le\dfrac{h^4}{180}\cdot12=\dfrac{1}{15n^4}\le10^{-6}$ needs $n^4\ge66\,667$, $n\ge16.07$, and $n$ must be even: $n=18$. (Actual errors: $T_{409}$: $3.7\times10^{-7}$; $S_{18}$: $7.8\times10^{-8}$.)
Signs Here $f''(0)\lt0$ near the left end and the trapezoidal error came out positive ($T_4\lt I$): the sign of $I-T_n$ is that of $-f''(\xi)$ for some $\xi$, and $f''\lt0$ on $[0,0.707)$ dominates. For Simpson, $f^{(4)}$ is positive near $0$, and indeed $S_4\gt I$.
✏️ Example 4 — A rule with a fixed end point: what degree is possible?
Find $w_0,w_1$ and $\alpha\in(0,1]$ so that $\int_0^1f\approx w_0f(0)+w_1f(\alpha)$ has the highest possible degree of precision. Prove or disprove: some choice gives degree of precision $3$.
Moments Exactness for $1,x,x^2$ means $w_0+w_1=1$, $w_1\alpha=\tfrac12$, $w_1\alpha^2=\tfrac13$.
Solve Dividing the last two, $\alpha=\tfrac23$; then $w_1=\tfrac34$, $w_0=\tfrac14$. The rule $\int_0^1f\approx\tfrac14f(0)+\tfrac34f\!\left(\tfrac23\right)$ is exact for all quadratics.
Cubic For $x^3$: $\tfrac34\cdot\tfrac{8}{27}=\tfrac29\ne\tfrac14$. So the degree of precision is exactly $2$.
Disprove degree 3 Degree $3$ requires the three equations above, which force $\alpha=\tfrac23$, $w_1=\tfrac34$ — and that choice fails for $x^3$. So no choice works. (With three free parameters one expects to match three moments; Gauss's rule below frees both nodes and matches four.)
🧭 Choosing a rule in practice
  1. Tabulated data at equal steps: composite Simpson if the number of subintervals is even; if it is odd, use Simpson on all but three panels and the 3/8 rule on the remaining three (both are of order 4).
  2. A formula for $f$ that can be evaluated anywhere: Gauss–Legendre (next subsection), or Romberg (last subsection) if you want an automatic error estimate.
  3. Smooth periodic $f$ over a full period: the plain trapezoidal rule — it converges faster than any power of $h$ (Theorem 5.43).
  4. Singular or non-smooth $f$ (e.g. $\sqrt x$ at $0$, a kink): remove the singularity by substitution or split the interval at the kink; no rule attains its nominal order otherwise.
  5. Error control: compute with $n$ and $2n$; the difference estimates the error (for an order-$p$ rule, $I-Q_{2n}\approx\dfrac{Q_{2n}-Q_n}{2^p-1}$).
Interactive 2 — Quadrature Lab: Shapes, Errors and Observed Order

The shaded region is what the rule actually integrates: rectangles (midpoint), trapezoids, parabolic arcs (Simpson), or, for the 2-point Gauss rule, the region under the line through the two Gauss points of each panel (its integral equals the Gauss value, because the rule is exact for linear functions). Dots are the function evaluations. Press Play to double the number of subintervals $n$ and watch the error ratio $E_{n/2}/E_n$: it settles at $2^p$, where $p$ is the observed order. Try the periodic and the non-smooth integrands.

—
n · evaluations—
approximation—
exact—
error I − Q—
E(n/2)/E(n) → order—

Gaussian Quadrature

A Newton–Cotes rule with $n$ nodes fixes the nodes and chooses the $n$ weights, so it can match $n$ moments (sometimes $n+1$, by symmetry). If the nodes are free as well, there are $2n$ parameters, and one may hope to integrate exactly all polynomials of degree $2n-1$. Gauss showed in 1814 that this is possible, that it is the best possible, and that the nodes are the zeros of the Legendre polynomials (§2.2, where $P_0=1$, $P_1=x$, $P_2=\tfrac12(3x^2-1)$, $P_3=\tfrac12(5x^3-3x)$, and $\int_{-1}^1P_mP_n\,dx=0$ for $m\ne n$; in particular $P_n$ is orthogonal to every polynomial of degree $\lt n$).

📘 Definition 5.25 — Gauss–Legendre quadrature

The $n$-point Gauss–Legendre rule on $[-1,1]$ is the interpolatory rule $G_n(f)=\sum_{i=1}^nw_if(t_i)$ whose nodes $t_1,\dots,t_n$ are the zeros of $P_n$ and whose weights are $w_i=\int_{-1}^1\ell_i(t)\,dt$. On $[a,b]$ one uses the affine change of variable $x=\tfrac{a+b}2+\tfrac{b-a}2t$:

$$\int_a^bf(x)\,dx\approx\frac{b-a}{2}\sum_{i=1}^nw_i\,f\!\left(\frac{a+b}{2}+\frac{b-a}{2}t_i\right).$$
$n$nodes $t_i$weights $w_i$exact for degree
1$0$$2$$1$ (midpoint rule)
2$\pm\tfrac{1}{\sqrt3}\approx\pm0.577350$$1,\ 1$$3$
3$0,\ \pm\sqrt{\tfrac35}\approx\pm0.774597$$\tfrac89,\ \tfrac59,\ \tfrac59$$5$
📐 Theorem 5.42 — Gauss quadrature theorem

Let $n\ge1$.

  1. No rule $\sum_{i=1}^nw_if(x_i)$ with $n$ nodes is exact for all polynomials of degree $2n$ on $[-1,1]$.
  2. $P_n$ has $n$ distinct real zeros, all in $(-1,1)$.
  3. The Gauss–Legendre rule $G_n$ is exact for all polynomials of degree $\le2n-1$, and it is the only $n$-node rule with this property.
  4. All weights are positive: $w_i=\int_{-1}^1\ell_i(t)^2\,dt\gt0$, and $\sum w_i=2$.
  5. (Error term, stated without proof.) If $f\in C^{2n}[-1,1]$, $$\int_{-1}^1f-G_n(f)=\frac{2^{2n+1}(n!)^4}{(2n+1)\big((2n)!\big)^3}\,f^{(2n)}(\xi),$$ which is $\tfrac{1}{135}f^{(4)}(\xi)$ for $n=2$ and $\tfrac{1}{15750}f^{(6)}(\xi)$ for $n=3$. On $[a,b]$ the factor $2^{2n+1}$ becomes $(b-a)^{2n+1}$; e.g. $\tfrac{(b-a)^5}{4320}f^{(4)}(\xi)$ for $n=2$.

Proof. (1) Let $\omega(x)=\prod_{i=1}^n(x-x_i)$. Then $\omega^2$ has degree $2n$, the rule gives $\sum w_i\omega(x_i)^2=0$, but $\int_{-1}^1\omega^2\gt0$.

(2) Let $z_1\lt\cdots\lt z_k$ be the points of $(-1,1)$ where $P_n$ changes sign; $k\le n$. If $k\lt n$, the polynomial $q(x)=\prod_j(x-z_j)$ has degree $k\lt n$ and changes sign exactly where $P_n$ does, so $P_nq$ has constant sign on $(-1,1)$ and is not identically zero, whence $\int_{-1}^1P_nq\ne0$ — contradicting orthogonality. So $k=n$; these $n$ sign changes are $n$ distinct zeros, and a polynomial of degree $n$ has no others.

(3) Let $\deg p\le2n-1$. Divide by $P_n$: $p=qP_n+r$ with $\deg q\le n-1$ and $\deg r\le n-1$. Then $\int_{-1}^1p=\int qP_n+\int r=0+\int r$ by orthogonality. On the other hand $p(t_i)=r(t_i)$ because $P_n(t_i)=0$, so $G_n(p)=G_n(r)=\int r$, since an interpolatory rule with $n$ nodes is exact for degree $\le n-1$ (Theorem 5.38). Hence $G_n(p)=\int p$. For uniqueness, suppose a rule with nodes $x_i$ is exact for degree $\le2n-1$, and let $\omega=\prod(x-x_i)$. For every $q$ of degree $\le n-1$, $\deg(q\omega)\le2n-1$, so $\int q\omega=\sum w_iq(x_i)\omega(x_i)=0$. Thus the monic polynomial $\omega$ of degree $n$ is orthogonal to all polynomials of degree $\lt n$; so is $P_n/c_n$ ($c_n$ its leading coefficient), and their difference has degree $\lt n$ and is orthogonal to itself, hence zero. The nodes are the zeros of $P_n$, and the weights are then forced by Theorem 5.38.

(4) $\ell_i^2$ has degree $2n-2\le2n-1$, so by (3) $\int\ell_i^2=\sum_jw_j\ell_i(t_j)^2=w_i$, because $\ell_i(t_j)=\delta_{ij}$. Applying (3) to $p\equiv1$ gives $\sum w_i=2$. ∎

Positivity of the weights matters: it makes the rule stable (rounding errors in the $f(t_i)$ are not amplified, since $\sum|w_i|=\sum w_i=2$), and, together with exactness for degree $2n-1$ and the Weierstrass approximation theorem, it gives $G_n(f)\to\int_{-1}^1f$ for every continuous $f$ — something equally spaced Newton–Cotes rules cannot guarantee.

✏️ Example 5 — Five rules for $\ln2$
Approximate $\ln2=\int_1^2\frac{dx}{x}=0.693147$ by Simpson's 1/3 rule ($3$ nodes), the 3/8 rule ($4$ nodes), and the Gauss–Legendre rules with $2$ and $3$ nodes. Check the sign and size of the $2$-point Gauss error against Theorem 5.42(5).
Simpson $h=\tfrac12$: $\tfrac{1}{6}\big[1+4\cdot\tfrac23+\tfrac12\big]=\tfrac{25}{36}=0.694444$. Error $I-S=-1.30\times10^{-3}$.
3/8 rule $h=\tfrac13$: $\tfrac18\big[1+3\cdot\tfrac34+3\cdot\tfrac35+\tfrac12\big]=\tfrac18\cdot5.55=0.693750$. Error $-6.03\times10^{-4}$.
Gauss, 2 points $x=\tfrac32+\tfrac12t$, nodes $\tfrac32\pm\tfrac{1}{2\sqrt3}$: $$\tfrac12\left(\frac{1}{1.5-0.288675}+\frac{1}{1.5+0.288675}\right)=\frac{9}{13}=0.692308.$$ Error $+8.39\times10^{-4}$, with only two evaluations.
Gauss, 3 points Nodes $1.5$ and $1.5\pm0.387298$, weights $\tfrac12\cdot\tfrac89,\tfrac12\cdot\tfrac59$: $\tfrac49\cdot\tfrac{1}{1.5}+\tfrac{5}{18}\left(\tfrac{1}{1.112702}+\tfrac{1}{1.887298}\right)=0.693122$. Error $+2.55\times10^{-5}$ — fifty times better than Simpson with the same number of evaluations.
Error check For $n=2$ on $[1,2]$: $I-G_2=\tfrac{1}{4320}f^{(4)}(\xi)$ with $f^{(4)}=24/x^5\in[\tfrac{24}{32},24]$, so $I-G_2\in[1.7\times10^{-4},\,5.6\times10^{-3}]$; positive, as observed. Simpson's error $-\tfrac{h^5}{90}f^{(4)}(\xi)$ is negative, also as observed: the two rules bracket the integral here.

Richardson Extrapolation and Romberg Integration

When the error of a method has a known form, two computations with different step sizes can be combined to cancel the leading error term. For the trapezoidal rule, the form is given by a classical expansion.

📐 Theorem 5.43 — Euler–Maclaurin expansion of the trapezoidal error

Let $f\in C^{2m+2}[a,b]$ and $T(h)=T_n$ with $h=(b-a)/n$. Then

$$T(h)-I=\frac{h^2}{12}\big[f'(b)-f'(a)\big]-\frac{h^4}{720}\big[f'''(b)-f'''(a)\big]+\cdots+c_mh^{2m}\big[f^{(2m-1)}(b)-f^{(2m-1)}(a)\big]+R_m,$$

with constants $c_k=B_{2k}/(2k)!$ ($B_2=\tfrac16$, $B_4=-\tfrac1{30}$ the Bernoulli numbers) that do not depend on $f$ or $h$, and $|R_m|\le C_m(b-a)h^{2m+2}\max|f^{(2m+2)}|$. In particular the error has an expansion in even powers of $h$; and if $f$ is smooth and periodic with period $b-a$, all bracketed terms vanish, so $T(h)-I=O(h^{2m+2})$ for every $m$.

Proof (sketch of the first term). On one panel $[x_{i-1},x_i]$ let $q_i(x)=\tfrac12(x-x_{i-1})(x_i-x)\ge0$, which vanishes at both ends and has $q_i''=-1$. Two integrations by parts give $\int_{x_{i-1}}^{x_i}q_if''\,dx=\tfrac h2(f_{i-1}+f_i)-\int_{x_{i-1}}^{x_i}f\,dx$. Since $q_i\ge0$ and $\int q_i=\tfrac{h^3}{12}$, the left side equals $\tfrac{h^3}{12}f''(\eta_i)$. Summing, $T(h)-I=\tfrac{h^2}{12}\,h\sum_if''(\eta_i)$, and $h\sum_if''(\eta_i)$ is a Riemann sum for $\int_a^bf''=f'(b)-f'(a)$; so $T(h)-I=\tfrac{h^2}{12}[f'(b)-f'(a)]+o(h^2)$. Repeating the integration by parts with the periodic Bernoulli polynomials (which play the role of $q_i$) produces the higher terms and the bound on $R_m$. ∎

📘 Definition 5.26 — Richardson extrapolation; the Romberg table

Suppose a computable quantity satisfies $A(h)=A+ch^p+O(h^q)$ with $q\gt p$ and $c$ independent of $h$. The Richardson extrapolate is

$$A_1(h)=\frac{2^pA(h/2)-A(h)}{2^p-1}=A(h/2)+\frac{A(h/2)-A(h)}{2^p-1}.$$

Romberg integration applies this repeatedly to the trapezoidal rule. With $h_k=(b-a)/2^k$ put $R(k,0)=T(h_k)$ and, for $1\le j\le k$, $$R(k,j)=R(k,j-1)+\frac{R(k,j-1)-R(k-1,j-1)}{4^j-1}.$$

📐 Theorem 5.44 — Richardson extrapolation and Romberg integration
  1. Under the hypothesis of Definition 5.26, $A_1(h)=A+O(h^q)$; moreover $A(h/2)-A\approx\dfrac{A(h/2)-A(h)}{2^p-1}$ is a computable estimate of the error of $A(h/2)$.
  2. $R(k,1)$ is the composite Simpson rule $S_{2^k}$, and $R(k,2)$ is the composite Boole rule.
  3. If $f\in C^{2j+2}[a,b]$, then $R(k,j)-I=O(h_k^{2j+2})$ as $k\to\infty$.

Proof. (1) Since $c\,2^p(h/2)^p=ch^p$, $$2^pA(h/2)-A(h)=(2^p-1)A+O(h^q).$$ Dividing by $2^p-1$ gives the claim, and subtracting $A$ from $A(h/2)=A_1(h)-\tfrac{A(h/2)-A(h)}{2^p-1}$ gives the estimate.

(2) Let $h=h_{k-1}$. In $4T(h/2)-T(h)$ the old nodes $x_i$ carry weight $4\cdot\tfrac h2-h=h$ (interior) or $\tfrac h2$ (ends), and the new midpoints carry $4\cdot\tfrac h2=2h$. Dividing by $3$: $\tfrac{h}{6}\big[f_0+4f_{1/2}+2f_1+4f_{3/2}+\cdots+f_n\big]$, which is composite Simpson with step $h/2$. The same computation applied to $\tfrac{16S(h/2)-S(h)}{15}$ gives the weights $\tfrac{2h'}{45}(7,32,12,32,7)$ on each group of four panels of width $h'=h/4$ (Exercise IV.3).

(3) By Theorem 5.43, $$R(k,0)=I+a_1h_k^2+\cdots+a_{j}h_k^{2j}+O(h_k^{2j+2})$$ with $a_i$ independent of $k$. The step from column $j-1$ to $j$ is Richardson with $p=2j$ (since $h_{k-1}=2h_k$, $2^{2j}=4^j$); by induction column $j-1$ has an expansion starting at $h_k^{2j}$, and the combination removes that term without disturbing the form of the rest. ∎

✏️ Example 6 — Romberg's table for $\pi$
Compute the Romberg table up to $R(4,4)$ for $\int_0^1\frac{4}{1+x^2}\,dx=\pi$ and comment on the accuracy of each column.
Column 0 $T(1)=\tfrac12(4+2)=3$, $T(\tfrac12)=\tfrac12\big[\tfrac12(4+2)+3.2\big]=3.1$, then $T(\tfrac14)=3.131176$, $T(\tfrac18)=3.138988$, $T(\tfrac1{16})=3.140942$ (each new value reuses the old nodes and adds the new midpoints: $T(h/2)=\tfrac12T(h)+\tfrac h2\sum f(\text{midpoints})$).
$k$$R(k,0)$$R(k,1)$$R(k,2)$$R(k,3)$$R(k,4)$
03.000000
13.1000003.133333
23.1311763.1415693.142118
33.1389883.1415933.1415943.141586
43.1409423.141592653.141592663.141592643.14159267
Errors Column 0 errors: $1.4\times10^{-1},4.2\times10^{-2},1.0\times10^{-2},2.6\times10^{-3},6.5\times10^{-4}$ — ratio $4$. Column 1 (Simpson): $8.3\times10^{-3},2.4\times10^{-5},1.5\times10^{-7},2.4\times10^{-9}$. The last row is accurate to about $10^{-8}$ in every column from $1$ on, with only $17$ function values.
A surprise Column 1 improves by factors $344,159,64$ — eventually $64=2^6$ per row rather than $16$: here $f'(x)=-8x/(1+x^2)^2$ and $f'''$ happen to satisfy $f'(1)-f'(0)=-2$ but $f'''(1)-f'''(0)=0$ ($f'''(x)=96x(1-x^2)/(1+x^2)^4$), so the $h^4$ term of Theorem 5.43 is absent and Simpson behaves like an order-6 rule. Consequently $R(k,2)$, designed to remove an $h^4$ term that is not there, is not better than $R(k,1)$ — extrapolation helps only when the assumed error form is the true one.
✏️ Example 7 — Convexity and the sign of the error: prove or disprove
Let $f\in C^2[a,b]$ with $f''\ge0$ and $I=\int_a^bf$. (a) Prove that $M_n\le I\le T_n$ for every $n$. (b) Prove or disprove: $S_n\ge I$ for every even $n$.
(a) Error terms By Theorem 5.41, $I-T_n=-\tfrac{(b-a)h^2}{12}f''(\xi)\le0$ and $I-M_n=\tfrac{(b-a)h^2}{24}f''(\eta)\ge0$.
(a) Geometry The same holds for every convex $f$ (no $C^2$ needed): on each panel the chord lies above the graph, so $T_n\ge I$; and the midpoint value $hf(m)$ equals the integral of the tangent line (or any supporting line) at $m$, which lies below the graph, so $M_n\le I$.
(b) Disprove The sign of Simpson's error is governed by $f^{(4)}$, not by $f''$. Take $f(x)=x^2-\tfrac{x^4}{12}$ on $[-1,1]$: $f''=2-x^2\gt0$, but $f^{(4)}=-2$. With $n=2$, $S_2=\tfrac13\big[f(-1)+4f(0)+f(1)\big]=\tfrac{11}{18}=0.6111$, while $I=\tfrac23-\tfrac1{30}=\tfrac{19}{30}=0.6333$. So $S_2\lt I$. (For $f=x^4$, also convex, $S_2=\tfrac23\gt\tfrac25=I$; no inequality holds in general.)
Bonus Since $S_{2n}=\tfrac13(T_n+2M_n)$ (Exercise II.7), Simpson is a weighted average of an overestimate and an underestimate of a convex integrand — which is another way to see why it is so accurate, and why its error sign is not fixed.
⚠️ Counterexamples and pitfalls
  1. A smaller step is not always better for derivatives. Rounding error grows like $\varepsilon/h$ (Theorem 5.37): with double precision the central quotient for $e^x$ at $1$ is best near $h=10^{-5}$ and is worse at $h=10^{-10}$ than at $h=10^{-3}$ (Interactive 1).
  2. Simpson needs an even number of subintervals. With $n$ odd, $S_n$ is not defined; use the 3/8 rule on three of the panels.
  3. Simpson is not always more accurate than the trapezoidal rule. For $\int_0^{2\pi}\cos^2x\,dx=\pi$ with $n=4$ ($h=\tfrac\pi2$, values $1,0,1,0,1$): $T_4=\tfrac\pi2\big(\tfrac12+0+1+0+\tfrac12\big)=\pi$ exactly, while $S_4=\tfrac\pi6(1+0+2+0+1)=\tfrac{2\pi}3$. For periodic integrands the trapezoidal rule is the method of choice (Theorem 5.43).
  4. Error formulas need smoothness. For $\int_0^1\sqrt x\,dx=\tfrac23$, $f''$ and $f^{(4)}$ are unbounded at $0$: the errors of $T_n$ and $S_n$ both shrink only like $h^{3/2}$ (ratios $2.8$ on doubling $n$, not $4$ or $16$). Substituting $x=t^2$ gives $\int_0^12t^2dt$, which Simpson integrates exactly.
  5. More equally spaced nodes can make things worse. The $9$-node closed Newton–Cotes rule has negative weights ($-\tfrac{464}{14175}$, $-\tfrac{454}{2835}$, …), and for $f=1/(1+25x^2)$ on $[-1,1]$ the single-panel Newton–Cotes values $Q$ with $9,11,13,17,21$ nodes give $Q-I=-0.25,\,0.39,\,-0.61,\,-1.8,\,-5.9$ (with $I=0.549$): they diverge, like the interpolants of Runge's example (§5.3). Use composite rules or Gauss rules, whose weights are positive.
  6. Degree of precision is not "number of nodes minus one". Simpson (3 nodes) and the 3/8 rule (4 nodes) both have degree $3$; the 1-node midpoint rule has degree $1$; the $n$-point Gauss rule has degree $2n-1$.
  7. Local versus global order. One Simpson panel has error $O(h^5)$, the composite rule $O(h^4)$; one trapezoid $O(h^3)$, the composite rule $O(h^2)$. Exam options often quote the wrong one.
  8. Gauss rules need $f$ at irrational points. They cannot be applied to data tabulated at equal steps; and a Gauss rule on $[a,b]$ needs the change of variable (with the factor $\tfrac{b-a}{2}$).
  9. Extrapolation needs the right error expansion. Romberg assumes $T(h)-I=a_1h^2+a_2h^4+\cdots$. For $\sqrt x$ the expansion contains $h^{3/2}$, and the Romberg columns do not improve; for the integrand of Example 6 the $h^4$ term is missing and column 2 does not help.
  10. The sign of an error term is that of a derivative somewhere, not everywhere. "$I-T_n=-\tfrac{(b-a)h^2}{12}f''(\xi)$" lets you conclude $T_n\ge I$ only when $f''\ge0$ on the whole interval.

Exercises

I
Numerical differentiation.
  • 1 For $f(x)=\ln x$ and $h=0.1$, compute $D_+(h)$ and $D_0(h)$ at $x_0=1$. Check that the central error lies within the bounds given by Theorem 5.35(2).
  • 2 Show that $\dfrac{f(x_0-2h)-8f(x_0-h)+8f(x_0+h)-f(x_0+2h)}{12h}=f'(x_0)+O(h^4)$ for $f\in C^5$, and find the leading error term.
  • 3 Find the largest $k$ such that $D_0(h)$ is exact for all polynomials of degree $\le k$.
  • 4 Find $a,b,c$ such that $\dfrac{af(x_0)+bf(x_0+h)+cf(x_0+2h)}{h}$ equals $f'(x_0)$ for all quadratics, and give the leading error term.
  • 5 The table $x=0,0.5,1,1.5,2$; $f=1,\ 0.3125,\ -1,\ -0.6875,\ 5$ comes from a polynomial of degree $4$. Compute $f'(0)$ from Theorem 5.36 using differences up to $\Delta^4$, and explain why the answer is exact.
  • 6 From the same table, compute $D^2(0.5)$ at $x_0=1$. The polynomial is $x^4-3x^2+1$; compare with $f''(1)$ and verify the error formula of Theorem 5.35(3) exactly.
  • 7 Values of $f$ are known to within $10^{-6}$ and $|f'''|\le10$. Find the step $h^*$ that minimises the bound of Theorem 5.37 for the central quotient, and the resulting bound.
  • 8 Prove or disprove: if $\lim_{h\to0}D_0(h)$ exists at $x_0$, then $f$ is differentiable at $x_0$.
1 $D_+(0.1)=\ln1.1/0.1=0.953102$ (error $-0.0469$); $D_0(0.1)=(\ln1.1-\ln0.9)/0.2=1.003353$ (error $+0.003353$). Theorem 5.35(2): $D_0-f'=\tfrac{h^2}{6}f'''(\xi)$ with $f'''=2/x^3$, $\xi\in(0.9,1.1)$, so $D_0-f'\in\big[\tfrac{0.01}{6}\cdot\tfrac{2}{1.331},\tfrac{0.01}{6}\cdot\tfrac{2}{0.729}\big]=[0.00250,0.00457]$. The observed $0.00335$ lies inside.
2 From $f(x_0\pm h)-f(x_0\mp h)$ expansions: $f(x_0+h)-f(x_0-h)=2hf'+\tfrac{h^3}{3}f'''+\tfrac{h^5}{60}f^{(5)}+\cdots$ and $f(x_0+2h)-f(x_0-2h)=4hf'+\tfrac{8h^3}{3}f'''+\tfrac{8h^5}{15}f^{(5)}+\cdots$. Then $8(\cdot)_h-(\cdot)_{2h}=12hf'+\big(\tfrac{8}{60}-\tfrac{32}{60}\big)h^5f^{(5)}+\cdots=12hf'-\tfrac25h^5f^{(5)}+\cdots$. Dividing by $12h$: the formula equals $f'(x_0)-\tfrac{h^4}{30}f^{(5)}(x_0)+O(h^6)$. (It is $\tfrac{4D_0(h)-D_0(2h)}{3}$, a Richardson extrapolate.)
3 $k=2$. The error is $-\tfrac{h^2}{6}f'''(\xi)$, zero for quadratics; for $f=x^3$ at $x_0$: $D_0=\tfrac{(x_0+h)^3-(x_0-h)^3}{2h}=3x_0^2+h^2\ne3x_0^2$.
4 Exactness for $1$, $(x-x_0)$, $(x-x_0)^2$: $a+b+c=0$, $b+2c=1$, $b+4c=0$. So $c=-\tfrac12$, $b=2$, $a=-\tfrac32$: the formula $\tfrac{-3f_0+4f_1-f_2}{2h}$, with $f'(x_0)-(\text{formula})=\tfrac{h^2}{3}f'''(\xi)$ (Theorem 5.35(4)).
5 Differences at $x_0=0$: $\Delta f_0=-0.6875$, $\Delta^2f_0=-0.625$, $\Delta^3f_0=2.25$, $\Delta^4f_0=1.5$. Then $f'(0)\approx\tfrac{1}{0.5}\big(-0.6875+0.3125+0.75-0.375\big)=0$. Exact, because for a polynomial of degree $4$ the series of Theorem 5.36 terminates at $\Delta^4$ (Theorem 5.36). Indeed $f'(x)=4x^3-6x$ vanishes at $0$.
6 $D^2=\tfrac{-0.6875-2(-1)+0.3125}{0.25}=6.5$, while $f''(1)=12-6=6$. Theorem 5.35(3): $f''-D^2=-\tfrac{h^2}{12}f^{(4)}=-\tfrac{0.25}{12}\cdot24=-0.5$. Exactly the observed $6-6.5$ (here $f^{(4)}\equiv24$ is constant, so the formula is exact).
7 $h^*=(3\cdot10^{-6}/10)^{1/3}=(3\times10^{-7})^{1/3}=6.69\times10^{-3}$; bound $\tfrac12(9\cdot10^{-12}\cdot10)^{1/3}=2.24\times10^{-4}$ (check: $10^{-6}/h^*=1.49\times10^{-4}$ plus $10h^{*2}/6=7.5\times10^{-5}$).
8 False. For $f(x)=|x|$ at $x_0=0$, $D_0(h)=\tfrac{|h|-|-h|}{2h}=0$ for all $h$, so the limit is $0$, but $f$ is not differentiable at $0$. (The symmetric quotient sees only the odd part of $f$ about $x_0$.)
II
Newton–Cotes and composite rules.
  • 1 Approximate $\int_0^1\frac{dx}{1+x}$ by $T_4$ and $S_4$ and compare with $\ln2$.
  • 2 Approximate $\int_1^4\sqrt x\,dx$ by the 3/8 rule with $n=3$ and give the error.
  • 3 Using the error bounds, find the smallest $n$ guaranteeing an error $\le10^{-4}$ for $\int_0^\pi\sin x\,dx$ by (a) $T_n$; (b) $S_n$.
  • 4 Show directly from the definition that the trapezoidal rule has degree of precision exactly $1$ and Simpson's rule exactly $3$ (test monomials in $x-m$).
  • 5 Derive the weights of the 3/8 rule on $[0,3]$ with nodes $0,1,2,3$ from the moment equations.
  • 6 A car's speed (in m/s) is recorded every $10$ s: $0,12,21,27,30,31,31$ at $t=0,10,\dots,60$. Estimate the distance travelled in the minute by Simpson's rule and by the trapezoidal rule.
  • 7 Prove the identities $T_{2n}=\tfrac12(T_n+M_n)$ and $S_{2n}=\tfrac13(T_n+2M_n)$.
  • 8 Prove that for every cubic polynomial $f$ and every $n$, $T_n-I=\tfrac{h^2}{12}\big(f'(b)-f'(a)\big)$ exactly. Check it for $f=x^3-2x^2+x+3$ on $[0,2]$ with $n=1$.
  • 9 Explain why composite Simpson is "exact for cubics" while the trapezoidal error for a cubic is never zero unless $f'(a)=f'(b)$.
1 $h=0.25$, values $1,0.8,0.666667,0.571429,0.5$. $T_4=0.697024$ (error $-3.9\times10^{-3}$), $S_4=0.693254$ (error $-1.07\times10^{-4}$); $\ln2=0.693147$.
2 $h=1$: $\tfrac38\big[1+3\sqrt2+3\sqrt3+2\big]=4.664547$; exact $\tfrac23(8-1)=\tfrac{14}{3}=4.666667$; error $I-Q=+0.00212$ (consistent with $-\tfrac{3}{80}f^{(4)}(\xi)$, $f^{(4)}=-\tfrac{15}{16}x^{-7/2}\lt0$).
3 $|f''|,|f^{(4)}|\le1$, $h=\pi/n$. (a) $\tfrac{\pi h^2}{12}=\tfrac{\pi^3}{12n^2}\le10^{-4}$ gives $n^2\ge25\,839$, $n\ge161$. (b) $\tfrac{\pi h^4}{180}=\tfrac{\pi^5}{180n^4}\le10^{-4}$ gives $n^4\ge17\,001$, $n\ge11.42$, so $n=12$ (even). Actual errors: $6.3\times10^{-5}$ and $5.3\times10^{-5}$.
4 On $[m-h,m+h]$, Simpson: $(x-m)^k$ for $k=0,1,2,3$ gives $2h,0,\tfrac{2h^3}{3},0$ both exactly and by the rule ($\tfrac h3[h^2+h^2]=\tfrac{2h^3}3$); for $k=4$: exact $\tfrac{2h^5}{5}$, rule $\tfrac h3\cdot2h^4=\tfrac{2h^5}3$. Trapezoid on $[m-\tfrac h2,m+\tfrac h2]$: exact for $1$ and $(x-m)$; for $(x-m)^2$ exact $\tfrac{h^3}{12}$, rule $\tfrac h2\cdot\tfrac{h^2}{2}=\tfrac{h^3}{4}$.
5 By symmetry $w_0=w_3$, $w_1=w_2$. Moments: $2w_0+2w_1=3$ and (for $x^2$) $w_1+4w_1+9w_0=9$, i.e. $9w_0+5w_1=9$. Solving: $w_0=\tfrac38$, $w_1=\tfrac98$ — the rule $\tfrac38[f_0+3f_1+3f_2+f_3]$. (The $x$ and $x^3$ equations then hold by symmetry.)
6 $h=10$ s, $n=6$. Simpson: $\tfrac{10}{3}\big[0+4(12+27+31)+2(21+30)+31\big]=\tfrac{10}{3}\cdot413=1376.7$ m. Trapezoid: $10\big[0+12+21+27+30+31+\tfrac{31}{2}\big]=1365$ m. Simpson is preferred (order 4), assuming the speed varies smoothly.
7 The nodes of $T_{2n}$ are the nodes of $T_n$ plus the midpoints. $T_{2n}=\tfrac h2\big[\tfrac12f_0+f_1+\cdots+\tfrac12f_n\big]+\tfrac h2\sum f(\text{midpoints})=\tfrac12T_n+\tfrac12M_n$. Then $S_{2n}=\tfrac{4T_{2n}-T_n}{3}$ (Theorem 5.44(2)) $=\tfrac{2T_n+2M_n-T_n}{3}=\tfrac{T_n+2M_n}{3}$.
8 In the proof of Theorem 5.43, each panel contributes $\int q_if''$ with $q_i$ symmetric about the panel midpoint $m_i$ and $f''$ linear, so $\int q_if''=f''(m_i)\int q_i=\tfrac{h^3}{12}f''(m_i)$ exactly. Summing: $T_n-I=\tfrac{h^2}{12}\cdot h\sum f''(m_i)=\tfrac{h^2}{12}M_n(f'')=\tfrac{h^2}{12}\int_a^bf''$, because the midpoint rule is exact for the linear $f''$. Check: $f'=3x^2-4x+1$, $f'(2)-f'(0)=4$, $h=2$: $\tfrac{4}{12}\cdot4=\tfrac43$; directly $T_1=1\cdot(3+5)=8$, $I=\tfrac{20}{3}$, $T_1-I=\tfrac43$. ✓
9 For a cubic, $f^{(4)}\equiv0$ in Theorem 5.41, so $S_n=I$. By part 8 the trapezoidal error is $\tfrac{h^2}{12}(f'(b)-f'(a))$, which vanishes iff $f'(a)=f'(b)$ — e.g. it is $0$ for $x^3-3x$ on $[-2,2]$.
III
Degree of precision and Gaussian quadrature.
  • 1 Find the degree of precision of $\int_{-1}^1f\approx\tfrac23\big[2f(-\tfrac12)-f(0)+2f(\tfrac12)\big]$.
  • 2 Derive the $2$-point Gauss–Legendre rule by solving $w_1+w_2=2$, $w_1x_1+w_2x_2=0$, $w_1x_1^2+w_2x_2^2=\tfrac23$, $w_1x_1^3+w_2x_2^3=0$.
  • 3 Approximate $\int_0^{\pi/2}\sin x\,dx$ with $G_2$ and $G_3$ and give the errors.
  • 4 Verify directly that $G_3$ integrates $x^4$ exactly on $[-1,1]$ but not $x^6$.
  • 5 Prove that the weights of the Gauss–Legendre rule are positive, but give an interpolatory rule (with nodes in $[a,b]$) having a negative weight.
  • 6 Find the one-point rule $\int_0^1x\,f(x)\,dx\approx w\,f(x_1)$ of highest degree of precision (a Gauss rule for the weight $x$).
  • 7 Prove that the nodes of any $n$-point rule exact for degree $2n-1$ on $[-1,1]$ are the zeros of $P_n$.
  • 8 Using Theorem 5.42(5), find the smallest $n$ for which $G_n$ (transformed to $[0,1]$) is guaranteed to give $\int_0^1e^x\,dx$ with error $\lt10^{-10}$.
1 $1$: $\tfrac23(2-1+2)=2$ ✓. Odd powers: $0$ by symmetry ✓. $x^2$: $\tfrac23(\tfrac12+\tfrac12)=\tfrac23$ ✓. $x^4$: $\tfrac23(\tfrac18+\tfrac18)=\tfrac16\ne\tfrac25$. Degree $3$ (it is the open Newton–Cotes rule with three nodes; note the negative weight).
2 The rule must be symmetric: from the odd equations, if $x_2=-x_1$ then $w_1=w_2=1$ and $2x_1^2=\tfrac23$, $x_1=\tfrac1{\sqrt3}$. (Without assuming symmetry: $(x-x_1)(x-x_2)=x^2+px+q$ satisfies $\sum w_ix_i^k(x_i^2+px_i+q)=0$ for $k=0,1$, giving $\tfrac23+2q=0$ and $p\cdot\tfrac23=0$; so $x^2-\tfrac13$, the monic $P_2$.)
3 $x=\tfrac\pi4(1+t)$. $G_2=\tfrac\pi4\big[\sin(\tfrac\pi4(1-\tfrac{1}{\sqrt3}))+\sin(\tfrac\pi4(1+\tfrac1{\sqrt3}))\big]=0.998473$ (error $+1.53\times10^{-3}$); $G_3=1.000008$ (error $-8.1\times10^{-6}$).
4 $G_3(x^4)=\tfrac59\cdot2\cdot\tfrac{9}{25}=\tfrac25=\int_{-1}^1x^4$. $G_3(x^6)=\tfrac{10}{9}\cdot\tfrac{27}{125}=\tfrac{6}{25}\ne\tfrac27$. (Degree exactly $5=2\cdot3-1$; $x^5$ is exact by symmetry.)
5 Positivity: Theorem 5.42(4), $w_i=\int\ell_i^2$. Negative weight: part 1 (weight $-\tfrac23$ at $0$), or the 9-node Newton–Cotes rule.
6 Exactness for $1$ and $x$: $w=\int_0^1x\,dx=\tfrac12$ and $wx_1=\int_0^1x^2dx=\tfrac13$, so $x_1=\tfrac23$. For $x^2$: $\tfrac12\cdot\tfrac49=\tfrac29\ne\tfrac14$. Degree $1=2\cdot1-1$: the node is the zero of the degree-1 polynomial $x-\tfrac23$, orthogonal to constants for the weight $x$.
7 This is the uniqueness part of Theorem 5.42(3): $\omega=\prod(x-x_i)$ is orthogonal to every polynomial of degree $\le n-1$ (apply the rule to $q\omega$), hence $\omega=P_n/c_n$.
8 On $[0,1]$ the error is $\tfrac{(n!)^4}{(2n+1)((2n)!)^3}f^{(2n)}(\xi)$, and $f^{(2n)}=e^x\le e$. $n=4$: $5.6\times10^{-10}\cdot e=1.5\times10^{-9}$ — not enough; $n=5$: $3.9\times10^{-13}\cdot e=1.1\times10^{-12}$. So $n=5$. (Actual errors: $n=4$: $9.3\times10^{-10}$; $n=5$: $6.5\times10^{-13}$.)
IV
Richardson extrapolation, Romberg integration and proofs.
  • 1 Build the Romberg table up to $R(2,2)$ for $\int_0^1xe^x\,dx=1$.
  • 2 For $f=\sin$ at $x_0=1$, compute $D_0(0.2)$, $D_0(0.1)$ and their Richardson extrapolate; compare with $\cos1$.
  • 3 Show that $\tfrac{16S_4-S_2}{15}$ on $[a,b]$ is Boole's rule $\tfrac{2h}{45}(7f_0+32f_1+12f_2+32f_3+7f_4)$, $h=\tfrac{b-a}{4}$, and that its degree of precision is $5$.
  • 4 For $\int_0^{2\pi}e^{\sin x}dx=2\pi I_0(1)=7.954926521$, compute $T_4$ and $T_8$ and explain the accuracy of $T_8$.
  • 5 (Corrected trapezoidal rule.) Show that $T_n-\tfrac{h^2}{12}\big(f'(b)-f'(a)\big)=I+O(h^4)$ and apply it to $\int_0^1e^x\,dx$ with $n=2$.
  • 6 If $A(h)=A+ch+O(h^2)$, write the Richardson formula and apply it to the forward quotients of Example 1.
  • 7 Suppose $Q(h)-I\approx Ch^p$. Show that $p\approx\log_2\dfrac{Q(h)-Q(h/2)}{Q(h/2)-Q(h/4)}$, and estimate $p$ from $T(\tfrac12),T(\tfrac14),T(\tfrac18)$ of Example 6 without using the value of $\pi$.
1 $R(0,0)=T(1)=\tfrac e2=1.359141$; $R(1,0)=1.091751$; $R(2,0)=1.023064$. $R(1,1)=1.091751+\tfrac{1.091751-1.359141}{3}=1.002621$; $R(2,1)=1.000169$; $R(2,2)=1.000169+\tfrac{1.000169-1.002621}{15}=1.000006$. Errors $3.6\times10^{-1}$, $2.6\times10^{-3}$, $5.6\times10^{-6}$ along the diagonal.
2 $D_0(0.2)=\tfrac{\sin1.2-\sin0.8}{0.4}=0.536707$, $D_0(0.1)=0.539402$; extrapolate $\tfrac{4(0.539402)-0.536707}{3}=0.540301$. $\cos1=0.540302$: errors $-3.6\times10^{-3}$, $-9.0\times10^{-4}$, $-1.8\times10^{-6}$.
3 $S_4=\tfrac h3(1,4,2,4,1)$ and $S_2=\tfrac{2h}{3}(1,0,4,0,1)$ (weights on $f_0,\dots,f_4$). $\tfrac{1}{15}\big[\tfrac{16h}{3}(1,4,2,4,1)-\tfrac{2h}{3}(1,0,4,0,1)\big]=\tfrac{h}{45}(14,64,24,64,14)=\tfrac{2h}{45}(7,32,12,32,7)$. It is the closed Newton–Cotes rule with $5$ nodes ($n=4$ even), so by Theorem 5.40 its degree is $5$; on $[0,1]$: exact for $x^5$ ($\tfrac16$) but gives $\tfrac{55}{384}\ne\tfrac17$ for $x^6$.
4 $T_4=\tfrac\pi2(1+e+1+e^{-1})=7.989323$ (error $3.4\times10^{-2}$); $T_8=7.954928$ (error $1.3\times10^{-6}$); $T_{16}$ is correct to machine precision. The integrand is smooth and $2\pi$-periodic, so every Euler–Maclaurin correction term vanishes (Theorem 5.43) and the error decreases faster than any power of $h$. (Simpson with $n=8$ has error $1.1\times10^{-2}$, far worse.)
5 Theorem 5.43 with $m=1$: $T_n-I-\tfrac{h^2}{12}[f'(b)-f'(a)]=-\tfrac{h^4}{720}[\cdots]+O(h^6)=O(h^4)$. For $e^x$, $n=2$: $T_2=\tfrac14(1+2e^{0.5}+e)=1.753931$, correction $\tfrac{0.25}{12}(e-1)=0.035798$, corrected value $1.718134$ versus $e-1=1.718282$ (error $1.5\times10^{-4}$, against $3.6\times10^{-2}$ for $T_2$).
6 $p=1$: $A_1=2A(h/2)-A(h)$. With $D_+(0.1)=1.051709$, $D_+(0.05)=1.025422$: $A_1=0.999135$, error $-8.7\times10^{-4}$ (compared with $2.5\times10^{-2}$). The remaining error is $O(h^2)$, so a second step would use the factor $4$.
7 $Q(h)-Q(h/2)\approx Ch^p(1-2^{-p})$ and $Q(h/2)-Q(h/4)\approx Ch^p2^{-p}(1-2^{-p})$; their ratio is $2^p$. From Example 6: $\tfrac{3.131176-3.1}{3.138988-3.131176}=3.99$, so $p\approx\log_23.99=2.00$, as expected for the trapezoidal rule.
🎯 Exam corner CSIR Part BCSIR Part CGATE MA

E1. CSIR Part B GATE MA The nodes $x_1,x_2\in[0,1]$ and weights $w_1,w_2$ are chosen so that $\int_0^1f(x)\,dx\approx w_1f(x_1)+w_2f(x_2)$ has the highest possible degree of precision. Then $x_1x_2$ equals (A) $\tfrac14$; (B) $\tfrac16$; (C) $\tfrac13$; (D) $\tfrac1{12}$.

Idea The optimal 2-node rule is Gauss–Legendre (degree $3$), transported from $[-1,1]$ by $x=\tfrac12(1+t)$.
Compute $x_{1,2}=\tfrac12\pm\tfrac{1}{2\sqrt3}$, so $x_1x_2=\tfrac14-\tfrac1{12}=\tfrac16$. (Equivalently, $x_1,x_2$ are the roots of the monic quadratic orthogonal to $1$ and $x$ on $[0,1]$: $x^2-x+\tfrac16$.)
Answer (B).

E2. CSIR Part B The composite trapezoidal rule with $n$ equal subintervals is used for $\int_0^1x^2\,dx$. The smallest $n$ for which the error is at most $10^{-4}$ is (A) $29$; (B) $40$; (C) $41$; (D) $100$.

Idea $f''\equiv2$ is constant, so the error formula of Theorem 5.41 is exact: $T_n-I=\tfrac{h^2}{12}\cdot2=\tfrac{1}{6n^2}$.
Compute $\tfrac{1}{6n^2}\le10^{-4}\iff n^2\ge1666.7\iff n\ge40.8$. Check: $n=40$ gives $1.04\times10^{-4}$, $n=41$ gives $0.99\times10^{-4}$. ($29$ is the answer for the midpoint rule, whose error is $\tfrac{1}{12n^2}$.)
Answer (C).

E3. CSIR Part B Let $k$ be the largest integer such that $\dfrac{f(x_0+h)-2f(x_0)+f(x_0-h)}{h^2}=f''(x_0)$ for every polynomial $f$ of degree $\le k$, every $x_0$ and every $h\gt0$. Then $k$ is (A) $1$; (B) $2$; (C) $3$; (D) $4$.

Idea By Theorem 5.35(3) the error is $-\tfrac{h^2}{12}f^{(4)}(\xi)$; it vanishes for cubics. Directly, the cubic term $(x-x_0)^3$ is odd about $x_0$ and contributes $h^3-2\cdot0+(-h)^3=0$.
Degree 4 fails For $f=(x-x_0)^4$: $\tfrac{h^4+h^4}{h^2}=2h^2\ne0=f''(x_0)$.
Answer (C).

E4. CSIR Part C Which of the following statements are true? (One or more options may be correct.) (A) The $n$-point Gauss–Legendre rule integrates every polynomial of degree $2n-1$ exactly over $[-1,1]$. (B) The closed Newton–Cotes rule with $5$ nodes has degree of precision $5$. (C) Simpson's 3/8 rule has degree of precision $4$. (D) All weights of every closed Newton–Cotes rule are positive.

(A) True Theorem 5.42(3).
(B) True $5$ nodes means $n=4$, even, so the degree is $n+1=5$ (Theorem 5.40). This is Boole's rule (Exercise IV.3).
(C) False $4$ nodes, $n=3$ odd: degree $3$. On $[0,3]$ with $f=x^4$: rule $\tfrac38(0+3+48+81)=49.5$, exact $48.6$.
(D) False The $9$-node rule has weights $-\tfrac{464}{14175}$ and $-\tfrac{454}{2835}$ (relative to $b-a=1$).
Answer (A) and (B).

E5. CSIR Part C Let $f\in C^4[0,1]$ with $f''(x)\gt0$ for all $x$, $I=\int_0^1f$, and let $T_n$, $M_n$, $S_n$ be the composite trapezoidal, midpoint and Simpson rules with $n$ subintervals. Which of the following are necessarily true for every $n\ge1$? (A) $M_n\le I\le T_n$. (B) $T_{2n}=\tfrac12(T_n+M_n)$. (C) $S_{2n}\ge I$. (D) $T_{2n}\le T_n$.

(A) True Example 7(a).
(B) True An identity valid for every $f$ (Exercise II.7).
(C) False $f(x)=x^2-\tfrac{x^4}{12}$: $f''=2-x^2\gt0$ on $[0,1]$ but $f^{(4)}=-2$, so $I-S_{2n}=-\tfrac{h^4}{180}(-2)\gt0$, i.e. $S_{2n}\lt I$. Concretely $S_2=\tfrac{91}{288}=0.31597\lt\tfrac{19}{60}=0.31667$.
(D) True By (B) and (A), $T_{2n}=\tfrac12(T_n+M_n)\le\tfrac12(T_n+T_n)=T_n$ since $M_n\le I\le T_n$.
Answer (A), (B) and (D).

E6. CSIR Part C Values of a function $f\in C^3$ are available with absolute errors at most $\varepsilon$, and $|f'''|\le M$. $f'(x_0)$ is estimated by the central quotient $\tilde D_0(h)$, and $B(h)=\varepsilon/h+Mh^2/6$ bounds the total error. Which of the following are true? (A) $B$ is minimised at a step proportional to $\varepsilon^{1/3}$. (B) The minimum of $B$ is proportional to $\varepsilon^{2/3}$. (C) For the forward quotient the corresponding optimal step is also proportional to $\varepsilon^{1/3}$. (D) For fixed $\varepsilon\gt0$, $\tilde D_0(h)\to f'(x_0)$ as $h\to0$.

(A) True $B'(h)=0$ at $h^*=(3\varepsilon/M)^{1/3}$ (Theorem 5.37).
(B) True $B(h^*)=\tfrac12(9\varepsilon^2M)^{1/3}\propto\varepsilon^{2/3}$.
(C) False The forward bound $2\varepsilon/h+M_2h/2$ is minimised at $h^*=2\sqrt{\varepsilon/M_2}\propto\varepsilon^{1/2}$.
(D) False The data-error contribution $(\varepsilon_+-\varepsilon_-)/(2h)$ can be as large as $\varepsilon/h\to\infty$; with $\varepsilon_\pm=\pm\varepsilon$ the computed quotient is off by exactly $\varepsilon/h$ plus the truncation error.
Answer (A) and (B).
🧑‍🏫 For the teacher

Suggested plan — 3 lectures × 60 min.

  1. Numerical differentiation. Definition 5.22 and Theorem 5.35 by Taylor expansion on the board (do (2) in full; set (3) as a two-minute exercise). Example 1 live; then Theorem 5.36 with the operator identity $hD=\log(1+\Delta)$ and Example 2. Close with Theorem 5.37 and project Interactive 1: ask the class to predict where the V bottoms out before switching on the noise.
  2. Newton–Cotes and composite rules. Definition 5.23, Theorem 5.38 (Vandermonde), the four basic rules; prove the trapezoidal and Simpson error terms (Theorem 5.39 — the $E(t)$ proof is short and memorable). Theorem 5.40 (symmetry), Theorem 5.41, Example 3. Interactive 2 with $e^{-x^2}$ and then $\sqrt x$ — let students guess the ratios.
  3. Gauss, Richardson, Romberg. Theorem 5.42 in full (it is a beautiful use of orthogonality), Example 5; Euler–Maclaurin (first term only), Definition 5.26, Theorem 5.44, Example 6. Show the periodic integrand in Interactive 2 to motivate Theorem 5.43. Finish with Example 7 and Exam-corner E5.

Discussion questions. (1) Why does integration smooth out data errors while differentiation amplifies them? Relate to $\sum|w_i|$ versus $\sum|c_k|/h^m$. (2) Gauss rules are "twice as good" as Newton–Cotes with the same number of points. Why are Newton–Cotes rules still taught and used? (3) In Example 6, why does the Romberg column 2 not improve on column 1? What does this say about blindly trusting an extrapolation table?

Misconceptions to watch for. "Simpson has degree 2 because it uses a parabola"; confusing local $O(h^5)$ with global $O(h^4)$; using Simpson with an odd number of panels; thinking that $h\to0$ always improves a difference quotient; forgetting the factor $\tfrac{b-a}2$ when transporting Gauss nodes; believing that more Newton–Cotes nodes always means more accuracy; reading the sign of $I-T_n$ from $f''$ at one point.

Suggested homework. I(1, 2, 4, 7, 8), II(1, 3, 6, 7, 8), III(1, 2, 3, 6, 8), IV(1, 3, 4, 7); Exam corner E2, E4, E5.

🔬 Research–Teaching NexusResearch-tutored · optional, about 60 minutes

Research question. How long is an elliptical orbit? The perimeter of the ellipse $x=a\cos t$, $y=b\sin t$ is $P=\int_0^{2\pi}\sqrt{a^2\sin^2t+b^2\cos^2t}\,dt$, an elliptic integral with no elementary formula. How many points does the trapezoidal rule need, how does that depend on the eccentricity, and how good are Ramanujan's famous closed-form approximations?

Why it matters. Orbit lengths are needed in mission design for satellites and space probes; the same integral gives the length of an elliptical running track or of a gear's pitch curve, and the problem of "how many sample points does a periodic integral need" is central to signal processing and to spectral methods for differential equations.

What to do.

  1. Implement the trapezoidal rule $T_N$ on $[0,2\pi]$ with $N=4,8,16,32,64$ for $a=1$ and $b=0.5$, and for a comet-like $b=0.05$. Obtain a reference value with a large $N$ (or a library routine for the complete elliptic integral, $P=4aE(e)$, $e^2=1-b^2/a^2$).
  2. Tabulate the errors. Is the decrease like a power $N^{-p}$ (straight line on a log–log plot) or geometric, like $\rho^{-N}$ (straight line on a semi-log plot)? Estimate $\rho$ for both ellipses.
  3. Repeat with composite Simpson for the same numbers of points. Explain, using Theorem 5.43, why Simpson loses.
  4. Compare with Ramanujan's approximations $P\approx\pi\big[3(a+b)-\sqrt{(3a+b)(a+3b)}\big]$ and $P\approx\pi(a+b)\Big(1+\dfrac{3\lambda}{10+\sqrt{4-3\lambda}}\Big)$, $\lambda=\left(\tfrac{a-b}{a+b}\right)^2$.

Tools: Python (NumPy; scipy.special.ellipe for the reference value) or a spreadsheet.

Hand in: A one-page note with the two error tables, the semi-log plot, your estimates of $\rho$, and a sentence on when Ramanujan's second formula is "good enough" for engineering.

Going further. The geometric rate is governed by how far the integrand extends analytically into the complex $t$-plane (a strip of half-width $\sigma$ gives errors decaying roughly like $e^{-\sigma N}$). Find where $a^2\sin^2t+b^2\cos^2t$ vanishes for complex $t$ and predict $\rho=e^{\sigma}$ from it; compare with your estimates.

Instructor note: for $a=1$, $b=0.5$ the perimeter is $4.844224110$; trapezoidal errors are $-1.3\times10^{-1},-4.4\times10^{-3},-1.8\times10^{-5},-9.4\times10^{-10}$ for $N=4,8,16,32$ (geometric), and machine precision at $N=64$. For $b=0.05$ ($P=4.019425619$) the errors are $-0.72,-0.15,-0.026,-0.0032,-0.0002$ — still geometric but much slower, because the complex zeros of the integrand approach the real axis ($\tanh\sigma=b/a$). Ramanujan's second formula has error $-2.2\times10^{-9}$ for $b=0.5$ and $-2.1\times10^{-4}$ for $b=0.05$; the first has $-1.4\times10^{-5}$ and $-7.1\times10^{-3}$.

🧪 Self-check quiz

0/5 correct

Q1. The degree of precision of Simpson's 1/3 rule is

Q2. For $f\in C^2[a,b]$, the error of the composite trapezoidal rule with step $h$ is

Q3. The nodes of the 2-point Gauss–Legendre rule on $[-1,1]$ are

Q4. One Richardson step $\tfrac13\big(4T(h/2)-T(h)\big)$ applied to the composite trapezoidal rule gives

Q5. The central quotient $\tfrac{f(x_0+h)-f(x_0-h)}{2h}$ is computed in floating-point arithmetic for $h=10^{-1},10^{-2},\dots,10^{-12}$. Typically its error