Exercises — Error in polynomial interpolation

WHAT we count: $4$ nodes means $n+1=4$, so $n=3$. The polynomial has degree $\le 3$. WHICH derivative: the formula uses $f^{(n+1)}=f^{(4)}$, divided by $(n+1)!=4!=24$. $E(x)=\frac{f^{(4)}(\xi )}{24}(x-x_0)(x-x_1)(x-x_2)(x-x_3).$ Answer: $n=3$, and $f^{(4)}$ appears.

Condition: $f\in C^{n+1}[a,b]$ — $f$ has $n+1$ continuous derivatives on the interval. Why: the derivation differentiates the helper function $g$ exactly $n+1$ times (Step 5 of the parent proof), so $f^{(n+1)}$ must exist and be continuous for Rolle to keep producing zeros.

$\omega (x)=(x-0)(x-1)(x-3)=x(x-1)(x-3).$ At $x=2$: $\omega (2)=2\cdot (2-1)\cdot (2-3)=2\cdot 1\cdot (-1)=-2.$ Answer: $\omega (x)=x(x-1)(x-3)$, and $\omega (2)=-2$.

WHAT: linear means $n=1$, so we use $f^{\prime \prime }$ and $\omega (x)=(x-0)(x-0.2)$. $E(x)=\frac{f^{\prime \prime }(\xi )}{2!}x(x-0.2).$ Bound the derivative: $f^{\prime \prime }(x)=-\cos x$, so $|f^{\prime \prime }|\le 1$ on $[0,0.2]$ (largest at $x=0$, $|-\cos 0|=1$). Thus $M_2=1$. Evaluate $\omega$ at the point: $\omega (0.1)=0.1\cdot (0.1-0.2)=0.1\cdot (-0.1)=-0.01$, so $|\omega (0.1)|=0.01$. Combine: $|E(0.1)|\le \frac{M_2}{2}|\omega (0.1)|=\frac{1}{2}\cdot 0.01=\mathrm{0.005.}$ Answer: $|E(0.1)|\le 0.005$.

WHAT $h$ is here: the two nodes are $0$ and $0.2$, so the node spacing is $h=x_1-x_0=0.2$, and $\max |f^{\prime \prime }|=1$. $\max |E|\le \frac{h^2}{8}\cdot 1=\frac{0.04}{8}=\mathrm{0.005.}$ WHY they match: the midpoint of $[0,0.2]$ is $x=0.1$, and the midpoint is exactly where $|\omega |=h^2/4=0.01$ is largest. So Exercise 2.1's pointwise bound at the midpoint equals the global worst-case bound. Answer: $0.005$ — identical, because $0.1$ is the worst point.

WHERE the $\frac{2h^3}{3\sqrt{3}}$ comes from (see figure): the node polynomial for three equally spaced nodes is a cubic $\omega (x)=(x-x_0)(x-x_0-h)(x-x_0-2h)$. It crosses zero at the three nodes and has two interior humps — one positive, one negative — of equal size (the red curve). To find the hump height we do calculus: set ${\omega }^{\prime }(x)=0$, solve for the two turning points, and plug back. Doing this (parent, Example 3) gives the peak magnitude $\frac{2h^3}{3\sqrt{3}}$. The figure shows the two symmetric red humps whose height is exactly this value. WHAT: $n=2$, so we need $f^{\prime \prime \prime }$. For $f=e^x$, $f^{\prime \prime \prime }=e^x$, and ${\max }_{[0,1]}|f^{\prime \prime \prime }|=e^1=e$. Node-polynomial max: $h=\frac{1}{2}$, so $\max |\omega |=\frac{2h^3}{3\sqrt{3}}=\frac{2\cdot (1/2{)}^3}{3\sqrt{3}}=\frac{2\cdot \frac{1}{8}}{3\sqrt{3}}=\frac{1/4}{3\sqrt{3}}=\frac{1}{12\sqrt{3}}.$ Combine: $\max |E|\le \frac{1}{6}\cdot \frac{1}{12\sqrt{3}}\cdot e=\frac{e}{72\sqrt{3}}\approx \frac{2.71828}{124.708}\approx \mathrm{0.021797.}$ Answer: $\max |E|\lesssim 0.0218$.

