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

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.