9.2 Interpolation, Numerical Differentiation and Integration
The interpolating polynomial in Lagrange and Newton form with its error term, divided and finite differences, derivatives from difference quotients and their errors, and the Newton–Cotes integration rules — trapezoidal, Simpson 1/3 and 3/8, simple and composite — with error terms and degree of precision.
A function is often known only through a table of values — readings from an instrument every ten seconds, a solution of a differential equation computed on a grid, a special function tabulated once and stored. Three questions then come up again and again: what is the value between the tabulated points, what is the derivative, and what is the integral? Even when a formula is available it may be useless for these purposes: $\int_0^1e^{-x^2}\,dx$, which every statistician needs, has no elementary antiderivative. The answer to all three questions is the same idea. Replace $f$ by the polynomial that passes through the tabulated points — the interpolating polynomial — and evaluate, differentiate or integrate that polynomial instead. Everything in this section follows from one existence theorem and one error formula for interpolation.
In GATE MA this is one of the most computational parts of the syllabus. MCQs and NATs ask for the value of an interpolating polynomial, a divided difference, a forward difference, a derivative estimate, or a trapezoidal or Simpson approximation from a table — often with the virtual calculator. MSQs test the error theory: which rule has which degree of precision, how the error of a composite rule scales with $h$, when a difference formula is exact, what happens to interpolation as the number of nodes grows. We use the root-finding and linear-algebra language of §9.1, Rolle's theorem and Taylor's theorem; the numerical solution of differential equations in §9.3 is built on the same ideas.
The Interpolating Polynomial and Its Error
Throughout, $\mathcal{P}_n$ is the space of real polynomials of degree at most $n$, and $x_0,x_1,\dots,x_n$ are distinct points called nodes, with values $f_i=f(x_i)$.
A polynomial $p\in\mathcal{P}_n$ interpolates $f$ at the nodes if $p(x_i)=f_i$ for $i=0,\dots,n$. The Lagrange basis polynomials and the nodal polynomial are
$$\ell_i(x)=\prod_{j\ne i}\frac{x-x_j}{x_i-x_j}\quad(i=0,\dots,n),$$ $$\omega_{n+1}(x)=(x-x_0)(x-x_1)\cdots(x-x_n).$$Each $\ell_i$ has degree $n$ and satisfies $\ell_i(x_j)=1$ if $j=i$ and $0$ if $j\ne i$; $\omega_{n+1}$ is monic of degree $n+1$ and vanishes exactly at the nodes.
Proof. Existence: $\sum_if_i\ell_i$ has degree $\le n$, and at $x_j$ only the term $i=j$ survives, giving $f_j$. Uniqueness: if $p,q\in\mathcal{P}_n$ both interpolate, $p-q\in\mathcal{P}_n$ has the $n+1$ distinct roots $x_0,\dots,x_n$, so $p-q=0$ (a nonzero polynomial of degree $\le n$ has at most $n$ roots). The last statements follow from uniqueness: $f$ interpolates itself, and the constant $1$ is interpolated by $\sum_i1\cdot\ell_i$. (Equivalently, the Vandermonde matrix $[x_i^{\,j}]$ of the linear system for the coefficients has determinant $\prod_{i\gt j}(x_i-x_j)\ne0$.) ∎
Let $f\in C^{n+1}[a,b]$, let $x_0,\dots,x_n\in[a,b]$ be distinct and let $p_n$ interpolate $f$ at them. For every $x\in[a,b]$ there is $\xi=\xi_x$ in the smallest interval containing $x,x_0,\dots,x_n$ with
$$f(x)-p_n(x)=\frac{f^{(n+1)}(\xi_x)}{(n+1)!}\,\omega_{n+1}(x).$$Hence $|f(x)-p_n(x)|\le\dfrac{M_{n+1}}{(n+1)!}|\omega_{n+1}(x)|$ with $M_{n+1}=\max_{[a,b]}|f^{(n+1)}|$. Special cases: linear interpolation between $x_0$ and $x_1=x_0+h$: $|f-p_1|\le\tfrac18M_2h^2$ on $[x_0,x_1]$. Quadratic interpolation at $x_0,x_0+h,x_0+2h$: $|f-p_2|\le\dfrac{M_3h^3}{9\sqrt3}$ on $[x_0,x_0+2h]$. Equally spaced nodes in general: $|f-p_n|\le\dfrac{M_{n+1}h^{n+1}}{4(n+1)}$ on $[x_0,x_n]$.
Proof. If $x$ is a node both sides are $0$. Otherwise $\omega_{n+1}(x)\ne0$; fix $x$ and define $$g(t)=f(t)-p_n(t)-\big(f(x)-p_n(x)\big)\frac{\omega_{n+1}(t)}{\omega_{n+1}(x)}.$$ Then $g\in C^{n+1}$ and $g$ vanishes at the $n+2$ distinct points $x_0,\dots,x_n,x$. By Rolle's theorem $g'$ has at least $n+1$ zeros between them, $g''$ at least $n$, …, and $g^{(n+1)}$ at least one zero $\xi$, all in the smallest interval containing these points. Since $p_n^{(n+1)}=0$ and $\omega_{n+1}^{(n+1)}=(n+1)!$, we get $0=g^{(n+1)}(\xi)$ $=f^{(n+1)}(\xi)-\big(f(x)-p_n(x)\big)\dfrac{(n+1)!}{\omega_{n+1}(x)}$, which is the formula. Special cases. On $[x_0,x_1]$, $|(x-x_0)(x-x_1)|$ is largest at the midpoint, where it equals $h^2/4$; divide by $2!$. For three equally spaced nodes put $x=x_1+th$: $|\omega_3|=h^3|t^3-t|$, whose maximum on $[-1,1]$ is $\tfrac{2}{3\sqrt3}$ at $t=\pm\tfrac1{\sqrt3}$; divide by $3!$. The general equally spaced bound follows from the estimate $|\omega_{n+1}(x)|\le\tfrac14h^{n+1}n!$ on $[x_0,x_n]$ (bound the two factors nearest $x$ by $\tfrac14h^2$ together, and the others by $2h,3h,\dots$). ∎
Two remarks that GATE questions exploit. First, the sign of the error is the sign of $f^{(n+1)}(\xi)\,\omega_{n+1}(x)$: if $f^{(n+1)}$ has constant sign, you can tell in advance whether the interpolant over- or under-estimates. Second, the error has the shape of the nodal polynomial — it vanishes at the nodes and is largest near the ends of an equally spaced table (Interactive 1 shows both curves together).
Newton's Form: Divided and Finite Differences
Lagrange's formula is perfect for theory, but adding a node changes every term. Newton's form builds $p_n$ one node at a time, $p_k=p_{k-1}+c_k\,(x-x_0)\cdots(x-x_{k-1})$ with a new coefficient $c_k$, and the new coefficients are divided differences.
For distinct points, $f[x_i]=f(x_i)$ and, recursively,
$$f[x_i,x_{i+1},\dots,x_{i+k}]=\frac{f[x_{i+1},\dots,x_{i+k}]-f[x_i,\dots,x_{i+k-1}]}{x_{i+k}-x_i}.$$So $f[x_0,x_1]=\frac{f_1-f_0}{x_1-x_0}$ is a chord slope and $f[x_0,x_1,x_2]=\frac{f[x_1,x_2]-f[x_0,x_1]}{x_2-x_0}$. In the divided-difference table each entry is written between the two entries it comes from, and its denominator is the distance between the two extreme nodes it involves.
Proof. For a set $S$ of nodes let $P_S$ be its interpolant and $c(S)$ the coefficient of $x^{|S|-1}$ in $P_S$. We show $c(S)$ satisfies the recursion of Definition 9.11, so $c(\{x_i,\dots,x_{i+k}\})=f[x_i,\dots,x_{i+k}]$. Let $S=\{x_i,\dots,x_{i+k}\}$, $A=S\setminus\{x_{i+k}\}$, $B=S\setminus\{x_i\}$. The polynomial $$Q(x)=\frac{(x-x_i)P_B(x)-(x-x_{i+k})P_A(x)}{x_{i+k}-x_i}$$ has degree $\le k$, equals $f$ at $x_i$ (only the second term survives there and gives $P_A(x_i)=f_i$), at $x_{i+k}$, and at every common node of $A$ and $B$ (where it is $\frac{(x-x_i)-(x-x_{i+k})}{x_{i+k}-x_i}f=f$). So $Q=P_S$, and comparing coefficients of $x^k$ gives $c(S)=\frac{c(B)-c(A)}{x_{i+k}-x_i}$. Now $p_k-p_{k-1}$ has degree $\le k$, vanishes at $x_0,\dots,x_{k-1}$, and has leading coefficient $c(\{x_0..x_k\})$; hence $p_k-p_{k-1}=f[x_0,\dots,x_k](x-x_0)\cdots(x-x_{k-1})$, and summing over $k$ gives the formula. For the last statement, add $x$ as an extra node: the interpolant at $x_0,\dots,x_n,x$ equals $p_n+f[x_0,\dots,x_n,x]\omega_{n+1}$ and takes the value $f(x)$ at $x$. ∎
- Explicit form and symmetry: $f[x_0,\dots,x_n]=\displaystyle\sum_{i=0}^{n}\frac{f_i}{\prod_{j\ne i}(x_i-x_j)}$; so the divided difference does not depend on the order of its arguments.
- Mean value property: if $f\in C^n[a,b]$ and the nodes lie in $[a,b]$, then $f[x_0,\dots,x_n]=\dfrac{f^{(n)}(\xi)}{n!}$ for some $\xi$ between the smallest and largest node.
- Polynomials: if $f$ is a polynomial of degree $n$ with leading coefficient $a$, every $n$-th divided difference of $f$ equals $a$ and every divided difference of order $\gt n$ is $0$.
Proof. (1) The coefficient of $x^n$ in Lagrange's formula is $\sum_if_i\big/\prod_{j\ne i}(x_i-x_j)$; by Theorem 9.17 it is $f[x_0,\dots,x_n]$. The sum is visibly symmetric. (2) Compare the last statement of Theorem 9.17 (with $n-1$ in place of $n$) with Theorem 9.16: $f[x_0,\dots,x_{n-1},x]\,\omega_n(x)=\frac{f^{(n)}(\xi)}{n!}\omega_n(x)$; cancel $\omega_n(x)\ne0$ and rename $x$ as $x_n$. (3) The interpolant of degree $\le n$ is $f$ itself, whose $x^n$-coefficient is $a$; and for more than $n+1$ nodes the interpolant is still $f$, whose higher coefficients vanish. ∎
For equally spaced nodes $x_i=x_0+ih$ the divisions are by multiples of $h$, and it is convenient to work with plain differences and the operators of the finite-difference calculus.
With $f_i=f(x_0+ih)$, the forward, backward and central differences are
$$\Delta f_i=f_{i+1}-f_i,\qquad\nabla f_i=f_i-f_{i-1},\qquad\delta f_i=f_{i+\frac12}-f_{i-\frac12},$$with higher differences defined recursively ($\Delta^{k+1}f_i=\Delta^kf_{i+1}-\Delta^kf_i$, and so on). The shift operator is $Ef(x)=f(x+h)$ and $D=\frac{d}{dx}$. As operators: $\Delta=E-1$, $\nabla=1-E^{-1}$, $\delta=E^{1/2}-E^{-1/2}$, and, for analytic $f$ (Taylor's series), $E=e^{hD}$. Hence $\nabla^kf_{i}=\Delta^kf_{i-k}$ and $\Delta^kf_i=\sum_{j=0}^{k}(-1)^{k-j}\binom kjf_{i+j}$.
(a) $\displaystyle f[x_i,x_{i+1},\dots,x_{i+k}]=\frac{\Delta^kf_i}{k!\,h^k}$. Consequently, for a polynomial of degree $n$ with leading coefficient $a$, $\Delta^nf\equiv a\,n!\,h^n$ is constant and $\Delta^{n+1}f\equiv0$.
(b) Newton's forward formula (for $x$ near the top of the table): with $x=x_0+sh$,
$$p_n(x)=f_0+s\,\Delta f_0+\frac{s(s-1)}{2!}\Delta^2f_0+\cdots+\binom sn\Delta^nf_0.$$(c) Newton's backward formula (for $x$ near the bottom): with $x=x_n+sh$,
$$p_n(x)=f_n+s\,\nabla f_n+\frac{s(s+1)}{2!}\nabla^2f_n+\cdots+\binom{s+n-1}{n}\nabla^nf_n.$$Both are the same polynomial $p_n$ through $x_0,\dots,x_n$, merely expanded about different ends. The forward error is $f(x)-p_n(x)=\binom{s}{n+1}h^{n+1}f^{(n+1)}(\xi)$.
Proof. (a) By induction on $k$: $f[x_i,\dots,x_{i+k+1}]=\dfrac{\Delta^kf_{i+1}-\Delta^kf_i}{k!\,h^k\cdot(k+1)h}$ $=\dfrac{\Delta^{k+1}f_i}{(k+1)!\,h^{k+1}}$. The polynomial statement is Theorem 9.18(3). (b) With $x=x_0+sh$ we have $x-x_j=(s-j)h$, so $(x-x_0)\cdots(x-x_{k-1})$ $=h^ks(s-1)\cdots(s-k+1)$ $=k!\,h^k\binom sk$; substitute (a) into Theorem 9.17. (c) List the nodes in the order $x_n,x_{n-1},\dots,x_0$ (allowed by symmetry, Theorem 9.18(1)); then $x-x_{n-j}=(s+j)h$, and $f[x_n,\dots,x_{n-k}]=\nabla^kf_n/(k!\,h^k)$. The error formula is Theorem 9.16 with $\omega_{n+1}(x)=h^{n+1}s(s-1)\cdots(s-n)$. ∎
- Unequally spaced data, or nodes that may be added: divided-difference table and Newton's form. Quick check: the last column is the leading coefficient.
- Equally spaced data: difference table. Interpolate near the top with the forward formula ($s=(x-x_0)/h$), near the bottom with the backward formula ($s=(x-x_n)/h$, negative). Constant $k$-th differences mean the data come from a polynomial of degree $k$.
- A single value, three or four nodes: Lagrange's formula, computing the $\ell_i(x)$ as numbers (check they sum to $1$).
- Error questions: Theorem 9.16 with the max of $|f^{(n+1)}|$; for linear interpolation $\tfrac18M_2h^2$. To find the step for a given accuracy, solve the bound for $h$.
Numerical Differentiation
Differentiating the interpolating polynomial, or equivalently combining Taylor expansions, gives formulas for derivatives in terms of tabulated values.
For 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 has order of accuracy $p$ if its truncation error is $O(h^p)$ as $h\to0$ for every smooth $f$ (and not $O(h^{p+1})$ in general). In operator language $hD=\log E=\log(1+\Delta)=\Delta-\tfrac12\Delta^2+\tfrac13\Delta^3-\cdots$, which gives $f'(x_0)\approx\frac1h\left(\Delta f_0-\tfrac12\Delta^2f_0+\tfrac13\Delta^3f_0-\cdots\right)$ from the top of a table.
There are points $\xi$ in the interval spanned by the nodes used such that
- ($f\in C^2$) $\ f'(x_0)=D_+(h)-\dfrac h2f''(\xi)$ — order $1$; similarly $f'(x_0)=D_-(h)+\dfrac h2f''(\xi)$;
- ($f\in C^3$) $\ f'(x_0)=D_0(h)-\dfrac{h^2}{6}f'''(\xi)$ — order $2$;
- ($f\in C^4$) $\ f''(x_0)=D^2(h)-\dfrac{h^2}{12}f^{(4)}(\xi)$ — order $2$;
- ($f\in C^3$) $\ f'(x_0)=\dfrac{-3f_0+4f_1-f_2}{2h}+\dfrac{h^2}{3}f'''(\xi)$ — a one-sided formula of order $2$, with $f_k=f(x_0+kh)$.
So $D_+$ and $D_-$ are exact for polynomials of degree $\le1$; $D_0$ and the one-sided three-point formula are exact for degree $\le2$; and $D^2$ (whose error involves $f^{(4)}$) is exact for $f''$ of every polynomial of degree $\le3$.
Proof. (1) Taylor: $f(x_0+h)=f_0+hf'_0+\tfrac{h^2}2f''(\xi)$; rearrange. (2) $f(x_0\pm h)=f_0\pm hf_0'+\tfrac{h^2}2f_0''\pm\tfrac{h^3}6f'''(\xi_\pm)$; subtract and divide by $2h$: $D_0(h)=f_0'+\tfrac{h^2}{12}\big(f'''(\xi_+)+f'''(\xi_-)\big)$, and the average of $f'''(\xi_\pm)$ is some $f'''(\xi)$ by the intermediate value theorem. (3) The same with fourth-order expansions, adding instead of subtracting: the odd terms cancel and $D^2(h)=f_0''+\tfrac{h^2}{24}\big(f^{(4)}(\eta_+)+f^{(4)}(\eta_-)\big)$. (4) Expand $f_1$ and $f_2$ to third order: $-3f_0+4f_1-f_2$ $=2hf_0'+\big(4\cdot\tfrac{h^3}{6}f'''(\eta_1)-\tfrac{8h^3}{6}f'''(\eta_2)\big)$, which is $2hf'_0-\tfrac{2h^3}{3}f'''(\xi)$ when $f'''$ is continuous (a weighted mean value argument); divide by $2h$. The exactness statements follow: for a cubic, $f'''$ is a nonzero constant, so $D_0$ has error $-\tfrac{h^2}6f'''\ne0$ and is exact only up to degree $2$, whereas $f^{(4)}=0$ makes $D^2$ exact. ∎
Proof. The computed quotient uses $f(x_0\pm h)+\varepsilon_\pm$ with $|\varepsilon_\pm|\le\varepsilon$, which adds at most $\frac{2\varepsilon}{2h}=\frac{\varepsilon}h$ to the truncation error of Theorem 9.20(2). Minimise $\phi(h)=\frac\varepsilon h+\frac{Mh^2}{6}$: $\phi'(h)=-\frac{\varepsilon}{h^2}+\frac{Mh}3=0$ gives $h^3=\frac{3\varepsilon}M$. ∎
Numerical Integration: Newton–Cotes Rules
Proof. (a) If $Q$ is interpolatory and $\deg p\le n$, then $p$ is its own interpolant, so $Q(p)=\int p$. Conversely, if the degree is $\ge n$, apply $Q$ to $\ell_i$ (degree $n$): $Q(\ell_i)=\sum_jw_j\ell_i(x_j)=w_i$ must equal $\int\ell_i$. Taking $p=1$ gives $\sum w_i=b-a$. (b) The rule is exact for degree $\le n$ by (a). The polynomial $(x-m)^{n+1}$ is odd about $m$ ($n+1$ is odd), so $\int_a^b(x-m)^{n+1}dx=0$, and the symmetric rule gives $0$ too, because the contributions of $x_i$ and $x_{n-i}$ cancel. Every polynomial of degree $n+1$ is a multiple of $(x-m)^{n+1}$ plus one of degree $\le n$, so the rule is exact for degree $n+1$. (c) $p=\omega_{n+1}^2\ge0$ has degree $2n+2$ and $\int p\gt0$, but $Q(p)=0$. ∎
The closed Newton–Cotes rule with $n+1$ nodes is the interpolatory rule with equally spaced nodes $x_i=a+ih$, $h=\frac{b-a}{n}$. The first ones, with $f_i=f(x_i)$:
- $n=1$, trapezoidal rule: $\ \displaystyle\int_a^bf\approx\frac h2(f_0+f_1)$, $h=b-a$;
- $n=2$, Simpson's 1/3 rule: $\ \displaystyle\int_a^bf\approx\frac h3(f_0+4f_1+f_2)$, $h=\frac{b-a}2$;
- $n=3$, Simpson's 3/8 rule: $\ \displaystyle\int_a^bf\approx\frac{3h}8(f_0+3f_1+3f_2+f_3)$, $h=\frac{b-a}3$;
- $n=4$, Boole's rule: $\ \displaystyle\int_a^bf\approx\frac{2h}{45}(7f_0+32f_1+12f_2+32f_3+7f_4)$.
Open Newton–Cotes rules use only interior equally spaced points; the simplest is the midpoint rule $\int_a^bf\approx(b-a)f\!\left(\frac{a+b}2\right)$.
With $h$ as in Definition 9.15 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-hf(m)=+\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$ (Boole's rule: $5$, error $-\tfrac{8h^7}{945}f^{(6)}(\xi)$).
Proof. Trapezoidal. By Theorem 9.16, $f(x)-p_1(x)=\tfrac12f''(\eta_x)(x-a)(x-b)$, and $x\mapsto f''(\eta_x)$ is continuous on $(a,b)$ (it equals $2\frac{f(x)-p_1(x)}{(x-a)(x-b)}$). Since $(x-a)(x-b)\le0$ on $[a,b]$, the mean value theorem for integrals with a weight of constant sign gives
$$\int_a^b(f-p_1)=\frac{f''(\xi)}2\int_a^b(x-a)(x-b)\,dx=\frac{f''(\xi)}2\left(-\frac{h^3}6\right)=-\frac{h^3}{12}f''(\xi).$$
Midpoint. Taylor about $m$: $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)=\tfrac12f''(\xi)\int_a^b(x-m)^2dx=\tfrac{h^3}{24}f''(\xi)$.
Simpson (careful sketch). Let $p_3$ be the cubic that agrees with $f$ at $a,m,b$ and whose derivative agrees with $f'$ at $m$ (Hermite interpolation with $m$ counted twice). Simpson's rule is exact for cubics (Theorem 9.22(b) with $n=2$) and uses only the values at $a,m,b$, where $p_3=f$; hence $S(f)=S(p_3)=\int_a^bp_3$. The Rolle argument of Theorem 9.16, with the double node counted twice, gives $f(x)-p_3(x)=\tfrac{f^{(4)}(\eta_x)}{24}(x-a)(x-m)^2(x-b)$, and $(x-a)(x-m)^2(x-b)\le0$ on $[a,b]$. So $\int_a^b(f-p_3)=\tfrac{f^{(4)}(\xi)}{24}\int_a^b(x-a)(x-m)^2(x-b)\,dx$. With $m=0$, $a=-h$, $b=h$ the integral is $\int_{-h}^{h}(x^2-h^2)x^2dx=-\tfrac{4h^5}{15}$, and $\tfrac1{24}\cdot\left(-\tfrac{4}{15}\right)=-\tfrac1{90}$. The $3/8$ rule is handled in the Go deeper reference. ∎
Let $h=\frac{b-a}n$, $x_i=a+ih$, $f_i=f(x_i)$ and $I=\int_a^bf$. For some $\xi\in(a,b)$:
$$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);$$and the composite $3/8$ rule ($n$ a multiple of $3$) has error $-\frac{(b-a)h^4}{80}f^{(4)}(\xi)$. So the composite trapezoidal and midpoint rules have order $2$ (halving $h$ divides the error by about $4$) and the composite Simpson rules order $4$ (by about $16$). Also $S_{2n}=\frac{4T_{2n}-T_n}{3}$ and $S_{2n}=\frac{2M_n+T_n}{3}$.
Proof. Apply Theorem 9.23 on each panel $[x_{i-1},x_i]$ and add: $I-T_n=-\frac{h^3}{12}\sum_{i=1}^nf''(\xi_i)$. The average $\frac1n\sum f''(\xi_i)$ lies between the minimum and the maximum of the continuous function $f''$, so it equals $f''(\xi)$ for some $\xi$ (intermediate value theorem), and $\frac{h^3}{12}\,n\,f''(\xi)=\frac{(b-a)h^2}{12}f''(\xi)$. The midpoint rule is identical. For Simpson, apply the single rule on the $\frac n2$ double panels $[x_{2j-2},x_{2j}]$: $I-S_n=-\frac{h^5}{90}\cdot\frac n2f^{(4)}(\xi)=-\frac{(b-a)h^4}{180}f^{(4)}(\xi)$; the $3/8$ case is the same with $\frac n3$ triple panels. For the identities, compare weights, writing $k=\frac h2$ for the step of $T_{2n}$ and $S_{2n}$. In $\frac{4T_{2n}-T_n}{3}$ a new midpoint gets $\frac{4k}{3}$, an old interior point $\frac{4k-h}{3}=\frac{2k}{3}$, and an end point $\frac{2k-h/2}{3}=\frac{k}{3}$ — exactly Simpson's weights $\frac k3(1,4,2,4,\dots,4,1)$. Finally $T_{2n}=\frac12(T_n+M_n)$ turns one identity into the other. ∎
- Count panels first: $n$ subintervals means $n+1$ ordinates. Simpson 1/3 needs $n$ even, 3/8 needs $n$ a multiple of $3$. With an odd number of panels, combine one 3/8 block with 1/3 blocks.
- Weights: trapezoidal $1,2,2,\dots,2,1$ times $\frac h2$; Simpson $1,4,2,4,\dots,2,4,1$ times $\frac h3$; 3/8: $1,3,3,2,3,3,2,\dots,3,3,1$ times $\frac{3h}8$.
- Degree of precision of a strange rule: test $1,x,x^2,\dots$ in turn (shift to a symmetric interval to kill odd powers).
- Required $n$: bound $|f''|$ or $|f^{(4)}|$ on $[a,b]$, solve the composite error bound for $h$, round $n$ up (and to an even number for Simpson).
- Signs: for $f''\gt0$, $T_n\gt I\gt M_n$; Simpson combines them as $\frac{2M+T}{3}$ to cancel the leading errors.
- More nodes can make interpolation worse (Runge). For $f(x)=\frac1{1+25x^2}$ on $[-1,1]$ with equally spaced nodes, $\max|f-p_n|\to\infty$ as $n\to\infty$, although $f$ is analytic on the real line. Chebyshev nodes $\cos\frac{(2i+1)\pi}{2n+2}$ cure this (Interactive 1).
- Interpolation is not approximation. The Weierstrass theorem (§4.2) says polynomials approximate continuous functions uniformly; it does not say interpolants at equally spaced nodes do. For $|x|$ on $[-1,1]$ with equally spaced nodes, $p_n(x)$ converges to $|x|$ only at $x=-1,0,1$.
- The error formula needs smoothness ($f\in C^{n+1}$), and $\xi$ depends on $x$ — it is not one fixed point for the whole interval.
- Constant $k$-th differences need equal spacing. For unequal nodes use divided differences; $\Delta^kf$ of a degree-$k$ polynomial equals $a\,k!\,h^k$, not $a$.
- The forward difference is not exact for quadratics ($D_+$ of $x^2$ at $0$ is $h$, not $0$); the central difference is exact for quadratics but not for cubics ($D_0$ of $x^3$ at $0$ is $h^2$).
- Smaller $h$ is not always better in differentiation: below $h^*=(3\varepsilon/M)^{1/3}$ rounding errors dominate (Theorem 9.21).
- More nodes do not always raise the degree of precision. Simpson's 1/3 rule (3 nodes) and 3/8 rule (4 nodes) both have degree $3$; the trapezoidal rule (2 nodes) and the midpoint rule (1 node) both have degree $1$.
- "Order 4" needs $f\in C^4$. For $\int_0^1\sqrt x\,dx$, halving $h$ divides the composite Simpson error by about $2^{1.5}\approx2.83$, not $16$: $f'$ is unbounded at $0$.
- The trapezoidal rule does not always overestimate — only for convex $f$. For $\sin x$ on $[0,\pi]$ (concave) it underestimates.
- High-order Newton–Cotes rules are unreliable: from $n=8$ on, some weights are negative, and the rules need not converge as $n\to\infty$. Use composite low-order rules instead.
- The midpoint rule is not "less accurate because it uses one point": its error constant $\frac1{24}$ is half the trapezoidal $\frac1{12}$.
- CSIR Unit 3 · §5.3 Finite Differences and Interpolation — the operator calculus of $E,\Delta,\nabla,\delta,\mu$ with proofs, error bounds for equally spaced nodes, Hermite interpolation with its error term, cubic splines and their minimum-curvature property, and Runge's phenomenon with the optimality of Chebyshev nodes.
- CSIR Unit 3 · §5.4 Numerical Differentiation and Integration — the full error analysis of the Simpson 3/8 and Boole rules, the degree of precision of all Newton–Cotes rules, Gaussian quadrature, the Euler–Maclaurin expansion, and Richardson extrapolation with Romberg integration.
Two Labs
Exercises
- 1 Find the polynomial of degree $\le2$ through $(0,1)$, $(1,3)$, $(2,7)$ by Lagrange's formula.
- 2 Build the divided-difference table for $(1,2)$, $(2,3)$, $(4,11)$, $(5,18)$, find the interpolating polynomial and its value at $3$. What is its degree?
- 3 Prove that $\sum_{i=0}^{n}x_i\,\ell_i(x)=x$ for $n\ge1$, and more generally $\sum_ix_i^k\ell_i(x)=x^k$ for $k\le n$.
- 4 A table of $\sin x$ has step $h=0.1$. Bound the error of linear interpolation in it.
- 5 What step $h$ makes linear interpolation in a table of $e^x$ on $[0,1]$ accurate to $10^{-6}$?
- 6 Bound the error of quadratic interpolation (three consecutive equally spaced nodes) in a table of $\sin x$ with $h=0.1$.
- 7 Show that $f[x_0,x_1,\dots,x_n]=\dfrac{(-1)^n}{x_0x_1\cdots x_n}$ for $f(x)=\frac1x$ (nonzero nodes).
- 8 Interpolate $|x|$ at $-1,0,1$. What is the error at $x=\tfrac12$? Why does Theorem 9.16 not apply?
- 9 Prove or disprove: if $p_n$ interpolates $f$ at $n+1$ equally spaced nodes in $[-1,1]$ and $f$ is infinitely differentiable, then $p_n\to f$ uniformly as $n\to\infty$.
- 1 Tabulate $f(x)=x^3-x$ at $x=0,1,2,3,4$ and form all forward differences. Explain the third column.
- 2 Prove $\Delta\nabla=\nabla\Delta=\Delta-\nabla=\delta^2$.
- 3 Show that $\Delta^2e^{x}=(e^h-1)^2e^x$ (step $h$), and more generally $\Delta^ke^{x}=(e^h-1)^ke^x$.
- 4 Use Newton's forward formula with the table $x=0,1,2,3$, $f=1,2,9,28$ to find $f(1.5)$.
- 5 Same table: find $f(2.5)$ with the backward formula.
- 6 The values $f(0)=1$, $f(1)=3$, $f(3)=31$, $f(4)=69$ come from a cubic. Find the missing $f(2)$ without finding the cubic.
- 7 Prove that $\Delta^n(x^n)=n!\,h^n$ and $\Delta^{n+1}(x^n)=0$.
- 1 With $h=0.1$, estimate the derivative of $\sin x$ at $0.5$ by $D_+$ and $D_0$ (use $\sin0.4=0.389418$, $\sin0.5=0.479426$, $\sin0.6=0.564642$) and compare with $\cos0.5=0.877583$.
- 2 Derive the formula of Theorem 9.20(4) by differentiating the quadratic interpolant at $x_0,x_1,x_2$.
- 3 Estimate $f''(0.5)$ for $f=\sin$ from the data of III.1 and give the error.
- 4 Values of $f$ carry errors up to $\varepsilon=10^{-10}$ and $|f'''|\le1$. Find the best step for the central difference and the resulting error bound.
- 5 Richardson extrapolation: show that $\frac{4D_0(h/2)-D_0(h)}{3}$ has error $O(h^4)$ for smooth $f$, and apply it to $\log x$ at $2$ with $h=0.1$ (use $\log2.05=0.717840$, $\log1.95=0.667829$ and the data of Example 4).
- 6 Prove or disprove: $D_0(h)$ gives the exact derivative of every cubic at every point.
- 1 Apply Simpson's 1/3 rule (one double panel) to $\int_0^1x^4dx$ and verify that the error equals $-\frac{h^5}{90}f^{(4)}$ exactly.
- 2 Apply Simpson's 3/8 rule to $\int_0^3x^4dx$ and check the error term.
- 3 Compute $T_4$ and $S_4$ for $\int_0^\pi\sin x\,dx$. Which error has which sign, and why?
- 4 How many panels does composite Simpson need for $\int_1^2\log x\,dx$ with error at most $10^{-8}$?
- 5 Find the degree of precision of $\int_0^1f\approx\frac14\left[f(0)+3f\!\left(\tfrac23\right)\right]$.
- 6 Find $a,b,c$ so that $\int_0^1f\approx af(0)+bf(1)+cf'(0)$ is exact for all quadratics. What is its degree of precision?
- 7 Prove that $M_n\le\int_a^bf\le T_n$ for convex $f\in C^2[a,b]$, and deduce a two-sided bound for $\int_0^1e^{-x}dx$ from $M_2$ and $T_2$.
- 8 Hydrology. The depth of a river (in metres) measured every $2$ m across its $12$ m width is $0, 1.2, 2.1, 2.6, 2.4, 1.5, 0$. Estimate the cross-sectional area by Simpson's 1/3 rule and by the trapezoidal rule.
- 9 Prove the identity $S_{2n}=\frac{4T_{2n}-T_n}3$ for $n=1$ directly from the formulas.
- 10 Prove or disprove: a quadrature rule with $3$ nodes can have degree of precision $5$, but not $6$.
E1. GATE MA · MCQ Let $p$ be the polynomial of degree at most $3$ with $p(0)=1$, $p(1)=0$, $p(2)=1$, $p(3)=10$. Then $p(4)$ equals (A) $29$; (B) $31$; (C) $33$; (D) $35$.
E2. GATE MA · MCQ The degree of precision of the rule $\displaystyle\int_{-1}^{1}f(x)\,dx\approx\frac23\left[2f\!\left(-\tfrac12\right)-f(0)+2f\!\left(\tfrac12\right)\right]$ is (A) $1$; (B) $2$; (C) $3$; (D) $4$.
E3. GATE MA · MSQ Which of the following statements is/are true? (One or more options may be correct.) (A) For $f\in C^3$, the central difference $\frac{f(x+h)-f(x-h)}{2h}$ approximates $f'(x)$ with error $O(h^2)$. (B) The forward difference $\frac{f(x+h)-f(x)}{h}$ gives the exact derivative of every quadratic polynomial. (C) For $f\in C^2[a,b]$, halving $h$ in the composite trapezoidal rule reduces the error by a factor close to $4$ for small $h$, provided $f'(b)\ne f'(a)$. (D) For $\int_0^1\sqrt x\,dx$, halving $h$ in the composite Simpson rule reduces the error by a factor close to $16$.
E4. GATE MA · MSQ Which of the following is/are true? (One or more options may be correct.) (A) If $f(x)=2x^3+x$ is tabulated with step $h$, then $\Delta^3f\equiv12h^3$. (B) For $f(x)=x^2$ and any three distinct points, $f[x_0,x_1,x_2]=1$. (C) For $f(x)=\frac1{1+25x^2}$ the interpolating polynomials at $n+1$ equally spaced nodes of $[-1,1]$ converge to $f$ uniformly on $[-1,1]$ as $n\to\infty$. (D) $\Delta\nabla=\Delta-\nabla$.
E5. GATE MA · NAT The speed of a car, read every $10$ seconds, is $0,12,20,24,26\ \text{m/s}$ at $t=0,10,20,30,40$ s. The distance travelled in these $40$ seconds, estimated by the composite Simpson 1/3 rule, is ______ metres (correct to the nearest integer).
E6. GATE MA · NAT The composite trapezoidal rule with $n$ equal subintervals is used for $\int_0^2e^x\,dx$. The smallest $n$ for which the standard error bound $\frac{(b-a)h^2}{12}\max_{[a,b]}|f''|$ is at most $10^{-4}$ is ______.
Suggested plan — 3 lectures × 60 min.
- Interpolation. Definition 9.10, Theorem 9.15 (existence by Lagrange, uniqueness by root counting). Theorem 9.16 with the Rolle proof in full — it is the engine of the whole section. Example 1, emphasising the two-sided bound and the sign. Interactive 1: $e^x$ with $n=2,4,8$, then Runge's function with equal and Chebyshev nodes; let students observe the error following $\omega_{n+1}$.
- Newton's form and differences. Definition 9.11, Theorem 9.17 (state; prove the recursion with the $Q$ trick), Theorem 9.18. Example 2 on the board — add the fifth point and watch only one diagonal change. Definition 9.12, Theorem 9.19, Example 3, Exercise II.6. Numerical differentiation: Definition 9.13, Theorem 9.20 by Taylor, Example 4, Theorem 9.21 (ask the class why a smaller $h$ can be worse).
- Integration. Definition 9.14, Theorem 9.22, Definition 9.15, Theorem 9.23 (trapezoid and midpoint proofs in full, Simpson via the Hermite cubic). Theorem 9.24, Examples 5–7. Interactive 2: order $2$ vs $4$ on the log–log plot, then $\sqrt x$ and $x^3$ under Simpson. GATE corner E2, E3 and E6 live.
Discussion questions. (1) Simpson's rule uses three points but integrates cubics exactly. Where does the "free" degree come from, and why does the 3/8 rule not get one? (2) The error of interpolation is $\frac{f^{(n+1)}(\xi)}{(n+1)!}\omega_{n+1}(x)$. Which of the two factors can we control, and how do Chebyshev nodes control it? (3) Why is numerical differentiation ill-conditioned while numerical integration is well-conditioned?
Misconceptions to watch for. Believing more nodes always help; applying the error formula to non-smooth functions; forgetting that $s$ is negative in the backward formula; using Simpson with an odd number of panels; confusing the single-panel error $O(h^5)$ with the composite error $O(h^4)$; claiming the trapezoidal rule always overestimates; thinking the 3/8 rule is more accurate than the 1/3 rule because it uses more points.
Suggested homework. I(2, 4, 5, 7, 9), II(1, 4, 6), III(1, 2, 5), IV(1, 3, 4, 6, 7, 8); GATE corner E1, E4, E5.
Research question. When the integrand is not smooth, what order of convergence do the trapezoidal and Simpson rules really achieve — and can you predict it from the type of singularity?
Why it matters. Integrands with a corner or a square-root behaviour at an end point are everywhere: the flow rate through a pipe near the wall, the stress near the tip of a crack (which behaves like $r^{-1/2}$), probability densities with a kink, the energy spectrum of a signal. The textbook orders $2$ and $4$ assume $f\in C^2$ and $f\in C^4$; engineers who rely on them for such integrands can be badly misled about how many sample points they need.
What to do.
- For $f(x)=x^\alpha$ on $[0,1]$ with $\alpha=0.5,\ 1.5,\ 2.5,\ 4.5$, compute the composite trapezoidal and Simpson errors for $n=8,16,32,\dots,256$ (exact value $\frac1{\alpha+1}$).
- Estimate the observed order $p\approx\log_2\frac{E_n}{E_{2n}}$ for each case and make a table.
- Conjecture a formula for $p$ in terms of $\alpha$ for each rule. (Hint: compare $\min(2,\ \alpha+1)$ and $\min(4,\ \alpha+1)$.)
- Explain the conjecture: show that the first panel alone contributes an error of order $h^{\alpha+1}$, while the remaining panels behave like a smooth integrand.
Tools: Python (a loop and a few lines of numpy) or a spreadsheet.
Hand in: the table of observed orders, your conjectured formula, and a half-page argument for it.
Going further. A change of variables $x=t^2$ turns $\int_0^1\sqrt x\,dx$ into a smooth integral; try it and observe order $4$ again. Read about Gauss–Jacobi quadrature, which builds the singular weight into the rule.
🧪 Self-check quiz
Q1. The degree of precision of Simpson's 1/3 rule is
Q2. Linear interpolation in a table with step $h$ of a function with $|f''|\le M$ has error at most
Q3. If $f$ is a polynomial of degree $4$ with leading coefficient $3$, then for any five distinct points $f[x_0,x_1,x_2,x_3,x_4]$ equals
Q4. The central difference $\frac{f(x+h)-f(x-h)}{2h}$ approximates $f'(x)$ with truncation error of order
Q5. For $f\in C^4[a,b]$, the error of the composite Simpson rule with step $h$ is