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

Define $\boxed{\Vert v\Vert =\sqrt{⟨v,v⟩}}$. Positive definiteness gives nonnegativity and separation of zero, and bilinearity gives absolute homogeneity. Cauchy–Schwarz follows by minimizing the nonnegative quadratic $\Vert u-tv{\Vert }^2$ in real $t$. It then gives $\Vert u+v{\Vert }^2\le (\Vert u\Vert +\Vert v\Vert {)}^2$, establishing the triangle inequality. Thus this is a norm.

Interpret the weighted function space as measurable functions modulo equality almost everywhere, so the integral form is a genuine inner product. Assume $q\in {\Pi }_k\subseteq V$. If the residual is orthogonal to ${\Pi }_k$, then for $p\in {\Pi }_k$,Thus $q$ is a best approximation. Conversely, if it is best, take any $r\in {\Pi }_k$ and vary through $q+tr$. The polynomialhas a minimum at $t=0$, so its derivative there vanishes. Hence $\boxed{⟨f-q,r⟩=0}$ for every $r\in {\Pi }_k$. The same Pythagorean identity proves uniqueness of the best approximation.

Write $q(x)=a+bx$. Orthogonality of $x^2-q$ to $1,x$ givesThe entries are obtained by integrating $1/x,1,x,x^2$ over the given interval. Subtracting the second equation divided by two from the first gives $(\log 3-1)a=-1/3$. ThusThe Gram matrix is positive definite, with determinant $4(\log 3-1)>0$, so this orthogonal projection is the unique best approximation.

As explained by admissible polynomials for a singular inverse-linear weight, there is a domain issue: the constant polynomial does not belong to the weighted space, because ${\int }_0^1{x}^{-1}dx=\infty$. Hence the full space ${\Pi }_{n-1}$ is not a subspace of $V$, and the preceding inner-product projection theorem cannot be applied to it as stated.

Nevertheless a meaningful finite-error best approximation does exist after restricting to admissible polynomials. The target $x^n$ lies in $V$ for every $n\ge 1$, since its squared integrand near zero is $x^{2n-1}$. A polynomial $p\in {\Pi }_{n-1}$ has finite error exactly when $p(0)=0$: otherwise the residual tends to a nonzero constant and its weighted squared integral diverges; if $p(0)=0$, it has at least a simple zero and is integrable in the required norm. Thus the admissible approximation space isFor $n=1$ it is $\{0\}$, giving best approximation zero. For $n\ge 2$ it is a finite-dimensional inner-product subspace with positive definite Gram matrix, so it has a unique orthogonal projection of $x^n$. Therefore the full polynomial-space formulation is not defined inside $V$, but the finite-error interpretation has a unique best approximation. Declaring that no best approximation can exist under any interpretation would miss this admissible subspace.

The best-approximation characterization gives $⟨f-q,q⟩=0$, since $q\in {\Pi }_k$. ConsequentlyTaking nonnegative square roots proves $\boxed{\Vert q\Vert \le \Vert f\Vert }$. Thus an orthogonal projection cannot increase the norm.

A real square QR factorization is $A=QR$ with $Q^{\mathsf{T}}Q=I$ and $R$ upper triangular. For an invertible matrix it can be made unique by requiring positive diagonal entries of $R$.

If $A$ is orthogonal, then $R=Q^{\mathsf{T}}A$ is orthogonal as well. An orthogonal upper triangular matrix is diagonal with entries $\pm 1$: its first column has just its first entry, which must have modulus one, and orthogonality then zeros the rest of the first row; repeat inductively on the lower block. Thusand under the positive-diagonal convention $\boxed{R=I}$, $Q=A$.

The first column is five times $(4,0,3,0{)}^{\mathsf{T}}/5$. Its orthogonal companion in the first-and-third-coordinate plane is $(3,0,-4,0{)}^{\mathsf{T}}/5$, and the second column has positive residual seven times that vector. The remaining coordinate directions can therefore be read off immediately rather than performing a general four-dimensional orthogonalization. One obtainsThe columns of $Q$ are visibly orthonormal. Taking their inner products with each column of the given matrix gives the displayed $R$, which also verifies $QR=A$ and positive diagonal entries.

At step $k$, choose a real shift ${\mu }_k$, factor $A_k-{\mu }_{k}I=Q_k{R}_k$, and setThe last equality proves orthogonal similarity at every step. Thus all iterates have the same eigenvalues; if $A_k$ is symmetric, the last expression is symmetric, proving symmetry by induction.

For the specified matrix, let $e=(1,\dots ,1{)}^{\mathsf{T}}$. Then $A=I-2e{e}^{\mathsf{T}}/n$ and $e^{\mathsf{T}}e=n$, so $A^{\mathsf{T}}=A$ and $A^2=I$. It is a Householder reflection, hence orthogonal. With the standard positive-diagonal QR convention, part (a) gives $Q=A$, $R=I$ at the first unshifted step, and therefore $A_1=RQ=A$. The same repeats forever: the unshifted algorithm is stationary.

If arbitrary diagonal signs in QR are allowed, $R=D$, $Q=AD$ for a sign matrix $D$, and the next iterate is $DAD$. Its off-diagonal magnitudes are unchanged, so even then only sign changes occur, not progress toward a diagonal form. This explains the role of the usual convention in the literal stationary-iterate statement.