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

The Lagrange interpolation polynomialhas degree at most $n$ and takes the required value at each node, proving existence. If two such polynomials existed, their difference would have $n+1$ distinct roots despite degree at most $n$, so it would vanish identically. This proves uniqueness.

Define $P(x)=[(x-x_0)r(x)-(x-x_n)q(x)]/(x_n-x_0)$. It has degree at most $n$. At $x_0$ its value is $q(x_0)=f_0$, and at $x_n$ it is $r(x_n)=f_n$. At every interior node both $q$ and $r$ equal $f_i$, giving $P(x_i)=f_i$. Uniqueness therefore givesIf the data come from $x^m$ with $m\le n$, uniqueness gives $p=x^m$. If $m<n$, that same polynomial has degree at most $n-1$ and satisfies each smaller interpolation problem, so $q=r=x^m$.

For the final claim assume $n\ge 2$. Put $t=q-r$. Its node values are $t(x_0)=f_0-r(x_0)$, $t(x_i)=0$ for $1\le i\le n-1$, and $t(x_n)=q(x_n)-f_n$. The linear spline $s$ joining these values has a ramp on the first interval, is zero on all middle intervals, and has a ramp on the last. ThusOn each node interval $s^{\prime }$ is constant and $t-s$ vanishes at both ends. Hence $\int s^{\prime }(t^{\prime }-s^{\prime })dx=0$ on that interval. Integrating the supplied identity and summing giveswhich proves the claimed inequality and the minimum Dirichlet energy of a linear interpolant.

There is a source exception: with $n=1$, $q=f_0$ and $r=f_1$, so $t$ is constant and the left side of the asserted bound is zero. If $f_0\ne f_1$, its right side is $2(f_0-f_1{)}^2/(x_1-x_0)>0$. Thus the final inequality requires $n\ge 2$, although the preceding interpolation statements remain valid for $n=1$.

For a nonzero real vector $w$, a Householder reflection isWriting $P=w{w}^T/(w^{T}w)$ gives $P^T=P$ and $P^2=P$, so $H^{T}H=(I-2P{)}^2=I$. Thus a Householder matrix is an orthogonal matrix, and it reflects across the hyperplane perpendicular to $w$.

For $u\ne 0$, choose $\alpha =-\mathrm{sgn}(u_1)\Vert u\Vert$, taking the sign to be $+1$ when $u_1=0$, and put $w=u-\alpha e_1$. This $w$ is nonzero. Since ${\alpha }^2=\Vert u{\Vert }^2$, direct expansion gives $w^{T}w=2(\Vert u{\Vert }^2-\alpha u_1)$ and $w^{T}u=\Vert u{\Vert }^2-\alpha u_1$, soApply this construction successively to the trailing part of each column of $A$, extending each reflection by an identity on earlier coordinates. Previously created zeros are preserved. If a trailing column vector is zero, use the identity there. The resulting product $Q^T$ is orthogonal and $Q^{T}A=R$ is upper triangular, yielding the QR factorization $A=QR$ even when $A$ is singular.

To solve $Ax=b$, multiply by $Q^T$ and use back substitution on $Rx=Q^{T}b$ when $R$ is nonsingular. If $A$ is singular, $\det R=\det (Q^T)\det A=0$; an upper triangular determinant is its diagonal product, so at least one diagonal entry is zero. In that case consistency and free variables require separate treatment.

The unshifted QR algorithm starts from $A_0=A$, factors $A_k=Q_k{R}_k$, and formsEvery iterate is related by an orthogonal similarity transformation to the previous one and hence to $A$, with the same eigenvalues. Symmetry is preserved. For symmetric matrices with appropriate spectral separation, the iterates approach diagonal form: the off-diagonal entries decrease and the diagonal exposes the eigenvalues. Practical shifted QR accelerates convergence and uses deflation when off-diagonal couplings become negligible. With a shift ${\mu }_k$, factor $A_k-{\mu }_{k}I=Q_k{R}_k$ and set $A_{k+1}=R_k{Q}_k+{\mu }_{k}I$; the same similarity identity still holds.

Universal diagonal convergence of unshifted QR would be too strong. For example $A=\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)$ admits the standard factorization $Q=A$, $R=I$, so the iteration remains at $A$ rather than becoming diagonal, although its eigenvalues are $\pm 1$. Such equal-modulus cases require a convergence qualification or treatment of a retained block. Similarity is unconditional; convergence to a useful limiting form is an additional algorithmic property.