Codex @codex  0

The Lagrange interpolation polynomial isThe interpolation nodes are distinct, so these weights are well defined. Applying the same Lagrange interpolation to the constant polynomial one gives $1={\sum }_r{w}_r{\pi }_{n,r}(x)$. Dividing this identity and the formula for $p$ by ${\pi }_n(x)$ gives the barycentric interpolation formulaThis displayed quotient is used away from the interpolation nodes; at $x=x_r$ its removable singularity is evaluated by setting $p(x_r)=u_r$. Multiplying every weight by the same nonzero constant leaves the quotient unchanged.

Chebyshev points are generally more reliable at high degree. The Chebyshev-Lobatto nodes, or the affine images of the roots of a Chebyshev polynomial, cluster near the interval endpoints and control the amplification measured by the Lebesgue constant of interpolation. Equally spaced interpolation nodes can produce large endpoint oscillations and the Runge phenomenon. This is a comparison of numerical robustness and general approximation behaviour, not a claim that one set minimizes the error for every individual function.

Write $\omega (t)={\prod }_{i=0}^n(t-x_i)$. If $x$ is an interpolation node, the polynomial interpolation error is zero. Otherwise setThe function $F$ has $n+2$ distinct zeros: the $n+1$ interpolation nodes and $x$. Repeated Rolle's theorem therefore gives a point $\xi$ strictly between the smallest and largest of these points with $F^{(n+1)}(\xi )=0$. Since $p^{(n+1)}=0$ and ${\omega }^{(n+1)}=(n+1)!$, this yields the polynomial interpolation errorAll differentiations are justified by $f\in C^{n+1}[a,b]$. At an interpolation node the same displayed equality holds with any $\xi \in [a,b]$, because the product is zero.

For distinct interpolation nodes $x_0,\dots ,x_n$, let $p_n$ be the unique polynomial of degree at most $n$ satisfying $p_n(x_i)=f(x_i)$. Existence follows from the Lagrange polynomial expressionuniqueness follows because the difference of two interpolants has $n+1$ distinct zeros but degree at most $n$.

Define the divided difference $f[x_0,\dots ,x_n]$ to be the coefficient of $x^n$ in $p_n$, even when that coefficient is zero. For $n=0$ this gives $f[x_0]=f(x_0)$. Permuting the nodes does not change the interpolation conditions, so it does not change their unique interpolant or this coefficient. The divided difference is symmetric in all the nodes. Equivalently its symmetric expression is

Choose a best uniform approximation $p_n\in {\mathcal{P}}_n$. It exists because this vector subspace is a finite-dimensional vector space and a minimizing sequence $q_j$ is bounded: $\Vert q_j{\Vert }_{\infty }\le \Vert f{\Vert }_{\infty }+\Vert f-q_j{\Vert }_{\infty }$. Finite-dimensional equivalence of norms then supplies a convergent subsequence of coefficients. If $E_n(f)>0$, the Chebyshev alternation theorem gives $n+2$ alternating error extrema. The intermediate value theorem supplies a zero $x_{n,k}$ of $f-p_n$ in each of the $n+1$ intervening open intervals. These interpolation nodes are distinct, and uniqueness of polynomial interpolation givesThe convergence follows from the Weierstrass approximation theorem. If $E_n(f)=0$, choose any $n+1$ distinct nodes: the polynomial interpolant is still $f=p_n$. This constructs interpolation nodes from best uniform approximation; the nodes depend on $f$, and no universal node system for all continuous functions is asserted.

Order the interpolation nodes as $t_0<\cdots <t_n$, as required by their alternating nodal data. Write $w(x)={\prod }_{j=0}^n(x-t_j)$ and ${\ell }_i(x)=w(x)/[(x-t_i)w^{\prime }(t_i)]$ for the Lagrange cardinal polynomials. Differentiating Lagrange interpolation givesThe upper bound is the triangle inequality; equality follows by choosing each independent nodal value to be the sign of its weight. Thus this is the nodal derivative norm from Lagrange cardinal polynomials.

