Past exam of the options II course of the University of Oxford / 2012 / P (Numerical Analysis)

A real square matrix $Q$ is orthogonal when $Q^{T}Q=I$, equivalently $Q^{-1}=Q^T$. For $c=\cos \theta$ and $s=\sin \theta$,Thus $M(\theta )$ is orthogonal for every allowed angle, and indeed for every real angle.

Using orthogonality,Both norms are nonnegative, so taking square roots provesThus an orthogonal matrix is a Euclidean isometry fixing the origin.

The columns outside indices $i,j$ are unchanged coordinate vectors. The remaining two columns have nonzero entries only in rows $i,j$, with the $2\times 2$ block $M(\theta )$. They have squared norm ${\cos }^2\theta +{\sin }^2\theta =1$ and mutual inner product zero; they are also orthogonal to all the unchanged columns. Hence $J^{T}J=I$.

Let $r=\sqrt{x_i^2+x_j^2}$. If $r>0$, choose $\theta \in [-\pi ,\pi ]$ with $\cos \theta =x_i/r$ and $\sin \theta =x_j/r$. ThenEvery other coordinate is unchanged. If $r=0$, choose $\theta =0$; the same conclusions hold. Therefore the procedure can be fixed with the nonnegative pivot conventionThis is a Givens rotation.

Write $J_1,J_2,J_3$ for the actual successive rotations $J(1,2)$, $J(1,3)$, and $J(2,3)$, each selected using the currently transformed matrix. The first eliminates position $(2,1)$; the second eliminates $(3,1)$ while leaving row two unchanged. After these, the first column is $(r_{11},0,0{)}^T$. The final rotation of rows two and three preserves both zeros in that column and eliminates $(3,2)$. HenceA lower-triangular starting matrix does not force any further zeros above the diagonal. For example, the lower-triangular matrix with all entries on and below its diagonal equal to one gives, with the nonnegative pivot convention,which has all upper-triangular entries nonzero.

Inverting the product of rotations yields the QR factorizationThe order reverses when taking the transpose. If $A$ is orthogonal, then $R$ is both orthogonal and upper triangular. Its first column forces $|r_{11}|=1$ and orthogonality with the other columns forces $r_{12}=r_{13}=0$. Applying the same argument to the remaining block makes $R$ diagonal with entries of modulus one.

Our elimination rule makes $r_{11}$ and $r_{22}$ positive when nonzero, so they are both one. Every rotation has determinant one; thus $\det R=\det A$ andWithout a fixed pivot-sign convention one could only specify a diagonal sign matrix. The convention chosen in part (c) determines the precise signs above.

Subtract the two finite sums. In the shifted sum replace the summation index $k$ by $k-1$. For every interior index the new coefficient isby Pascal's identity; the two endpoint coefficients agree as well. ThereforeFor a degree-$d$ polynomial with leading coefficient $c\ne 0$, the backward difference has leading termSince $h>0$, this coefficient is nonzero for $d\ge 1$. Starting with $Q_{(0)}=P$, iteration gives degree $n-r$ and leading coefficient $c{h}^{r}n!/(n-r)!$ for $0\le r\le n$. The next difference of the resulting constant is zero:

A natural cubic spline with the given knots is a $C^2$ function that is polynomial of degree at most three on each interval between consecutive knots and has $S^{\prime \prime }(x_0)=S^{\prime \prime }(x_4)=0$. With the usual whole-line convention, it extends affinely outside the extreme knots. The word natural refers to these endpoint second-derivative conditions; the interpolation values must be specified separately.

For $H_k(x)=(x-x_k{)}_{+}^3$, direct differentiation on either side of the knot givesBoth one-sided limits of the function and its first two derivatives at $x_k$ are zero, so these formulas are continuous there andIts third derivative jumps from zero to six, which is permitted for a cubic spline.

The finite sum of truncated cubes is $C^2$ by part (b) and is cubic on each knot interval. For $x\le 0$, every term vanishes. For $x\ge 4h$, every truncated power equals its ordinary polynomial, so part (a) applied to $P(x)=x^3$ givesIt is therefore zero on both exterior intervals. Its $C^2$ regularity makes the endpoint second derivatives zero too, proving naturality.

Evaluation at the five knots givesFor example the three interior values in units of $h^3$ are $1$, $8-4=4$, and $27-4\cdot 8+6=1$. At $4h$ the cancellation is $64-4\cdot 27+6\cdot 8-4=0$.

For $h=1$ an explicit graph description isIt is symmetric about $x=2$, increases from zero to its maximum four at the centre, and decreases symmetrically back to zero. It joins the zero tails with zero first and second derivatives.