Exercises — Polynomial interpolation — Lagrange form, Newton's divided differences

WHAT: Count the fitting polynomials. WHY: With $n+1=3$ points we look for a polynomial of degree $\le n=2$. Such a polynomial has $3$ free coefficients $a_0,a_1,a_2$ in $a_0+a_{1}x+a_2{x}^2$. Demanding it hit $3$ points gives $3$ linear equations — a square system. The nodes $0,2,3$ are distinct, so the Vandermonde determinant ${\prod }_{i<j}(x_j-x_i)=(2-0)(3-0)(3-2)=2\cdot 3\cdot 1=6\ne 0$. A square system with nonzero determinant has exactly one solution. Answer: exactly $1$.

WHAT: Build the switch that is on only at $x_1=2$. WHY numerator: it must be zero at the other nodes $x_0=0$ and $x_2=3$, so include factors $(x-0)$ and $(x-3)$. WHY denominator: to force $L_1(2)=1$, divide by the numerator's value at $x=2$. $L_1(x)=\frac{(x-0)(x-3)}{(2-0)(2-3)}=\frac{x(x-3)}{2\cdot (-1)}=\frac{x(x-3)}{-2}.$ Values: $L_1(0)=\frac{0}{-2}=0$, $L_1(3)=\frac{0}{-2}=0$, $L_1(2)=\frac{2(-1)}{-2}=1$. This is the Kronecker delta property $L_1(x_k)={\delta }_{1k}$. ✔

WHAT: Assemble $P(x)=\sum y_i{L}_i(x)$. Build all three switches (nodes $0,2,3$): $L_0=\frac{(x-2)(x-3)}{(0-2)(0-3)}=\frac{(x-2)(x-3)}{6},$ $L_1=\frac{x(x-3)}{(2-0)(2-3)}=\frac{x(x-3)}{-2},$ $L_2=\frac{x(x-2)}{(3-0)(3-2)}=\frac{x(x-2)}{3}.$ WHY these denominators: each is the numerator evaluated at its own node, guaranteeing $L_i(x_i)=1$. Weight by $y_i=1,5,4$: $P(x)=1\cdot \frac{(x-2)(x-3)}{6}+5\cdot \frac{x(x-3)}{-2}+4\cdot \frac{x(x-2)}{3}.$ Expand each:

• $\frac{1}{6}(x^2-5x+6)=\frac{1}{6}{x}^2-\frac{5}{6}x+1$
• $-\frac{5}{2}(x^2-3x)=-\frac{5}{2}{x}^2+\frac{15}{2}x$
• $\frac{4}{3}(x^2-2x)=\frac{4}{3}{x}^2-\frac{8}{3}x$

Sum the $x^2$: $\frac{1}{6}-\frac{5}{2}+\frac{4}{3}=\frac{1-15+8}{6}=-1$. Sum the $x$: $-\frac{5}{6}+\frac{15}{2}-\frac{8}{3}=\frac{-5+45-16}{6}=\frac{24}{6}=4$. Constant: $1$. $\boxed{P(x)=-x^2+4x+1.}$ Check: $P(0)=1$✔, $P(2)=-4+8+1=5$✔, $P(3)=-9+12+1=4$✔.

WHAT: Build the divided-difference table, read the top diagonal. First differences (secant slopes): $f[x_0,x_1]=\frac{5-1}{2-0}=2,f[x_1,x_2]=\frac{4-5}{3-2}=-1.$ Second difference (slope of those slopes): $f[x_0,x_1,x_2]=\frac{-1-2}{3-0}=\frac{-3}{3}=-1.$ Top-diagonal coefficients: $f[x_0]=1,f[x_0,x_1]=2,f[x_0,x_1,x_2]=-1$. $P(x)=1+2(x-0)-1(x-0)(x-2)=1+2x-(x^2-2x)=-x^2+4x+1.$ WHY it matches 2.1: by the uniqueness theorem there is only one degree-$\le 2$ interpolant — Lagrange and Newton are two recipes for the same curve. ✔

WHAT: Extend the table with the fourth node $x_3=5,y_3=-11$; only the new bottom entries are computed. New first difference: $f[x_2,x_3]=\frac{-11-4}{5-3}=\frac{-15}{2}=-7.5$. New second difference: $f[x_1,x_2,x_3]=\frac{-7.5-(-1)}{5-2}=\frac{-6.5}{3}=-\frac{13}{6}$. New third difference (top of the cubic column): $f[x_0,x_1,x_2,x_3]=\frac{-\frac{13}{6}-(-1)}{5-0}=\frac{-\frac{13}{6}+1}{5}=\frac{-\frac{7}{6}}{5}=-\frac{7}{30}.$ WHY we keep the old terms: the new term carries the factor $(x-0)(x-2)(x-3)$, which is zero at $x_0,x_1,x_2$ — so it cannot disturb the three values already fixed. $P_3(x)=\underset{\text{old quadratic}}{\underbrace{-x^2+4x+1}}-\frac{7}{30}x(x-2)(x-3).$ Check the new point $P_3(5)=(-25+20+1)-\frac{7}{30}\cdot 5\cdot 3\cdot 2=-4-\frac{7}{30}\cdot 30=-4-7=-11.$ ✔

WHAT: Compute the slope both orderings. $f[x_0,x_1]=\frac{4-5}{3-2}=-1,f[x_1,x_0]=\frac{5-4}{2-3}=\frac{1}{-1}=-1.$ Equal. WHY it must be so: the secant slope between two points is a geometric quantity — the line through them — independent of which point you name first. The sign flips in both numerator and denominator and cancels. What it buys: you may reorder nodes freely to make arithmetic clean, and the highest-order divided difference (the leading coefficient of $P$) is the same no matter the order.

