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

The Krylov subspace is $K_k(A,r)=\mathrm{span}\{r,Ar,\dots ,A^{k-1}r\}$. Write $x_k-x_0=q(A)r_0$ with $\mathrm{deg}q\le k-1$. For the exact solution, $r_0=A(x-x_0)$, soThis polynomial has degree at most $k$ and $p(0)=1$. It is the error-polynomial representation for a Krylov subspace method.

Every point in the affine search space is uniquely $x_k=x_0+V_{k}y$, since the columns of $V_k$ form a basis. Its linear-system residual is $r_k=r_0-A{V}_{k}y$, so minimizing the residual is exactly the linear least-squares problem ${\min }_y\Vert r_0-A{V}_{k}y{\Vert }_2$.

Use the standard starting choice $v_1=r_0/\Vert r_0{\Vert }_2$ and an orthonormal extended basis $V_{k+1}$. If $A{V}_k=V_{k+1}{L}_k$, then $r_0=V_{k+1}(\Vert r_0{\Vert }_2{e}_1)$ and orthonormality givesThe starting-vector choice is needed for this particular $e_1$ representation; an arbitrary orthonormal basis need not have those initial coordinates.

The Arnoldi iteration constructs the basis. At column $j$, orthogonalize $A{v}_j$ against $v_1,\dots ,v_j$, recording coefficients $h_{ij}=v_i^{T}A{v}_j$; normalize the remaining vector with $h_{j+1,j}$ to get $v_{j+1}$. This makes $L_k$ an upper Hessenberg matrix of size $(k+1)\times k$. The resulting GMRES algorithm starts from $x_0,r_0$, grows this Arnoldi basis, solves the small least-squares problem, and sets $x_k=x_0+V_{k}y$. Its small residual norm provides the stopping test. Incremental Givens rotations efficiently update the small QR decomposition instead of solving it anew. Zero initial residual means the system is already solved; Arnoldi breakdown gives an invariant subspace and, for nonsingular $A$, permits exact solution within it.

One restarted step chooses $x_j=x_{j-1}+{\alpha }_j{r}_{j-1}$ to minimize the new residual norm. Since $r_{j-1}=A(x-x_{j-1})$,and induction givesThese polynomials have degree at most one; a zero step gives the constant polynomial one.

In the specified example the first search space is spanned by $b=(1,1{)}^T$. Writing $x_1=\alpha b$, its squared residual norm is $(1-\alpha {)}^2+(1+\alpha {)}^2=2+2{\alpha }^2$, uniquely minimized at $\alpha =0$. Thus restarted GMRES gives $\boxed{x_1=x_2=(0,0{)}^T}$ and stagnates forever, repeatedly facing the same minimization problem.

Without restarting, the first iterate is still zero, but $K_2(A,b)=\mathrm{span}\{(1,1{)}^T,(1,-1{)}^T\}={\mathbb{R}}^2$. The second minimization finds the exact solution $\boxed{x_2=(1,-1{)}^T}$. This one-step restarted GMRES stagnation example shows how discarding the accumulated search space can prevent convergence even for a nonsingular two-dimensional system.