Past exam of the numerical analysis course of the University of Oxford / 2023 / 2

For the distinct interpolation nodes, define the Lagrange cardinal polynomialsEvery denominator is nonzero, each $L_i$ has polynomial degree at most $n$, and $L_i(x_j)={\delta }_{ij}$. Hence the Lagrange interpolation polynomialbelongs to ${\Pi }_n$ and has $p_n(x_j)=f_j$. This proves existence.

If $p_n$ and ${\tilde{p}}_n$ both fit the data, their difference has polynomial degree at most $n$ but vanishes at the $n+1$ distinct interpolation nodes. Repeated application of the factor theorem implies that ${\prod }_{j=0}^n(x-x_j)$ divides that difference. A nonzero polynomial of degree at most $n$ cannot have such a divisor of degree $n+1$. Thus $p_n-{\tilde{p}}_n=0$, proving uniqueness. When $n=0$, the empty product defining $L_0$ is $1$, so the argument includes the constant case.

The monomial $x^k$ lies in ${\Pi }_n$ and already fits the data. Uniqueness of polynomial interpolation therefore givesApply this result with a nonnegative integer $m\le n$. Its Lagrange interpolation representation is the polynomial identityThe numerator in each summand is a monic polynomial of degree $n$, so the coefficient of $x^n$ on the right is exactly ${\sum }_i{x}_i^m/{\prod }_{j\ne i}(x_i-x_j)$. The coefficient on the left is zero for $m<n$ and one for $m=n$. Comparing coefficients proves the Lagrange leading-coefficient identityThe intended exponent range is $m\ge 0$: arbitrary negative exponents would not give this polynomial identity. For $m=0$, $x_i^0$ denotes the value of the constant polynomial $1$, including at a zero interpolation node.

Clearing the denominators in the rational interpolation conditions givesThese are $n+1$ linear equations for $(m+1)+\ell =n+1$ unknowns. The $i$th row of the coefficient matrix, in the order $a_0,\dots ,a_m,b_0,\dots ,b_{\ell -1}$, isThis rational interpolation linearization is equivalent to the original fraction conditions only if $r(x_i)\ne 0$ at every interpolation node. If $r(x_i)=0$, the cleared equation merely forces $q(x_i)=0$, leaving the fraction undefined.

For $f_i=x_i^{m+1}$, the coefficient row becomesThis is the Vandermonde matrix, whose determinant is ${\prod }_{0\le i<j\le n}(x_j-x_i)\ne 0$. Equivalently, a vector in its null space would define a degree-at-most-$n$ polynomial vanishing at all $n+1$ distinct interpolation nodes, which is zero by the preceding uniqueness proof. Thus the cleared linear system has exactly one solution.

There is also a constructive description of that solution. Define the monic polynomialThe polynomial $x^{m+1}r(x)-q(x)$ is monic of degree $n+1$ and vanishes at every interpolation node. It must therefore equal $W(x)$. By polynomial division, write uniquelyThe quotient $R$ is monic of degree $\ell$, andis the unique coefficient solution. This does not assert that $R$ is nonzero at every interpolation node.

For a counterexample with $m=0$, $\ell =1$, choose $x_0=0,x_1=1$ and the specified data $f_i=x_i$, so $f_0=0,f_1=1$. The cleared equations reduce togiving the unique solution $q(x)=0$, $r(x)=x-1$. But at $x_1=1$ the quotient is $0/0$. Indeed, any genuine rational interpolant of this prescribed form would need $r(0)\ne 0$; then $q(0)/r(0)=0$ forces the constant numerator to be zero. At a nonzero denominator its value at $1$ would also be zero, never one. Cancelling the common factor in the cleared candidate would merely give the identically zero rational function, which still fails the data. Hence