Past exam of the numerical linear algebra course of the University of Oxford / 2011 (C12.1a, DMAC 2A88, DMSU 2A88)

Original solutions to the Numerical Linear Algebra paper of 14 June 2011. Source: the older Mathematics release, supplied in Part C 2007 11.pdf, pages 469–472. All three questions and their fourteen lettered parts are covered.

A real singular value decomposition has the form $A=U\Sigma V^T$, where $U\in {\mathbb{R}}^{m\times m}$ and $V\in {\mathbb{R}}^{n\times n}$ are orthogonal matrices, and $\Sigma$ is a rectangular diagonal matrix with entries ${\sigma }_1\ge \cdots \ge {\sigma }_{\min (m,n)}\ge 0$. These entries are the singular values. Their squares are the eigenvalues of $A^{T}A$, omitting the additional zero eigenvalues when $n>m$. The positive singular values number exactly the matrix rank.

Use the singular value decomposition and the orthogonal invariance of the Euclidean norm. Put $z=V^{T}x$ and $c=U^{T}b$. Since precisely ${\sigma }_1,\dots ,{\sigma }_r$ are positive,The second sum is independent of $x$ and cannot be removed. The first sum vanishes exactly when $z_j=c_j/{\sigma }_j$ for $1\le j\le r$, while $z_{r+1},\dots ,z_n$ are arbitrary. Thus every least-squares solution isThe unavoidable linear-system residual is the component of $b$ orthogonal to the column space of $A$:The minimum-norm least-squares solution sets all ${\alpha }_j=0$ and equals $A^{+}b$, where $A^{+}$ is the Moore-Penrose inverse. The squared minimum, rather than the minimum itself, is the second sum in the first display.

Let $u_j$ and $v_j$ be the columns of the orthogonal matrices $U$ and $V$ in the singular value decomposition. Multiplying by the rectangular diagonal matrix retains its $r$ nonzero diagonal entries:The families $(u_j)$ and $(v_j)$ are orthonormal, hence in particular orthogonal. Each summand is a rank-one outer product, and the remaining terms vanish because their singular values are zero.

For the matrix's Euclidean operator norm, orthogonal invariance of the Euclidean norm givesTaking $x=v_1$ gives equality, so $\Vert A{\Vert }_2={\sigma }_1$. For the Frobenius norm, the trace identity and the singular value decomposition giveConsequentlyHere the Euclidean matrix norm means the operator norm induced by the vector Euclidean norm, rather than the entrywise Euclidean length, which is the Frobenius norm.

The two columns are orthogonal, with lengths one and two; equivalently $A^{T}A=\mathrm{diag}(1,4)$. Ordering the singular values decreasingly requires swapping the right coordinate directions. One full singular value decomposition isBoth $U$ and $V$ are orthogonal matrices, and direct matrix multiplication gives $U\Sigma V^T=A$. Hence

The spectral theorem for real symmetric matrices gives $A=Q\Lambda Q^T$ with an orthogonal matrix $Q$. Positive definiteness makes every eigenvalue ${\lambda }_i$ positive. Define the matrix square rootIt is symmetric, its square is $A$, and for any nonzero vector $x$,Thus it is also positive-definite, and its matrix inverse is $A^{-1/2}=Q\mathrm{diag}({\lambda }_i^{-1/2})Q^T$.

The induced matrix norm associated with the given energy norm is a supremum of length ratios. The invertible change of variables $y=A^{1/2}x$ givesThe last expression is the Euclidean operator norm. This is the matrix norm induced by an energy norm: transforming to coordinates with Euclidean lengths transforms the operator by the corresponding matrix similarity.

Write $A=D+L+R$, where $D$ is the diagonal matrix of diagonal entries of $A$, and $L,R$ are its strictly lower- and upper-triangular parts. Since $A$ is symmetric, $R=L^T$. Subtract the two factors in the SOR iteration:Therefore, for $\omega \ne 0$,Positive definiteness makes each $D_{ii}>0$, so the triangular matrix $B(\omega )$ is an invertible matrix for every $\omega \ne 0$. The original formula gives $C(0)=I$; the expression for $B(\omega )$ itself is undefined there. The affine term ensuring that the desired solution is a fixed point is $c=B(\omega {)}^{-1}b$.

