Past exam of the options II course of the University of Oxford / 2004 / P / P3 / Solution

The Lagrange interpolation polynomialhas degree at most $n$ and takes the required value at each node, proving existence. If two such polynomials existed, their difference would have $n+1$ distinct roots despite degree at most $n$, so it would vanish identically. This proves uniqueness.

Define $P(x)=[(x-x_0)r(x)-(x-x_n)q(x)]/(x_n-x_0)$. It has degree at most $n$. At $x_0$ its value is $q(x_0)=f_0$, and at $x_n$ it is $r(x_n)=f_n$. At every interior node both $q$ and $r$ equal $f_i$, giving $P(x_i)=f_i$. Uniqueness therefore givesIf the data come from $x^m$ with $m\le n$, uniqueness gives $p=x^m$. If $m<n$, that same polynomial has degree at most $n-1$ and satisfies each smaller interpolation problem, so $q=r=x^m$.

For the final claim assume $n\ge 2$. Put $t=q-r$. Its node values are $t(x_0)=f_0-r(x_0)$, $t(x_i)=0$ for $1\le i\le n-1$, and $t(x_n)=q(x_n)-f_n$. The linear spline $s$ joining these values has a ramp on the first interval, is zero on all middle intervals, and has a ramp on the last. ThusOn each node interval $s^{\prime }$ is constant and $t-s$ vanishes at both ends. Hence $\int s^{\prime }(t^{\prime }-s^{\prime })dx=0$ on that interval. Integrating the supplied identity and summing giveswhich proves the claimed inequality and the minimum Dirichlet energy of a linear interpolant.

There is a source exception: with $n=1$, $q=f_0$ and $r=f_1$, so $t$ is constant and the left side of the asserted bound is zero. If $f_0\ne f_1$, its right side is $2(f_0-f_1{)}^2/(x_1-x_0)>0$. Thus the final inequality requires $n\ge 2$, although the preceding interpolation statements remain valid for $n=1$.