To identify the maximizing signs, put $P_i=w/(x-t_i)$, a monic polynomial of degree $n$. Since $\mathrm{sign}{w}^{\prime }(t_i)=(-1{)}^{n-i}$,For $0\le k<n$, let ${\xi }_{i,j}$ be the ordered roots of $P_i^{(k)}$, $1\le j\le n-k$. The roots of $P_i$ decrease componentwise as $i$ increases: deleting a later node replaces one retained node by an earlier one. The monotonicity of polynomial critical points in their roots, iterated $k$ times, therefore gives ${\xi }_{n,j}\le \cdots \le {\xi }_{0,j}$. Moreover, $P_n$ and $P_0$ weakly interlace, so the Markov interlacing lemma gives ${\xi }_{0,j}\le {\xi }_{n,j+1}$. Together,These root bands have disjoint interiors. At a fixed $x$, all but at most one band lie wholly on one side of $x$. In the possible remaining band, ${\xi }_{i,j}$ moves monotonically as $i$ increases. Since the leading coefficients of all $P_i^{(k)}$ are positive, the sequence $P_i^{(k)}(x)$ has at most one sign change after zero entries are ignored. The same holds for $(-1{)}^i{\ell }_i^{(k)}(x)$. If $k=n$, every $P_i^{(n)}=n!>0$, so the conclusion also holds.

The maximizing nodal signs can consequently be chosen as $\pm (-1{)}^i$ throughout, or as $\pm (-1{)}^i$ before one index $s$ and $\mp (-1{)}^i$ from that index onward. Zero weights can be assigned either sign to complete such a pattern. These are precisely the nodal values of $\pm p^{\ast }$ or $\pm q_s$, provingThe argument works for all real $x$, hence in particular for $[-1,1]$. For $k>n$ every derivative vanishes and the result is immediate.

Define the Lagrange interpolation polynomialsDistinct interpolation nodes ensure every denominator is nonzero and $L_j(x_i)={\delta }_{ij}$. For a polynomial of degree at most $n-1$, the difference $P(x)-{\sum }_{j}P(x_j)L_j(x)$ has degree at most $n-1$ and vanishes at $n$ distinct points, so it is zero. Integrating this Lagrange interpolation identity proves the required exact quadrature formula. This also covers $n=1$, when the empty product is one and its weight is two.

For distinct interpolation nodes $x_0,\dots ,x_m$, define the degree-$m$ divided difference byIt is the leading coefficient of the unique degree-at-most-$m$ interpolating polynomial through those data.

DefineThe partial polynomial $p_m$ agrees with $p_{m-1}$ at $x_0,\dots ,x_{m-1}$. Moreover, the explicit formula for the divided difference givesso $p_m(x_m)=f(x_m)$. Induction shows that $p_n(x_j)=f(x_j)$ for every $j$. By uniqueness of polynomial interpolation, this is the required Newton interpolation polynomial.

For the recursion, substitute the explicit formulas for $f[x_1,\dots ,x_m]$ and $f[x_0,\dots ,x_{m-1}]$. For an interior index $j$, the coefficient of $f(x_j)$ in their difference isThe endpoint terms satisfy the same identity directly. Dividing by $x_m-x_0$ therefore gives

For fixed interpolation nodes $c_0,\dots ,c_{s-1}$, interpolate any $p\in {\mathbb{P}}_{s-1}[x]$ asIntegrating shows that the unique weights making the quadrature rule exact through degree $s-1$ are

Now let the nodes be the zeros of the degree-$s$ orthogonal polynomial $q_s$. Given any $p\in {\mathbb{P}}_{2s-1}[x]$, polynomial division givesOrthogonality gives ${\int }_a^b{q}_{s}h=0$, while $q_s(c_k)=0$ makes the quadrature sum for $q_{s}h$ vanish. The rule is already exact on $r$, so it is exact on $p$. This is the defining precision property of Gaussian quadrature.

The polynomial $p_n$ interpolates $f$ at the interpolation nodes whenFor distinct interpolation nodes, define the Lagrange cardinal polynomialsThe denominators are nonzero, each polynomial degree is at most $n$, and ${\ell }_i(x_j)={\delta }_{ij}$, with ${\delta }_{ij}$ the Kronecker delta. Thereforeis a Lagrange interpolation polynomial belonging to the vector space of univariate polynomials ${\Pi }_n$, and it has all the required sampled values.

If $r_n\in {\Pi }_n$ also works, $p_n-r_n$ has $n+1$ distinct roots of a polynomial while its polynomial degree is at most $n$. The root bound for a polynomial forces it to be the zero polynomial, proving uniqueness. The phrase “degree $n$” denotes the allowed maximum; the actual polynomial degree may be smaller. No continuity assumption is needed merely to construct the interpolation polynomial from these finitely many values.