Apply the matrix norm induced by an energy norm and set $T=A^{1/2}C(\omega )A^{-1/2}=I-A^{1/2}{B}^{-1}{A}^{1/2}$. Multiplication givesThe bracket factors as $B^{-T}(B+B^T-A)B^{-1}$. Because $B=D/\omega +L$ and $A=D+L+L^T$,Thus $T^{T}T=M(\omega )$ for the stated matrix. In particular $M(\omega )$ is a positive semidefinite matrix. The Euclidean operator norm squared is the largest eigenvalue of $T^{T}T$, and all those eigenvalues are nonnegative. ConsequentlyThis identity is the algebraic step in the energy-norm proof of convergence of SOR; spectral radius equals the largest eigenvalue here because $M(\omega )=T^{T}T$.

For $0<\omega <2$, the coefficient $\gamma =2/\omega -1$ is positive. Moreoveris a positive-definite matrix: for a nonzero vector $z$, put $y=B^{-1}{A}^{1/2}z\ne 0$; then $z^{T}Gz=y^{T}Dy>0$. Hence every eigenvalue of $M=I-\gamma G$ is strictly below one. Part (d) also gives $M=T^{T}T$, so these eigenvalues are nonnegative. ThereforeThe energy-norm proof of convergence of SOR thus makes the iteration a strict contraction mapping in this norm. Its forward error satisfies $e^{(j+1)}=C(\omega )e^{(j)}$, so it converges geometrically to zero.

For the quadratic function, write $r_j=b-A{x}_j$ and restrict to the full line $x_j+\alpha p_j$. Symmetry of $A$ givesThe coefficient $p_j^{T}A{p}_j$ is positive by positive definiteness and $p_j\ne 0$. The unique minimizer is thereforeQuadratic minimization along a line also gives the exact changeThus strict decrease holds exactly when $p_j^T{r}_j\ne 0$. The search is over the whole line, so ${\alpha }_j$ can be negative; a positive step size would require the additional descent direction condition $p_j^T{r}_j>0$.

The exact minimization gives $r_{j+1}=r_j-{\alpha }_{j}A{p}_j$, with ${\alpha }_j=p_j^T{r}_j/(p_j^{T}A{p}_j)$. For steepest descent method, the next search direction is $p_{j+1}=r_{j+1}$. HenceThus consecutive nonzero search directions are orthogonal. This calculation even covers an arbitrary initial direction $p_1$, as in the generic algorithm: it only needs the exact preceding line minimization and the choice $p_{j+1}=r_{j+1}$. If the new linear-system residual is zero, the linear system is already solved. No pairwise orthogonality of all nonconsecutive directions is asserted.

Nonzero vectors $p_1,\dots ,p_k$ are conjugate directions with respect to $A$ when $p_i^{T}A{p}_j=0$ for $i\ne j$. They are linearly independent: if ${\sum }_i{c}_i{p}_i=0$, multiplication by $p_j^{T}A$ gives $c_j{p}_j^{T}A{p}_j=0$, hence $c_j=0$ by positive definiteness. There are consequently at most $n$ such directions.

The finite termination of conjugate directions follows from the residual orthogonality maintained by the exact line minimizations. At step $j$,For $i<j$, conjugacy gives $p_i^T{r}_{j+1}=p_i^T{r}_j$. By mathematical induction, $r_{j+1}$ is orthogonal to every $p_1,\dots ,p_j$. After $n$ nonzero conjugate directions they form a basis of ${\mathbb{R}}^n$, forcing $r_{n+1}=0$. Thus the method reaches $Ax=b$ in at most $n$ steps, and positive definiteness makes that solution unique. The claim is in exact arithmetic; rounding errors need not preserve exact conjugacy.

Since $A{p}_1=(5,2{)}^T$, an A-conjugate direction $p_2=(a,b{)}^T$ must satisfy $5a+2b=0$. One nonzero choice isDirect matrix multiplication gives $A{p}_2=(3,-3{)}^T$, and $p_1^{T}A{p}_2=0$. All nonzero scalar multiples of this vector also qualify.