Past exam of the numerical analysis course of the University of Oxford / 2017 (A7, A13759W1)

Source release: Oxford examination archive, member FOI-20210708-1 - Data/a13759w1 (2).pdf. The cover dates this examination to 12 June 2017.

Answer availability checked on 28 October 2026: Oxford advertises solutions for even examination years and an exceptional release for 2019; its stated policy excludes other odd years. No advertisement covering this exact paper or selected parts was found in a bounded search of official sources.^[ref]

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.

A Newton-Cotes quadrature integrates a Lagrange interpolation polynomial at equally spaced quadrature nodes. For the Newton-Cotes closed quadrature, the endpoints are included: write $x_j=a+jh$, $h=(b-a)/n$, and useThese quadrature weights depend on the quadrature nodes, not on the sampled function. Open Newton-Cotes quadrature uses equally spaced interior quadrature nodes instead.

For Simpson's rule, use $n=2$ and set $x=a+ht$, so $0\le t\le 2$. The Lagrange cardinal polynomials becomeIntegrating these quadratic polynomials gives $1/3$, $4/3$, $1/3$, respectively. The change of variable contributes $h$, soIts degree of precision of a quadrature rule is three: it integrates every quadratic polynomial by construction, and also the cubic nodal polynomial $(x-a)(x-a-h)(x-b)$, whose integral vanishes by odd symmetry about $a+h$. Any cubic polynomial differs from its quadratic polynomial interpolant by a constant multiple of this nodal polynomial.

Read the differential order $dxdy$ literally: take quadrature nodes $X=(c,(c+d)/2,d)$ in $x$ and $Y=(a,(a+b)/2,b)$ in $y$. Applying Simpson's rule first in $x$ and then in $y$ multiplies the one-dimensional quadrature weights. With $s=(1,4,1)$, this tensor-product quadrature isEquivalently, the nine sampled function values have the quadrature weight arraywith rows indexed by the $x$ quadrature nodes and columns by the $y$ quadrature nodes. The quadrature weights sum to the rectangle's area. If the intended coordinate assignment is instead $x\in [a,b]$, $y\in [c,d]$, exchange $X$ and $Y$ in the formula. Both conventions give the same calculation on the unit square used below.

For the separable integrand, tensor-product quadrature factors into two one-dimensional applications of Simpson's rule:soThe exact double integral, evaluated by Fubini's theorem and the power rule for integration, isThe $x$ factor is always integrated exactly. All quadrature error therefore comes from applying Simpson's rule to the $y$ factor.

At $q=2$, the preceding tensor-product quadrature givesBoth factors of the separable integrand are quadratic polynomials, so exactness follows directly from the construction of Simpson's rule.

At $q=3$,The $y$ factor is now a cubic polynomial. Simpson's rule still integrates it exactly because its degree of precision of a quadrature rule is three. Exactness of tensor-product quadrature depends on the polynomial degree in each variable, rather than their sum.

At $q=4$,This is an overestimate, with signed quadrature errorThe relative error is $(1/720)/(1/30)=1/24$, approximately $4.17\%$. The quartic polynomial $y^4$ lies beyond the degree of precision of a quadrature rule of Simpson's rule, so the exactness of the previous cases no longer applies.

Gaussian elimination uses elementary row operations to remove entries below successive pivot elements, reducing a linear system to one with an upper triangular matrix. Back substitution then solves that system. It also computes a reusable matrix factorization, so additional right-hand sides can be handled by forward substitution and back substitution without repeating the elimination.

For elimination without row exchanges, let $A^{(1)}=A$. At step $k$, provided the pivot element $a_{kk}^{(k)}$ is nonzero, form the elimination multipliersand perform ${\text{row}}_i\leftarrow {\text{row}}_i-m_{ik}{\text{row}}_k$, applying the same operation to the right-hand side. More explicitly the resulting entries satisfy $a_{ij}^{(k+1)}=a_{ij}^{(k)}-m_{ik}{a}_{kj}^{(k)}$ for $i>k$, $j\ge k$.

Let $E_k=I-{\sum }_{i>k}{m}_{ik}{e}_i{e}_k^T$, where $e_i$ are the standard basis vectors. ThenThe matrix $L$ is a unit lower triangular matrix storing the elimination multipliers, while $U$ is an upper triangular matrix:Solving $Ax=b$ becomes $Ly=b$ followed by $Ux=y$. If a required pivot element vanishes, an unpermuted LU decomposition can fail even for an invertible matrix. Row exchanges, typically selected by partial pivoting, instead produce $PA=LU$ with a permutation matrix $P$; then solve $Ly=Pb$, $Ux=y$.

Since every $u_{jj}>0$, the diagonal matrix $D$ is invertible. SetThe division is by the diagonal entry of row $i$. Thus $\hat{U}$ is an upper triangular matrix with diagonal entries one and $A=LD\hat{U}$.