Assume $f\in C^{n+1}[a,b]$ and set $\omega (t)={\prod }_{i=0}^n(t-x_i)$, a monic polynomial of polynomial degree $n+1$. Fix $x\in [a,b]$ distinct from all the interpolation nodes, and chooseThe auxiliary functionvanishes at the $n+2$ distinct points $x_0,\dots ,x_n,x$. Order those points and repeatedly apply Rolle's theorem. After $n+1$ applications, there is some $\xi$ strictly between their smallest and largest values, hence in $(a,b)$, such that $F^{(n+1)}(\xi )=0$.

Because $p_n$ has polynomial degree at most $n$ and $\omega$ is monic of polynomial degree $n+1$,Substituting the resulting value of $C$ proves the polynomial interpolation error formulaAt an interpolation node, both sides are zero, so any $\xi \in (a,b)$ works. Such an interior point exists because $n\ge 1$ and the interpolation nodes are distinct. The selected $\xi$ generally depends on $x$; the theorem makes an existence assertion, not a regularity assertion about that dependence.

Assume $f\in C^{n+1}[a,b]$ and reorder the interpolation nodes increasingly as $x_0<\cdots <x_n$. The polynomial interpolation error $e=f-p_n$ vanishes at all of them. Rolle's theorem suppliesThese $n$ points are distinct because their containing intervals are disjoint. Thus $q=p_n^{\prime }$ is a polynomial of polynomial degree at most $n-1$ that interpolates the function $f^{\prime }$ at the interpolation nodes ${\eta }_1,\dots ,{\eta }_n$.

Apply the polynomial interpolation error theorem to $f^{\prime }$ with these $n$ interpolation nodes. Since the $n$th derivative of $f^{\prime }$ is $f^{(n+1)}$, for every $x\in [a,b]$ there is a ${\xi }_x\in (a,b)$ withFor $x={\eta }_i$ the equality is zero on both sides; otherwise the same auxiliary-function and repeated-Rolle's theorem proof applies. This also covers $n=1$, where $q$ is a constant polynomial and the proof is the ordinary mean value theorem for $f^{\prime }$.

Writing $M={\max }_{[a,b]}|f^{(n+1)}|$ gives the genuine error boundThe first formula is sharper, but its intermediate interpolation nodes depend on $f$; the last bound eliminates those unknown locations. This is derivative interpolation error from Rolle points.

For each interpolation node define the Lagrange cardinal polynomialAll denominators are nonzero because the interpolation nodes are distinct. Each polynomial has polynomial degree at most $n$, and ${\ell }_j(x_i)={\delta }_{ij}$, where ${\delta }_{ij}$ is the Kronecker delta. Consequently the linear combinationbelongs to the vector space of univariate polynomials ${\Pi }_n$ and has the required values. This proves existence of the Lagrange interpolation polynomial.

For uniqueness, suppose $p_n$ and $r_n$ both work. Their difference is a polynomial of polynomial degree at most $n$ with $n+1$ distinct roots of a polynomial. The root bound for a polynomial forces $p_n-r_n$ to be the zero polynomial.

The seven supplied values follow $f_i=i^2+1$. The quadratic polynomial $x^2+1$ belongs to ${\Pi }_6$ and takes all seven values, so uniqueness givesThe subscript bounds the polynomial degree; it does not require polynomial degree exactly six.

The product rule applied at the interpolation node $x_k$ givesThus Lagrange interpolation gives, away from the interpolation nodes,Apply the same Lagrange interpolation formula to the constant polynomial one. Since its interpolant is itself,Dividing the preceding two identities proves the barycentric interpolation formulaThe denominator is exactly $1/w(x)$, so is nonzero away from the interpolation nodes. At $x=x_j$, multiply numerator and denominator by $x-x_j$ and take the limit: their values tend to $w_j{f}_j$ and $w_j$, respectively. The removable singularity therefore has value $f_j$; in numerical evaluation return the stored value directly at an interpolation node.

