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

Source release: Oxford examination archive, member FOI-20210708-1 - Data/a13759w1 (4).pdf. The cover dates the examination to 26 June 2015.

Answer availability checked on 28 October 2026: a bounded search of official Oxford sources found no advertisement of complete or selected-part solutions for this exact paper. Oxford's stated policy excludes odd examination years apart from the exceptional release for 2019.^[ref]

For $a<b$, the one-panel trapezoidal rule isIt integrates the linear interpolation between the two endpoint samples. Indeed the affine functionhas definite integral $T(f)$. The two quadrature nodes are $a,b$ and both quadrature weights are $(b-a)/2$.

It suffices to assume $f\in C^2[a,b]$. The polynomial interpolation error for the endpoint linear interpolant gives, for every interior $x$, some ${\xi }_x\in (a,b)$ withLet $M={\max }_{[a,b]}|f^{\prime \prime }|$, which exists by continuity of the second derivative and the extreme value theorem. Since $(x-a)(b-x)\ge 0$,Integrating this pointwise inequality and using the triangle inequality for an integral yieldsThusThis derivation does not require choosing ${\xi }_x$ as a continuous function of $x$; the pointwise upper bound is sufficient.

The constant is sharp. Take the quadratic polynomial $f(x)=(x-a{)}^2$ and write $L=b-a$. Its exact integral is $L^3/3$, its trapezoidal rule value is $L^3/2$, and $\max |f^{\prime \prime }|=2$. ConsequentlyEquality holds, so no smaller universal constant than $1/12$ works under these assumptions. This is the sharp one-panel trapezoidal error bound.

The trapezoidal rule is exact for every affine function $f(x)=\alpha +\beta x$, equivalently every polynomial of polynomial degree at most one: the linear interpolant is the function itself. These functions have $f^{\prime \prime }=0$, so the preceding upper bound is also zero. There is no contradiction: zero error is precisely what the bound predicts.

The degree of precision of a quadrature rule is one, since the quadratic polynomial in part (i) is not integrated exactly. This does not exclude exactness for particular higher-degree or nonpolynomial functions. For example $f(x)=(x-m{)}^3$, $m=(a+b)/2$, has zero integral and opposite endpoint values, so the trapezoidal rule also gives zero. Its second derivative is generally nonzero, making the upper bound positive; an upper bound need not be attained. Signed quadrature error can cancel.

On a partition of an interval $a=x_0<x_1<\cdots <x_N=b$, apply the trapezoidal rule separately to each panel and add:For uniform spacing $h=(b-a)/N$, this composite trapezoidal rule becomesEach interior sample occurs in two panels; their half-quadrature weights combine to $h$. The endpoint quadrature weights are $h/2$.

Use the nonpolynomial function $f(x)=1+\sin x$ on $[-1,1]$. Its exact integral isbecause the sine is an odd function.

For every uniform partition of an interval with $N\ge 1$ panels, the quadrature nodes satisfy $x_{N-j}=-x_j$. Their composite trapezoidal rule quadrature weights agree, so the two sampled sine values cancel. If there is a node at zero its sine value is already zero. The constant term is integrated exactly, givingThis is symmetric trapezoidal exactness for odd functions, applied after adding a constant function so that the resulting definite integral is nonzero. It is exactness for this particular integrand, rather than a claim that every nonpolynomial function is integrated exactly.

Write $E(h)$ for the supplied approximation. The asymptotic expansion iswhere $O$ is Big O notation. At the refined parameter $h/3$,Multiply this identity by nine and subtract the first one. The unknown leading truncation error coefficient cancels:Thus the Richardson extrapolation estimate isThe two supplied values giveThe correction to the finer approximation is $(3-2)/8=1/8$. Neglecting the higher-order remainder would also give $c=9/8$.

The conclusion is asymptotic: the leading error order improves from two to at least three when both parameter values are in the range of the stated asymptotic expansion. With no bound on the remainder constant, the two finite observations alone do not guarantee that $25/8$ is closer to $Y$. Indeed, for any proposed value $L$, the polynomial modelsatisfies $E(1)=2$, $E(1/3)=3$ and the required asymptotic expansion with true limit $L$. This is why finite observations do not certify Richardson extrapolation accuracy: asymptotic cancellation provides an improved-order estimator, while a numerical error certificate needs quantitative remainder information.

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.

The remainder in part (b) involves an unspecified $\xi =\xi (x)$. Its existence for every $x$ does not ensure a differentiable selection. Even if such a selection existed and $f$ had an additional derivative, the product rule and chain rule would giveThe first term cannot be discarded or bounded from the given information. Neither $f^{(n+2)}$ nor ${\xi }^{\prime }$ is supplied by the original theorem.

For an explicit demonstration, interpolate the cubic polynomial $f(x)=x^3$ at zero and one. Then $p_1(x)=x$, andDifferentiating correctly givesTreating the remainder coefficient $x+1$ as a constant would omit $x(x-1)$ and give a wrong answer at every interior point. An existential intermediate point cannot be frozen when differentiating. Part (i) instead applies Rolle's theorem directly to the polynomial interpolation error.