To use symmetry without assuming the conclusion, multiply by the matrix inverse of $L$ and its transpose:The matrix $M$ is symmetric because $A$ is a symmetric matrix. It is also an upper triangular matrix, since every factor on the right is an upper triangular matrix. A symmetric upper triangular matrix is diagonal. Its diagonal is exactly $D$, because $\hat{U}$ and $L^{-T}$ have diagonal entries one. Hence $M=D$, givingThis is the LDL decomposition.

Take the positive square roots of the diagonal entries:The matrix $\hat{L}$ is a lower triangular matrix with positive diagonal, andThis is a Cholesky decomposition. For a nonzero vector $x$, the vector ${\hat{L}}^{T}x$ is nonzero because ${\hat{L}}^T$ is invertible. ThereforeHere $\Vert \cdot {\Vert }_2$ is the Euclidean norm. Thus $A$ is a positive-definite matrix.

For a real square matrix, a QR factorization writes $B=QR$ with $Q$ an orthogonal matrix, $Q^{T}Q=I$, and $R$ an upper triangular matrix. If $B$ is invertible, so is $R$, andCompute $Q^{T}b$ and use back substitution; no matrix inverse needs to be formed.

Apply the Gram-Schmidt process to the columns $b_1,b_2,b_3$. The first column has Euclidean norm two, giving $q_1=(1,0,0{)}^T$ and $r_{11}=2$. For the second column,For the third column,This residual already has Euclidean norm one. Set $q_3=(0,-3/5,4/5{)}^T$ and $r_{33}=1$. ThusThe columns of $Q$ are orthonormal, and matrix multiplication verifies $QR=B$.

Using precisely this QR factorization, transform the right-hand side:Back substitution in $Rx=Q^{T}b$ givesTherefore

A linear spline is a continuous function whose restriction to every interval $[x_{i-1},x_i]$ is a polynomial of polynomial degree at most one. With $h_i=x_i-x_{i-1}$ and ${\ell }_i=\ell (x_i)$, linear interpolation givesIntegrating the two linear polynomials and adding the contributions givesThis is the composite trapezoidal rule applied to the nodal values, and it is exact for the linear spline itself, including nonuniform spline knots.

A cubic spline on this partition of an interval is a function $S\in C^2[x_0,x_n]$ that restricts to a polynomial of polynomial degree at most three on every interval $[x_{i-1},x_i]$. Thus its second derivative is continuous and piecewise of polynomial degree at most one: $S^{\prime \prime }$ is a linear spline on the same spline knots. Its third derivative is constant on each open interval and can jump across the spline knots; its fourth derivative vanishes inside each open interval.

Put $E=T-S$. Matching interpolation data and endpoint derivatives givesThe endpoint slope constraints make $S$ a clamped cubic spline. The decisive step in its minimum roughness property of a clamped cubic spline is the orthogonality identityProve it separately on each interval. Two applications of integration by parts, using the vanishing fourth derivative of the cubic piece, giveThe second boundary term is zero because $E$ vanishes at both endpoints of this interval. Sum over $i$. At each interior spline knot, the two values of $S^{\prime \prime }{E}^{\prime }$ agree because both factors are continuous, so the contributions cancel. The remaining outer boundary terms vanish because $E^{\prime }$ is zero at both outer endpoints. This proves the identity.

Expanding the square now gives the stronger exact equalityThe last integral is nonnegative, proving the required inequality. It measures the excess second derivative roughness penalty of $T$ over $S$.

The argument applies directly to twice continuously differentiable competitors. More generally it holds when $T^{\prime }$ is an absolutely continuous function and $T^{\prime \prime }$ is square-integrable, the usual finite-energy class for this second derivative roughness penalty. Mere existence of pointwise second derivatives does not by itself guarantee that all displayed integrals exist; the variational statement is understood for admissible competitors with this regularity.

Let $R$ be a second cubic spline matching the same values and endpoint derivatives. The minimum roughness property of a clamped cubic spline applied with $S$ as the minimizing cubic spline gives $J(R)\ge J(S)$, where $J(u)={\int }_{x_0}^{x_n}(u^{\prime \prime }{)}^{2}dx$. Applying the same argument with their roles exchanged gives $J(S)\ge J(R)$. Hence equality holds, and the exact identity from part (i) yieldsThe integrand is continuous and nonnegative. If it were positive somewhere, it would have a positive integral over a small interval. It follows that $R^{\prime \prime }=S^{\prime \prime }$ everywhere. Consequently $R-S$ is an affine function. Its value and derivative vanish at $x_0$, so it is identically zero. Thus $R=S$, proving uniqueness of the clamped cubic spline with the prescribed data. Existence was assumed in the question; this argument establishes the remaining uniqueness claim.

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.