Chapter 5 · Numerical Analysis

5.3 Finite Differences and Interpolation

Finite differences and the shift operator $E$, the interpolating polynomial in Lagrange and Newton form with its error term, divided differences, Hermite interpolation, cubic splines — and Runge's phenomenon, which shows why more equally spaced nodes can make an interpolant worse.

Before computers, every scientist owned books of tables — logarithms, sines, Bessel functions, star positions — and the first thing taught about a table was how to read between its lines. Henry Briggs built his logarithm tables in the 1620s by adding up differences; Newton's interpolation formulas of 1676 were written to do exactly this job; and the great numerical tables of the twentieth century were checked by looking at their high-order differences, where a single misprinted digit stands out like a fingerprint. The tables are gone, but the problem is everywhere: a sensor is calibrated at a handful of temperatures and must be read at all the others; a weather model knows the pressure on a grid and needs it at an aircraft's position; a car designer fixes a few points of a body panel and wants a smooth curve through them (the word spline comes from the flexible wooden strips that shipwrights bent through fixed points); a font stores a letter as a few control points and draws the outline from them.

The mathematical problem is: given values $f(x_0),\dots,f(x_n)$ at nodes $x_0,\dots,x_n$, construct a simple function that takes these values, and say how far it is from $f$ elsewhere. This section develops the answer in the order it is examined. Finite differences and the operator calculus ($E$, $\Delta=E-1$, $\nabla$, $\delta$) handle equally spaced data; the interpolating polynomial exists and is unique, can be written in Lagrange or Newton form, and has an error term that looks like a Taylor remainder; divided differences make Newton's form work for any nodes and also handle derivative data (Hermite interpolation); and cubic splines are the remedy for Runge's phenomenon, the surprising fact that polynomial interpolation at more and more equally spaced nodes can diverge. Interpolation is also the engine of the next two sections: numerical differentiation and integration (§5.4) and multistep methods for ODEs (§5.5) are obtained by differentiating or integrating an interpolating polynomial. CSIR NET asks for $\Delta^n$ of a polynomial, the value of an interpolating polynomial at a point, divided differences, the degree and error term of a Hermite interpolant, the conditions that define a natural spline, and — in Part C — the counterexamples collected in the ⚠️ box below.

Finite Differences and the Shift Operator

Throughout this subsection the nodes are equally spaced: $x_i=x_0+ih$ for integers $i$, with a fixed step $h\gt0$, and $f_i=f(x_i)$. It is convenient to let the operators below act on functions defined on all of $\mathbb{R}$ (or on a grid), so that $f_{i+1/2}=f(x_i+\tfrac h2)$ makes sense.

📘 Definition 5.15 — Forward, backward and central differences

The first forward, backward and central differences of $f$ at $x_i$ are

$$\Delta f_i=f_{i+1}-f_i,\qquad \nabla f_i=f_i-f_{i-1},\qquad \delta f_i=f_{i+1/2}-f_{i-1/2}.$$

Higher differences are defined recursively: $\Delta^{k+1}f_i=\Delta^kf_{i+1}-\Delta^kf_i$, and similarly for $\nabla$ and $\delta$ (with $\Delta^0f_i=f_i$). The difference table lists $f_0,f_1,\dots,f_N$ in a column and, in the $k$-th column to the right, the differences $\Delta^kf_0,\dots,\Delta^kf_{N-k}$, each written between the two entries it is computed from.

One table serves all three notations: $\nabla^kf_i=\Delta^kf_{i-k}$ and $\delta^{2m}f_i=\Delta^{2m}f_{i-m}$, so the forward differences of $f_0$ run down the diagonal from the top, the backward differences of $f_N$ run up the diagonal from the bottom, and the even central differences of $f_i$ lie on the horizontal line through $f_i$.

📘 Definition 5.16 — Shift, averaging and differential operators

For a step $h$ the shift operator $E$, its real powers, the averaging operator $\mu$ and the differentiation operator $D$ act on functions by

$$Ef(x)=f(x+h),\qquad E^{s}f(x)=f(x+sh)\ (s\in\mathbb{R}),$$ $$\mu f(x)=\tfrac12\big(f(x+\tfrac h2)+f(x-\tfrac h2)\big),\qquad Df(x)=f'(x).$$