WHAT (build $P$): values $f(-2)=\frac{1}{5}$, $f(0)=1$, $f(2)=\frac{1}{5}$. By symmetry $P$ is even. Newton table with $x_0=-2,x_1=0,x_2=2$: $f[x_0,x_1]=\frac{1-\frac{1}{5}}{0-(-2)}=\frac{\frac{4}{5}}{2}=\frac{2}{5},f[x_1,x_2]=\frac{\frac{1}{5}-1}{2-0}=-\frac{2}{5},$ $f[x_0,x_1,x_2]=\frac{-\frac{2}{5}-\frac{2}{5}}{2-(-2)}=\frac{-\frac{4}{5}}{4}=-\frac{1}{5}.$ $P(x)=\frac{1}{5}+\frac{2}{5}(x+2)-\frac{1}{5}(x+2)(x-0)=\frac{1}{5}+\frac{2}{5}x+\frac{4}{5}-\frac{1}{5}(x^2+2x).$ Combine: constant $\frac{1}{5}+\frac{4}{5}=1$; $x$: $\frac{2}{5}-\frac{2}{5}=0$; $x^2$: $-\frac{1}{5}$. So $P(x)=1-\frac{1}{5}{x}^2.$ At $x=1$: $P(1)=1-\frac{1}{5}=\frac{4}{5}=0.8$. True $f(1)=\frac{1}{2}=0.5$. True error $=0.5-0.8=-0.3$.

WHAT (error formula): with $n=2$, $f(x)-P(x)=\frac{f^{\prime \prime \prime }(\xi )}{3!}(x+2)(x-0)(x-2).$ At $x=1$ the node product is $(3)(1)(-1)=-3$. WHY we need a bound on $f^{\prime \prime \prime }$: we don't know $\xi$, so we bound $|f^{\prime \prime \prime }|$ over $[-2,2]$. For $f=(1+x^2{)}^{-1}$, $f^{\prime \prime \prime }(x)=\frac{24x(1-x^2)}{(1+x^2{)}^4}.$ Its magnitude on $[-2,2]$ peaks near $x\approx \pm 0.32$ at about $|f^{\prime \prime \prime }|\approx 4.62$ (evaluate to confirm). Take the safe bound $M=4.62$. $|f(1)-P(1)|\le \frac{M}{6}\cdot |-3|=\frac{4.62}{6}\cdot 3\approx \mathrm{2.31.}$ Reading: the true error $0.3$ comfortably sits under the guaranteed bound $2.31$ — the bound is honest but loose (it uses the worst-case $f^{\prime \prime \prime }$). See the figure.

The error factor ${\prod }_i(x-x_i)$ grows huge near the interval ends while $|f^{(n+1)}|$ also explodes, so high-degree equispaced interpolation of $\frac{1}{1+x^2}$ oscillates wildly between the end nodes — the Runge phenomenon. Fixes: cluster nodes toward the ends with Chebyshev nodes, or abandon one high-degree polynomial for piecewise low-degree Cubic splines.

WHAT: Take the limit of the secant-slope definition. $f[x_0,x_1]=\frac{f(x_1)-f(x_0)}{x_1-x_0}.$ WHY this is exactly a derivative: the right side is the difference quotient — the very object whose limit defines $f^{\prime }(x_0)$. As $x_1\to x_0$, ${\lim }_{x_1\to x_0}\frac{f(x_1)-f(x_0)}{x_1-x_0}=f^{\prime }(x_0).$ Interpretation: when nodes collide the interpolant is forced to match not just the value but the slope at $x_0$ (this is Hermite interpolation). Pushing further, $f[x_0,\dots ,x_k]\to \frac{f^{(k)}(x_0)}{k!}$, and Newton's form degenerates into the Taylor series — the two ideas are one theory seen at different node spacings.

From 2.2, $f[x_0,x_1,x_2]=-1$, and indeed the coefficient of $x^2$ is $-1$. They match. WHY in general: in Newton's form $P(x)={\sum }_{k=0}^{n}f[x_0,\dots ,x_k]{\prod }_{j=0}^{k-1}(x-x_j),$ only the last term ($k=n$) contains $x^n$, and its product ${\prod }_{j=0}^{n-1}(x-x_j)$ has leading term $x^n$ with coefficient $1$. So the coefficient of $x^n$ in $P$ is exactly $f[x_0,\dots ,x_n]$. Combined with symmetry (Ex. 3.2), this makes the top divided difference an order-independent fingerprint of the data.

WHAT: Build the table. All $y=3$. $f[x_0,x_1]=\frac{3-3}{4-1}=0,f[x_1,x_2]=\frac{3-3}{6-4}=0,f[x_0,x_1,x_2]=\frac{0-0}{6-1}=0.$ Newton: $P(x)=3+0(x-1)+0(x-1)(x-4)=3$. Answer: the constant student is right — $P(x)=3$, degree $0$. The "$\le n$" in the theorem again does its job: three points on a horizontal line give the constant polynomial. The vanishing top divided difference ($=$ leading coefficient) is the diagnostic that the true degree is below $n$. ✔

Uniqueness comes from ::: a square Vandermonde system with nonzero determinant ${\prod }_{i<j}(x_j-x_i)$ for distinct nodes. The top divided difference $f[x_0,\dots ,x_n]$ equals ::: the leading coefficient of $P(x)$ (order-independent). Adding a data point is cheap in Newton's form because ::: the new term has factor $\prod (x-x_j)$ vanishing at all old nodes, so you just append it. The error formula is only usable as ::: a bound, replacing $f^{(n+1)}(\xi )$ by its max magnitude $M$ (since $\xi$ is unknown).