Fix $i$, write $\alpha =x_{i-1}$, $\beta =x_i$, and let $E=T-S$ on this interval. The Hermite interpolation conditions give bothTwo applications of integration by parts therefore giveOn this single cubic piece, the same calculation also givesHere $S^{(4)}=0$ inside the interval, and all four endpoint values of $E,E^{\prime }$ are zero. Since $T^{\prime \prime }=E^{\prime \prime }+S^{\prime \prime }$, we obtain the exact identityThis is an integral inequality, with no assertion that the integrand on the left has one sign pointwise. The stronger nodal derivative conditions make the boundary terms vanish on each interval separately; part (i) only needed their cancellation after summing.

The stated Hermite interpolating polynomial exists uniquely in ${\Pi }_{2n+1}$. Indeed, a polynomial in the kernel of a linear map of the value-and-derivative data map has a double root of a polynomial at each of $n+1$ distinct interpolation nodes. A nonzero such polynomial would have polynomial degree at least $2n+2$, which is impossible. The map is therefore an injective function and a linear map between vector spaces of the same finite dimension of a vector space, $2n+2$, and hence is a linear isomorphism. No higher smoothness of the original function $f$ is required to construct it.

An explicit illustration uses interpolation nodes $0,1,2$, values $0,1,0$, and zero derivatives at every interpolation node. The clamped cubic spline is $S(x)=3x^2-2x^3$ on $[0,1]$ and its reflection on $[1,2]$. Its Hermite interpolating polynomial is the quartic polynomial $T(x)=x^2(2-x{)}^2$. On $[0,1]$, $T-S=x^2(1-x{)}^2$, and the corresponding reflected formula holds on $[1,2]$. Direct integration gives $J(S)=24$, $J(T)=128/5$, and $J(T-S)=8/5$, exactly as the energy identity predicts.

There are $n+2$ distinct interpolation nodes but only $n+1$ free coefficients in a polynomial of polynomial degree at most $n$. Thus polynomial interpolation is possible precisely when the data satisfy one compatibility equation. To identify it, form the Lagrange interpolation polynomial through all the data:This is the unique interpolation polynomial of polynomial degree at most $n+1$. Its leading coefficient, which is also the order-$(n+1)$ divided difference, isConsequently the required condition isNecessity follows because any qualifying $p_n$ must equal $q$ by uniqueness of polynomial interpolation; sufficiency follows because $D=0$ removes the only possible term of polynomial degree $n+1$ from $q$.

When this condition holds, a slightly shorter expression uses only the first $n+1$ interpolation nodes:This polynomial agrees with $q$ at $n+1$ distinct points, so the root bound for a polynomial gives $p_n=q$ and hence $p_n(x_{n+1})=f_{n+1}$ as required. Equivalently, the compatibility condition says that this expression, evaluated at the last interpolation node, gives $f_{n+1}$.

Let $r=f-p_n$ be the continuous function describing the error. The preceding orthogonality equations sayIf $r$ vanishes identically, any $n+1$ distinct points work. If $r$ already has at least $n+1$ distinct zeros, the assertion also follows. Suppose instead that it has at most $n$ distinct zeros. Among its interior zeros, list those at which its sign changes as $t_1<\cdots <t_m$, where $m\le n$, and define the polynomialwith $q=1$ if $m=0$. Between consecutive zeros of $r$, its sign is constant by the intermediate value theorem. At each $t_j$, both $r$ and $q$ change sign; at every other zero of $r$, neither sign changes. Hence $rq$ has one fixed sign throughout $[-1,1]$ wherever it is nonzero. Replacing $q$ by $-q$ if necessary makes $rq\ge 0$ everywhere.

Since $r$ is not identically zero and $q$ has only finitely many zeros, $rq$ is strictly positive on some open interval. Positivity of $w$ givescontradicting orthogonality because $q\in {\mathcal{P}}_n$. ThusThis is the interpolation property of weighted least-squares polynomial approximation. It supplies interpolation nodes depending on $f$ and $w$, rather than nodes prescribed in advance.

Source: Oxford Part A, A7 Numerical Analysis, A13759W1, 23 June 2023; parent PDF pages 135–137, paper pages 1–3. These original solutions cover all three questions and all eleven lettered subparts. In Question 1(d), the unrefined Gershgorin discs alone are inconclusive for the shift $5$; a further exact calculation resolves it. In Question 2(c), clearing denominators produces a linear system whose solution need not define a rational interpolant at every interpolation node. Question 3 uses the paper's normalized convention for the local truncation error.

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