Chapter 9 · Numerical Analysis

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)$.

📘 Definition 9.10 — Interpolating polynomial; Lagrange basis; nodal polynomial

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.

📐 Theorem 9.15 — Existence and uniqueness; Lagrange's formula
For distinct nodes $x_0,\dots,x_n$ and any values $f_0,\dots,f_n$ there is exactly one $p_n\in\mathcal{P}_n$ with $p_n(x_i)=f_i$ for all $i$, namely $$p_n(x)=\sum_{i=0}^{n}f_i\,\ell_i(x).$$ In particular, if $f$ is itself a polynomial of degree $\le n$, then $p_n=f$; and $\sum_i\ell_i(x)=1$ for all $x$.

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$.) ∎

📐 Theorem 9.16 — The interpolation error

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).

✏️ Example 1 — Lagrange interpolation of $e^x$ with a two-sided error bound
Using $e^0=1$, $e^{0.5}=1.648721$, $e^1=2.718282$, estimate $e^{0.25}$ by quadratic interpolation. Bound the error from above and below without using the true value, and decide its sign.
Basis values At $x=\tfrac14$ with nodes $0,\tfrac12,1$: $\ell_0=\frac{(\frac14-\frac12)(\frac14-1)}{(0-\frac12)(0-1)}=\tfrac38$, $\ell_1=\frac{(\frac14)(\frac14-1)}{(\frac12)(\frac12-1)}=\tfrac34$, $\ell_2=\frac{(\frac14)(\frac14-\frac12)}{(1)(\frac12)}=-\tfrac18$. (Check: $\tfrac38+\tfrac34-\tfrac18=1$.)
Estimate $p_2\!\left(\tfrac14\right)=\tfrac38(1)+\tfrac34(1.648721)-\tfrac18(2.718282)=1.271756$.
Error $\omega_3\!\left(\tfrac14\right)=\tfrac14\cdot\left(-\tfrac14\right)\cdot\left(-\tfrac34\right)=\tfrac3{64}=0.046875$ and $f'''=e^x\in[1,e]$ on $[0,1]$. So $e^{0.25}-p_2(0.25)=\tfrac{e^{\xi}}{6}\cdot0.046875$ lies between $\tfrac{0.046875}{6}=0.0078$ and $\tfrac{0.046875\,e}{6}=0.0212$, and it is positive: the interpolant underestimates.
Check $e^{0.25}=1.284025$, error $0.012270$ — inside $[0.0078,\ 0.0212]$ and positive. (It corresponds to $e^{\xi}\approx1.571$, i.e. $\xi\approx0.45$.)

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.

📘 Definition 9.11 — 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.

📐 Theorem 9.17 — Newton's divided-difference formula
The interpolating polynomial at distinct nodes $x_0,\dots,x_n$ is $$p_n(x)=f[x_0]+f[x_0,x_1](x-x_0)+f[x_0,x_1,x_2](x-x_0)(x-x_1)+\cdots$$ $$\cdots+f[x_0,\dots,x_n](x-x_0)\cdots(x-x_{n-1}).$$ Thus $f[x_0,\dots,x_n]$ is the leading coefficient (coefficient of $x^n$) of the interpolant at $x_0,\dots,x_n$. Moreover, for any $x$ different from the nodes, $f(x)-p_n(x)=f[x_0,\dots,x_n,x]\;\omega_{n+1}(x)$.

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$. ∎

📐 Theorem 9.18 — Properties of divided differences
  1. 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.
  2. 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.
  3. 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.

📘 Definition 9.12 — Finite differences and the shift operator

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}$.

📐 Theorem 9.19 — Differences and Newton's forward and backward formulas

(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)$. ∎

✏️ Example 2 — A divided-difference table, and a hidden cubic
The data $x=-1,0,2,3$ with $f=2,1,5,22$ are given. (a) Find the interpolating polynomial in Newton's form and evaluate it at $1.5$. (b) A fifth reading $f(1)=0$ arrives. Update the table and interpret the result.
First differences $f[-1,0]=\frac{1-2}{1}=-1$, $f[0,2]=\frac{5-1}{2}=2$, $f[2,3]=\frac{22-5}{1}=17$.
Higher $f[-1,0,2]=\frac{2-(-1)}{2-(-1)}=1$, $f[0,2,3]=\frac{17-2}{3-0}=5$, $f[-1,0,2,3]=\frac{5-1}{3-(-1)}=1$.
(a) Newton form $p_3(x)=2-(x+1)+(x+1)x+(x+1)x(x-2)$, which expands to $x^3-2x+1$. At $1.5$: $3.375-3+1=1.375$.
(b) Update Append $x=1$ at the bottom: $f[3,1]=\frac{0-22}{1-3}=11$, $f[2,3,1]=\frac{11-17}{1-2}=6$, $f[0,2,3,1]=\frac{6-5}{1-0}=1$, $f[-1,0,2,3,1]=\frac{1-1}{1-(-1)}=0$.
Interpretation The new coefficient is $0$, so $p_4=p_3$: the fifth point lies on the same cubic ($1-2+1=0$ ✓). A vanishing $(n+1)$-th divided difference is the signature of data from a polynomial of degree $\le n$ (Theorem 9.18(3)). Only one new diagonal of the table had to be computed — the advantage of Newton's form.
✏️ Example 3 — Forward and backward interpolation in an equally spaced table
A town's population (in thousands) was $40,46,55,67,82$ in the years $2000,2005,2010,2015,2020$. Estimate the population in $2003$ with Newton's forward formula and in $2018$ with the backward formula, and explain why no higher-degree terms are needed.
Difference table $\Delta$: $6,\ 9,\ 12,\ 15$; $\Delta^2$: $3,\ 3,\ 3$; $\Delta^3$: $0,\ 0$; $\Delta^4$: $0$. The second differences are constant, so the data lie on a quadratic (Theorem 9.19(a)) and $p_4=p_2$.
2003, forward $h=5$, $s=\frac{2003-2000}{5}=0.6$: $p=40+0.6(6)+\frac{0.6(-0.4)}{2}(3)=40+3.6-0.36=43.24$ thousand.
2018, backward $s=\frac{2018-2020}{5}=-0.4$, with $\nabla f_4=15$, $\nabla^2f_4=3$: $p=82+(-0.4)(15)+\frac{(-0.4)(0.6)}{2}(3)=82-6-0.36=75.64$ thousand.
Check Both formulas give the same quadratic; evaluating the Lagrange form through all five points also gives $43.24$ and $75.64$. (Of course, a real population need not be a quadratic in time: interpolation reproduces the data, not the truth between them.)
🧭 Which interpolation formula?
  1. 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.
  2. 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$.
  3. A single value, three or four nodes: Lagrange's formula, computing the $\ell_i(x)$ as numbers (check they sum to $1$).
  4. 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.

📘 Definition 9.13 — Difference quotients; order of accuracy

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.

📐 Theorem 9.20 — Error terms of the basic difference formulas

There are points $\xi$ in the interval spanned by the nodes used such that

  1. ($f\in C^2$) $\ f'(x_0)=D_+(h)-\dfrac h2f''(\xi)$ — order $1$; similarly $f'(x_0)=D_-(h)+\dfrac h2f''(\xi)$;
  2. ($f\in C^3$) $\ f'(x_0)=D_0(h)-\dfrac{h^2}{6}f'''(\xi)$ — order $2$;
  3. ($f\in C^4$) $\ f''(x_0)=D^2(h)-\dfrac{h^2}{12}f^{(4)}(\xi)$ — order $2$;
  4. ($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. ∎

📐 Theorem 9.21 — Truncation versus rounding: the best step
If the values of $f$ are known only up to an absolute error $\varepsilon$ and $|f'''|\le M$, the total error of the central difference satisfies $$\big|f'(x_0)-\tilde D_0(h)\big|\le\frac{\varepsilon}{h}+\frac{Mh^2}{6},$$ which is smallest for $h^*=(3\varepsilon/M)^{1/3}$. Taking $h$ smaller than about $h^*$ makes the computed derivative worse, not better. (For the forward difference the bound is $\frac{2\varepsilon}{h}+\frac{Mh}{2}$ with $|f''|\le M$, minimised at $h^*=2\sqrt{\varepsilon/M}$.)

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$. ∎

✏️ Example 4 — Derivatives of $\log x$ at $x=2$ from a table
From $\log1.9=0.641854$, $\log2=0.693147$, $\log2.1=0.741937$ (and $\log2.2=0.788457$), estimate $f'(2)$ and $f''(2)$ for $f=\log$ by the forward, central and one-sided three-point formulas with $h=0.1$, and compare the errors with Theorem 9.20.
Forward $D_+=\frac{0.741937-0.693147}{0.1}=0.48790$. True $f'(2)=0.5$; error $0.01210$. Prediction: $\tfrac h2|f''|\approx0.05\cdot\tfrac14=0.0125$ (with $f''=-1/x^2$ between $-\tfrac14$ and $-\tfrac1{4.41}$). ✓
Central $D_0=\frac{0.741937-0.641854}{0.2}=0.500417$; error $f'-D_0=-0.000417$. Prediction: $-\tfrac{h^2}6f'''=-\tfrac{0.01}{6}\cdot\tfrac{2}{8}=-0.000417$. ✓ (Thirty times more accurate for the same work.)
Three-point one-sided $\frac{-3(0.693147)+4(0.741937)-0.788457}{0.2}=0.49925$; error $0.00075$, close to $\tfrac{h^2}3f'''(2)=\tfrac{0.01}{3}\cdot\tfrac14=0.00083$.
Second derivative $D^2=\frac{0.741937-2(0.693147)+0.641854}{0.01}=-0.25031$; true $f''(2)=-0.25$, error $0.00031$; prediction $-\tfrac{h^2}{12}f^{(4)}(2)=-\tfrac{0.01}{12}\cdot\left(-\tfrac{6}{16}\right)=0.00031$. ✓

Numerical Integration: Newton–Cotes Rules

📘 Definition 9.14 — Quadrature rule; degree of precision
A quadrature rule on $[a,b]$ is $Q(f)=\sum_{i=0}^{n}w_if(x_i)$, an approximation to $I(f)=\int_a^bf(x)\,dx$, with nodes $x_i$ and weights $w_i$. Its degree of precision is the largest $d$ such that $Q(p)=I(p)$ for every polynomial $p$ of degree $\le d$; equivalently, $Q(x^k)=I(x^k)$ for $k=0,1,\dots,d$ but not for $k=d+1$. A rule is interpolatory if $w_i=\int_a^b\ell_i(x)\,dx$, i.e. $Q(f)=\int_a^bp_n$ where $p_n$ interpolates $f$ at the nodes.
📐 Theorem 9.22 — Interpolatory rules and the bonus degree of symmetric rules
(a) A rule with $n+1$ distinct nodes has degree of precision $\ge n$ if and only if it is interpolatory; its weights are then uniquely determined by the nodes, and they satisfy $\sum w_i=b-a$. (b) If the nodes are symmetric about $m=\frac{a+b}2$, the weights are symmetric ($w_i=w_{n-i}$), and $n$ is even, then the degree of precision is at least $n+1$. (c) No rule with $n+1$ nodes has degree of precision $2n+2$ or more.

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$. ∎

📘 Definition 9.15 — Newton–Cotes rules

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)$.

📐 Theorem 9.23 — Error terms of the basic rules

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. ∎

📐 Theorem 9.24 — Composite rules and their errors

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. ∎

✏️ Example 5 — $\pi$ from $\int_0^1\frac{dx}{1+x^2}$
Approximate $\int_0^1\frac{dx}{1+x^2}=\frac\pi4$ by the composite trapezoidal and Simpson rules with $n=4$, and compare the errors with Theorem 9.24.
Table $h=0.25$: $f_0=1$, $f_1=\frac{16}{17}=0.941176$, $f_2=0.8$, $f_3=0.64$, $f_4=0.5$.
Trapezoidal $T_4=0.25\,[0.5+0.941176+0.8+0.64+0.25]=0.782794$; $4T_4=3.131176$. Error $I-T_4=0.002604$.
Simpson $S_4=\frac{0.25}{3}\,[1+4(0.941176+0.64)+2(0.8)+0.5]=0.785392$; $4S_4=3.141569$. Error $I-S_4=6.0\times10^{-6}$ — about $430$ times smaller with the same five function values.
Theory The trapezoidal error is $-\frac{h^2}{12}f''(\xi)$ with $b-a=1$; here the average of $f''$ is $\frac{f'(1)-f'(0)}{1}=-\frac12$, and $-\frac{0.0625}{12}\left(-\frac12\right)=0.002604$, matching almost exactly. Also $T_2=0.775$ and $\frac{4T_4-T_2}{3}=0.785392=S_4$, as Theorem 9.24 says.
✏️ Example 6 — How many panels for six decimals?
How many subintervals guarantee $\left|\int_0^1e^{-x^2}dx-Q\right|\le10^{-6}$ when $Q$ is (a) the composite trapezoidal rule, (b) the composite Simpson rule?
Derivative bounds $f''=(4x^2-2)e^{-x^2}$ and $f^{(4)}=(16x^4-48x^2+12)e^{-x^2}$. On $[0,1]$, $|f''|\le2$ and $|f^{(4)}|\le12$, both maxima at $x=0$.
(a) Trapezoidal $\frac{h^2}{12}\cdot2\le10^{-6}$ gives $h\le\sqrt{6\times10^{-6}}=0.002449$, i.e. $n=\frac1h\ge408.2$: $n=409$.
(b) Simpson $\frac{h^4}{180}\cdot12\le10^{-6}$ gives $h^4\le1.5\times10^{-5}$, $h\le0.06223$, $n\ge16.07$; $n$ must be even: $n=18$.
Check With $I=0.7468241$, the actual errors are $3.7\times10^{-7}$ for $T_{409}$ and $7.8\times10^{-8}$ for $S_{18}$: the a priori bounds are safe but pessimistic. Simpson needs $19$ function values, the trapezoidal rule $410$.
✏️ Example 7 — Designing rules by undetermined coefficients
(a) Find $w_0,w_1,w_2$ so that $\int_0^2f\approx w_0f(0)+w_1f(1)+w_2f(2)$ is exact for all quadratics, and find the degree of precision. (b) For which $c\gt0$ does $\int_{-1}^1f\approx f(-c)+f(c)$ have the highest degree of precision, and what is it? (c) Prove or disprove: for convex $f$ the composite trapezoidal rule never underestimates $\int_a^bf$.
(a) Equations $f=1$: $w_0+w_1+w_2=2$; $f=x$: $w_1+2w_2=2$; $f=x^2$: $w_1+4w_2=\frac83$. So $w_2=\frac13$, $w_1=\frac43$, $w_0=\frac13$: Simpson's rule with $h=1$.
(a) Degree $f=x^3$: rule $\frac43+\frac83=4=\int_0^2x^3dx$ ✓; $f=x^4$: rule $\frac43+\frac{16}3=\frac{20}3\ne\frac{32}5$. Degree $3$ — one more than the three nodes promise (Theorem 9.22(b)).
(b) The rule is symmetric, so it is exact for $1$ (giving $2$ ✓), $x$ and $x^3$ for every $c$. For $x^2$ it needs $2c^2=\frac23$, i.e. $c=\frac1{\sqrt3}$; then for $x^4$: $2c^4=\frac29\ne\frac25$. Highest degree $3$, at $c=\frac1{\sqrt3}$ — the two-point Gauss rule, which reaches the limit $2n+1$ of Theorem 9.22(c) with $n+1=2$ nodes.
(c) True If $f\in C^2$ with $f''\ge0$, then $I-T_n=-\frac{(b-a)h^2}{12}f''(\xi)\le0$. Without smoothness: a convex function lies below each of its chords, so on every panel the trapezoid's top edge is above the graph. Either way $T_n\ge I$. (Similarly $M_n\le I$: the midpoint rectangle has the same area as the tangent trapezoid at the midpoint, which lies below the graph.)
🧭 Quadrature in GATE time
  1. 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.
  2. 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$.
  3. Degree of precision of a strange rule: test $1,x,x^2,\dots$ in turn (shift to a symmetric interval to kill odd powers).
  4. 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).
  5. Signs: for $f''\gt0$, $T_n\gt I\gt M_n$; Simpson combines them as $\frac{2M+T}{3}$ to cancel the leading errors.
⚠️ Counterexamples and pitfalls
  1. 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).
  2. 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$.
  3. 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.
  4. 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$.
  5. 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$).
  6. Smaller $h$ is not always better in differentiation: below $h^*=(3\varepsilon/M)^{1/3}$ rounding errors dominate (Theorem 9.21).
  7. 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$.
  8. "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$.
  9. The trapezoidal rule does not always overestimate — only for convex $f$. For $\sin x$ on $[0,\pi]$ (concave) it underestimates.
  10. 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.
  11. The midpoint rule is not "less accurate because it uses one point": its error constant $\frac1{24}$ is half the trapezoidal $\frac1{12}$.
📚 Go deeper — full proofs in the CSIR NET course
  • 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

Interactive 1 — The Interpolation Error Has the Shape of $\omega_{n+1}$

Left: $f$ (dark) and its interpolant $p_n$ (red) at $n+1$ nodes on $[-1,1]$. Right: the error $f-p_n$ (blue) and the nodal polynomial $\omega_{n+1}$ rescaled to the same height (amber, dashed) — Theorem 9.16 says they differ only by the factor $f^{(n+1)}(\xi_x)/(n+1)!$. Press Play to raise $n$; switch between equally spaced and Chebyshev nodes, and try Runge's function.

n (degree)—
max |f − pₙ|—
max |ωₙ₊₁|—
bound M/(n+1)! · max|ω|—
Interactive 2 — Quadrature Lab: Shapes, Errors and the Observed Order

Left: the integrand with the shapes the chosen composite rule actually integrates — trapezoids, midpoint rectangles, parabolic arcs (Simpson 1/3) or cubic arcs (Simpson 3/8). Right: $\log_{10}|\text{error}|$ against $\log_{10}n$ for this rule; the slope is $-$(order). Press Play to cycle $n$; compare $\sqrt x$ (not smooth at $0$) with the smooth integrands, and $x^3$ under Simpson.

n (panels)—
approximation—
error I − Q—
observed order log₂(Eₙ/E₂ₙ)—

Exercises

I
Interpolation.
  • 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 $\ell_0=\frac{(x-1)(x-2)}2$, $\ell_1=-x(x-2)$, $\ell_2=\frac{x(x-1)}2$: $p=\ell_0+3\ell_1+7\ell_2=x^2+x+1$.
2 First: $1,\ 4,\ 7$; second: $\frac{4-1}{3}=1,\ \frac{7-4}{3}=1$; third: $0$. $p=2+(x-1)+(x-1)(x-2)=x^2-2x+3$, of degree $2$ (the third divided difference vanishes); $p(3)=6$.
3 $x^k$ ($k\le n$) is a polynomial of degree $\le n$, so it equals its own interpolant (Theorem 9.15): $x^k=\sum_ix_i^k\ell_i(x)$. $k=1$ gives the first identity.
4 $|f''|=|\sin x|\le1$: error $\le\frac18h^2=0.00125$.
5 $\frac18e\,h^2\le10^{-6}$: $h\le\sqrt{8\times10^{-6}/e}\approx0.00172$.
6 $|f'''|\le1$: error $\le\frac{h^3}{9\sqrt3}=\frac{0.001}{15.59}\approx6.4\times10^{-5}$.
7 Induction. $f[x_0,x_1]=\frac{1/x_1-1/x_0}{x_1-x_0}=-\frac1{x_0x_1}$. If true for $n-1$: $f[x_0,\dots,x_n]=\frac{1}{x_n-x_0}\left(\frac{(-1)^{n-1}}{x_1\cdots x_n}-\frac{(-1)^{n-1}}{x_0\cdots x_{n-1}}\right)=\frac{(-1)^{n-1}}{x_1\cdots x_{n-1}}\cdot\frac{x_0-x_n}{x_0x_n(x_n-x_0)}$, which is $\frac{(-1)^n}{x_0\cdots x_n}$.
8 $p_2(x)=x^2$ (through $(−1,1),(0,0),(1,1)$). At $\frac12$: $|x|-x^2=\frac12-\frac14=\frac14$. $|x|$ is not $C^3$ (not even differentiable at $0$).
9 False: Runge's $f(x)=\frac1{1+25x^2}$ is infinitely differentiable on $\mathbb{R}$, but $\max_{[-1,1]}|f-p_n|\to\infty$. The derivatives $f^{(n+1)}$ grow like $(n+1)!\,5^{n+1}$, which defeats the factor $\frac{1}{(n+1)!}$ in Theorem 9.16.
II
Finite differences.
  • 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 $f=0,0,6,24,60$; $\Delta$: $0,6,18,36$; $\Delta^2$: $6,12,18$; $\Delta^3$: $6,6$; $\Delta^4$: $0$. The third differences equal $1\cdot3!\cdot1^3=6$ (Theorem 9.19(a)).
2 $\Delta\nabla=(E-1)(1-E^{-1})=E-2+E^{-1}$ (the operators commute); $\Delta-\nabla=(E-1)-(1-E^{-1})=E-2+E^{-1}$; $\delta^2=(E^{1/2}-E^{-1/2})^2=E-2+E^{-1}$.
3 $\Delta e^x=e^{x+h}-e^x=(e^h-1)e^x$; $\Delta$ acts on $e^x$ as multiplication by $(e^h-1)$, so $\Delta^ke^x=(e^h-1)^ke^x$.
4 $\Delta$: $1,7,19$; $\Delta^2$: $6,12$; $\Delta^3$: $6$. $s=1.5$: $1+1.5(1)+\frac{1.5(0.5)}{2}(6)+\frac{1.5(0.5)(-0.5)}{6}(6)=1+1.5+2.25-0.375=4.375$. (The data are $x^3+1$: $1.5^3+1=4.375$ ✓.)
5 $s=\frac{2.5-3}{1}=-0.5$, $\nabla f_3=19$, $\nabla^2f_3=12$, $\nabla^3f_3=6$: $28-9.5+\frac{(-0.5)(0.5)}{2}(12)+\frac{(-0.5)(0.5)(1.5)}{6}(6)=28-9.5-1.5-0.375=16.625=2.5^3+1$ ✓.
6 $\Delta^4f_0=f_0-4f_1+6f_2-4f_3+f_4=0$: $1-12+6f_2-124+69=0$, so $f_2=11$. (Indeed the cubic is $x^3+x+1$.)
7 $\Delta(x^n)=(x+h)^n-x^n=nhx^{n-1}+(\text{lower degree})$: $\Delta$ lowers the degree by one and multiplies the leading coefficient by $nh$. Applying it $n$ times gives the constant $n!\,h^n$, and once more gives $0$.
III
Numerical differentiation.
  • 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 $D_+=\frac{0.564642-0.479426}{0.1}=0.85216$, error $0.0254$; $D_0=\frac{0.564642-0.389418}{0.2}=0.87612$, error $0.00146$ (prediction $\frac{h^2}6\cos0.5=0.00146$ ✓).
2 In Newton's forward form with $x=x_0+sh$: $p_2=f_0+s\Delta f_0+\frac{s(s-1)}2\Delta^2f_0$, so $p_2'(x_0)=\frac1h\left(\Delta f_0-\frac12\Delta^2f_0\right)=\frac{1}{h}\left(f_1-f_0-\frac{f_2-2f_1+f_0}{2}\right)=\frac{-3f_0+4f_1-f_2}{2h}$.
3 $D^2=\frac{0.564642-2(0.479426)+0.389418}{0.01}=-0.4792$; true $-\sin0.5=-0.479426$, error about $2\times10^{-4}$. With exact sines the formula gives $-0.479026$: truncation error $\frac{h^2}{12}\sin0.5\approx4.0\times10^{-4}$ (Theorem 9.20(3)). Rounding the data to six decimals ($\varepsilon=5\times10^{-7}$) can shift $D^2$ by up to $\frac{4\varepsilon}{h^2}=2\times10^{-4}$, and here it happens to shift it back towards the true value — six-decimal data are barely enough for a second derivative with $h=0.1$.
4 $h^*=(3\times10^{-10})^{1/3}\approx6.7\times10^{-4}$; bound $\frac{\varepsilon}{h^*}+\frac{(h^*)^2}{6}\approx1.5\times10^{-7}+7.5\times10^{-8}\approx2.2\times10^{-7}$.
5 $D_0(h)=f'+c_2h^2+c_4h^4+\cdots$ (only even powers, by symmetry), so $4D_0(h/2)-D_0(h)=3f'+O(h^4)$. Data: $D_0(0.1)=0.500417$, $D_0(0.05)=\frac{0.717840-0.667829}{0.1}=0.50011$; extrapolated $\frac{4(0.50011)-0.500417}{3}=0.50001$ (with full-precision logarithms: $0.4999998$, error $1.6\times10^{-7}$).
6 False. For $f=x^3$ at $0$: $D_0(h)=\frac{h^3-(-h)^3}{2h}=h^2\ne0=f'(0)$. ($D_0$ is exact for quadratics only.)
IV
Numerical integration.
  • 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$.
1 $h=\frac12$: $S=\frac16\left(0+4\cdot\frac1{16}+1\right)=\frac5{24}=0.208333$; $I=0.2$; $I-S=-\frac1{120}$. Formula: $-\frac{(1/2)^5}{90}\cdot24=-\frac{24}{2880}=-\frac1{120}$ ✓ (exact because $f^{(4)}=24$ is constant).
2 $h=1$: $\frac38(0+3+48+81)=49.5$; $I=\frac{243}5=48.6$; $I-Q=-0.9=-\frac{3\cdot1^5}{80}\cdot24$ ✓.
3 $T_4=\frac\pi4\left[\sin\frac\pi4+\sin\frac\pi2+\sin\frac{3\pi}4\right]=\frac\pi4(1+\sqrt2)\approx1.896119$ (error $+0.1039$); $S_4=\frac{\pi}{12}\left[4\left(\tfrac{\sqrt2}2\right)\cdot2+2\cdot1\right]=\frac{\pi}{12}(2+4\sqrt2)\approx2.004560$ (error $-0.00456$). $\sin$ is concave ($f''\lt0$), so $I-T=-\frac{(b-a)h^2}{12}f''\gt0$; $f^{(4)}=\sin\ge0$, so $I-S\lt0$.
4 $f^{(4)}=-6/x^4$, $|f^{(4)}|\le6$: $\frac{h^4}{180}\cdot6\le10^{-8}$, $h\le(3\times10^{-7})^{1/4}\approx0.0234$, $n\ge42.7$; take $n=44$.
5 $f=1$: $1$ ✓; $x$: $\frac14\cdot2=\frac12$ ✓; $x^2$: $\frac14\cdot\frac43=\frac13$ ✓; $x^3$: $\frac14\cdot\frac89=\frac29\ne\frac14$. Degree $2$ (a Radau rule: two nodes, one of them fixed at an end).
6 $1$: $a+b=1$; $x$: $b+c=\frac12$; $x^2$: $b=\frac13$. So $a=\frac23$, $b=\frac13$, $c=\frac16$. $x^3$: $b=\frac13\ne\frac14$: degree $2$.
7 By Theorem 9.24, $I-T_n=-\frac{(b-a)h^2}{12}f''(\xi)\le0$ and $I-M_n=\frac{(b-a)h^2}{24}f''(\eta)\ge0$. For $e^{-x}$: $M_2=\frac12\left(e^{-1/4}+e^{-3/4}\right)=0.62558$, $T_2=\frac12\left(\frac12+e^{-1/2}+\frac{e^{-1}}2\right)=0.64523$; indeed $I=1-e^{-1}=0.63212$ lies between.
8 $h=2$, $n=6$. Simpson: $\frac23[0+4(1.2+2.6+1.5)+2(2.1+2.4)+0]=\frac23(21.2+9)=20.13\ \text{m}^2$. Trapezoidal: $2(1.2+2.1+2.6+2.4+1.5)=19.6\ \text{m}^2$.
9 On $[a,b]$ with $m$ the midpoint and $H=b-a$: $T_1=\frac H2(f_a+f_b)$, $T_2=\frac H4(f_a+2f_m+f_b)$, so $\frac{4T_2-T_1}3=\frac H3\left(f_a+2f_m+f_b-\frac{f_a+f_b}2\right)=\frac H6(f_a+4f_m+f_b)=S_2$.
10 True. The three-point Gauss rule (nodes $0,\pm\sqrt{3/5}$ on $[-1,1]$, weights $\frac89,\frac59,\frac59$) has degree $5$; degree $6$ is impossible by Theorem 9.22(c) ($2n+2=6$ with $n=2$).
🎯 GATE corner GATE MA · MCQGATE MA · MSQGATE MA · NAT

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$.

Differences $\Delta$: $-1,1,9$; $\Delta^2$: $2,8$; $\Delta^3$: $6$. For a cubic the third difference is constant, so extend the table: $\Delta^2=8+6=14$, $\Delta=9+14=23$, $p(4)=10+23=33$.
Check Newton's form gives $p(x)=1-x+x(x-1)+x(x-1)(x-2)=x^3-2x^2+1$, and $64-32+1=33$.
Answer (C).

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$.

Even powers $1$: $\frac23(2-1+2)=2$ ✓. $x^2$: $\frac23\left(\frac24+\frac24\right)=\frac23=\int_{-1}^1x^2$ ✓. $x^4$: $\frac23\left(\frac2{16}+\frac2{16}\right)=\frac16\ne\frac25$ ✗.
Odd powers The rule is symmetric, so $x$ and $x^3$ give $0=\int_{-1}^1$ ✓.
Answer (C) — an open Newton–Cotes rule with three nodes and degree $3$ (Theorem 9.22(b)).

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$.

(A) True Theorem 9.20(2): error $-\frac{h^2}6f'''(\xi)$.
(B) False For $x^2$ at $x$: $\frac{(x+h)^2-x^2}{h}=2x+h\ne2x$.
(C) True $I-T_n=-\frac{h^2}{12}\sum_i hf''(\xi_i)$, and $\sum_ihf''(\xi_i)\to\int_a^bf''=f'(b)-f'(a)\ne0$; so $I-T_n\approx-\frac{h^2}{12}\big(f'(b)-f'(a)\big)$, and halving $h$ divides it by about $4$.
(D) False $\sqrt x\notin C^4[0,1]$; the observed factor is about $2^{1.5}\approx2.83$ (the error behaves like $h^{1.5}$, dominated by the first panel).
Answer (A) and (C).

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$.

(A) True $\Delta^3$ of a cubic with leading coefficient $a=2$ is $a\cdot3!\cdot h^3=12h^3$ (Theorem 9.19(a)); the term $x$ contributes nothing to $\Delta^3$.
(B) True The second divided difference of a quadratic is its leading coefficient (Theorem 9.18(3)).
(C) False Runge's phenomenon: the maximum error tends to infinity near $\pm1$.
(D) True Both equal $E-2+E^{-1}$ (Exercise II.2).
Answer (A), (B) and (D).

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).

Rule $n=4$ panels, $h=10$: $\frac{10}{3}\big[0+4(12)+2(20)+4(24)+26\big]=\frac{10}3(210)$.
Compare The trapezoidal rule gives $10\,[0+12+20+24+13]=690$ m.
Answer $700$ m (accept $699$ to $701$).

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 ______.

Bound $h=\frac2n$, $\max|f''|=e^2$: $\frac{2}{12}\cdot\frac4{n^2}\cdot e^2\le10^{-4}$, i.e. $n^2\ge\frac{2e^2}{3}\times10^4=49260.4$.
Solve $n\ge221.95$, so $n=222$ (at $n=221$ the bound is $1.009\times10^{-4}$).
Answer $222$ (exact integer).
🧑‍🏫 For the teacher

Suggested plan — 3 lectures × 60 min.

  1. 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}$.
  2. 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).
  3. 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–Teaching NexusResearch-tutored · optional, about 60 minutes

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.

  1. 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}$).
  2. Estimate the observed order $p\approx\log_2\frac{E_n}{E_{2n}}$ for each case and make a table.
  3. Conjecture a formula for $p$ in terms of $\alpha$ for each rule. (Hint: compare $\min(2,\ \alpha+1)$ and $\min(4,\ \alpha+1)$.)
  4. 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.

Instructor note: going from $n=64$ to $n=128$ the observed orders are about $1.49$ (trapezoid) and $1.50$ (Simpson) for $\alpha=0.5$; $1.99$ and $2.50$ for $\alpha=1.5$; $2.00$ and $3.47$ for $\alpha=2.5$ (tending to $3.5$); $2.00$ and $4.00$ for $\alpha=4.5$. This matches $p=\min(2,\alpha+1)$ for the trapezoidal rule and $p=\min(4,\alpha+1)$ for Simpson's rule (for non-integer $\alpha$).

🧪 Self-check quiz

0/5 correct

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