Write ${\tilde{p}}_1$ and $\tilde{q}$ for the quantities computed from the perturbed second sample. The endpoint linear interpolation and its derivative areCompare them on their interpolation interval $0\le x\le h$, with fixed $a>0$. Put $x=th$, $0\le t\le 1$. The Taylor series of the sine gives, uniformly in $t$,Here the second equality compares with $f^{\prime }(0)=a$. More generally, the exact derivative is $f^{\prime }(th)=a\cos (ath)$ andThe input perturbation itself changes the value interpolant by exactly $aϵx/h$, and changes its derivative by exactly $aϵ/h$. ThusFor fixed nonzero $ϵ$, the value approximation has a bounded noise floor: its maximum error approaches $a|ϵ|$, and at $x=h$ that error is exactly $a|ϵ|$. It does not converge uniformly to the exact values as $h\to 0$. However, it does not amplify the absolute sample perturbation on $[0,h]$. The derivative error instead grows without bound like $a|ϵ|/h$.

With exact samples, $ϵ=0$, both approximations do converge on the shrinking interval: the value error is $O(h^3)$ for this particular sine, and the derivative error is $O(h^2)$. With step-dependent noise, value convergence requires $ϵ(h)\to 0$, whereas derivative convergence requires the stronger $ϵ(h)=o(h)$, where $o$ denotes little o notation.

This is noise amplification by differentiation of a linear interpolant. Value interpolation has an absolute perturbation bound independent of $h$ on the sampled interval. Numerical differentiation has a perturbation factor $1/h$, expressing the ill-posedness of numerical differentiation from values with fixed absolute uncertainty. The amplification follows from the mathematical data map even in exact arithmetic; it is distinct from additional roundoff error in a particular implementation. For fixed $x$ outside $[0,h]$, the operation becomes extrapolation, and the value perturbation $aϵx/h$ can also diverge.

A real square matrix $Q$ is an orthogonal matrix when $Q^{T}Q=I$, equivalently its columns form an orthonormal basis. Here $Q^T$ is the transpose and $I$ the identity matrix. For every vector $x$,Taking nonnegative square roots provesThus an orthogonal matrix preserves the Euclidean norm.

Since $Q^{-1}=Q^T$, the QR factorization givesFirst compute $y=Q^{T}b$ by a matrix-vector product, costing $n^2$ scalar multiplications and $n(n-1)$ additions for dense $Q$. Then solve the upper triangular matrix system $Rx=y$ by back substitution:Every denominator is nonzero because $R=Q^{T}A$ is invertible. The back substitution costs $n(n-1)$ multiplications and subtractions together, plus $n$ divisions, for $n^2$ arithmetic operations. Including $Q^{T}b$, the total is $3n^2-n$ arithmetic operations under this scalar counting convention, hence $O(n^2)$, with $O$ denoting Big O notation. The already supplied QR factorization is reused; no matrix inverse needs to be computed.

Choose the following consistent sign convention. The Givens rotation $J(i,j,\theta )$ equals the identity matrix except for the block on coordinates $i,j$:Thus it changes only the $i$th and $j$th coordinates of a vector. Write $c=\cos \theta$, $s=\sin \theta$. Its two-coordinate block satisfiesAll remaining coordinates are unchanged, so $J^{T}J=I_n$. Hence every such Givens rotation is an orthogonal matrix. With this convention the two-coordinate rotation matrix rotates through angle $-\theta$.

Let $r=\sqrt{x_i^2+x_j^2}$. If $r>0$, choose $\theta$ so thatSuch an angle exists because the two ratios have squared sum one. Then the changed coordinates areAll other coordinates satisfy $y_k=x_k$. If $r=0$, both input coordinates are zero; take $\theta =0$, giving the identity matrix on this pair. In all cases,This fixes a nonnegative retained coordinate and handles division by zero explicitly. For floating-point computation, the stable construction of a Givens rotation uses scaled Euclidean norm evaluation to avoid unnecessarily overflowing or underflowing the squares.

Apply the product from right to left, choosing every Givens rotation from the current first column. First $J(1,2)$ replaces $(a_1,a_2)$ by $(\sqrt{a_1^2+a_2^2},0)$. Next $J(1,3)$ combines that retained entry with $a_3$ and sets the third entry to zero. Inductively, after eliminating coordinates $2,\dots ,k$, the first coordinate isand coordinates $2,\dots ,k$ are zero. Later Givens rotations involve only coordinate one and a new coordinate, so those zeros remain zero. Thereforewhere $e_1$ is the first standard basis vector. The zero vector is included by choosing the identity matrix for every zero pair. The nonnegative sign follows from the convention fixed in part (c)(ii). This is the first-column stage of QR decomposition by Givens rotations.

Put $C=Q_{1}A$ and write its second column as $v$. For $n\ge 3$, takewhere each angle is computed from the current second column, in the right-to-left application order. These Givens rotations eliminate its entries in rows $3,\dots ,n$ by accumulating their Euclidean norm in row two.

Each rotation acts only on rows with indices at least two. The first column of $C$ is $\Vert a{\Vert }_2{e}_1$, whose entries in all those rows are zero. Mixing two zeros leaves them zero, and row one is untouched. Thus the first column is unchanged. The resulting matrix has the formThis verifies both required properties, including the case of zero second-column tail. When $n=2$ there are no rows to eliminate: take $Q_2=I_2$, the empty product. No sign change of $v_2$ is required in that case. Each Givens row-pair update preserves previously eliminated columns, which is the central invariant of QR decomposition by Givens rotations.

The orthonormal columns satisfy $\Vert a{\Vert }_2=\Vert b{\Vert }_2=1$ and $a^{T}b=0$. By part (i), $Q_{1}a=e_1$. A product of orthogonal matrices is an orthogonal matrix, since $Q_1^T{Q}_1=I$. ConsequentlyThe last expression is the first coordinate of the transformed second column. Thus the first row isThe one in the first entry uses the nonnegative retained-coordinate convention. A different consistent sign convention could give $(-1,0)$ instead; the second entry must still be zero by preservation of the inner product.