Past exam of the Probability, statistics and options II course of the University of Oxford / 2009 / P (Numerical Analysis)

Interpolation means $p_n(x_i)=f(x_i)$ for every node. Define the cardinal polynomials ${\ell }_i(x)={\prod }_{j\ne i}(x-x_j)/(x_i-x_j)$, which are well defined because the nodes are distinct. They have degree $n$ and satisfy ${\ell }_i(x_j)={\delta }_{ij}$. Hencebelongs to ${\Pi }_n$ and interpolates. If two polynomials in ${\Pi }_n$ interpolate the same data, their difference has $n+1$ distinct zeros but degree at most $n$, so it is zero. This proves uniqueness. The phrase “of degree $n$” denotes membership in ${\Pi }_n$ here: the actual degree may be smaller, for example for constant data.

Multiplying the Vandermonde matrix $A_n$ by a coefficient vector $(c_0,\dots ,c_n{)}^T$ evaluates the polynomial ${\sum }_j{c}_j{x}^j$ at all nodes. If the result is zero, part (a)'s uniqueness for the zero interpolation data forces every coefficient to be zero. Thus the square matrix has trivial kernel and is invertible. Equivalently the interpolation map is a linear bijection between two spaces of dimension $n+1$.

If $x$ is a node, both sides vanish and any $\xi \in (a,b)$ works. Otherwise put $\omega (t)={\prod }_i(t-x_i)$ and $C=(f(x)-p_n(x))/\omega (x)$. The function $H(t)=f(t)-p_n(t)-C\omega (t)$ has $n+2$ distinct zeros, at the nodes and at $x$. Repeated application of Rolle's theorem gives an interior point $\xi$ where $H^{(n+1)}(\xi )=0$. As $p_n^{(n+1)}=0$ and ${\omega }^{(n+1)}=(n+1)!$, this gives $C=f^{(n+1)}(\xi )/(n+1)!$. ThereforeThe distinct nodes and $n\ge 1$ ensure $a<b$, so the interior point is meaningful.

Every derivative of order $n+1$ of $\sin 2x$ has magnitude at most $2^{n+1}$. Pair the symmetric nodes $a=i/n$ and $1-a$. For $0\le x,a\le 1$,If there is an unpaired middle node, its factor has magnitude at most $1/2$. Thus the full nodal product is at most $2^{-(n+1)}$, giving the stronger bound $\Vert f-p_n{\Vert }_{\infty }\le 1/(n+1)!$. In particular this implies the requestedThe bound tends to zero by factorial growth, so $\boxed{p_n\to f\text{ uniformly on }[0,1]}$. This conclusion uses smoothness of this particular function and does not assert uniform convergence of equispaced interpolation for arbitrary continuous data.

Set $P=v{v}^T/(v^{T}v)$. Since $v\ne 0$, it is well defined, symmetric and idempotent: $P^T=P$, $P^2=P$. Therefore $H_{v,\alpha }=I-\alpha P$ is symmetric, andBecause $P\ne 0$, this equals $I$ exactly when $\alpha (\alpha -2)=0$. Hence $\boxed{H_{v,\alpha }\text{ orthogonal}⟺\alpha \in \{0,2\}}$.

If $x\in S_v$, then $v^{T}x=0$ and $Px=0$, so $\boxed{H_{v}x=x}$. For arbitrary $x$, $v^{T}P=v^T$, givingThus the Householder map fixes the hyperplane orthogonal to $v$ and reverses the component in its normal direction: it is a reflection, not merely an arbitrary orthogonal map.

Choose $c=-{\mathrm{sgn}}_{+}(x_1)\Vert x\Vert$, with ${\mathrm{sgn}}_{+}(0)=1$, and put $v=x-c{e}_1$. The opposite sign choice guarantees $v\ne 0$, even if $x$ is already parallel to $e_1$. Since $c^2=\Vert x{\Vert }^2$,Consequently $H_{v}x=x-2v(v^{T}x)/(v^{T}v)=x-v$, yieldingThe sign choice also avoids cancellation in constructing $v$ numerically.

Proceed column by column. At stage $j=1,\dots ,n-2$, consider the entries below the diagonal in column $j$, indexed $j+1,\dots ,n$. If this tail is nonzero, part (c) provides a Householder matrix sending it to a multiple of its first coordinate vector. Embed this matrix as an orthogonal matrix acting identically on coordinates $1,\dots ,j$, and apply the similarity transformation $A\mapsto Q_j^{T}A{Q}_j$. The tail's entries below row $j+1$ become zero. Symmetry is preserved, so the corresponding entries in row $j$ vanish too. If the tail is already zero, use the identity transformation.

Earlier reduced columns remain unchanged in their required zero positions: all their entries in the newly mixed tail coordinates were already zero, and the first $j$ coordinates are fixed. Thus each stage preserves the previous zeros while creating the next ones. After $n-2$ stages, all entries at distance greater than one from the diagonal vanish. With the product $Q=Q_1\cdots Q_{n-2}$ one has $Q^{T}Q=I$ andThis constructive reduction uses only reflections on successive trailing subspaces.