All of them are linear, and they commute with one another (for $D$: $(Ef)'(x)=f'(x+h)=(Ef')(x)$). Two operators are equal if they agree on every function under consideration; sums, products (compositions) and constant multiples are formed as usual, and $1$ denotes the identity.

The point of the operator notation is that $\Delta$, $\nabla$, $\delta$ and $\mu$ are all built from $E$, so identities between them become identities between polynomials in $E^{1/2}$ — and polynomial algebra with commuting symbols is legitimate.

📐 Theorem 5.21 — The operator calculus of finite differences
  1. $\Delta=E-1$, $\ \nabla=1-E^{-1}$, $\ \delta=E^{1/2}-E^{-1/2}$, $\ \mu=\tfrac12\big(E^{1/2}+E^{-1/2}\big)$.
  2. $\nabla=\Delta E^{-1}$, $\ \delta=\Delta E^{-1/2}=\nabla E^{1/2}$, $\ \Delta-\nabla=\Delta\nabla=\delta^2$, $\ \mu^2=1+\tfrac14\delta^2$, $\ \mu\delta=\tfrac12(\Delta+\nabla)$.
  3. For every $k\in\mathbb{N}$, $$\Delta^kf_i=\sum_{j=0}^{k}(-1)^{k-j}\binom kj f_{i+j},\qquad f_{i+k}=\sum_{j=0}^{k}\binom kj\Delta^jf_i.$$
  4. On the polynomials of degree $\le n$, $E=e^{hD}=\sum_{k=0}^{n}\dfrac{h^kD^k}{k!}$ and $hD=\log(1+\Delta)$ $=\Delta-\tfrac12\Delta^2+\tfrac13\Delta^3-\dots$ $\pm\tfrac1n\Delta^n$; both sums are finite there.

Proof. (1) $\Delta f(x)=f(x+h)-f(x)=(E-1)f(x)$; $\nabla f(x)=f(x)-f(x-h)=(1-E^{-1})f(x)$; the formulas for $\delta$ and $\mu$ are their definitions with $E^{\pm1/2}f(x)=f(x\pm\tfrac h2)$.

(2) Using (1) and $E^aE^b=E^{a+b}$: $\Delta E^{-1}=1-E^{-1}=\nabla$; $\Delta E^{-1/2}=E^{1/2}-E^{-1/2}=\delta$; $\Delta-\nabla=E-2+E^{-1}$, $\ \Delta\nabla=(E-1)(1-E^{-1})=E-2+E^{-1}$ and $\delta^2=(E^{1/2}-E^{-1/2})^2=E-2+E^{-1}$. Next $\mu^2=\tfrac14(E+2+E^{-1})$ $=\tfrac14(E-2+E^{-1})+1$ $=1+\tfrac14\delta^2$, and $\mu\delta=\tfrac12(E^{1/2}+E^{-1/2})(E^{1/2}-E^{-1/2})$ $=\tfrac12(E-E^{-1})$ $=\tfrac12\big((E-1)+(1-E^{-1})\big)=\tfrac12(\Delta+\nabla)$.

(3) Since $E$ commutes with the identity, the binomial theorem applies to $(E-1)^k$ and to $(1+\Delta)^k$: $\Delta^k=\sum_j\binom kj E^j(-1)^{k-j}$ and $E^k=(1+\Delta)^k=\sum_j\binom kj\Delta^j$. Apply both to $f$ at $x_i$.

(4) For a polynomial $p$ of degree $\le n$, Taylor's formula is exact: $p(x+h)=\sum_{k=0}^n\tfrac{h^k}{k!}p^{(k)}(x)$, i.e. $E=\sum_{k\le n}\tfrac{(hD)^k}{k!}$ on this space; since $D^{n+1}=0$ there, this is $e^{hD}$ with a terminating series. Hence $\Delta=e^{hD}-1$, which has no constant term, so $\Delta^{n+1}=0$ on the space as well. In the ring of formal power series $\mathbb{Q}[[t]]$ one has $\log\big(1+(e^t-1)\big)=t$; substituting the commuting nilpotent operator $hD$ for $t$ (every series becomes a finite sum because $(hD)^{n+1}=0$) gives $\log(1+\Delta)=hD$. ∎

Formula (4) is the bridge to numerical differentiation: truncating $hD=\Delta-\tfrac12\Delta^2+\dots$ gives the forward-difference formulas for $f'$ that §5.4 studies with their error terms. The next theorem explains why difference tables of polynomials end in a column of constants and then zeros.

📐 Theorem 5.22 — Differences of polynomials

Let $p(x)=a\,x^n+(\text{terms of lower degree})$ with $a\ne0$, $n\ge1$, and let the step be $h$.

  1. $\Delta p$ is a polynomial of degree exactly $n-1$ with leading coefficient $n\,a\,h$.
  2. $\Delta^np\equiv n!\,a\,h^n$ is constant, and $\Delta^kp\equiv0$ for every $k\gt n$.
  3. For the factorial polynomials $x^{(k)}=x(x-h)(x-2h)$ $\cdots(x-(k-1)h)$ (with $x^{(0)}=1$), $\Delta x^{(k)}=k\,h\,x^{(k-1)}$.
  4. Conversely, if values $f_0,\dots,f_N$ at equally spaced nodes satisfy $\Delta^{n+1}f_i=0$ for $i=0,\dots,N-n-1$, then some polynomial $q$ of degree $\le n$ has $q(x_i)=f_i$ for all $i=0,\dots,N$.
  5. If $f\in C^k[x_i,x_{i+k}]$, then $\Delta^kf_i=h^k f^{(k)}(\xi)$ for some $\xi\in[x_i,x_{i+k}]$.

Proof. (1) By the binomial theorem, $(x+h)^m-x^m=m\,h\,x^{m-1}+(\text{degree}\le m-2)$. Applying this to every term of $p$, the term $a x^n$ contributes $n a h x^{n-1}$ plus lower terms and every other term contributes only degree $\le n-2$; as $nah\ne0$, $\deg\Delta p=n-1$.

(2) Apply (1) $n$ times: $\Delta^np$ has degree $0$ and leading coefficient $n(n-1)\cdots1\cdot a\,h^n$. The difference of a constant is $0$.

(3) $(x+h)^{(k)}=(x+h)\,x(x-h)\cdots(x-(k-2)h)$ $=(x+h)\,x^{(k-1)}$ and $x^{(k)}=x^{(k-1)}\,(x-(k-1)h)$; subtracting, $\Delta x^{(k)}=x^{(k-1)}\big[(x+h)-(x-(k-1)h)\big]$ $=k\,h\,x^{(k-1)}$.

(4) Since $\Delta^{n+1}f_i=0$ for all admissible $i$, also $\Delta^{k}f_i=0$ for every $k\ge n+1$ (higher differences are differences of zeros). For $0\le j\le N$, Theorem 5.21(3) gives $f_j=\sum_{k=0}^{j}\binom jk\Delta^kf_0=\sum_{k=0}^{\min(j,n)}\binom jk\Delta^kf_0$. Define $$Q(s)=\sum_{k=0}^{n}\binom sk\Delta^kf_0,\qquad \binom sk=\frac{s(s-1)\cdots(s-k+1)}{k!},$$ a polynomial in $s$ of degree $\le n$. For an integer $0\le j\le N$, $\binom jk=0$ when $k\gt j$, so $Q(j)=f_j$. Then $q(x)=Q\big((x-x_0)/h\big)$ works.

(5) For $g\in C^1$, $\Delta g(x)=\int_0^h g'(x+t)\,dt$. Applying this $k$ times (each $\Delta$ commutes with the integrals), $$\Delta^kf(x)=\int_0^h\!\!\cdots\int_0^h f^{(k)}(x+t_1+\dots+t_k)\,dt_1\cdots dt_k .$$ The integrand is continuous on the cube $[0,h]^k$, whose volume is $h^k$, and takes values between $\min f^{(k)}$ and $\max f^{(k)}$ on $[x,x+kh]$; by the intermediate value theorem the average value $\Delta^kf(x)/h^k$ equals $f^{(k)}(\xi)$ for some $\xi\in[x,x+kh]$. Put $x=x_i$. ∎

Part (3) is why factorial polynomials are to $\Delta$ what powers are to $D$: $\Delta x^{(k)}=khx^{(k-1)}$ mirrors $Dx^k=kx^{k-1}$. It turns sums into "anti-differences" (Exercise I.5). Part (5) says that $\Delta^kf_i/h^k$ approximates $f^{(k)}$ — and, read backwards, that a smooth function's high differences are small, which is what makes an isolated error in a table visible.

✏️ Example 1 — Finding a wrong entry in a table
A table of a cubic polynomial at $x=0,1,\dots,7$ reads $3,\ 2,\ 3,\ 12,\ 53,\ 78,\ 147,\ 248$. Exactly one entry is wrong (two digits were swapped). Find it and correct it.
Table Differencing three times ($h=1$):
$x$$f$$\Delta f$$\Delta^2f$$\Delta^3f$
03$-1$26
121824
23932$-48$
31241$-16$60
4532544$-12$
5786932
6147101
7248
The fingerprint For a cubic the third differences must be constant (Theorem 5.22(2)). If $f_m$ carries an error $\varepsilon$, Theorem 5.21(3) shows that $\Delta^3f_i=f_{i+3}-3f_{i+2}+3f_{i+1}-f_i$ picks up $\varepsilon$, $-3\varepsilon$, $3\varepsilon$, $-\varepsilon$ for $i=m-3,m-2,m-1,m$: the binomial coefficients with alternating signs. The observed third differences $6,24,-48,60,-12$ are $c+\varepsilon,\ c-3\varepsilon,\ c+3\varepsilon,\ c-\varepsilon$ after the first, with $c=6$ and $\varepsilon=18$.
Locate The pattern starts at $\Delta^3f_1$ (i.e. $m-3=1$), so $m=4$: the entry at $x=4$ is too large by $18$. The correct value is $53-18=35$ (the digits $3$ and $5$ were swapped).
Check With $f_4=35$ the third differences are $6,6,6,6,6$; the data are $p(x)=x^3-2x^2+3$, whose $\Delta^3p=3!\cdot1\cdot1^3=6$. An error in $f_m$ spreads into a fan $\binom kj$-shaped in the $k$-th column — Interactive 2 lets you inject one and watch it.
✏️ Example 2 — Prove or disprove: operator identities
Decide which statements are true for every function $f$ (step $h$), and prove or disprove each. (a) $\Delta^n(e^{x})=(e^h-1)^n\,e^{x}$. (b) $\Delta(fg)=f\,\Delta g+g\,\Delta f$. (c) $\nabla\Delta=\Delta-\nabla$. (d) With $h=1$: if $\Delta^3f(k)=0$ for every integer $k$, then $f$ is a polynomial of degree at most $2$.
(a) True $\Delta e^x=e^{x+h}-e^x=(e^h-1)e^x$, so $e^x$ is an "eigenfunction" of $\Delta$ with eigenvalue $e^h-1$; induction gives the $n$-th power. (As $h\to0$, $\Delta^n e^x/h^n\to e^x$, in line with Theorem 5.22(5).)
(b) False The correct rule is $\Delta(fg)(x)=f(x+h)g(x+h)-f(x)g(x)$ $=f(x)\,\Delta g(x)+g(x+h)\,\Delta f(x)$ $=f\Delta g+g\Delta f+\Delta f\,\Delta g$. Counterexample: $f=g=x$, $h=1$: $\Delta x^2=2x+1$ but $x\cdot1+x\cdot1=2x$.
(c) True Both equal $E-2+E^{-1}=\delta^2$ (Theorem 5.21(2)); the operators commute, so $\nabla\Delta=\Delta\nabla$.
(d) False $f(x)=x^2+\sin(\pi x)$ agrees with $x^2$ at every integer, so $\Delta^3f(k)=\Delta^3(x^2)(k)=0$, but $f$ is not a polynomial. Differences see a function only through its values on the grid; Theorem 5.22(4) concludes only that the tabulated values are those of a polynomial.

The Interpolation Problem and Lagrange's Formula

From now on the nodes need not be equally spaced. Let $\mathcal{P}_n$ denote the real polynomials of degree at most $n$ (a vector space of dimension $n+1$).

📘 Definition 5.17 — Interpolating polynomial, nodal polynomial, Lagrange basis

Let $x_0,\dots,x_n$ be distinct real numbers (the nodes) and $y_0,\dots,y_n$ real numbers (often $y_i=f(x_i)$). A polynomial $p\in\mathcal{P}_n$ with $p(x_i)=y_i$ for $i=0,\dots,n$ is called an interpolating polynomial for the data. The nodal polynomial and the Lagrange basis polynomials are

$$\omega_{n+1}(x)=\prod_{j=0}^{n}(x-x_j),\qquad L_i(x)=\prod_{j\ne i}\frac{x-x_j}{x_i-x_j}=\frac{\omega_{n+1}(x)}{(x-x_i)\,\omega_{n+1}'(x_i)}.$$

Each $L_i$ has degree exactly $n$ and satisfies $L_i(x_k)=\delta_{ik}$ (Kronecker delta). The second expression for $L_i$ uses $\omega_{n+1}'(x_i)=\prod_{j\ne i}(x_i-x_j)$, obtained by differentiating the product and setting $x=x_i$.

📐 Theorem 5.23 — Existence and uniqueness; Lagrange's formula

For distinct nodes $x_0,\dots,x_n$ and any values $y_0,\dots,y_n$ there is exactly one $p\in\mathcal{P}_n$ with $p(x_i)=y_i$ $(0\le i\le n)$, namely

$$p(x)=\sum_{i=0}^{n}y_i\,L_i(x)\qquad\text{(Lagrange's interpolation formula).}$$

Equivalently, the Vandermonde matrix $V=(x_i^{\,j})_{0\le i,j\le n}$ is nonsingular; in fact $\det V=\prod_{0\le i\lt j\le n}(x_j-x_i)$.

Proof. Existence. The sum $\sum y_iL_i$ lies in $\mathcal{P}_n$, and at $x_k$ it equals $\sum_iy_i\delta_{ik}=y_k$. Uniqueness. If $p,q\in\mathcal{P}_n$ both interpolate, then $p-q\in\mathcal{P}_n$ vanishes at the $n+1$ distinct points $x_0,\dots,x_n$; a nonzero polynomial of degree $\le n$ has at most $n$ roots, so $p=q$.

Vandermonde. Writing $p(x)=\sum_j c_jx^j$, the conditions $p(x_i)=y_i$ read $Vc=y$. We have just shown that this system has a solution for every $y$ and that the solution is unique, so $V$ is invertible. For the formula, regard $\det V$ as a function of the last node $x_n=t$: expanding along the last row it is a polynomial in $t$ of degree $\le n$ with leading coefficient the Vandermonde determinant of $x_0,\dots,x_{n-1}$, and it vanishes at $t=x_0,\dots,x_{n-1}$ (two equal rows). Hence $\det V=\det V_{n-1}\prod_{i\lt n}(x_n-x_i)$, and induction on $n$ gives the product. ∎

Two consequences are used constantly. First, interpolation is exact on $\mathcal{P}_n$: if $f\in\mathcal{P}_n$, its interpolant is $f$ itself. Applied to $f=1$ and $f=x^k$ this gives the identities $\sum_iL_i(x)\equiv1$ and $\sum_ix_i^kL_i(x)\equiv x^k$ for $k\le n$. Second, the interpolant does not depend on the formula used to compute it: Lagrange's form, Newton's form, solving the Vandermonde system or any clever trick produce the same polynomial — a fact that turns many exam questions into one-liners (Exam corner E2). In computation, Lagrange's form is usually evaluated in the stable barycentric form $p(x)=\dfrac{\sum_i w_iy_i/(x-x_i)}{\sum_i w_i/(x-x_i)}$, $w_i=1/\omega_{n+1}'(x_i)$, obtained by dividing $\sum y_iL_i$ by $\sum L_i=1$; Interactive 1 uses it.

How good is $p$ away from the nodes? The answer looks like Taylor's remainder, with the nodal polynomial in place of $(x-x_0)^{n+1}$.

📐 Theorem 5.24 — The interpolation error (Cauchy's remainder)

Let $f\in C^{n+1}[a,b]$, let $x_0,\dots,x_n\in[a,b]$ be distinct, and let $p_n\in\mathcal{P}_n$ interpolate $f$ at these nodes. Then for every $x\in[a,b]$ there is $\xi=\xi_x$ in the smallest interval containing $x,x_0,\dots,x_n$ such that

$$f(x)-p_n(x)=\frac{f^{(n+1)}(\xi_x)}{(n+1)!}\,\omega_{n+1}(x).$$

Consequently $|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)}|$. For linear interpolation between $x_0$ and $x_1=x_0+h$ this gives $|f(x)-p_1(x)|\le\tfrac18M_2h^2$ on $[x_0,x_1]$.

Proof. If $x$ is a node, both sides are $0$ (any $\xi$ will do). Otherwise $\omega_{n+1}(x)\ne0$ and we may define, for $t\in[a,b]$, $$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}[a,b]$ 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 strictly between consecutive ones of these points, $g''$ has at least $n$, …, and $g^{(n+1)}$ has at least one zero $\xi$, all within the smallest interval containing $x,x_0,\dots,x_n$. Since $p_n^{(n+1)}=0$ and $\omega_{n+1}^{(n+1)}=(n+1)!$ ($\omega_{n+1}$ is monic of degree $n+1$), $$0=g^{(n+1)}(\xi)=f^{(n+1)}(\xi)-\big(f(x)-p_n(x)\big)\frac{(n+1)!}{\omega_{n+1}(x)},$$ which is the formula. For linear interpolation, $|\omega_2(x)|=(x-x_0)(x_1-x)\le h^2/4$ (maximum at the midpoint), so the error is at most $\tfrac{M_2}{2}\cdot\tfrac{h^2}{4}$. ∎

The formula separates the two sources of error: the function (through $f^{(n+1)}$, which we cannot control) and the nodes (through $\omega_{n+1}$, which we can). For equally spaced nodes the nodal polynomial is small in the middle of the table and large near its ends — and enormous outside it, which is why extrapolation is dangerous.

📐 Theorem 5.25 — Error bound for equally spaced nodes

Let $x_i=x_0+ih$ $(0\le i\le n,\ n\ge1)$. Then $|\omega_{n+1}(x)|\le\tfrac14\,n!\,h^{n+1}$ for every $x\in[x_0,x_n]$. Hence, if $f\in C^{n+1}[x_0,x_n]$,

$$\max_{[x_0,x_n]}|f-p_n|\le\frac{M_{n+1}\,h^{n+1}}{4(n+1)}.$$

Proof. Let $x\in[x_j,x_{j+1}]$ for some $0\le j\le n-1$. The two nearest factors satisfy $|(x-x_j)(x-x_{j+1})|\le h^2/4$. For $i\lt j$, $|x-x_i|\le(j+1-i)h$, and the product of these $j$ factors is at most $(j+1)!\,h^{j}$; for $i\gt j+1$, $|x-x_i|\le(i-j)h$, and the product of these $n-j-1$ factors is at most $(n-j)!\,h^{n-j-1}$. So $|\omega_{n+1}(x)|\le\tfrac14(j+1)!\,(n-j)!\,h^{n+1}$. Finally $(j+1)!\,(n-j)!=(n+1)!\big/\binom{n+1}{j+1}$ $\le(n+1)!/(n+1)=n!$, because $\binom{n+1}{j+1}\ge n+1$ for $1\le j+1\le n$. Combine with Theorem 5.24. ∎

For $f=e^x$ on $[0,1]$ this bound tends to $0$ very fast as $n\to\infty$ (as $h=1/n$). The bound is useless, however, when $M_{n+1}$ grows faster than $(n+1)/h^{n+1}$ — the subject of the last subsection.

✏️ Example 3 — $\log 3$ from $\log 1$, $\log 2$, $\log 4$
Using $\log1=0$, $\log2$ and $\log4=2\log2$ only, estimate $\log3$ by quadratic interpolation. Bound the error with Theorem 5.24, compare with the true error, and find the point $\xi$ of the theorem.
Basis at $x=3$ Nodes $1,2,4$: $L_0(3)=\dfrac{(3-2)(3-4)}{(1-2)(1-4)}=-\tfrac13$, $\ L_1(3)=\dfrac{(3-1)(3-4)}{(2-1)(2-4)}=1$, $\ L_2(3)=\dfrac{(3-1)(3-2)}{(4-1)(4-2)}=\tfrac13$. (Check: $-\tfrac13+1+\tfrac13=1=\sum L_i$.)
Estimate $p_2(3)=0\cdot(-\tfrac13)+\log2\cdot1+2\log2\cdot\tfrac13$ $=\tfrac53\log2=1.155\,245$. The true value is $\log3=1.098\,612$, so $f(3)-p_2(3)=-0.056\,633$.
Bound $f'''(x)=2/x^3$ lies between $2/64$ and $2$ on $[1,4]$, and $\omega_3(3)=(3-1)(3-2)(3-4)=-2$. By Theorem 5.24 the error is $\tfrac{2/\xi^3}{6}\cdot(-2)$, which is negative and of size between $\tfrac{2/64}{6}\cdot2=0.0104$ and $\tfrac26\cdot2=0.667$. The true error $-0.0566$ is negative and inside this range.
The point $\xi$ Solving $-\tfrac{2}{3\xi^3}=-0.056\,633$ gives $\xi^3=11.77$, $\xi=2.275\in(1,4)$. The theorem promises such a $\xi$ but gives no formula for it; $\xi$ depends on $x$.

Divided Differences and Newton's Formulas

Lagrange's formula has a practical defect: adding one more node changes every basis polynomial, so all the work is lost. Newton's form builds the interpolant one node at a time, $p_k=p_{k-1}+(\text{correction})$, and the corrections are computed from a table, just as for equally spaced data — with divided differences instead of differences.

📘 Definition 5.18 — Divided differences

For distinct points $x_0,x_1,\dots$ the divided differences of $f$ are defined recursively by $f[x_i]=f(x_i)$ and

$$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},\qquad k\ge1.$$

So $f[x_0,x_1]=\dfrac{f(x_1)-f(x_0)}{x_1-x_0}$ is the slope of a chord and $f[x_0,x_1,x_2]=\dfrac{f[x_1,x_2]-f[x_0,x_1]}{x_2-x_0}$. The divided-difference table is arranged like a difference table; the denominator of an entry is the distance between the two extreme nodes it involves.

📐 Theorem 5.26 — Newton's divided-difference interpolation formula

Let $x_0,\dots,x_n$ be distinct. The interpolating polynomial of $f$ at these nodes 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)(x-x_1)\cdots(x-x_{n-1}).$$

In particular $f[x_0,\dots,x_n]$ is the leading coefficient (the coefficient of $x^n$) of the polynomial in $\mathcal{P}_n$ interpolating $f$ at $x_0,\dots,x_n$, and $p_k(x)=p_{k-1}(x)+f[x_0,\dots,x_k]\,\omega_k(x)$ with $\omega_k(x)=(x-x_0)\cdots(x-x_{k-1})$.

Proof. For a finite set $S$ of distinct nodes write $P_S$ for the polynomial of degree $\le|S|-1$ interpolating $f$ on $S$ (Theorem 5.23), and $\ell(S)$ for its coefficient of $x^{|S|-1}$. We first show by induction on $k$ that $\ell(\{x_i,\dots,x_{i+k}\})=f[x_i,\dots,x_{i+k}]$. For $k=0$ both sides are $f(x_i)$. For the step, let $q=P_{\{x_i,\dots,x_{i+k-1}\}}$ and $r=P_{\{x_{i+1},\dots,x_{i+k}\}}$, and put $$P(x)=\frac{(x-x_i)\,r(x)-(x-x_{i+k})\,q(x)}{x_{i+k}-x_i}\qquad\text{(Neville–Aitken).}$$ $P$ has degree $\le k$. At $x_i$: $P=\frac{-(x_i-x_{i+k})q(x_i)}{x_{i+k}-x_i}=f(x_i)$. At $x_{i+k}$: $P=r(x_{i+k})=f(x_{i+k})$. At an interior node $x_j$ both $q$ and $r$ equal $f(x_j)$, so $P(x_j)=f(x_j)\frac{(x_j-x_i)-(x_j-x_{i+k})}{x_{i+k}-x_i}=f(x_j)$. By uniqueness $P=P_{\{x_i,\dots,x_{i+k}\}}$, and comparing coefficients of $x^k$, $$\ell(\{x_i,\dots,x_{i+k}\})=\frac{\ell(\{x_{i+1},\dots,x_{i+k}\})-\ell(\{x_i,\dots,x_{i+k-1}\})}{x_{i+k}-x_i},$$ which by the induction hypothesis is the recursion of Definition 5.18.

Now let $p_k=P_{\{x_0,\dots,x_k\}}$. The difference $p_k-p_{k-1}$ has degree $\le k$ and vanishes at $x_0,\dots,x_{k-1}$, so it equals $c\,\omega_k(x)$ for a constant $c$; comparing coefficients of $x^k$, $c=\ell(\{x_0,\dots,x_k\})=f[x_0,\dots,x_k]$. Summing $p_n=p_0+\sum_{k=1}^n(p_k-p_{k-1})$ gives the formula. ∎

Newton's form is also the cheapest to evaluate: with nested multiplication (Horner's scheme) $p_n(x)=c_0+(x-x_0)\big(c_1+(x-x_1)\big(c_2+\cdots\big)\big)$ costs $n$ multiplications once the table ($\tfrac12n(n+1)$ divisions) is built. The theorem has several consequences that CSIR questions test directly.

📐 Theorem 5.27 — Properties of divided differences
  1. Explicit formula and symmetry. $f[x_0,\dots,x_n]=\displaystyle\sum_{i=0}^{n}\frac{f(x_i)}{\omega_{n+1}'(x_i)}$ $\displaystyle=\sum_{i=0}^n\frac{f(x_i)}{\prod_{j\ne i}(x_i-x_j)}$; hence $f[x_0,\dots,x_n]$ is a symmetric function of its arguments and depends linearly on $f$.
  2. Error in Newton form. If $x$ is not a node, $f(x)-p_n(x)=f[x_0,\dots,x_n,x]\,\omega_{n+1}(x)$.
  3. Mean value property. If $f\in C^n[a,b]$ and the $x_i\in[a,b]$, then $f[x_0,\dots,x_n]=\dfrac{f^{(n)}(\xi)}{n!}$ for some $\xi$ in the smallest interval containing the nodes.
  4. Polynomials. If $f$ is a polynomial of degree $m$ with leading coefficient $a$, then $f[x_0,\dots,x_n]=a$ if $n=m$ and $=0$ if $n\gt m$, for all distinct nodes.
  5. Repeated nodes (Hermite–Genocchi). If $f\in C^n$, then $$f[x_0,\dots,x_n]=\int_{\Sigma_n}f^{(n)}\big(t_0x_0+\dots+t_nx_n\big)\,dt_1\cdots dt_n,$$ where $\Sigma_n=\{t_i\ge0,\ t_0+\dots+t_n=1\}$ (and $t_0=1-t_1-\dots-t_n$). The right side is continuous in the nodes, so divided differences extend to coincident nodes, with $f[\underbrace{x,\dots,x}_{k+1}]=\dfrac{f^{(k)}(x)}{k!}$; in particular $f[x,x]=f'(x)$.

Proof. (1) In Lagrange's form, the coefficient of $x^n$ in $\sum f(x_i)L_i(x)$ is $\sum f(x_i)/\prod_{j\ne i}(x_i-x_j)$; by Theorem 5.26 it is also $f[x_0,\dots,x_n]$. The sum is unchanged by any permutation of the nodes and is linear in $f$.

(2) Add $x$ as an extra node: by Theorem 5.26 (with the nodes $x_0,\dots,x_n,x$), $P(t)=p_n(t)+f[x_0,\dots,x_n,x]\,\omega_{n+1}(t)$ interpolates $f$ at $x$ as well; put $t=x$.

(3) Apply (2) with the $n$ nodes $x_0,\dots,x_{n-1}$ and the extra point $x_n$, and compare with Theorem 5.24 for these $n$ nodes (it needs only $f\in C^n$): $f[x_0,\dots,x_n]\,\omega_n(x_n)=\dfrac{f^{(n)}(\xi)}{n!}\,\omega_n(x_n)$, and $\omega_n(x_n)\ne0$.

(4) If $n\ge m$, the interpolant of $f$ in $\mathcal{P}_n$ is $f$ itself, whose coefficient of $x^n$ is $a$ (if $n=m$) or $0$ (if $n\gt m$). Alternatively use (3): $f^{(n)}/n!$ is $a$ or $0$.

(5) Sketch. For $n=1$: $\int_0^1f'(x_0+t(x_1-x_0))\,dt=\frac{f(x_1)-f(x_0)}{x_1-x_0}$. In general one shows that the integral satisfies the recursion of Definition 5.18, by integrating out one variable with the fundamental theorem of calculus; induction finishes the proof. With all nodes equal to $x$ the integrand is the constant $f^{(n)}(x)$ and the simplex $\Sigma_n$ has $n$-dimensional volume $1/n!$. ∎

Property (3) explains the name "mean value property": for $n=1$ it is the mean value theorem. It also gives the cleanest proof that $\Delta^n p=n!\,a\,h^n$ for polynomials, through the next theorem, which specialises Newton's formula to equally spaced nodes.

📐 Theorem 5.28 — Newton's forward and backward difference formulas

Let $x_i=x_0+ih$ and $\binom sk=\dfrac{s(s-1)\cdots(s-k+1)}{k!}$ for real $s$. Then

$$f[x_i,\dots,x_{i+k}]=\frac{\Delta^kf_i}{k!\,h^k}=\frac{\nabla^kf_{i+k}}{k!\,h^k}.$$

Forward formula (Newton–Gregory; for $x$ near the top of the table): with $x=x_0+sh$,

$$p_n(x)=\sum_{k=0}^{n}\binom sk\Delta^kf_0=f_0+s\,\Delta f_0+\frac{s(s-1)}{2!}\Delta^2f_0+\dots$$

Backward formula (for $x$ near the bottom of the table): with $x=x_n+sh$,

$$p_n(x)=\sum_{k=0}^{n}\binom{s+k-1}{k}\nabla^kf_n=f_n+s\,\nabla f_n+\frac{s(s+1)}{2!}\nabla^2f_n+\dots$$

Both are the same polynomial $p_n$ on the nodes $x_0,\dots,x_n$. If $f\in C^{n+1}$, the errors are $f(x)-p_n(x)=\binom{s}{n+1}h^{n+1}f^{(n+1)}(\xi)$ (forward) and $=\binom{s+n}{n+1}h^{n+1}f^{(n+1)}(\xi)$ (backward).

Proof. Induction on $k$: for $k=0$ both sides are $f_i$; if the identity holds for $k$, then $$f[x_i,\dots,x_{i+k+1}]=\frac{\Delta^kf_{i+1}-\Delta^kf_i}{k!\,h^k\,(x_{i+k+1}-x_i)}=\frac{\Delta^{k+1}f_i}{k!\,h^k\,(k+1)h}=\frac{\Delta^{k+1}f_i}{(k+1)!\,h^{k+1}}.$$ The backward version is the same statement because $\nabla^kf_{i+k}=\Delta^kf_i$. For the forward formula, $x-x_j=(s-j)h$, so $\omega_k(x)=(x-x_0)\cdots(x-x_{k-1})$ $=h^k\,s(s-1)\cdots(s-k+1)$ $=k!\,h^k\binom sk$; insert in Theorem 5.26. For the backward formula, list the nodes in the order $x_n,x_{n-1},\dots,x_0$ (allowed by Theorem 5.27(1)): then $f[x_n,\dots,x_{n-k}]=\nabla^kf_n/(k!h^k)$ and $(x-x_n)(x-x_{n-1})\cdots(x-x_{n-k+1})$ $=h^k s(s+1)\cdots(s+k-1)=k!\,h^k\binom{s+k-1}{k}$. The errors follow from Theorem 5.24 in the same way, since $\omega_{n+1}(x)=(n+1)!\,h^{n+1}\binom s{n+1}$ in the forward variable and $=(n+1)!\,h^{n+1}\binom{s+n}{n+1}$ in the backward one. ∎

Central formulas. Taking the nodes in the zig-zag order $x_0,x_1,x_{-1},x_2,x_{-2},\dots$ in Theorem 5.26 gives Gauss's forward formula $$p(x_0+sh)=f_0+s\,\Delta f_0+\binom s2\Delta^2f_{-1}+\binom{s+1}3\Delta^3f_{-1}+\binom{s+1}4\Delta^4f_{-2}+\cdots,$$ and averaging it with Gauss's backward formula (order $x_0,x_{-1},x_1,\dots$) gives Stirling's formula $$p(x_0+sh)=f_0+s\,\mu\delta f_0+\frac{s^2}{2}\delta^2f_0+\binom{s+1}{3}\mu\delta^3f_0+\frac{s^2(s^2-1)}{4!}\delta^4f_0+\cdots.$$ They use the differences on the line through $x_0$ and are preferred for $|s|\le\tfrac14$; Bessel's formula (centred on $x_{1/2}$) is preferred for $s$ near $\tfrac12$. On the same set of nodes they all produce the same polynomial; they differ only in which terms one may drop when stopping early.

✏️ Example 4 — A divided-difference table, and what one changed reading does
(a) Find the polynomial of least degree through $(-2,-17)$, $(-1,0)$, $(1,4)$, $(2,15)$, $(4,115)$. (b) The last reading is corrected to $f(4)=120$. Which entries of the table change, and by how much does the top coefficient change? Explain the answer by Theorem 5.27(1).
Table Denominators: first order $x_{i+1}-x_i$, second order $x_{i+2}-x_i$, and so on.
$x_i$$f[x_i]$1st2nd3rd4th
$-2$$-17$$17$$-5$$2$$0$
$-1$$0$$2$$3$$2$
$1$$4$$11$$13$
$2$$15$$50$
$4$$115$
(a) Newton form For example $f[-2,-1,1]=\frac{2-17}{1-(-2)}=-5$ and $f[1,2,4]=\frac{50-11}{4-1}=13$. The fourth divided difference is $0$ and the third ones are constant, so the data lie on a cubic (Theorem 5.27(4)): $$p(x)=-17+17(x+2)-5(x+2)(x+1)+2(x+2)(x+1)(x-1),$$ which expands to $p(x)=2x^3-x^2+3$. Check: $p(4)=128-16+3=115$.
(b) What changes Only the entries that involve $f(4)$ — the bottom diagonal — change: $f[2,4]=52.5$, $f[1,2,4]=\tfrac{83}{6}$, $f[-1,1,2,4]=\tfrac{13}{6}$, $f[-2,-1,1,2,4]=\tfrac1{36}$. The Newton coefficients $-17,17,-5,2$ (top row) are unchanged; the new interpolant is $p(x)+\tfrac1{36}(x+2)(x+1)(x-1)(x-2)$, a quartic.
Why $\tfrac1{36}$ By Theorem 5.27(1) the top coefficient depends on $f(4)$ only through the term $f(4)/\omega_5'(4)$, and $\omega_5'(4)=(4+2)(4+1)(4-1)(4-2)=180$. A change of $5$ in $f(4)$ changes it by $\tfrac5{180}=\tfrac1{36}$. This is how one error propagates through a divided-difference table.
✏️ Example 5 — Forward and backward interpolation in a table of $\sqrt x$
The values of $\sqrt x$ for $x=1.0,1.1,\dots,1.5$, rounded to five decimals, are $1.00000$, $1.04881$, $1.09545$, $1.14018$, $1.18322$, $1.22474$. Estimate $\sqrt{1.05}$ with the forward formula and $\sqrt{1.48}$ with the backward formula. How many differences are worth using?
Table Differences in units of the fifth decimal:
$x$$f$$\Delta$$\Delta^2$$\Delta^3$$\Delta^4$$\Delta^5$
1.01.000004881$-217$26$-4$$-1$
1.11.048814664$-191$22$-5$
1.21.095454473$-169$17
1.31.140184304$-152$
1.41.183224152
1.51.22474
Forward, $x=1.05$ $s=(1.05-1.0)/0.1=0.5$; $\binom{s}{2}=-0.125$, $\binom s3=0.0625$, $\binom s4=-0.039\,06$. So $p=1+0.5(0.04881)-0.125(-0.00217)$ $+0.0625(0.00026)$ $-0.039\,06(-0.00004)$ and the partial sums are $1.024\,405$, $1.024\,676$, $1.024\,693$, $1.024\,694$. True value: $\sqrt{1.05}=1.024\,695$.
Backward, $x=1.48$ $x_n=1.5$, $s=(1.48-1.5)/0.1=-0.2$; the coefficients $\binom{s+k-1}{k}$ are $-0.2$, $-0.08$, $-0.048$, $-0.0336$ for $k=1,\dots,4$, applied to $\nabla f_5=0.04152$, $\nabla^2f_5=-0.00152$, $\nabla^3f_5=0.00017$, $\nabla^4f_5=-0.00005$. Partial sums: $1.216\,436$, $1.216\,558$, $1.216\,549$, $1.216\,551$. True value: $1.216\,553$.
When to stop The fifth difference, $-1$ unit, is at the level of rounding noise: each table entry may be off by half a unit, and a $k$-th difference of such errors can reach $2^{k-1}$ units. Differences beyond the fourth carry no information here, and the answers are good to about one unit in the sixth decimal — the accuracy of the data, not of the formula. (By Theorem 5.28 the truncation error after the $\Delta^3$ term is about $|\binom s4\Delta^4f_0|\approx2\times10^{-6}$, matching the last correction.)
Interactive 2 — Newton's Formula One Term at a Time, and How an Error Spreads Through the Table

Press Next (or Play): the interpolant $p_k$ grows one node at a time, $p_k=p_{k-1}+f[x_0,\dots,x_k]\,\omega_k$. The current $p_k$ is drawn over the previous one and the function (dashed); the correction term is plotted along the bottom. In the table below, the entries along the top row are Newton's coefficients. Choose an error $\varepsilon$ in the reading at $x_3$ and watch it spread through the higher columns — for equally spaced data in the binomial fan $\varepsilon,-3\varepsilon,3\varepsilon,-\varepsilon$ of Example 1. Drag $x^*$ to compare the next term with the true error.

—
degree k—
new coefficient—
p_k(x*)—
true error f − p_k—
next term at x*—
🧭 Problem-solving strategy — which interpolation formula?
  1. Value at one point, few nodes, no table needed: Lagrange's formula; compute the $L_i(x)$ numerically and check $\sum L_i(x)=1$.
  2. Unequal nodes, or nodes may be added later: a divided-difference table and Newton's form; read the coefficients along the top diagonal, and use the next term $f[x_0,\dots,x_{n+1}]\omega_{n+1}(x)$ as an error estimate.
  3. Equally spaced table: forward formula near the top ($s=(x-x_0)/h$), backward formula near the bottom ($s=(x-x_n)/h\lt0$), Stirling/Bessel in the middle. Stop when the differences reach rounding level.
  4. "Find the polynomial" questions with a trick: if $f$ is itself a polynomial of degree $n+1$ with leading coefficient $a$, its interpolant at $n+1$ nodes is $f-a\,\omega_{n+1}$ (the difference has degree $\le n$ and interpolates). If the data come from a polynomial of degree $\le n$, the interpolant is that polynomial.
  5. Error questions: $\dfrac{M_{n+1}}{(n+1)!}\max|\omega_{n+1}|$; for equal spacing $\max|\omega_{n+1}|\le\tfrac14n!h^{n+1}$, and for linear interpolation $\tfrac18M_2h^2$.
  6. Derivative data, or a smooth curve through many points: Hermite or a spline — next subsection.

Hermite Interpolation and Cubic Splines

Often more than values are known: a trajectory is recorded with positions and velocities, a cam profile is specified with slopes at its ends. Matching derivatives as well gives Hermite (osculating) interpolation. And when many points must be joined by a smooth curve, a single polynomial is the wrong tool — one uses low-degree pieces glued smoothly together: splines.

📘 Definition 5.19 — Hermite interpolation

Let $x_0,\dots,x_n$ be distinct and let values $y_i$ and slopes $y_i'$ be given. The Hermite interpolation problem asks for $H\in\mathcal{P}_{2n+1}$ with

$$H(x_i)=y_i,\qquad H'(x_i)=y_i'\qquad(i=0,\dots,n).$$

More generally, one may prescribe $H(x_i),H'(x_i),\dots,H^{(m_i-1)}(x_i)$ at each node (multiplicity $m_i\ge1$) and look for $H\in\mathcal{P}_{N-1}$, $N=m_0+\dots+m_n$: the number of conditions equals the dimension of the space. With all $m_i=1$ this is Lagrange interpolation; with one node of multiplicity $n+1$ it is the Taylor polynomial.

📐 Theorem 5.29 — Hermite interpolation: existence, uniqueness, formula, error
  1. The Hermite problem of Definition 5.19 has exactly one solution $H\in\mathcal{P}_{2n+1}$.
  2. With the Lagrange basis $L_i$ of Definition 5.17, $$H(x)=\sum_{i=0}^n\Big[1-2L_i'(x_i)(x-x_i)\Big]L_i(x)^2\,y_i+\sum_{i=0}^n(x-x_i)L_i(x)^2\,y_i'.$$
  3. Newton's form holds with the node list $z_0=z_1=x_0$, $z_2=z_3=x_1$, …, $z_{2n}=z_{2n+1}=x_n$, where repeated-node entries are $f[x_i,x_i]=f'(x_i)$ (Theorem 5.27(5)): $H(x)=\sum_{k=0}^{2n+1}f[z_0,\dots,z_k]\,\pi_k(x)$ with $\pi_k(x)=(x-z_0)\cdots(x-z_{k-1})$.
  4. If $f\in C^{2n+2}[a,b]$, the nodes lie in $[a,b]$ and $y_i=f(x_i)$, $y_i'=f'(x_i)$, then for each $x\in[a,b]$ $$f(x)-H(x)=\frac{f^{(2n+2)}(\xi_x)}{(2n+2)!}\,\omega_{n+1}(x)^2$$ for some $\xi_x$ in the smallest interval containing $x$ and the nodes.

Proof. (1) If $H_1,H_2$ both solve the problem, $q=H_1-H_2\in\mathcal{P}_{2n+1}$ has $q(x_i)=q'(x_i)=0$, so each $x_i$ is a root of multiplicity at least $2$: $q$ has at least $2n+2$ roots counted with multiplicity, hence $q=0$. The map $H\mapsto(H(x_0),\dots,H(x_n),H'(x_0),\dots,H'(x_n))$ from $\mathcal{P}_{2n+1}$ (dimension $2n+2$) to $\mathbb{R}^{2n+2}$ is linear and injective, hence surjective: a solution exists.

(2) Put $A_i(x)=[1-2L_i'(x_i)(x-x_i)]L_i(x)^2$ and $B_i(x)=(x-x_i)L_i(x)^2$, both of degree $2n+1$. Since $L_i(x_k)=\delta_{ik}$: $A_i(x_k)=\delta_{ik}$ and $B_i(x_k)=0$. Differentiating, $A_i'(x)=-2L_i'(x_i)L_i(x)^2$ $+2[1-2L_i'(x_i)(x-x_i)]L_i(x)L_i'(x)$, which is $0$ at $x_k\ne x_i$ (factor $L_i(x_k)=0$) and $-2L_i'(x_i)+2L_i'(x_i)=0$ at $x_i$. Similarly $B_i'(x)=L_i(x)^2+2(x-x_i)L_i(x)L_i'(x)$ equals $\delta_{ik}$ at $x_k$. So $\sum y_iA_i+\sum y_i'B_i$ has the required values and slopes.

(3) Sketch. Interpolate at $2n+2$ distinct nodes $x_0,x_0+\eta,x_1,x_1+\eta,\dots$ and let $\eta\to0$: the divided differences converge by the continuity in Theorem 5.27(5), and the limit polynomial has the right values and slopes, so by (1) it is $H$.

(4) If $x$ is a node, both sides vanish. Otherwise set $g(t)=f(t)-H(t)$ $-\big(f(x)-H(x)\big)\omega_{n+1}(t)^2/\omega_{n+1}(x)^2$. Then $g$ vanishes at the $n+2$ distinct points $x_0,\dots,x_n,x$, so by Rolle $g'$ vanishes at $n+1$ points lying strictly between them; also $g'(x_i)=0$ at the $n+1$ nodes (each term has a double zero there). These $2n+2$ zeros of $g'$ are distinct, so by Rolle repeatedly $g^{(2n+2)}(\xi)=0$ for some $\xi$. As $H^{(2n+2)}=0$ and $(\omega_{n+1}^2)^{(2n+2)}=(2n+2)!$, this is the formula. ∎

The most used case is the cubic Hermite interpolant on one interval $[a,b]$, $h=b-a$, $x=a+th$: $$H(x)=y_0(1-3t^2+2t^3)+y_1(3t^2-2t^3)+h\,y_0'(t-2t^2+t^3)+h\,y_1'(t^3-t^2),$$ with error $\tfrac{f^{(4)}(\xi)}{24}(x-a)^2(x-b)^2$, at most $\tfrac{h^4}{384}\max|f^{(4)}|$. Using such pieces on every subinterval (with the true slopes at the knots) gives a piecewise cubic Hermite interpolant: it is $C^1$, but in general not $C^2$.

✏️ Example 6 — A cubic Hermite approximation of $\sin(\pi x/2)$
Find the cubic $H$ with $H(0)=0$, $H'(0)=\tfrac\pi2$, $H(1)=1$, $H'(1)=0$ (the values and slopes of $f(x)=\sin\tfrac{\pi x}{2}$). Estimate $\sin\tfrac\pi4$ by $H(\tfrac12)$ and compare the error with the bound of Theorem 5.29.
Repeated nodes Node list $0,0,1,1$ with $f[0,0]=f'(0)=\tfrac\pi2$, $f[1,1]=f'(1)=0$, $f[0,1]=1$. Then $f[0,0,1]=\dfrac{f[0,1]-f[0,0]}{1-0}=1-\tfrac\pi2$, $\ f[0,1,1]=\dfrac{f[1,1]-f[0,1]}{1-0}=-1$, and $f[0,0,1,1]=\dfrac{-1-(1-\frac\pi2)}{1-0}=\tfrac\pi2-2$.
Newton form $$H(x)=\tfrac\pi2x+\big(1-\tfrac\pi2\big)x^2+\big(\tfrac\pi2-2\big)x^2(x-1).$$ Check: $H(1)=\tfrac\pi2+1-\tfrac\pi2=1$ and $H'(1)=\tfrac\pi2+2-\pi+\tfrac\pi2-2=0$.
Estimate $H(\tfrac12)=\tfrac\pi4+\tfrac14-\tfrac\pi8$ $-\tfrac18\big(\tfrac\pi2-2\big)$ $=\tfrac12+\tfrac{\pi}{16}$ $=0.696\,350$, while $\sin\tfrac\pi4=0.707\,107$: the error is $0.010\,757$.
Bound $|f^{(4)}|=(\tfrac\pi2)^4|\sin\tfrac{\pi x}2|\le(\tfrac\pi2)^4=6.088$ and $x^2(x-1)^2=\tfrac1{16}$ at $x=\tfrac12$, so the error is at most $\tfrac{6.088}{24}\cdot\tfrac1{16}=0.015\,85$. The actual error $0.0108$ is within it, and positive, as the theorem predicts ($f^{(4)}\gt0$ on $(0,1)$ and $\omega^2\ge0$).

Hermite pieces are only $C^1$ and need slopes we may not know. A cubic spline uses only the values, and buys one more derivative of smoothness by letting the slopes at the knots be unknowns, fixed by the requirement that the second derivative be continuous.

📘 Definition 5.20 — Splines; natural and clamped cubic splines

Let $a=x_0\lt x_1\lt\dots\lt x_n=b$ (the knots). A spline of degree $k$ is a function $s\in C^{k-1}[a,b]$ whose restriction to each $[x_{i-1},x_i]$ is a polynomial of degree $\le k$. A cubic spline interpolant of data $y_0,\dots,y_n$ is a spline $s$ of degree $3$ with $s(x_i)=y_i$ for all $i$. It is called

naturalif $s''(a)=s''(b)=0$;
clamped (complete)if $s'(a)=f'(a)$ and $s'(b)=f'(b)$ are prescribed;
periodicif $y_0=y_n$ and $s',s''$ agree at $a$ and $b$;
not-a-knotif $s'''$ is continuous at $x_1$ and $x_{n-1}$.

The moments of $s$ are $M_i=s''(x_i)$. We write $h_i=x_i-x_{i-1}$ and $d_i=(y_i-y_{i-1})/h_i$ (the slopes of the chords).

A count shows why exactly two end conditions are needed: there are $4n$ coefficients, the interpolation conditions give $2n$ equations (each piece takes the right values at both of its ends, which also makes $s$ continuous), and continuity of $s'$ and $s''$ at the $n-1$ interior knots gives $2(n-1)$ more — a total of $4n-2$.

📐 Theorem 5.30 — The spline equations; existence and uniqueness

(a) A function $s$ is a cubic spline interpolant of $y_0,\dots,y_n$ if and only if on each $[x_{i-1},x_i]$

$$s(x)=M_{i-1}\frac{(x_i-x)^3}{6h_i}+M_i\frac{(x-x_{i-1})^3}{6h_i}+\Big(y_{i-1}-\frac{M_{i-1}h_i^2}{6}\Big)\frac{x_i-x}{h_i}+\Big(y_i-\frac{M_ih_i^2}{6}\Big)\frac{x-x_{i-1}}{h_i},$$

where the moments satisfy, for $i=1,\dots,n-1$,

$$h_iM_{i-1}+2(h_i+h_{i+1})M_i+h_{i+1}M_{i+1}=6\,(d_{i+1}-d_i).$$

(b) For the natural spline add $M_0=M_n=0$; for the clamped spline add $2h_1M_0+h_1M_1=6(d_1-f'(a))$ and $h_nM_{n-1}+2h_nM_n=6(f'(b)-d_n)$. In both cases the linear system for the moments is tridiagonal and strictly diagonally dominant, so the natural (and the clamped) cubic spline interpolant exists and is unique.

(c) For equal spacing $h$ the interior equations read $M_{i-1}+4M_i+M_{i+1}$ $=\dfrac{6}{h^2}\big(y_{i+1}-2y_i+y_{i-1}\big)$ $=\dfrac{6\,\Delta^2y_{i-1}}{h^2}$.

Proof. (a) On $[x_{i-1},x_i]$, $s''$ is linear, so it is the linear interpolant of its end values: $s''(x)=M_{i-1}\frac{x_i-x}{h_i}+M_i\frac{x-x_{i-1}}{h_i}$. Integrating twice gives the two cubic terms plus a linear function, and the conditions $s(x_{i-1})=y_{i-1}$, $s(x_i)=y_i$ fix that linear function as stated. Conversely, the displayed formula is a cubic on each piece with $s(x_{i-1})=y_{i-1}$, $s(x_i)=y_i$ and $s''(x_{i-1})=M_{i-1}$, $s''(x_i)=M_i$; so $s$ and $s''$ are continuous whatever the $M_i$ are, and only continuity of $s'$ remains. Differentiating, $$s'(x)=-M_{i-1}\frac{(x_i-x)^2}{2h_i}+M_i\frac{(x-x_{i-1})^2}{2h_i}+d_i-\frac{(M_i-M_{i-1})h_i}{6}.$$ Hence $s'(x_i^-)=d_i+\tfrac{h_i}{3}M_i+\tfrac{h_i}{6}M_{i-1}$, and from the formula on the next piece $s'(x_i^+)=d_{i+1}-\tfrac{h_{i+1}}3M_i-\tfrac{h_{i+1}}6M_{i+1}$. Equating and multiplying by $6$ gives the equation.

(b) The clamped conditions are $s'(x_0^+)=d_1-\tfrac{h_1}{3}M_0-\tfrac{h_1}6M_1$ $=f'(a)$ and $s'(x_n^-)=d_n+\tfrac{h_n}3M_n+\tfrac{h_n}6M_{n-1}$ $=f'(b)$, multiplied by $6$. In every row the diagonal entry ($2(h_i+h_{i+1})$, or $2h_1$, $2h_n$) exceeds the sum of the off-diagonal entries ($h_i+h_{i+1}$, or $h_1$, $h_n$). A strictly diagonally dominant matrix $A$ is nonsingular (§5.2): if $Am=0$ and $|m_i|=\max_j|m_j|$, then $|a_{ii}||m_i|$ $=|\sum_{j\ne i}a_{ij}m_j|$ $\le\big(\sum_{j\ne i}|a_{ij}|\big)|m_i|$, forcing $m_i=0$ and so $m=0$. So the moments, and with them $s$, are uniquely determined. (c) Put $h_i=h$ and divide by $h$. ∎

The system is solved in $O(n)$ operations by Gaussian elimination without pivoting (the Thomas algorithm; diagonal dominance makes it stable). Why "natural"? A thin elastic strip (a draughtsman's spline) forced through the points takes the shape that minimises its bending energy, and beyond the last point it is free, so it carries no bending moment there: $s''=0$. The next theorem makes this precise.

📐 Theorem 5.31 — Minimum curvature property of splines (Holladay)

Let $s$ be the natural cubic spline interpolating $y_0,\dots,y_n$ at $a=x_0\lt\dots\lt x_n=b$ ($n\ge1$). For every $g\in C^2[a,b]$ with $g(x_i)=y_i$ for all $i$,

$$\int_a^b s''(x)^2\,dx\le\int_a^b g''(x)^2\,dx,$$

with equality only if $g=s$. The same holds for the clamped spline among all $g\in C^2[a,b]$ with $g(x_i)=y_i$, $g'(a)=f'(a)$, $g'(b)=f'(b)$.

Proof. Put $e=g-s$, so $e(x_i)=0$ for all $i$, and expand $\int(g'')^2=\int(s'')^2+2\int s''e''+\int(e'')^2$. Integrate by parts on each $[x_{i-1},x_i]$, where $s'''$ is a constant $c_i$: $$\int_a^bs''e''\,dx=\Big[s''e'\Big]_a^b-\sum_{i=1}^nc_i\int_{x_{i-1}}^{x_i}e'(x)\,dx=\Big[s''e'\Big]_a^b-\sum_{i=1}^nc_i\big(e(x_i)-e(x_{i-1})\big).$$ The sum is $0$ because $e$ vanishes at the knots, and the boundary term is $0$ because $s''(a)=s''(b)=0$ (natural case) or $e'(a)=e'(b)=0$ (clamped case); the interior boundary terms cancel because $s''e'$ is continuous. Hence $\int(g'')^2=\int(s'')^2+\int(e'')^2\ge\int(s'')^2$. Equality forces $e''\equiv0$, so $e$ is linear; it vanishes at $x_0\ne x_n$, so $e\equiv0$. ∎

📐 Theorem 5.32 — Error of cubic spline interpolation (statement)

Let $f\in C^4[a,b]$, $h=\max_ih_i$, and let $s$ be the clamped cubic spline interpolant of $f$. Then

$$\|f-s\|_\infty\le\frac{5}{384}\,h^4\,\|f^{(4)}\|_\infty,$$

and $\|f^{(k)}-s^{(k)}\|_\infty\le C_k\,h^{4-k}\|f^{(4)}\|_\infty$ for $k=1,2,3$ (for $k=3$ under a bound on the ratio $\max h_i/\min h_i$). The natural spline has the same $O(h^4)$ accuracy away from the ends, but near the ends its error is only $O(h^2)$ unless $f''(a)=f''(b)=0$. In particular, spline interpolants converge to $f$ as $h\to0$ with no growth of the kind seen in the next subsection.

✏️ Example 7 — The natural spline through four points of $y=x^3$
Find the natural cubic spline $s$ through $(0,0)$, $(1,1)$, $(2,8)$, $(3,27)$. Compute $s(0.5)$, $s(1.5)$, $s(2.5)$ and compare with $x^3$. Explain why the error is largest on the last interval, and say what the clamped spline would give.
Equations $h=1$, $M_0=M_3=0$, and Theorem 5.30(c) at $i=1,2$: $4M_1+M_2=6(8-2+0)=36$, $\ M_1+4M_2=6(27-16+1)=72$.
Moments Eliminating, $15M_2=288-36$, so $M_2=16.8$ and $M_1=(36-16.8)/4=4.8$. (For $f=x^3$, $f''(1)=6$, $f''(2)=12$.)
Values On $[0,1]$: $s(x)=0.8x^3+0.2x$, so $s(0.5)=0.2$ ($x^3=0.125$). On $[1,2]$: $s(x)=0.8(2-x)^3+2.8(x-1)^3$ $+0.2(2-x)+5.2(x-1)$, so $s(1.5)=0.1+0.35+0.1+2.6=3.15$ ($3.375$). On $[2,3]$: $s(x)=2.8(3-x)^3+5.2(3-x)+27(x-2)$, so $s(2.5)=0.35+2.6+13.5=16.45$ ($15.625$).
Why, and the cure The natural condition imposes $s''(3)=0$, while $f''(3)=18$: the wrong end condition costs an error $0.825$ on the last interval. The clamped spline with $s'(0)=0$, $s'(3)=27$ is $x^3$ itself — $x^3$ is a cubic spline satisfying all its conditions, and Theorem 5.30 says there is only one. So splines reproduce cubics only with correct end conditions.

Runge's Phenomenon and the Choice of Nodes

Theorem 5.25 suggests that taking more and more equally spaced nodes always improves the interpolant. It does for $e^x$ or $\sin x$, whose derivatives are bounded by a constant. But in 1901 Carl Runge observed that for the harmless-looking function $f(x)=\dfrac1{1+25x^2}$ on $[-1,1]$ the interpolants at equally spaced nodes oscillate more and more wildly near $\pm1$. The error formula explains why: $|f^{(n+1)}|$ grows like $(n+1)!\,5^{n+1}$, faster than $\max|\omega_{n+1}|$ decreases.

max error, $n=$48121620
equal spacing0.4381.0453.6614.459.8
Chebyshev0.4020.1710.0690.0330.015
natural spline0.2790.0560.00690.00370.0032
📐 Theorem 5.33 — Runge's phenomenon (statement)

Let $f(x)=1/(1+25x^2)$ and let $p_n$ interpolate $f$ at the $n+1$ equally spaced nodes $-1+2i/n$ $(0\le i\le n)$. There is a number $x_c=0.7266\ldots$ such that

$$p_n(x)\to f(x)\ \text{ for }|x|\lt x_c,\qquad \limsup_{n\to\infty}|f(x)-p_n(x)|=\infty\ \text{ for }x_c\lt|x|\lt1,$$

and in particular $\max_{[-1,1]}|f-p_n|\to\infty$. The same divergence occurs for $1/(1+a^2x^2)$ whenever $a\gt a_0\approx1.90$, i.e. whenever the poles $\pm i/a$ are closer to the interval than $\pm0.5255\,i$; for $1/(1+x^2)$ the interpolants converge on all of $[-1,1]$. For every $f$ analytic on a sufficiently large region around $[-1,1]$ (for example $e^x$, $\sin x$, any polynomial) $p_n\to f$ uniformly.

Why (sketch). For $f$ analytic near $[-1,1]$ the error has the contour-integral form $f(x)-p_n(x)=\dfrac1{2\pi i}\oint_\Gamma\dfrac{\omega_{n+1}(x)}{\omega_{n+1}(z)}\dfrac{f(z)}{z-x}\,dz$, where $\Gamma$ encloses $[-1,1]$ inside the region where $f$ is analytic (by the residue theorem: the residues of the integrand at $z=x$ and at $z=x_i$ are $f(x)$ and $-f(x_i)L_i(x)$). Deforming $\Gamma$ outward picks up the poles $z=\pm i/5$ of $f$, so the size of the error is governed by $|\omega_{n+1}(x)/\omega_{n+1}(i/5)|$. For equally spaced nodes $|\omega_{n+1}(z)|^{1/n}\to e^{\varphi(z)}$ with $\varphi(z)=\tfrac12\int_{-1}^1\log|z-t|\,dt$, and the error at $x$ tends to $0$ or $\infty$ according as $\varphi(x)\lt\varphi(i/5)$ or $\varphi(x)\gt\varphi(i/5)$; numerically the boundary is $|x|=0.7266\ldots$. The function $\varphi$ is largest at the ends of the interval, because equally spaced nodes are relatively sparse there.

The cure is to put more nodes near the ends — optimally, the zeros of a Chebyshev polynomial.

📘 Definition 5.21 — Chebyshev polynomials and Chebyshev nodes

The Chebyshev polynomials are $T_0=1$, $T_1=x$, $T_{m+1}(x)=2xT_m(x)-T_{m-1}(x)$; for $x=\cos\theta\in[-1,1]$ they satisfy $T_m(\cos\theta)=\cos m\theta$. The $n+1$ Chebyshev nodes on $[-1,1]$ are the zeros of $T_{n+1}$:

$$x_i=\cos\frac{(2i+1)\pi}{2n+2},\qquad i=0,1,\dots,n,$$

and on $[a,b]$ they are $\tfrac{a+b}{2}+\tfrac{b-a}{2}x_i$. They are the projections onto the diameter of $n+1$ equally spaced points on a semicircle, so they cluster near $\pm1$.

📐 Theorem 5.34 — Chebyshev nodes minimise the nodal polynomial

(a) $T_{m}$ has degree $m$ and leading coefficient $2^{m-1}$ ($m\ge1$), and $\max_{[-1,1]}|T_m|=1$, attained with alternating signs at the $m+1$ points $\cos(k\pi/m)$, $k=0,\dots,m$.

(b) Among all monic polynomials $q$ of degree $n+1$, $\ \max_{[-1,1]}|q|\ge2^{-n}$, with equality for $q=2^{-n}T_{n+1}$. Hence the Chebyshev nodes minimise $\max_{[-1,1]}|\omega_{n+1}|$, the minimum being $2^{-n}$, and for $f\in C^{n+1}[-1,1]$

$$\max_{[-1,1]}|f-p_n|\le\frac{M_{n+1}}{2^n\,(n+1)!}.$$

On $[a,b]$ the bound becomes $\dfrac{M_{n+1}}{(n+1)!}\cdot2\Big(\dfrac{b-a}{4}\Big)^{n+1}$.

Proof. (a) $\cos(m+1)\theta+\cos(m-1)\theta=2\cos\theta\cos m\theta$ gives the recurrence, and induction shows $\deg T_m=m$ with leading coefficient $2^{m-1}$ (doubling at every step from $T_1=x$). Since $T_m(\cos\theta)=\cos m\theta$, $|T_m|\le1$ on $[-1,1]$, and at $\theta=k\pi/m$ the value is $(-1)^k$.

(b) $2^{-n}T_{n+1}$ is monic, its zeros are the Chebyshev nodes, so it equals $\omega_{n+1}$ for these nodes, and its maximum is $2^{-n}$. Suppose a monic $q$ of degree $n+1$ had $\max|q|\lt2^{-n}$. Then $r=2^{-n}T_{n+1}-q$ has degree $\le n$ (the leading terms cancel). At the $n+2$ points $y_k=\cos\frac{k\pi}{n+1}$, $2^{-n}T_{n+1}(y_k)=(-1)^k2^{-n}$ while $|q(y_k)|\lt2^{-n}$, so $r(y_k)$ has the sign $(-1)^k$. By the intermediate value theorem $r$ has a zero between consecutive $y_k$: at least $n+1$ zeros, so $r\equiv0$ — impossible, since then $q=2^{-n}T_{n+1}$ would have maximum exactly $2^{-n}$. The error bound is Theorem 5.24. For $[a,b]$, substitute $x=\frac{a+b}2+\frac{b-a}2t$: the nodal polynomial becomes $\big(\frac{b-a}2\big)^{n+1}2^{-n}T_{n+1}(t)$. ∎

Minimising $\omega_{n+1}$ is not the whole story: Theorem 5.34 still needs bounded $f^{(n+1)}$. The robust measure of a node set is the Lebesgue constant $\Lambda_n=\max_{[a,b]}\sum_i|L_i(x)|$. If $q\in\mathcal{P}_n$ is any polynomial, then $p_n-q$ interpolates $f-q$, so $|p_n-q|\le\Lambda_n\|f-q\|_\infty$ and $$\|f-p_n\|_\infty\le(1+\Lambda_n)\,\min_{q\in\mathcal{P}_n}\|f-q\|_\infty .$$ The same $\Lambda_n$ bounds how much errors in the data are amplified. For equally spaced nodes $\Lambda_n$ grows like $2^{n+1}/(e\,n\log n)$ ($\Lambda_{10}\approx29.9$, $\Lambda_{20}\approx10\,987$); for Chebyshev nodes $\Lambda_n\le\tfrac2\pi\log(n+1)+1$ ($\Lambda_{10}\approx2.49$, $\Lambda_{20}\approx2.90$). Combined with Jackson's theorem on best approximation, this gives uniform convergence of Chebyshev interpolants for every Lipschitz continuous $f$. No node system works for all continuous functions, however: Faber's theorem (1914) says that for every triangular array of nodes there is a continuous $f$ whose interpolants do not converge uniformly. Splines avoid the problem altogether: their Lebesgue constants stay bounded (about $1.55$ for natural splines on equally spaced knots).

Interactive 1 — Runge's Phenomenon: Equally Spaced Nodes, Chebyshev Nodes, Splines

The function $f$ (dark) is interpolated at the nodes by the interpolant; the shaded band is the error. Press Play to add nodes one by one. With equally spaced nodes and the Runge function the interpolant wiggles ever more violently near $\pm1$ while it improves in the middle; switch to Chebyshev nodes (crowded near the ends) or to a natural cubic spline and the error dies away. The lower strip shows the nodal polynomial $|\omega_{n+1}(x)|$, rescaled to its maximum: for equal spacing it is huge near the ends, for Chebyshev nodes it is level.

10
nodes n + 1—
max |f − p| on [−1, 1]—
where—
max |ω_(n+1)|—
Lebesgue constant Λ_n—
⚠️ Counterexamples and pitfalls
  1. More nodes can be worse. For $1/(1+25x^2)$ on $[-1,1]$ with equally spaced nodes, $\max|f-p_n|$ is $0.44$, $1.05$, $3.66$, $14.4$, $59.8$ for $n=4,8,12,16,20$ (Runge). Continuity, even analyticity on $\mathbb{R}$, does not guarantee convergence.
  2. Continuous but nowhere-convergent interpolation. For $f(x)=|x|$ and equally spaced nodes, $p_n(x)\to f(x)$ only at $x=-1,0,1$ (Bernstein); $\max|f-p_{20}|\approx95$. With Chebyshev nodes the same $f$ converges (slowly: error $0.029$ at $n=20$), because $|x|$ is Lipschitz.
  3. No universal nodes. By Faber's theorem every choice of nodes fails for some continuous function; "Chebyshev nodes always converge" is false without a smoothness hypothesis such as a Lipschitz condition.
  4. Vanishing differences on a grid do not make a polynomial. $f(x)=x^2+\sin\pi x$ has $\Delta^3f\equiv0$ on $\mathbb{Z}$ ($h=1$) but is not a polynomial; only the tabulated values are polynomial.
  5. No Leibniz rule for $\Delta$. $\Delta(fg)=f\Delta g+g\Delta f+\Delta f\,\Delta g$; e.g. $\Delta x^2=2x+h$ with step $h$, not $2x$.
  6. One zero divided difference proves nothing. For $(0,2),(1,0),(3,-4),(4,6)$, $f[0,1,3]=0$, yet the data lie on the cubic $x^3-4x^2+x+2$ (Exercise III.1). The degree is $\le m$ only when all $(m+1)$-th divided differences vanish.
  7. Interpolation with derivatives need not be solvable. A quadratic with prescribed $p(-1)$, $p'(0)$, $p(1)$ exists only if $p(1)-p(-1)=2p'(0)$, and is then not unique (Exercise II.7). Hermite data (value and slope at the same nodes) are always fine (Theorem 5.29); gaps in the derivative orders are not.
  8. The point $\xi$ is not a constant. In $f-p_n=\frac{f^{(n+1)}(\xi_x)}{(n+1)!}\omega_{n+1}$ the point depends on $x$; and the formula needs $f\in C^{n+1}$ — for $|x|$ it says nothing.
  9. Extrapolation is dangerous. The quintic through the $\sqrt x$ table of Example 5 (on $[1,1.5]$) gives $1.410\,73$ at $x=2$ (error $3.5\times10^{-3}$, compared with $10^{-6}$ inside the table) and $1.511$ at $x=3$ (true $1.732$): $\omega_6$ grows fast outside $[x_0,x_n]$.
  10. A natural spline does not reproduce cubics. Through four points of $x^3$ it is off by $0.825$ at $x=2.5$ (Example 7), because $f''(3)\ne0$; the clamped spline is exact.
  11. Piecewise cubic Hermite is only $C^1$. For $f=x^4$ with knots $0,1,3$ the second derivative jumps from $10$ to $4$ at $x=1$. (On equally spaced knots it happens to match for $x^4$ — check with unequal ones.)
  12. High differences of rounded data are noise. If each entry has a rounding error at most $\varepsilon$, the $k$-th differences can carry errors up to $2^k\varepsilon$; a difference column that stops decreasing and changes sign irregularly has reached rounding level (Example 5).

Exercises

I
Finite differences and operators.
  • 1 Construct the difference table of $f(x)=x^3-x$ for $x=0,1,\dots,5$ and check Theorem 5.22(2).
  • 2 Prove the identities $E\nabla=\nabla E=\Delta$, $\ \Delta-\nabla=\Delta\nabla$ and $\mu^2=1+\tfrac14\delta^2$ directly from the definitions, by applying both sides to a function $f$.
  • 3 Write $\Delta^3f_0$ in terms of $f_0,\dots,f_3$, and $f_3$ in terms of $f_0,\Delta f_0,\Delta^2f_0,\Delta^3f_0$.
  • 4 With step $h$, compute $\Delta^n(a^x)$ for $a\gt0$, and show that $\Delta\sin x=2\sin\tfrac h2\cos\big(x+\tfrac h2\big)$ and $\Delta^2\sin x=-4\sin^2\tfrac h2\,\sin(x+h)$.
  • 5 Take $h=1$. Show that $x^3=x^{(3)}+3x^{(2)}+x^{(1)}$ and that $\sum_{x=0}^{n-1}x^{(k)}=\dfrac{n^{(k+1)}}{k+1}$. Deduce $\sum_{x=1}^{m}x^3=\Big(\dfrac{m(m+1)}{2}\Big)^2$.
  • 6 A table of a cubic at $x=0,1,\dots,7$ reads $1,\ 2,\ 15,\ 52,\ 152,\ 246,\ 427,\ 680$. Find the wrong entry and correct it.
  • 7 Let $k\ge1$ and let $f$ be defined on the grid $h\mathbb{Z}$ with $\Delta^kf\equiv0$ there. Prove that $f$ agrees on $h\mathbb{Z}$ with a polynomial of degree $\lt k$, and give a non-polynomial continuous $f$ on $\mathbb{R}$ with $\Delta^2f\equiv0$ on $h\mathbb{Z}$.
  • 8 For $f(x)=x^3$ and $h=1$, verify $hD=\Delta-\tfrac12\Delta^2+\tfrac13\Delta^3$ at $x=1$ (Theorem 5.21(4)). What do the first two terms alone give?
1 $f$: $0,0,6,24,60,120$; $\Delta f$: $0,6,18,36,60$; $\Delta^2f$: $6,12,18,24$; $\Delta^3f$: $6,6,6$; $\Delta^4f=0$. Theorem 5.22(2): $\Delta^3f=3!\cdot1\cdot1^3=6$.
2 $E\nabla f(x)=\nabla f(x+h)$ $=f(x+h)-f(x)=\Delta f(x)$, and $\nabla Ef(x)$ $=Ef(x)-Ef(x-h)$ $=f(x+h)-f(x)$. $(\Delta-\nabla)f(x)$ $=f(x+h)-2f(x)+f(x-h)$ and $\Delta\nabla f(x)=\nabla f(x+h)-\nabla f(x)$ $=f(x+h)-2f(x)+f(x-h)$. Finally $\mu^2f(x)$ $=\tfrac14\big(f(x+h)+2f(x)+f(x-h)\big)$ and $\delta^2f(x)=f(x+h)-2f(x)+f(x-h)$, so $\mu^2f=f+\tfrac14\delta^2f$.
3 $\Delta^3f_0=f_3-3f_2+3f_1-f_0$ and $f_3=E^3f_0=(1+\Delta)^3f_0$ $=f_0+3\Delta f_0+3\Delta^2f_0+\Delta^3f_0$ (Theorem 5.21(3)).
4 $\Delta a^x=a^{x+h}-a^x=(a^h-1)a^x$, so $\Delta^na^x=(a^h-1)^na^x$. Using $\sin A-\sin B=2\cos\frac{A+B}2\sin\frac{A-B}2$: $\Delta\sin x=2\sin\frac h2\cos(x+\frac h2)$. Applying $\Delta$ again and $\cos A-\cos B=-2\sin\frac{A+B}2\sin\frac{A-B}2$: $\Delta^2\sin x=2\sin\frac h2\big[\cos(x+\frac{3h}2)$ $-\cos(x+\frac h2)\big]$ $=-4\sin^2\frac h2\sin(x+h)$.
5 $x^{(3)}+3x^{(2)}+x^{(1)}$ $=(x^3-3x^2+2x)+3(x^2-x)+x=x^3$. By Theorem 5.22(3), $\Delta\frac{x^{(k+1)}}{k+1}=x^{(k)}$, so the sum telescopes: $\sum_{x=0}^{n-1}x^{(k)}=\frac{n^{(k+1)}-0^{(k+1)}}{k+1}=\frac{n^{(k+1)}}{k+1}$. Hence $\sum_{x=0}^{n-1}x^3=\frac{n^{(4)}}4+n^{(3)}+\frac{n^{(2)}}2=\frac{n^2(n-1)^2}{4}$ (expand and factor). With $n=m+1$ this is $\big(\frac{m(m+1)}2\big)^2$.
6 Third differences: $12,\ 39,\ -69,\ 93,\ -15$. They have the form $c+\varepsilon,\ c-3\varepsilon,\ c+3\varepsilon,\ c-\varepsilon$ from the second one on, with $c=12$, $\varepsilon=27$, starting at $\Delta^3f_1$; so $f_4$ is wrong by $+27$ and should be $152-27=125$ (digits swapped). The data are $2x^3-x+1$, with $\Delta^3=12$.
7 Shift the grid so it starts at $x_0=0$. As in Theorem 5.22(4), $\Delta^jf=0$ for all $j\ge k$, and $f(jh)=\sum_{i=0}^{k-1}\binom ji\Delta^if(0)=Q(j)$ for every integer $j\ge0$, with $Q\in\mathcal{P}_{k-1}$. For negative $j$ use $\nabla$ instead, or note that $g=f-Q(x/h)$ satisfies $\Delta^kg\equiv0$ and $g(0)=\dots=g((k-1)h)=0$; then $g((j-1)h)$ is determined by $g(jh),\dots,g((j+k-1)h)$ through $\Delta^kg((j-1)h)=0$, and downward induction gives $g\equiv0$. Example: $f(x)=x+\sin(\pi x/h)$ equals $x$ on $h\mathbb{Z}$, so $\Delta^2f\equiv0$ there.
8 $f(1),\dots,f(4)=1,8,27,64$: $\Delta f_1=7$, $\Delta^2f_1=12$, $\Delta^3f_1=6$. Then $7-\tfrac12\cdot12+\tfrac13\cdot6=3=f'(1)$, exactly, since $\Delta^4x^3=0$. The first two terms give $7-6=1$: truncating the series is the source of the error in difference formulas for derivatives (§5.4).
II
Lagrange interpolation and the error term.
  • 1 Find the Lagrange interpolating polynomial through $(-1,2)$, $(1,4)$, $(2,11)$ and simplify it.
  • 2 Prove that $\sum_iL_i(x)\equiv1$ and $\sum_ix_i^kL_i(x)\equiv x^k$ for $0\le k\le n$. Deduce $\sum_i(x_i-x)^kL_i(x)\equiv0$ for $1\le k\le n$.
  • 3 A table of $\sin x$ ($x$ in radians) is to be read by linear interpolation with error at most $5\times10^{-7}$. What step $h$ is sufficient?
  • 4 Show that $\max_{|t|\le h}|(t+h)t(t-h)|=\dfrac{2h^3}{3\sqrt3}$. A table of $e^x$ on $[0,1]$ is read by quadratic interpolation at three consecutive nodes around $x$. Which step $h$ guarantees an error at most $10^{-6}$?
  • 5 (Inverse interpolation.) For $f(x)=x^3-x-1$, tabulate $f$ at $x=1.30,1.32,1.34$, interpolate $x$ as a quadratic function of $y=f(x)$, and estimate the root of $f$ (compare with §5.1, where $\alpha=1.324\,718$).
  • 6 Find, without solving a system, the polynomial of degree $\le2$ that interpolates $x^3$ at $0,1,2$.
  • 7 Show that a quadratic $p$ with prescribed $p(-1)=a$, $p'(0)=b$, $p(1)=c$ exists if and only if $c-a=2b$, and that it is then not unique.
  • 8 (Atmosphere.) The standard air density is $1.225$, $1.0066$ and $0.8194\ \text{kg/m}^3$ at altitudes $0$, $2$ and $4$ km. Estimate the density at $3$ km by quadratic interpolation (the standard value is $0.9093\ \text{kg/m}^3$).
1 $p=2\frac{(x-1)(x-2)}{(-2)(-3)}$ $+4\frac{(x+1)(x-2)}{(2)(-1)}$ $+11\frac{(x+1)(x-1)}{(3)(1)}$ $=\tfrac13(x^2-3x+2)-2(x^2-x-2)$ $+\tfrac{11}3(x^2-1)$ $=2x^2+x+1$. Check: $p(2)=11$.
2 The interpolant of $x^k\in\mathcal{P}_n$ is $x^k$ itself (uniqueness, Theorem 5.23), and by Lagrange's formula it is $\sum x_i^kL_i(x)$; $k=0$ gives $\sum L_i=1$. Expanding $(x_i-x)^k$ by the binomial theorem, $\sum_i(x_i-x)^kL_i(x)$ $=\sum_j\binom kj(-x)^{k-j}x^j$ $=(x-x)^k=0$.
3 $|\sin''|\le1$, so the error is at most $h^2/8$ (Theorem 5.24). $h^2/8\le5\times10^{-7}$ $\iff h\le\sqrt{4\times10^{-6}}=0.002$.
4 $g(t)=t^3-h^2t$ has $g'(t)=0$ at $t=\pm h/\sqrt3$ and $|g(\pm h/\sqrt3)|=\frac{2h^3}{3\sqrt3}$, larger than $|g(\pm h)|=0$. Error $\le\frac{e}{6}\cdot\frac{2h^3}{3\sqrt3}=\frac{e\,h^3}{9\sqrt3}\le10^{-6}$ $\iff h\le\big(9\sqrt3\times10^{-6}/e\big)^{1/3}=0.0179$. So $h=0.01$ is safe.
5 $y=f(x)$: $-0.103000$, $-0.020032$, $0.066104$. Lagrange in $y$ at $y=0$: $x\approx\sum x_iL_i(0)$ with $L_0(0)=\frac{(0-y_1)(0-y_2)}{(y_0-y_1)(y_0-y_2)}$, etc., giving $x\approx1.324\,721$, an error of $3\times10^{-6}$. Inverse interpolation is legitimate here because $f$ is monotone near the root, so $x$ is a smooth function of $y$.
6 $x^3-x(x-1)(x-2)$ has degree $2$ (the cubic terms cancel) and agrees with $x^3$ at $0,1,2$: it is $3x^2-2x$. (This is the trick of Strategy item 4.)
7 With $p=\alpha+\beta x+\gamma x^2$: $p(1)-p(-1)=2\beta=2p'(0)$, so $c-a=2b$ is necessary. If it holds, every $\alpha,\gamma$ with $\alpha+\gamma=\tfrac{a+c}2$ and $\beta=b$ works — infinitely many. The $3\times3$ system is singular: this is a Birkhoff problem (derivative of order $1$ at a node where the value is not given).
8 Nodes $0,2,4$, $x=3$: $L_0=\tfrac{(1)(-1)}{(-2)(-4)}=-\tfrac18$, $L_1=\tfrac{(3)(-1)}{(2)(-2)}=\tfrac34$, $L_2=\tfrac{(3)(1)}{(4)(2)}=\tfrac38$. $\rho(3)\approx-\tfrac{1.225}8$ $+\tfrac34(1.0066)+\tfrac38(0.8194)$ $=0.9091\ \text{kg/m}^3$, within $0.03\%$ of the standard value.
III
Divided differences and Newton's formulas.
  • 1 Build the divided-difference table for $(0,2)$, $(1,0)$, $(3,-4)$, $(4,6)$ and write the interpolant in Newton form. What does $f[0,1,3]=0$ tell you?
  • 2 Prove directly from Definition 5.18, by induction on $n$, that $f[x_0,\dots,x_n]=\sum_i f(x_i)/\omega_{n+1}'(x_i)$.
  • 3 For $f(x)=1/x$ and nonzero distinct nodes, show $f[x_0,\dots,x_n]=\dfrac{(-1)^n}{x_0x_1\cdots x_n}$.
  • 4 Show that $f[x_0,\dots,x_n]=x_0+x_1+\dots+x_n$ for $f(x)=x^{n+1}$.
  • 5 (Census.) The population of a town (in thousands) was $46,\ 66,\ 81,\ 93,\ 101$ in $1981,1991,2001,2011,2021$. Estimate it for $1986$ (forward formula) and $2018$ (backward formula).
  • 6 Let $p$ be a polynomial of degree $n\ge1$. Show that $x\mapsto p[x_0,x]$ (with $p[x_0,x_0]=p'(x_0)$) is a polynomial of degree $n-1$, and more generally that $x\mapsto p[x_0,\dots,x_{k-1},x]$ is a polynomial of degree $n-k$ for $k\le n$.
  • 7 Using the node order $x_0,x_1,x_{-1}$ in Newton's formula, derive the three-term Gauss forward formula $p(x_0+sh)=f_0+s\Delta f_0+\binom s2\Delta^2f_{-1}$.
  • 8 Show that $p_{n+1}(x)-p_n(x)$ $=f[x_0,\dots,x_{n+1}]\,\omega_{n+1}(x)$. In Example 3, add the node $5$ and use this "next term" to estimate the error of $p_2(3)$; compare with the true error.
Check-lab: a divided-difference calculator (exact fractions for integer, decimal or fraction input)
1 First order: $f[0,1]=-2$, $f[1,3]=-2$, $f[3,4]=10$; second: $f[0,1,3]=0$, $f[1,3,4]=4$; third: $f[0,1,3,4]=1$. So $p=2-2x+0\cdot x(x-1)$ $+1\cdot x(x-1)(x-3)$ $=x^3-4x^2+x+2$. $f[0,1,3]=0$ only says the quadratic through the first three points is linear (they are collinear); it says nothing about the degree of $p$.
2 For $n=0$ both sides are $f(x_0)$. Assume the formula for $n$ points, apply it to $\{x_1,\dots,x_n\}$ and $\{x_0,\dots,x_{n-1}\}$ and subtract. The coefficient of $f(x_0)$ is $-\frac{1}{(x_n-x_0)\prod_{j=1}^{n-1}(x_0-x_j)}=\frac1{\prod_{j=1}^{n}(x_0-x_j)}$, of $f(x_n)$ similarly $\frac1{\prod_{j\lt n}(x_n-x_j)}$, and for $0\lt i\lt n$ it is $\frac{1}{x_n-x_0}\Big[\frac{1}{x_i-x_n}-\frac1{x_i-x_0}\Big]\frac1{\prod_{j\ne0,i,n}(x_i-x_j)}$ $=\frac{1}{\prod_{j\ne i}(x_i-x_j)}$, since $\frac1{x_i-x_n}-\frac1{x_i-x_0}=\frac{x_n-x_0}{(x_i-x_0)(x_i-x_n)}$.
3 $n=1$: $\frac{1/x_1-1/x_0}{x_1-x_0}=-\frac1{x_0x_1}$. Step: $\frac{1}{x_{n}-x_0}\Big[\frac{(-1)^{n-1}}{x_1\cdots x_n}-\frac{(-1)^{n-1}}{x_0\cdots x_{n-1}}\Big]$ $=\frac{(-1)^{n-1}(x_0-x_n)}{(x_n-x_0)\,x_0\cdots x_n}=\frac{(-1)^n}{x_0\cdots x_n}$.
4 $x^{n+1}-\omega_{n+1}(x)$ has degree $\le n$ and interpolates $x^{n+1}$ at the nodes, so it is $p_n$; its coefficient of $x^n$ is $-(\text{coefficient of }x^n\text{ in }\omega_{n+1})$ $=x_0+\dots+x_n$ (Vieta). By Theorem 5.26 this is $f[x_0,\dots,x_n]$.
5 Differences: $\Delta$: $20,15,12,8$; $\Delta^2$: $-5,-3,-4$; $\Delta^3$: $2,-1$; $\Delta^4$: $-3$. 1986: $s=0.5$, $46+10+0.625+0.125+0.117=56.87$ thousand. 2018: $x_n=2021$, $s=-0.3$, $101-2.4+0.42$ $+0.0595+0.1205$ $=99.20$ thousand. (The irregular third and fourth differences warn that the cubic and quartic terms are not reliable; the quadratic estimates $56.6$ and $99.0$ thousand are about as good as the data allow.)
6 $p(x)-p(x_0)$ vanishes at $x_0$, so it is divisible by $x-x_0$: $p[x_0,x]=\frac{p(x)-p(x_0)}{x-x_0}$ is a polynomial $q_1$ of degree $n-1$ (its leading coefficient is that of $p$), and its value at $x_0$ is $p'(x_0)$. By symmetry $p[x_0,\dots,x_{k-1},x]=q_{k-1}[x_{k-1},x]$ with $q_{k-1}(x)=p[x_0,\dots,x_{k-2},x]$; induction on $k$ gives degree $n-k$.
7 $p=f[x_0]+f[x_0,x_1](x-x_0)$ $+f[x_0,x_1,x_{-1}](x-x_0)(x-x_1)$. By Theorem 5.28 (and symmetry) $f[x_0,x_1]=\Delta f_0/h$ and $f[x_{-1},x_0,x_1]=\Delta^2f_{-1}/(2h^2)$, while $(x-x_0)(x-x_1)=s(s-1)h^2$. Hence $p=f_0+s\Delta f_0+\frac{s(s-1)}2\Delta^2f_{-1}$.
8 $p_{n+1}-p_n$ has degree $\le n+1$, vanishes at $x_0,\dots,x_n$ and has leading coefficient $f[x_0,\dots,x_{n+1}]$ (Theorem 5.26). For $\log$ at $1,2,4,5$: $f[1,2,4,5]=0.018\,60$, and the next term at $x=3$ is $0.018\,60\cdot\omega_3(3)$ $=0.018\,60\cdot(-2)=-0.037\,2$. The true error is $-0.056\,6$: the estimate has the right sign and order of magnitude (it is exact only if $f[1,2,4,x]$ is constant).
IV
Hermite interpolation, splines and the choice of nodes.
  • 1 Find the cubic $p$ with $p(0)=1$, $p'(0)=0$, $p(1)=2$, $p'(1)=5$, using divided differences with repeated nodes, and compute $p(\tfrac12)$.
  • 2 Derive the four cubic Hermite basis functions on $[0,1]$ and show that the piecewise cubic Hermite interpolant on knots with spacing $h$ has error at most $\tfrac{h^4}{384}\max|f^{(4)}|$.
  • 3 Find the quadratic $p$ with $p(0)=f(0)$, $p'(0)=f'(0)$, $p(1)=f(1)$ and its error term.
  • 4 Let $S(x)=x^3-x$ on $[0,1]$ and $S(x)=a(x-1)^3$ $+b(x-1)^2+2(x-1)$ on $[1,2]$. For which $a,b$ is $S$ a cubic spline? A natural cubic spline?
  • 5 Find the natural cubic spline through $(0,1)$, $(1,0)$, $(2,1)$ and evaluate it at $x=\tfrac12$. Compare with the interpolating quadratic.
  • 6 Verify that the moments $M_i=6x_i$ of $f(x)=x^3$ satisfy the clamped spline equations for the data of Example 7 with $s'(0)=0$, $s'(3)=27$, and conclude that the clamped spline is $x^3$.
  • 7 Prove that the cubic splines with knots $x_0\lt\dots\lt x_n$ form a vector space of dimension $n+3$, with basis $1,x,x^2,x^3$, $(x-x_1)_+^3,\dots,(x-x_{n-1})_+^3$, where $u_+=\max(u,0)$.
  • 8 Compare $\max_{[-1,1]}|\omega_3|$ for the nodes $-1,0,1$ with that for the three Chebyshev nodes.
  • 9 (Experiment.) Use Interactive 1 to record $\max|f-p_n|$ for the Runge function at $n=4,8,12,16$ with equally spaced and with Chebyshev nodes, and for $f=|x|$ at $n=10,20$. Which bound of this section explains each trend?
1 Nodes $0,0,1,1$: $f[0,0]=0$, $f[0,1]=1$, $f[1,1]=5$; $f[0,0,1]=1$, $f[0,1,1]=4$; $f[0,0,1,1]=3$. So $p=1+0\cdot x+1\cdot x^2+3x^2(x-1)$ $=1-2x^2+3x^3$, and $p(\tfrac12)=1-\tfrac12+\tfrac38=\tfrac78$. Check: $p'(x)=-4x+9x^2$, $p'(1)=5$.
2 Write $H=a+bt+ct^2+dt^3$ and impose the four conditions for each data item: $h_{00}=1-3t^2+2t^3$ (value $1$ at $0$), $h_{01}=3t^2-2t^3$ (value $1$ at $1$), $h_{10}=t-2t^2+t^3$ (slope $1$ at $0$), $h_{11}=t^3-t^2$ (slope $1$ at $1$); on $[a,a+h]$ the slope terms are multiplied by $h$. By Theorem 5.29(4) with $n=1$ the error on $[x_{i-1},x_i]$ is $\frac{f^{(4)}(\xi)}{24}(x-x_{i-1})^2(x-x_i)^2$, and $(x-x_{i-1})^2(x-x_i)^2\le(h/2)^4=h^4/16$; $\frac1{24\cdot16}=\frac1{384}$.
3 Node list $0,0,1$: $p(x)=f(0)+f'(0)x$ $+\big(f(1)-f(0)-f'(0)\big)x^2$, since $f[0,0,1]=f[0,1]-f[0,0]$. The error is $\frac{f'''(\xi)}{6}x^2(x-1)$ (same Rolle argument: $g$ has a double zero at $0$ and simple zeros at $1$ and $x$).
4 At $x=1$: values $0=0$; slopes $S'(1^-)=3-1=2$ and $S'(1^+)=2$; second derivatives $S''(1^-)=6$ and $S''(1^+)=2b$. So $S$ is a cubic spline iff $b=3$ ($a$ arbitrary). Natural: $S''(0)=0$ holds automatically, and $S''(2)=6a+2b=6a+6=0$ gives $a=-1$.
5 One unknown: $4M_1=6(1-0+1)=12$, $M_1=3$. On $[0,1]$: $s(x)=\tfrac12x^3+(1-x)$ $+\big(0-\tfrac12\big)x$ $=\tfrac12x^3-\tfrac32x+1$, and $s(2-x)=s(x)$ by symmetry. $s(\tfrac12)=\tfrac1{16}-\tfrac34+1=0.3125$; the quadratic $(x-1)^2$ gives $0.25$. The spline is flatter at the ends ($s''(0)=0$) and dips less steeply.
6 $M=(0,6,12,18)$, $h=1$, $d=(1,7,19)$: $2M_0+M_1=6=6(d_1-0)$ ✓; $M_0+4M_1+M_2=36=6(d_2-d_1)$ ✓; $M_1+4M_2+M_3=72=6(d_3-d_2)$ ✓; $M_2+2M_3=48=6(27-d_3)$ ✓. So $x^3$ (whose moments these are) is a clamped spline for these data, and by uniqueness (Theorem 5.30) it is the clamped spline: the whole error in Example 7 comes from the natural end conditions.
7 The splines are closed under addition and scalar multiples, so they form a vector space $\mathcal{S}$. Each listed function is a cubic spline ($(x-x_i)_+^3$ is $C^2$). Independence: on $[x_0,x_1]$ only $1,x,x^2,x^3$ are nonzero, so their coefficients in a vanishing combination are $0$; then on $[x_1,x_2]$ only $(x-x_1)_+^3$ remains, so its coefficient is $0$; and so on. Spanning: given $s\in\mathcal{S}$, on each knot $x_i$ the jump of $s'''$ is some $c_i$, while $s,s',s''$ are continuous; so $s-\sum c_i(x-x_i)_+^3/6$ has continuous $s'''$ as well and is a single cubic. Dimension $4+(n-1)=n+3$ — hence the two extra end conditions in Theorem 5.30.
8 Equally spaced: $\omega_3=x^3-x$, maximum $\frac{2}{3\sqrt3}=0.385$ at $x=\pm\frac1{\sqrt3}$. Chebyshev nodes $0,\pm\frac{\sqrt3}2$: $\omega_3=x^3-\tfrac34x=\tfrac14T_3(x)$, maximum $\tfrac14$ (Theorem 5.34). A $35\%$ smaller error bound.
9 Runge function: equally spaced $0.438,\ 1.045,\ 3.66,\ 14.4$; Chebyshev $0.402,\ 0.171,\ 0.069,\ 0.033$. For $|x|$: equally spaced $0.66$ ($n=10$) and $95$ ($n=20$); Chebyshev $0.055$ and $0.028$. Equally spaced nodes have exploding Lebesgue constants and $\max|\omega_{n+1}|$ much larger near the ends (Theorem 5.33); Chebyshev nodes minimise $\max|\omega_{n+1}|$ (Theorem 5.34) and have $\Lambda_n=O(\log n)$, so they converge for these Lipschitz functions — geometrically for the analytic Runge function, only like $1/n$ for $|x|$.
🎯 Exam corner CSIR Part BCSIR Part CGATE MA

E1. CSIR Part B GATE MA With step $h=1$, the third forward difference $\Delta^3f(0)$ of $f(x)=x^4$ equals (A) $24$; (B) $36$; (C) $60$; (D) $0$.

Idea Theorem 5.21(3): $\Delta^3f_0=f_3-3f_2+3f_1-f_0$.
Compute $81-3\cdot16+3\cdot1-0=36$. (In general $\Delta^3x^4=24h^3x+36h^4$; (A) is its $x$-coefficient, and (D) would be right for a cubic.)
Answer (B) $36$.

E2. CSIR Part B Let $p$ be the polynomial of degree at most $3$ that agrees with $f(x)=x^4$ at $x=-1,0,1,2$. Then $p(3)$ equals (A) $81$; (B) $63$; (C) $57$; (D) $24$.

Idea $x^4-p(x)$ is monic of degree $4$ and vanishes at the four nodes, so $x^4-p(x)=(x+1)x(x-1)(x-2)$ (uniqueness, Theorem 5.23; equivalently Theorem 5.24 with $f^{(4)}/4!=1$).
Compute $p(3)=81-4\cdot3\cdot2\cdot1=57$. (A) forgets that $p\ne f$; (D) is $\omega_4(3)$ itself.
Answer (C) $57$.

E3. CSIR Part B GATE MA The function $s(x)=1+x-x^3$ on $[0,1]$, $s(x)=a+b(x-1)$ $+c(x-1)^2+d(x-1)^3$ on $[1,2]$ is a natural cubic spline on $[0,2]$ with knots $0,1,2$. Then $s(2)$ equals (A) $-3$; (B) $-5$; (C) $-1$; (D) $1$.

Smoothness at 1 From the left: $s(1)=1$, $s'(1)=1-3=-2$, $s''(1)=-6$. So $a=1$, $b=-2$, $2c=-6$, $c=-3$.
Natural ends $s''(0)=-6\cdot0=0$ holds; $s''(2)=2c+6d=-6+6d=0$ gives $d=1$.
Answer (A): $s(2)=1-2-3+1=-3$. ((B) comes from $d=-1$.)

E4. CSIR Part C Let $f:\mathbb{R}\to\mathbb{R}$ and let $x_0,x_1,\dots$ be distinct. Which of the following are true? (One or more options may be correct.) (A) $f[x_0,x_1,x_2]=f[x_2,x_0,x_1]$ for every $f$. (B) If $f$ is a polynomial of degree $n$, then $f[x_0,\dots,x_{n+1}]=0$ for all distinct $x_0,\dots,x_{n+1}$. (C) If $x_i=x_0+ih$, then $\Delta^nf(x_0)=n!\,h^n\,f[x_0,\dots,x_n]$. (D) If $f\in C^2(\mathbb{R})$, then $f[x_0,x_1,x_2]=\tfrac12f''(x_1)$ whenever $x_0\lt x_1\lt x_2$.

(A) True Divided differences are symmetric in their arguments (Theorem 5.27(1)).
(B) True Theorem 5.27(4): the $(n+1)$-th divided difference of a polynomial of degree $n$ vanishes, whatever the nodes.
(C) True Theorem 5.28.
(D) False The mean value property gives $\tfrac12f''(\xi)$ for some $\xi\in(x_0,x_2)$, not $\xi=x_1$. For $f=x^3$ and nodes $0,1,3$: $f[0,1,3]=0+1+3=4$ (Exercise III.4) but $\tfrac12f''(1)=3$.
Answer (A), (B) and (C).

E5. CSIR Part C For $n\ge1$ let $p_n$ be the polynomial of degree $\le n$ interpolating $f$ at $n+1$ nodes in $[-1,1]$. Which of the following are true? (A) For $f(x)=e^x$ and equally spaced nodes, $p_n\to f$ uniformly on $[-1,1]$. (B) For $f(x)=1/(1+25x^2)$ and equally spaced nodes, $\max_{[-1,1]}|f-p_n|\to\infty$. (C) If the nodes are the Chebyshev nodes, then $p_n\to f$ uniformly for every continuous $f$ on $[-1,1]$. (D) For the Chebyshev nodes, $\max_{[-1,1]}\big|\prod_{i=0}^n(x-x_i)\big|=2^{-n}$.

(A) True $M_{n+1}=e$ for all $n$ and $h=2/n$, so by Theorem 5.25 $\max|f-p_n|\le\dfrac{e\,(2/n)^{n+1}}{4(n+1)}\to0$.
(B) True Runge's phenomenon (Theorem 5.33): the error near $\pm1$ grows without bound ($59.8$ at $n=20$).
(C) False By Faber's theorem no array of nodes works for every continuous function; for Chebyshev nodes the Lebesgue constants $\Lambda_n\to\infty$, and the uniform boundedness principle produces a continuous $f$ with $\sup_n\|p_n\|_\infty=\infty$. Uniform convergence does hold under a Lipschitz condition.
(D) True The nodal polynomial is $2^{-n}T_{n+1}$ and $\max|T_{n+1}|=1$ (Theorem 5.34).
Answer (A), (B) and (D).

E6. CSIR Part C Let $a=x_0\lt\dots\lt x_n=b$ ($n\ge2$), let $f\in C^4[a,b]$, and let $s$ be the natural cubic spline interpolating $f$ at the knots. Which of the following are true? (A) $s\in C^2[a,b]$. (B) If $f$ is a cubic polynomial, then $s=f$. (C) $\int_a^b(s'')^2\le\int_a^b(g'')^2$ for every $g\in C^2[a,b]$ with $g(x_i)=f(x_i)$ for all $i$. (D) The piecewise cubic Hermite interpolant (using $f$ and $f'$ at every knot) always belongs to $C^2[a,b]$.

(A) True A cubic spline is $C^2$ by definition (Definition 5.20 with $k=3$).
(B) False Only if $f''(a)=f''(b)=0$. For $f=x^3$ on knots $0,1,2,3$, $s(2.5)=16.45\ne15.625$ (Example 7).
(C) True Holladay's theorem (Theorem 5.31).
(D) False It is only $C^1$: for $f=x^4$ and knots $0,1,3$ the second derivative is $10$ from the left of $1$ and $4$ from the right.
Answer (A) and (C).
🧑‍🏫 For the teacher

Suggested plan — 3 lectures × 60 min.

  1. Finite differences. Definitions 5.15–5.16 with one difference table on the board; Theorem 5.21 as operator algebra (let students derive $\Delta\nabla=\delta^2$ themselves); Theorem 5.22 with proofs of (1)–(4). Example 1: show the fan of an error before revealing the answer, then project Interactive 2 with the error at $x_3$ switched on. Example 2 as a five-minute Part C drill.
  2. The interpolating polynomial. Theorem 5.23 (uniqueness is the key idea of the lecture), Theorem 5.24 with the full Rolle proof, Theorem 5.25; Example 3. Divided differences: Theorem 5.26 via Neville–Aitken, Theorem 5.27(1)–(4); Example 4 on the board. Theorem 5.28 and Example 5; run Interactive 2 term by term on the $\sqrt x$ data to show when the terms reach rounding level.
  3. Derivatives, splines, nodes. Theorem 5.29 (proof of (1) and (4)) and Example 6; Theorem 5.30 derived on the board, Theorem 5.31 with full proof, Example 7. Finish with Runge: show the table, then project Interactive 1 (equally spaced → Chebyshev → spline), Theorem 5.34 with proof. Exam corner E2, E3 and E5 live.

Discussion questions. (1) The interpolating polynomial is unique, so why do we need Lagrange's, Newton's, Gauss's and Stirling's formulas? What does each one make easy? (2) The Runge function is infinitely differentiable on all of $\mathbb{R}$, yet interpolation fails. Why does the location of its complex poles decide the matter? (3) The natural spline minimises $\int(s'')^2$. Is that the right criterion for a car body, a railway track, or a font outline, and what would you minimise instead?

Misconceptions to watch for. "More nodes always give a better interpolant"; "$\Delta$ obeys the product rule"; "$\Delta^3f=0$ on a grid makes $f$ a quadratic"; the sign of $s$ in the backward formula; "$f[x_0,x_1,x_2]=\tfrac12f''(x_1)$"; "a natural spline reproduces cubics"; "Hermite interpolation at three nodes gives a cubic" (it gives degree $\le5$); treating $\xi$ in the error formula as a fixed number; extrapolating with a high-degree interpolant.

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

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

Research question. A temperature or pressure sensor — in an industrial furnace, a hospital incubator or a weather balloon — is calibrated at $n+1$ reference points, and every calibration reading carries a small measurement error, say at most $\varepsilon=0.01$ in suitable units. Between the reference points the instrument uses an interpolant of the calibration data. How much can the interpolant amplify the measurement errors, and which scheme — a polynomial at equally spaced points, a polynomial at Chebyshev points, or a natural cubic spline — should a calibration laboratory recommend?

Why it matters. Calibration tables underpin traceable measurement in medicine, manufacturing and climate science. A scheme that turns a $0.01$ error in the data into a $10$-unit error between the reference points is useless however accurate it is for exact data; the Lebesgue constant $\Lambda_n$ of this section is exactly the worst-case amplification factor.

What to do.

  1. Compute $\Lambda_n=\max_{[-1,1]}\sum_i|L_i(x)|$ (on $10^4$ sample points) for equally spaced and for Chebyshev nodes, $n=5,10,15,20$. Plot $\log\Lambda_n$ against $n$ and against $\log n$.
  2. Show that the worst case is attained: for a given $x^*$, the data errors $\varepsilon\,\operatorname{sign}L_i(x^*)$ produce an error $\varepsilon\sum_i|L_i(x^*)|$ at $x^*$.
  3. Take a smooth calibration curve, e.g. $f(x)=\log(2+x)$ on $[-1,1]$, add independent random errors uniform on $[-\varepsilon,\varepsilon]$ to the $n+1$ readings, and record $\max_{[-1,1]}|p_n^{\text{noisy}}-p_n|$ over $200$ trials. Compare the typical and the largest values with $\varepsilon\Lambda_n$.
  4. Repeat steps 1 and 3 for natural cubic splines on equally spaced knots (the "Lebesgue constant" of a spline is $\max\sum_i|s_i(x)|$, where $s_i$ is the spline with data $\delta_{ij}$).

Tools: Python (NumPy, SciPy's CubicSpline) or a spreadsheet; Interactive 1 for intuition about where the amplification happens.

Hand in: A table of Lebesgue constants, a plot of the noise experiment, and a one-paragraph recommendation to a calibration laboratory.

Going further. Read about the barycentric form of Lagrange interpolation and why, with Chebyshev points, it allows stable interpolation with thousands of nodes; or about least-squares fitting, which trades exact interpolation for robustness to noise.

Instructor note: approximate Lebesgue constants — equally spaced: $\Lambda_5\approx3.11$, $\Lambda_{10}\approx29.9$, $\Lambda_{15}\approx512$, $\Lambda_{20}\approx10\,987$ (growth like $2^{n+1}/(e\,n\log n)$, largest between the two outermost nodes); Chebyshev: $2.10$, $2.49$, $2.73$, $2.90$ (growth like $\tfrac2\pi\log n$); natural cubic splines on equally spaced knots: about $1.47$ for $n=5$ and $1.55$ for $n=10$ and $n=20$ (bounded). In the random experiment the observed amplification is usually well below $\varepsilon\Lambda_n$ (random signs partly cancel) but still grows exponentially for equally spaced nodes, so a degree-$20$ polynomial at equally spaced points amplifies errors of $0.01$ to errors of order $1$–$10$ near the ends. Students should conclude that Chebyshev nodes are excellent when the laboratory may choose the reference points, and splines when the points are fixed (e.g. equally spaced).

🧪 Self-check quiz

0/5 correct

Q1. In terms of the shift operator $E$ (step $h$), the backward difference operator $\nabla$ equals

Q2. Let $p$ be a polynomial of degree $4$ with leading coefficient $2$, and let $h=0.5$. Then $\Delta^4p$ is the constant

Q3. The values $f(x_i)$ and the slopes $f'(x_i)$ are prescribed at three distinct nodes. The Hermite interpolating polynomial is unique in the class of polynomials of degree at most

Q4. A cubic spline $s$ on $[a,b]$ interpolating given data is called natural if

Q5. Let $p_n$ interpolate $f(x)=1/(1+25x^2)$ at $n+1$ equally spaced nodes in $[-1,1]$. As $n\to\infty$, $\max_{[-1,1]}|f-p_n|$