Error in polynomial interpolation

WHAT are we measuring?

The central result we will derive:

WHY does this exact shape appear? (Derivation from scratch)

We want to show $E(x) = \dfrac{f^{(n+1)}(\xi)}{(n+1)!}\,\omega(x)$ .

Step 1 — Fix a point and build a helper function. Pick any point $\bar x$ that is not a node (if it is a node the error is $0$ and we're done). We don't yet know the error there; call the unknown constant $K$ defined by $f(\bar x) - p_n(\bar x) = K\,\omega(\bar x).$ Why this step? We are forcing the error to have the form (constant) $\times\omega$ . If we can prove $K=\dfrac{f^{(n+1)}(\xi)}{(n+1)!}$ , the formula is done. This is the Feynman move: assume the answer's shape, then pin it down.

Step 2 — Define an auxiliary function in a new variable $t$ : $g(t) = f(t) - p_n(t) - K\,\omega(t).$ Why this step? We want a function that vanishes at lots of points so we can apply Rolle repeatedly.

Step 3 — Count the zeros of $g$ .

At each node: $f(x_i)=p_n(x_i)$ and $\omega(x_i)=0$ , so $g(x_i)=0$ . That's $n+1$ zeros.
At $t=\bar x$ : by definition of $K$ , $g(\bar x)=f(\bar x)-p_n(\bar x)-K\omega(\bar x)=0$ . One more zero.

So $g$ has at least $n+2$ distinct zeros in $[a,b]$ .

Step 4 — Apply Rolle's theorem repeatedly. Why? Rolle says between two zeros of $g$ lies a zero of $g'$ .

$g$ has $\ge n+2$ zeros $\Rightarrow$ $g'$ has $\ge n+1$ zeros.
$g''$ has $\ge n$ zeros.
… $g^{(n+1)}$ has $\ge 1$ zero. Call it $\xi$ .

Step 5 — Differentiate $g$ exactly $n+1$ times. $g^{(n+1)}(t) = f^{(n+1)}(t) - p_n^{(n+1)}(t) - K\,\omega^{(n+1)}(t).$

$p_n$ has degree $\le n$ $\Rightarrow p_n^{(n+1)}\equiv 0$ .
$\omega(t)=t^{n+1}+(\text{lower})$ , so $\omega^{(n+1)}(t)=(n+1)!$ (a constant).

Hence $g^{(n+1)}(t)=f^{(n+1)}(t)-K\,(n+1)!.$

Step 6 — Evaluate at $\xi$ . Since $g^{(n+1)}(\xi)=0$ : $0=f^{(n+1)}(\xi)-K(n+1)! \;\Rightarrow\; K=\frac{f^{(n+1)}(\xi)}{(n+1)!}.$

Step 7 — Substitute back. From Step 1, $f(\bar x)-p_n(\bar x)=K\,\omega(\bar x)=\frac{f^{(n+1)}(\xi)}{(n+1)!}\,\omega(\bar x).\qquad\blacksquare$

Figure — Error in polynomial interpolation

HOW to use it — error bound

We rarely know $\xi$ , so we bound it. Let $M_{n+1}=\max_{[a,b]}|f^{(n+1)}(x)|$ . Then $|E(x)| \le \frac{M_{n+1}}{(n+1)!}\,|\omega(x)|,\qquad |\omega(x)|\le \prod_{i=0}^n |x-x_i|.$

Worked examples

Worked example Example 1 — Linear interpolation error (

$n=1$ ) Two nodes $x_0,x_1$ with $h=x_1-x_0$ . Then $E(x)=\frac{f''(\xi)}{2!}(x-x_0)(x-x_1).$ Why this step? $n+1=2$ so we need $f''$ and $\omega(x)=(x-x_0)(x-x_1)$ . The factor $(x-x_0)(x-x_1)$ is maximised in size at the midpoint $x=\tfrac{x_0+x_1}{2}$ , where $|(x-x_0)(x-x_1)|=\tfrac{h^2}{4}$ . Why? It's a downward parabola with roots $x_0,x_1$ ; vertex is at the midpoint. $\therefore \max|E|\le \frac{h^2}{8}\,\max|f''|.$ This is the classic trapezoidal-rule-style $O(h^2)$ error.

Worked example Example 2 — Numbers: interpolate

$f(x)=\ln x$ on $[1,2]$ linearly $f''(x)=-1/x^2$ , so $\max_{[1,2]}|f''| = |{-1/1^2}| = 1$ (largest at $x=1$ ). $h=1$ . Bound: $|E|\le \dfrac{h^2}{8}\cdot 1 = \dfrac{1}{8}=0.125.$ Check at $x=1.5$ : true $\ln 1.5=0.405465$ ; line $p(x)=\ln1+(\ln2-\ln1)(x-1)=0.693147(x-1)$ gives $p(1.5)=0.346574$ . Actual error $=0.405465-0.346574=0.058891$ , which indeed $\le 0.125$ . ✓ Why bound is loose: $\xi$ near $1.5$ gives $f''\approx -1/1.5^2=-0.444$ , not the worst-case $-1$ .

Worked example Example 3 — Quadratic interpolation (

$n=2$ ) Three equally spaced nodes $x_0,x_0+h,x_0+2h$ . $E(x)=\frac{f'''(\xi)}{6}(x-x_0)(x-x_0-h)(x-x_0-2h).$ Maximising $|\omega|$ over the interval (calculus on the cubic) gives $\max|\omega|=\dfrac{2h^3}{3\sqrt3}$ . Why this step? Differentiate $\omega$ , set to zero, find the interior extremum, plug back. So $\max|E|\le \frac{2h^3}{3\sqrt3\cdot 6}\max|f'''| = \frac{h^3}{9\sqrt3}\max|f'''|=O(h^3).$ Pattern: $n+1$ nodes $\Rightarrow$ error $O(h^{\,n+1})$ for smooth $f$ .

Common mistakes (steel-manned)

Recall Feynman: explain it to a 12-year-old

Imagine connecting dots on a graph with a smooth curve. You only know the height at the dots. Between dots you're guessing. How wrong can your guess be? Two things matter: how far you are from the nearest dots (the $\omega$ part — the more dots nearby, the safer), and how twisty the real line is (the derivative part — a straight road is easy to guess, a roller-coaster is not). The formula just multiplies "twistiness" by "distance from dots" and divides by a big factorial that softens it. Surprisingly, packing dots more tightly near the edges (Chebyshev) makes the worst guess much better.

Active recall

What is the interpolation error formula for degree-

n

interpolation?

E(x)=f(x)-p_n(x)=\dfrac{f^{(n+1)}(\xi)}{(n+1)!}\prod_{i=0}^n (x-x_i)

, with

\xi\in(a,b)

What smoothness condition does the error formula require?

f\in C^{n+1}[a,b]

, i.e.

f

has

n+1

continuous derivatives.

What is the node polynomial

\omega(x)

\omega(x)=\prod_{i=0}^n (x-x_i)

, which vanishes at every interpolation node.

In the derivation, why does

p_n^{(n+1)}\equiv 0

Because

p_n

has degree

\le n

, differentiating

n+1

times kills it.

What gives the

(n+1)!

in the denominator?

\omega(t)=t^{n+1}+\dots

\omega^{(n+1)}(t)=(n+1)!

, appearing when Rolle's theorem is applied

n+1

times.

How many zeros does the helper

g(t)

have, and why?

At least

n+2

: one at each of the

n+1

nodes plus one at the chosen point

\bar x

Error bound for linear interpolation with spacing

h

|E|\le \dfrac{h^2}{8}\max|f''|

Maximum of

|\omega|

for two nodes occurs where?

At the midpoint, value

h^2/4

What is the Runge phenomenon?

With equally spaced nodes, increasing the degree can make the interpolation error blow up near the endpoints (e.g. for

1/(1+25x^2)

Which two factors control the size of the interpolation error?

The high derivative

f^{(n+1)}

(function's curviness, not controllable) and

\omega(x)

(node placement, controllable).

Why do Chebyshev nodes help?

They cluster near the endpoints and minimise

\max|\omega(x)|

, reducing worst-case error and avoiding Runge oscillations.

For

n+1

equally spaced nodes, the error is what order in

h

O(h^{\,n+1})

for sufficiently smooth

f

Connections

Lagrange Interpolation — builds the $p_n$ whose error this is.
Newton Divided Differences — error term equals next divided difference $f[x_0,\dots,x_n,x]\,\omega(x)$ .
Taylor's Theorem with Remainder — limiting case as all nodes coalesce.
Rolle's Theorem / Mean Value Theorem — engine of the derivation.
Runge Phenomenon and Chebyshev Nodes — node-choice consequences.
Numerical Integration — Newton–Cotes error inherits this $\omega$ factor.

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, polynomial interpolation mein hum ek unknown function $f(x)$ ko ek polynomial $p_n(x)$ se replace karte hain jo diye gaye points (nodes) se exactly guzarta hai. Lekin points ke beech mein hum sirf guess kar rahe hote hain. Toh sawaal yeh hai: yeh guess kitni galat ho sakti hai? Iska answer error formula deta hai: $E(x)=\frac{f^{(n+1)}(\xi)}{(n+1)!}\,\omega(x)$ , jahan $\omega(x)=\prod (x-x_i)$ saare nodes ka product hai.

Is formula ko samajhne ke do simple parts hain. Pehla part $f^{(n+1)}$ — yeh batata hai function kitna "twisty" hai. Agar function bahut wiggle karta hai (high derivative bada), toh error bada. Yeh part aapke control mein nahi — function ki galti hai. Doosra part $\omega(x)$ — yeh aapke control mein hai, kyunki aap nodes choose karte ho. Jaha nodes paas-paas hote hain, $\omega$ chhota rehta hai aur error kam. Isliye Chebyshev nodes (jo endpoints ke paas zyada dense hote hain) error ko bahut acche se kam kar dete hain.

Derivation ka trick simple hai: ek helper function banao jo nodes par aur ek chuni hui point par zero ho — total $n+2$ zeros. Phir Rolle's theorem baar-baar lagao; har baar ek derivative ka zero milta hai, aur $n+1$ baar mein $g^{(n+1)}$ ka zero $\xi$ mil jaata hai. Wahin se $(n+1)!$ aur $f^{(n+1)}(\xi)$ pop out ho jaate hain. Bilkul Taylor series ke remainder jaisa, bas single point ki jagah spread-out nodes.

Ek important warning: zyada nodes daalne se hamesha error kam nahi hota! Equally spaced nodes ke saath degree badhane par endpoints ke paas error phat sakta hai — isko Runge phenomenon kehte hain. Isliye smartly nodes choose karo ya splines use karo.

WHAT are we measuring?

WHY does this exact shape appear? (Derivation from scratch)

HOW to use it — error bound

Worked examples

Common mistakes (steel-manned)

Active recall

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Numerical Methods

Connections