Past exam of the 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 Lagrange basis polynomialsDistinctness of the nodes makes every denominator nonzero, and ${\ell }_i(x_j)={\delta }_{ij}$. Thusis a polynomial of degree at most $n$ with the required values. If two such polynomials existed, their difference would have $n+1$ distinct roots while having degree at most $n$; the polynomial root bound makes it identically zero. Hence existence and uniqueness hold. The actual degree can be smaller than $n$, despite the conventional name.

Multiplication by the displayed Vandermonde matrix maps the coefficient vector of a polynomial of degree at most $n$ to its vector of values at the nodes. Part (a) proves that every vector of node values is attained uniquely, so this square linear map is bijective. Therefore $A_n$ is invertible. Equivalently, a kernel vector would define a polynomial of degree at most $n$ with $n+1$ distinct roots and would have to vanish.

If $x$ is a node the error and the product both vanish, and any interior $\xi$ works. Otherwise put $\omega (t)={\prod }_{i=0}^n(t-x_i)$ and $C=(f(x)-p_n(x))/\omega (x)$. The functionhas $n+2$ distinct zeros, at the nodes and at $x$. Repeated Rolle's theorem gives a point $\xi$ between the extreme zeros, and therefore in $(a,b)$, where $R^{(n+1)}(\xi )=0$. Since $p_n^{(n+1)}=0$ and ${\omega }^{(n+1)}=(n+1)!$, one gets $C=f^{(n+1)}(\xi )/(n+1)!$. Substitution gives

Every derivative of order $n+1$ of $\sin (2x)$ has absolute value at most $2^{n+1}$. The equally spaced nodes are symmetric about $1/2$. Pair each node $a\le 1/2$ with $1-a$; for $x\in [0,1]$,If an unpaired middle node remains, its factor satisfies $|x-1/2|\le 1/2$. Consequently the complete nodal product is at most $2^{-(n+1)}$. The error formula actually gives the stronger estimateThe first bound tends to zero, proving uniform convergence on the whole interval. There is no appeal to a general claim that equispaced interpolation always converges; the derivative and symmetric-product bounds are particular to this analytic function and these nodes.

Let $P=v{v}^T/(v^{T}v)$, which is a nonzero symmetric orthogonal projection: $P^T=P$ and $P^2=P$. Then $H_{v,\alpha }=I-\alpha P$ is symmetric andSince $P\ne 0$, this equals the identity exactly when $\alpha (\alpha -2)=0$. Thus

If $x\in S_v$, then $v^{T}x=0$ and the defining formula immediately gives $H_{v}x=x$. For arbitrary $x$,Thus the Householder reflection fixes the hyperplane perpendicular to $v$ pointwise and reverses the component along its normal.

Let $r=\Vert x\Vert >0$. Choose $c=-r$ if $x_1\ge 0$ and $c=r$ if $x_1<0$, and set $v=x-c{e}_1$. This opposite-sign choice ensures $v\ne 0$. Because $c^2=r^2$,ThereforeThe denominator is positive, including when $x$ already lies on the first coordinate axis.

Apply successive Householder reflections supported on smaller trailing coordinate sets. At step $k=1,\dots ,n-2$, let $x$ be the entries in rows $k+1,\dots ,n$ of column $k$ of the current symmetric matrix. If $x\ne 0$, part (c) gives an orthogonal reflection $H$ taking it to $c{e}_1$; if $x=0$, use the identity. Embed this as $Q_k=\mathrm{diag}(I_k,H)$ and replace the current matrix by $Q_k^{T}A{Q}_k$.

The first $k$ columns are unchanged by right multiplication. Left multiplication turns the tail of column $k$ into a vector supported only in row $k+1$. Previously treated columns have zero entries throughout this trailing coordinate set, so their zeros are preserved. Symmetry makes the matching row zeros appear as well. After the final step all entries below the first subdiagonal, and by symmetry above the first superdiagonal, vanish.

The product $Q=Q_1\cdots Q_{n-2}$ is orthogonal, andRestricting each transformation to its trailing coordinates is what preserves earlier zero patterns.