Past exam of the options II course of the University of Oxford / 2008 printed variant / P (Numerical Analysis)

The norm induced by a real inner product isPositive definiteness and homogeneity follow from the inner product axioms; Cauchy-Schwarz gives the triangle inequality by expanding $\Vert u+v{\Vert }^2$.

Use the usual weighted $L^2$ interpretation, identifying functions equal almost everywhere; on raw pointwise functions the displayed integral is only a seminorm. Assume $q\in {\Pi }_k\subset V$. If $f-q$ is orthogonal to ${\Pi }_k$, then for every $p\in {\Pi }_k$,Conversely, suppose $q$ minimizes the error. For $r\in {\Pi }_k$ and every real $t$, compare $q$ with $q+tr$:If the linear coefficient were nonzero, a sufficiently small $t$ with the appropriate sign would make the expression negative. Thus $⟨f-q,r⟩=0$ for every $r$, proving best approximation is equivalent to orthogonality of the residual.

Write $q=A+Bx$ and $\ell =\log 3$. Orthogonality of $x^2-q$ to $1$ and $x$ givesThe Gram matrix is positive definite, with determinant $4(\ell -1)>0$, so the solution is unique. Solving yields

The singular weight requires care about the space of admissible polynomials. Since $n\ge 1$, $x^n$ has finite squared norm. A polynomial $q$ has finite error relative to $x^n$ near zero exactly when $q(0)=0$: a nonzero constant term makes the integrand asymptotic to $q(0{)}^2/x$, whose integral diverges. If $q(0)=0$, the residual is $O(x)$ and the integrand is $O(x)$.

Thus the full space ${\Pi }_{n-1}$ is not a subspace of $V$, so the projection theorem cannot be applied to it as written. Nevertheless a unique best finite-error approximation does exist inFor $n=1$, this is the zero space and the answer is $q=0$. For $n\ge 2$, $W$ is finite dimensional and its Gram matrix is positive definite, because a nonzero polynomial cannot vanish on an interval. Solving the normal equations therefore gives its unique orthogonal projection of $x^n$. All omitted polynomials have infinite error, so this also minimizes the extended error over the full polynomial set. The distinction is an invalid full-space projection premise, not nonexistence of every finite-error best approximation. As throughout weighted $L^2$, use equivalence classes for the underlying measure.

The residual is orthogonal to $q\in {\Pi }_k$, so Pythagoras givesTaking nonnegative square roots proves $\boxed{\Vert q\Vert \le \Vert f\Vert }$.

A QR factorization is $A=QR$, where $Q^{T}Q=I$ and $R$ is upper triangular. If $A$ is orthogonal, so is $R=Q^{T}A$. Its inverse is upper triangular, but $R^{-1}=R^T$ is lower triangular, forcing $R$ to be diagonal. Orthogonality then givesWith the customary positive diagonal convention, $R=I$.

Only the first and third coordinates occur in the first two columns. Normalize the first column to get $q_1=(4,0,3,0{)}^T/5$. Removing its component from the second column leaves $(21,0,-28,0{)}^T/5$, of length seven, so $q_2=(3,0,-4,0{)}^T/5$. The remaining orthonormal columns can be $q_3=e_2$ and $q_4=e_4$. Taking their dot products with the columns of $A$ givesThe columns of $Q$ are orthonormal, and direct multiplication gives the source matrix. Exploiting its two-coordinate first block avoids unnecessary four-dimensional elimination.

Starting with $A_0=A$, choose real shifts ${\sigma }_j$, factor $A_j-{\sigma }_{j}I=Q_j{R}_j$, and setEach step is an orthogonal similarity, so the eigenvalues are preserved and all iterates are similar. If $A_j^T=A_j$, transposing $Q_j^T{A}_j{Q}_j$ proves symmetry of $A_{j+1}$, completing the induction.

The given matrix is the Householder reflectionIt has eigenvalue $-1$ along $1$ and $+1$ on its orthogonal complement, hence $A^{T}A=I$. In the positive-diagonal QR convention its unshifted factorization is $Q=A$, $R=I$, so the next iterate is again $A$. Thus unshifted QR is stationary, despite the matrix generally having nonzero off-diagonal entries. If arbitrary diagonal signs are allowed in $R$, a step can instead replace $A$ by $DAD$ for a diagonal sign matrix $D$; every off-diagonal magnitude remains unchanged. Such sign changes still make no progress towards diagonalization.