WHAT the object is (red curve in the figure): on $[x_0,x_1]$, $\omega (x)=(x-x_0)(x-x_1)$ is a downward-opening parabola (negative between its two roots $x_0=1,x_1=3$, which are the two black dots on the axis). It is largest in magnitude where the red parabola dips deepest. WHY calculus here: to find where a smooth curve turns, set its derivative to zero. That is precisely the question "where is the extremum?" $\omega (x)=x^2-(x_0+x_1)x+x_0{x}_1,{\omega }^{\prime }(x)=2x-(x_0+x_1)=0\Rightarrow x=\frac{x_0+x_1}{2}.$ WHAT IT LOOKS LIKE: in the figure the dashed vertical line marks $x=\frac{x_0+x_1}{2}=2$, and it meets the red curve exactly at its lowest point — the labelled arrow "$|\omega |=h^2/4$" points there. Evaluate: let $m=\frac{x_0+x_1}{2}$. Then $m-x_0=\frac{h}{2}$ and $m-x_1=-\frac{h}{2}$, so $\omega (m)=\left(\frac{h}{2}\right)(-\frac{h}{2})=-\frac{h^2}{4}\Rightarrow |\omega {|}_{\max }=\frac{h^2}{4}.$ With these nodes $h=x_1-x_0=2$, so the deepest dip is $-h^2/4=-1$, exactly the depth of the red vertex in the picture. Answer: maximum at the midpoint, value $h^2/4$. Combined with $1/2!$ this gives the famous $h^2/8$ factor.

WHAT the figure shows: the red curve is $|\omega (x)|$ for the seven equally spaced black nodes marked on the axis of $[-1,1]$. Between consecutive nodes it rises into a "hump" and drops back to zero at each node. WHAT $\omega$ measures: $|\omega (x)|={\prod }_i|x-x_i|$ is the product of distances from $x$ to every node. WHY ends are worse: a point near the middle of the node cluster has nodes on both sides, so several $|x-x_i|$ are small — the product stays small, which is why the central humps of the red curve are tiny. A point near an endpoint has all the far nodes on one side; almost every factor is large, so the product blows up — this is why the two outermost red humps tower far above the central ones (the arrow "end humps blow up" points at the tallest one). Consequence: with equally spaced nodes and high $n$, these end-humps grow explosively — this is the mechanism behind the Runge Phenomenon. Chebyshev Nodes fix it by placing nodes denser near the ends, shrinking those end-humps.

WHAT: at a node $x=x_j$, the factor $(x-x_j)$ inside $\omega (x)={\prod }_i(x-x_i)$ becomes $(x_j-x_j)=0$, so $\omega (x_j)=0$. THEREFORE $E(x_j)=\frac{f^{(n+1)}(\xi )}{(n+1)!}\cdot 0=0$ regardless of what $\xi$ is. WHY consistent: the whole point of $p_n$ is $p_n(x_j)=f(x_j)$, so $E(x_j)=f(x_j)-p_n(x_j)=0$ by construction. The formula reproduces this because $\omega$ was built to vanish at the nodes — the unknown $\xi$ never matters at a node since it is multiplied by zero.

The plan first (WHY the helper function). We want to prove the error at some chosen point $\bar{x}$ has the exact form $(\text{constant})\times \omega (\bar{x})$. Rolle's Theorem is our only tool: it says between two zeros of a function lies a zero of its derivative. To use it we need a single function that is already zero at many points. Neither $f-p_1$ (zero only at the $2$ nodes) nor $\omega$ (zero only at the nodes) alone is enough. The trick: manufacture one extra zero at $\bar{x}$ by subtracting a multiple of $\omega$ tuned so the combination vanishes there too. That is the entire reason for the shape of $g$ below — it is $f-p_1$ (which already dies at the nodes) minus $K\omega$ (which also dies at the nodes but whose free constant $K$ we bend to kill $g$ at $\bar{x}$ as well).

Step 1 — assume the shape / define $K$. Fix a non-node $\bar{x}\in (x_0,x_1)$. Choose the constant $K$ so that $f(\bar{x})-p_1(\bar{x})=K\omega (\bar{x}),\omega (t)=(t-x_0)(t-x_1).$ This is just naming the ratio; it commits us to nothing yet. If we can show $K=\frac{f^{\prime \prime }(\xi )}{2}$, we are done. Step 2 — helper function. $g(t)=f(t)-p_1(t)-K\omega (t).$ (Built exactly as motivated above.) Step 3 — count zeros. $g(x_0)=g(x_1)=0$ (nodes) and $g(\bar{x})=0$ (the way we picked $K$): three distinct zeros. Step 4 — Rolle. Three zeros of $g$ $\Rightarrow$ two zeros of $g^{\prime }$ $\Rightarrow$ one zero of $g^{\prime \prime }$; call it $\xi$. Step 5 — differentiate twice. $p_1$ is degree $\le 1\Rightarrow p_1^{\prime \prime }\equiv 0$; and $\omega (t)=t^2-(x_0+x_1)t+x_0{x}_1\Rightarrow {\omega }^{\prime \prime }(t)=2$. Hence $g^{\prime \prime }(t)=f^{\prime \prime }(t)-K\cdot 2.$ Step 6 — evaluate at $\xi$. $0=g^{\prime \prime }(\xi )=f^{\prime \prime }(\xi )-2K\Rightarrow K=\frac{f^{\prime \prime }(\xi )}{2}=\frac{f^{\prime \prime }(\xi )}{2!}.$ Step 7 — substitute. $f(\bar{x})-p_1(\bar{x})=\frac{f^{\prime \prime }(\xi )}{2}(\bar{x}-x_0)(\bar{x}-x_1).$ $■$ Matches the parent's Example 1 with $n+1=2$.

