Past exam of the numerical linear algebra and continuous optimisation course of the University of Oxford / 2009 / A

A real square orthogonal matrix satisfies $Q^{T}Q=Q{Q}^T=I$, so it preserves the Euclidean norm. The columns of $Z_h$ are orthonormal, hence $\Vert Z_{h}v{\Vert }_2=\Vert v{\Vert }_2$. The induced matrix norm therefore givesFor the left truncation, $\Vert Q_{\ell }^{T}A{\Vert }_2\le \Vert A{\Vert }_2$, and equality is guaranteed for arbitrary $A$ only when $\boxed{\ell =m}$. Indeed, if $\ell <m$, take $A=q_{\ell +1}{e}_1^T$, where $q_{\ell +1}$ is an omitted column of $Q$. Then $\Vert A{\Vert }_2=1$ but $Q_{\ell }^{T}A=0$. Merely taking $\ell \ge n$ does not guarantee preservation for an arbitrary $A$.

A full QR decomposition of a real $m\times n$ matrix is $A=QR$, with $Q$ orthogonal and $R$ upper trapezoidal; for a square matrix, $R$ is upper triangular. Fix the following sign convention for a Givens rotation: it is the identity except for its $(i,k)$ blockThe block transpose times the block is $I_2$ because $c^2+s^2=1$, proving orthogonality. Writing $r=\sqrt{x_i^2+x_k^2}$, the choice $\boxed{c=x_i/r,s=x_k/r}$ gives $(Jx{)}_k=0$ and $(Jx{)}_i=r$. To zero the other coordinate take $\boxed{c=x_k/r,s=-x_i/r}$, giving $(Jx{)}_i=0$. If $r=0$, both entries are already zero and the identity suffices.

For a tridiagonal matrix, successively rotate adjacent row pairs $(1,2),(2,3),\dots ,(n-1,n)$, each time zeroing the current entry $(k+1,k)$. Earlier columns remain triangular because both affected rows are already zero there. The result $R=J_{n-1}\cdots J_{1}A$ is upper triangular, so $Q=J_1^T\cdots J_{n-1}^T$ gives its QR decomposition. Only $n-1$ rotations are required; the resulting $R$ has at most two superdiagonals.

For a full square matrix, process columns $j=1,\dots ,n-1$. Within column $j$, for $i=n,n-1,\dots ,j+1$, rotate rows $(i-1,i)$ to eliminate the current $(i,j)$ entry. Previously cleared columns stay clear. With $J_1,\dots ,J_s$ in application order, $s=n(n-1)/2$, one has $\boxed{R=J_s\cdots J_{1}A,Q=J_1^T\cdots J_s^T}$. This is QR decomposition by Givens rotations.

The Gauss-Seidel method updates coordinates successively using the newest available entries:It is well-defined for every initial vector exactly when every $a_{ii}\ne 0$, equivalently when the triangular matrix $D+L$ is invertible. Nonsingularity of $A$ alone does not ensure this. The matrix form isIf the iterates converge to $z$, passing to the limit gives $(D+L)z=b-Uz$, hence $Az=b$. Nonsingularity identifies $z$ as the unique solution $x$.

Now assume $A$ is a symmetric positive-definite matrix. Testing with the coordinate vector gives $a_{ii}=e_i^{T}A{e}_i>0$, so $D$ is positive definite. The form $⟨v,w{⟩}_A=v^{T}Aw$ is an inner product: bilinearity and symmetry are immediate and positivity is the hypothesis. Its Cauchy-Schwarz inequality givesproving the triangle inequality; definiteness and absolute homogeneity are immediate. Thus $\Vert v{\Vert }_A=\sqrt{v^{T}Av}$ is the energy norm.

Subtract the iteration from the exact equation to obtain $(D+L)e_{k+1}=-L^T{e}_k$. HenceUsing the preceding iteration also gives $(D+L)e_k=-L^T{e}_{k-1}$ and therefore $A{e}_k=L^T(e_k-e_{k-1})$ for $k\ge 1$, as required.

Put $d=e_k-e_{k+1}$. Expanding the two quadratic forms and using the first identity gives the exact Gauss-Seidel energy decrease identity:Here $2d^{T}Ld=d^T(L+L^T)d$. If $d=0$, then $A{e}_k=0$, so $e_k=0$. Otherwise $d^{T}Dd>0$. Thus $\boxed{\Vert e_k{\Vert }_A>\Vert e_{k+1}{\Vert }_A}$ unless the exact solution has already been reached.

The Krylov subspace is $\boxed{K_k(A,r)=\mathrm{span}\{r,Ar,\dots ,A^{k-1}r\}}$. If $y-z=q(A)r$ for a polynomial $q$ of degree at most $k-1$, thenso $\mathrm{deg}p\le k$ and $p(0)=1$. Conversely, this residual identity impliesThus the converse holds whenever $A$ is invertible. More precisely, for fixed $A,r,k$ it holds for every such $y$ exactly when $\ker A\subseteq K_k(A,r)$: the identity determines $y-z$ only up to an arbitrary nullspace vector. Without this qualification the singular-matrix converse is false, for example when $A=0$, $r=e_1$ and $y-z=e_2$.

Assume $r\ne 0$ and exact arithmetic for the Lanczos algorithm. At step $j$ putprovided $w\ne 0$. The initial coefficient of $v_0=0$ is immaterial. Inductively suppose $v_1,\dots ,v_j$ are orthonormal. Then $v_j^{T}w=0$ by the choice of ${\delta }_j$. For $j>1$, symmetry and the preceding recurrence give $v_{j-1}^{T}A{v}_j={\gamma }_j$, so $v_{j-1}^{T}w=0$. If $i\le j-2$, the recurrence gives $A{v}_i\in \mathrm{span}(v_1,\dots ,v_{i+1})$, and therefore $v_i^{T}A{v}_j=(A{v}_i{)}^T{v}_j=0$. Hence $w$ is perpendicular to every preceding basis vector. Its normalization supplies the next orthonormal vector.

Every new $v_{j+1}$ belongs to $K_{j+1}(A,r)$. The $j+1$ orthonormal vectors are independent, whereas that Krylov subspace has dimension at most $j+1$; they therefore form its basis. Continuing the recurrence one more step givesIn particular $T_k=V_k^{T}A{V}_k$. If the next residual is zero, the last term is zero and the span is an invariant subspace; no undefined normalized vector is needed. If $v_1$ is an eigenvector, $A{v}_1={\delta }_1{v}_1$, so ${\gamma }_2=0$ immediately. The algorithm terminates with the exact one-dimensional invariant subspace, rather than generating further vectors. If $r=0$, the initial residual has already vanished and the normalization defining $v_1$ is unnecessary.