Krylov Subspaces, Arnoldi and GMRES: Examples and Counterexamples

Direct multiplication gives $Ab=e_1$ and $A^{2}b=0$. Therefore $q(A)b=0$ for $q(z)=z^2$, while no nonzero polynomial of degree $<2$ annihilates $b$ because neither $b$ nor $Ab$ is zero. Hence the grade is $\nu (A,b)=2$.

The displayed Krylov spaces follow from the vectors $b,Ab,A^{2}b$. Since the grade is $2$, [L1] predicts exactly the stabilization $K_m(A,b)=K_2(A,b)$ for $m\ge 2$, which agrees with the calculation.

Since $A{v}_1=2e_1+e_2$, the first Arnoldi coefficients are $h_{11}=2$, $h_{21}=1$, and $v_2=e_2$. Next, $A{v}_2=e_1+2e_2+e_3$, so $h_{12}=1$, $h_{22}=2$, $h_{32}=1$, and $v_3=e_3$.

Therefore $Q_2=[e_1{e}_2]$ and $Q_3{\bar{H}}_2=[A{e}_{1}A{e}_2]=A{Q}_2$. The vectors are orthonormal exactly as [L1] predicts, and the Hessenberg entries are visible column by column.

Here $K_1(A,b)=\mathrm{span}\{e_1\}$ and $A{e}_1=2e_1\in K_1(A,b)$, so the current Krylov space is $A$-invariant.

By [L1], that invariance is equivalent to exact Arnoldi breakdown at the next step. Concretely, the Arnoldi residual is $w_1=A{e}_1-⟨A{e}_1,e_1⟩e_1=2e_1-2e_1=0$.

One has $H_{2}y=3y$, so $\theta =3$ is a Ritz value and $u=Q_{2}y=\frac{1}{\sqrt{2}}(e_1+e_2)$ is the associated Ritz vector. Also $e_2^{\ast }y=1\mathrm{/}\sqrt{2}$.

Applying [L1] with $m=2$ gives $Au-\theta u=h_{3,2}(e_2^{\ast }y)v_3=1\cdot \frac{1}{\sqrt{2}}{e}_3$. Therefore $\mathrm{\parallel }Au-\theta u{\mathrm{\parallel }}_2=1\mathrm{/}\sqrt{2}$.

Since $r_0=e_2$, one has $\beta =1$ and $v_1=e_2$. Also $A{v}_1=(1,1{)}^{\mathsf{T}}$, so $h_{11}=1$ and the normalized residual is $v_2=e_1$ with $h_{21}=1$. Hence ${\bar{H}}_1=\left(\begin{array}{c}1\\ 1\end{array}\right)$.

By [L1], one-step GMRES minimizes $\mathrm{\parallel }(1-y,-y{)}^{\mathsf{T}}{\mathrm{\parallel }}_2^2=(1-y{)}^2+y^2$, whose derivative is $-2+4y$, so the minimizer is $y=\frac{1}{2}$. Therefore $x_1=x_0+Q_{1}y=\frac{1}{2}{e}_2$.

The initial residual is $r_0=e_1$, and the one-step GMRES search space is $x=\alpha e_1$. The corresponding residual is $r(\alpha )=e_1-\alpha A{e}_1=e_1-\alpha e_2$, so $\mathrm{\parallel }r(\alpha ){\mathrm{\parallel }}_2^2=1+{\alpha }^2$, minimized at $\alpha =0$. Thus the first GMRES step leaves the residual norm equal to $1$.

The matrix is invertible with $\det A=-2$, and $A^{\mathsf{T}}A=\left(\begin{array}{cc}1& 1\\ 1& 5\end{array}\right)$ has eigenvalues $3\pm \sqrt{5}$. Hence the singular values are $\sqrt{3+\sqrt{5}}$ and $\sqrt{3-\sqrt{5}}$, so ${\kappa }_2(A)=\frac{3+\sqrt{5}}{2}\mathrm{.}$ Therefore exact stagnation can occur even when ordinary conditioning is only moderate. This is consistent with [L1], which warns that nonnormal behavior depends on eigenvector geometry, not eigenvalues or ${\kappa }_2(A)$ alone.

The previous calculation gives the one-step GMRES minimizer $x_1=0$, so a GMRES$(1)$ cycle starting from $x_0=0$ ends where it started. Restarting therefore reproduces the same residual $r_0=e_1$ and the same one-step problem, so every cycle returns $0$ again.

By contrast, unrestarted GMRES on an invertible $2\times 2$ system reaches the exact solution by step $2$. Thus restart length $1$ preserves the cyclewise minimization promised by [L1] but discards the information needed for the full method's finite termination.

Direct evaluation of the operator routine gives the displayed vectors $Tb$ and $T^{2}b$. Those are exactly the data from which the first Krylov spaces and the first Arnoldi orthogonalization steps are formed.

No entrywise matrix storage was used in step 1.1: only the map $v\mapsto T(v)$, vector arithmetic, and inner products are needed. Therefore this sparse example fits the matrix-free access model [F1], and restarted cycles [F2] use the same access pattern on each new residual.