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

A real square matrix is orthogonal if $Q^{T}Q=I$. Then $\Vert Qx{\Vert }^2=x^T{Q}^{T}Qx=x^{T}x=\Vert x{\Vert }^2$, proving length preservation.

Define $J(i,j,\theta )$ to be identity outside rows and columns $i,j$, with blockThe block's transpose times itself is identity because ${\cos }^2\theta +{\sin }^2\theta =1$ and the off-diagonal terms cancel. Thus $J$ is orthogonal, with determinant one.

For $r=\sqrt{x_i^2+x_j^2}>0$, choose $\cos \theta =x_i/r$, $\sin \theta =x_j/r$. Then $y_i=r$, $y_j=0$ and every other coordinate is unchanged. If $r=0$, choose $\theta =0$. This fixes the useful nonnegative pivot convention.

Apply the rotations to the current matrix in the displayed order from right to left. First $J(1,2)$ eliminates entry $(2,1)$; then $J(1,3)$ eliminates $(3,1)$ without changing row two. Finally $J(2,3)$ eliminates $(3,2)$ while preserving the zeros in column one. ThusInverting the product gives $A=QR$. Even if $A$ starts lower triangular, the row rotations generally create nonzero entries above the diagonal; there is no further universal simplification. For example $A=\left(\begin{array}{ccc}1& 0& 0\\ 1& 1& 0\\ 1& 1& 1\end{array}\right)$ gives positive-pivotwhose three entries above the diagonal are all nonzero.

If $A$ is orthogonal, $R$ is both upper triangular and orthogonal. Orthogonality of its columns successively forces all off-diagonal entries to vanish and all diagonal entries to have absolute value one. The first two pivots are positive under our convention, and the rotations have determinant one. Therefore the precise result isWithout a specified pivot-sign convention, the invariant statement is a diagonal matrix with entries $\pm 1$ and product $\det A$.

A cubic spline is a twice continuously differentiable function whose restriction to each knot interval is a polynomial of degree at most three. Its second derivative is continuous and piecewise linear. Natural endpoint conditions are $C^{\prime \prime }(x_0)=C^{\prime \prime }(x_n)=0$.

Linearity of both the piecewise-polynomial and smoothness conditions, and of the endpoint equations, makes the natural splines a vector space $V$. A continuous piecewise linear second derivative with zero endpoint values is determined freely by its $n-1$ interior nodal values. Integrating twice adds two arbitrary affine constants. HenceThis count includes the case of one interval.

An interpolating spline has $S(x_i)=f_i$ at every node. Set $e=T-S$, so $e$ vanishes at all nodes. On each open knot interval $S^{(3)}$ is constant. Two integrations by parts giveThe terms containing $e$ vanish at nodes. When summed, the interior $e^{\prime }{S}^{\prime \prime }$ terms cancel because $e^{\prime }$ and $S^{\prime \prime }$ are continuous. The two outer terms vanish by the natural endpoint conditions. ThusIntegrating the given square identity now yields the sharper energy decompositionIn particular the natural interpolating spline minimizes the squared-curvature integral.

If $T$ is another natural interpolant, the same minimizing argument in both directions makes the two energies equal. The final nonnegative integral then vanishes, so $T^{\prime \prime }=S^{\prime \prime }$ everywhere by continuity. Their difference is affine and zero at all knots, including the two distinct endpoints, so $T=S$. This proves uniqueness.

It also supplies existence if needed: nodal evaluation is a linear map from the $(n+1)$-dimensional space $V$ to ${\mathbb{R}}^{n+1}$. Its kernel is zero by the same argument with zero data and the zero competitor. It is therefore surjective, so every data vector has a natural spline interpolant.