WHAT changes: each piece has node spacing $h=0.5$, and on each piece we use the linear bound $\frac{h^2}{8}\max |f^{\prime \prime }|$. Derivative: $f^{\prime \prime }(x)=-1/x^2$, $|f^{\prime \prime }|\le 1$ on $[1,2]$ (worst at $x=1$). Using this common bound $M_2=1$: $\max |E|\le \frac{h^2}{8}\cdot M_2=\frac{(0.5{)}^2}{8}\cdot 1=\frac{0.25}{8}=\mathrm{0.03125.}$ Compare: single piece with $h=1$ gave $0.125$. Halving $h$ divided the bound by $4$ — the hallmark $O(h^2)$ behaviour. Piecewise linear (small $h$) beats one big high-degree fit. Answer: $\le 0.03125$, four times smaller than the whole-interval bound.

WHAT: $\omega (x)=x^3-x$. To locate the interior extrema, set ${\omega }^{\prime }(x)=0$: ${\omega }^{\prime }(x)=3x^2-1=0\Rightarrow x=\pm \frac{1}{\sqrt{3}}.$ Evaluate: at $x=\frac{1}{\sqrt{3}}$, $\omega \left(\frac{1}{\sqrt{3}}\right)=\frac{1}{3\sqrt{3}}-\frac{1}{\sqrt{3}}=\frac{1-3}{3\sqrt{3}}=-\frac{2}{3\sqrt{3}}.$ By the odd symmetry $\omega (-x)=-\omega (x)$, the other extremum gives $+\frac{2}{3\sqrt{3}}$. Endpoints give $\omega (\pm 1)=0$. So $\max |\omega |=\frac{2}{3\sqrt{3}}\approx \mathrm{0.3849.}$ Consistency check with the parent's general formula $\frac{2h^3}{3\sqrt{3}}$: here the node spacing is $h=1$, giving $\frac{2}{3\sqrt{3}}$ — matches. ✓ Error bound: $n=2$, so $\max |E|\le \frac{\max |f^{\prime \prime \prime }|}{3!}\cdot \frac{2}{3\sqrt{3}}=\frac{2}{6\cdot 3\sqrt{3}}\max |f^{\prime \prime \prime }|=\frac{1}{9\sqrt{3}}\max |f^{\prime \prime \prime }|\approx 0.06415\max |f^{\prime \prime \prime }|.$ Answer: max at $x=\pm 1/\sqrt{3}$, value $2/(3\sqrt{3})\approx 0.3849$; bound $\frac{\max |f^{\prime \prime \prime }|}{9\sqrt{3}}$.

WHAT the two factors do: $|E|\lesssim \underset{\text{derivative knob}}{\underbrace{\frac{\max |f^{(n+1)}|}{(n+1)!}}}\cdot \underset{\text{node knob}}{\underbrace{\max |\omega |}}.$ Derivative knob: with $\max |f^{(n+1)}|\approx (n+1)!5^{n+1}$, the factorial cancels: $\frac{\max |f^{(n+1)}|}{(n+1)!}\approx 5^{n+1}\stackrel{n\to \infty }{\to }\infty .$ Node knob: for equally spaced nodes on $[-1,1]$, $\max |\omega |$ decays only like a small power/exponential that cannot beat $5^{n+1}$. So the product grows — the error blows up near the endpoints. This is exactly the Runge Phenomenon. WHY the factorial doesn't save us: the parent's mistake callout warned that $(n+1)!$ in the denominator looks like it always wins, but here the numerator carries its own $(n+1)!$ times $5^{n+1}$. Cure: switch the node knob — use Chebyshev Nodes (denser at the ends), which shrink $\max |\omega |$ to $2^{-n}$ scale, or abandon high degree entirely and use piecewise / spline interpolation. Both keep the product bounded. Answer: the $(n+1)!$ cancels against the function's own growth, leaving $\sim 5^{n+1}\to \infty$; cure = Chebyshev nodes or piecewise interpolation.

• Nodes $=n+1$; error uses $f^{(n+1)}$ over $(n+1)!$ times $\omega$.
• You control only $\omega$ (node placement); you cannot fix a wiggly $f^{(n+1)}$.
• Linear: worst at midpoint, $\max |\omega |=h^2/4$, bound $\frac{h^2}{8}{M}_2$.
• Quadratic on width-$h$ spacing: $\max |\omega |=\frac{2h^3}{3\sqrt{3}}$.
• Raising $n$ can worsen error (Runge); cure = Chebyshev nodes or piecewise fits.