Krylov methods and Lanczos convergence — Examples

We have $Ab=(1,2{)}^{\mathsf{T}}$ and the determinant of the matrix with columns $b,Ab$ is $1\cdot 2-1\cdot 1=1\mathrm{\ne }0$. Thus $K_2(A,b)={\mathbb{R}}^2$. The exact solution is $x_{\ast }=A^{-1}b=(1,1\mathrm{/}2{)}^{\mathsf{T}}\in K_2(A,b)$, so the minimum residual in [F1] is zero at step $2$.

In the first GMRES$(1)$ cycle, [F1] restricts $x_1$ to $x_0+yb=yb$ for a scalar $y$. Its residual is $b-yAb=(1-y,1-2y{)}^{\mathsf{T}}$, whose squared norm is $(1-y{)}^2+(1-2y{)}^2=5(y-3\mathrm{/}5{)}^2+1\mathrm{/}5$. The unique minimizer is $y=3\mathrm{/}5$, and the residual is $(2\mathrm{/}5,-1\mathrm{/}5{)}^{\mathsf{T}}$, which is nonzero. By [F3] this is the first-cycle residual before any restart.

Formally setting $p_0=b$ for $A_{-}$ gives $A_{-}{p}_0=(1,-1{)}^{\mathsf{T}}$, so $p_0^{\mathsf{T}}{A}_{-}{p}_0=1-1=0$ while $b^{\mathsf{T}}b=2$. Thus attempting the first CG update formula would divide by zero. Since $A_{-}$ is indefinite, [F1] does not define a CG step for it, and the SPD theorem [F2] does not apply.

The normalized first Lanczos vector is $q_1=b\mathrm{/}\sqrt{2}$. Then $q_1^{\mathsf{T}}{A}_{-}{q}_1=0$ and $A_{-}{q}_1=(1,-1{)}^{\mathsf{T}}\mathrm{/}\sqrt{2}$ has norm $1$, so the first subdiagonal coefficient is ${\beta }_1=1>0$. Hence [F3] applies at step $1$, with $\beta =\mathrm{\parallel }{r}_0{\mathrm{\parallel }}_2=\sqrt{2}$ and ${\bar{T}}_1=(0,1{)}^{\mathsf{T}}$. The squared objective is $\mathrm{\parallel }(\sqrt{2},0{)}^{\mathsf{T}}-(0,y{)}^{\mathsf{T}}{\mathrm{\parallel }}_2^2=2+\mathrm{\mid }y{\mathrm{\mid }}^2$, uniquely minimized at $y=0$ even over $\mathbb{C}$. Also $b$ and $A_{-}b=(1,-1{)}^{\mathsf{T}}$ are linearly independent, so [F4] gives $K_2(A_{-},b)={\mathbb{R}}^2$. The exact solution $A_{-}^{-1}b=(1,-1{)}^{\mathsf{T}}$ therefore lies in $K_2$; no step-$2$ MINRES claim is needed after the invariant-subspace breakdown.

For $A_{+}$, the first CG denominator is $b^{\mathsf{T}}{A}_{+}b=1+2=3>0$ and ${\alpha }_0=2\mathrm{/}3$. The exact solution is $x_{\ast }=A_{+}^{-1}b=(1,1\mathrm{/}2{)}^{\mathsf{T}}$, so $e_0=x_{\ast }-x_0=(1,1\mathrm{/}2{)}^{\mathsf{T}}$ and [F5] gives $\mathrm{\parallel }{e}_0{\mathrm{\parallel }}_{A_{+}}^2=1+2(1\mathrm{/}2{)}^2=3\mathrm{/}2$. The first iterate is $x_1=x_0+{\alpha }_{0}b=(2\mathrm{/}3,2\mathrm{/}3{)}^{\mathsf{T}}$, hence $e_1=x_{\ast }-x_1=(1\mathrm{/}3,-1\mathrm{/}6{)}^{\mathsf{T}}$ and $\mathrm{\parallel }{e}_1{\mathrm{\parallel }}_{A_{+}}^2=(1\mathrm{/}3{)}^2+2(1\mathrm{/}6{)}^2=1\mathrm{/}6$. Thus the energy-error norm decreases from $\sqrt{3\mathrm{/}2}$ to $1\mathrm{/}\sqrt{6}$, a factor of $1\mathrm{/}3$. The recursive residual is $r_1=b-{\alpha }_0{A}_{+}b=(1\mathrm{/}3,-1\mathrm{/}3{)}^{\mathsf{T}}\mathrm{\ne }0$. This verifies the positive first denominator and energy decrease in this SPD instance, contrasting with step 1.1.

Since $1\mathrm{/}10000+2(9999\mathrm{/}20000)=1$, the vector $b$ is unit. Also $Ab=(1\mathrm{/}10,2\alpha ,\alpha {)}^{\mathsf{T}}$. Set $v:=(-{\alpha }^2,9\alpha \mathrm{/}100,-8\alpha \mathrm{/}100{)}^{\mathsf{T}}\mathrm{.}$ Direct dot products give $v^{\mathsf{T}}b=0$ and $v^{\mathsf{T}}Ab=-{\alpha }^2\mathrm{/}10+18{\alpha }^2\mathrm{/}100-8{\alpha }^2\mathrm{/}100=0$. The vectors $b,Ab$ are independent because their first coordinates would force a proportionality factor $10$, while the second coordinates would force factor $2$. Hence $K_2(A,b)$ is two-dimensional and equals $v^{\perp }$.

We have $\frac{v_2^2+v_3^2}{v_1^2}=\frac{145(1\mathrm{/}10000)}{{\alpha }^2}=\frac{290}{9999}\mathrm{.}$ For every unit $x\in K_2(A,b)$, $v^{\mathsf{T}}x=0$. By [F2], $\mathrm{\mid }{x}_1{\mathrm{\mid }}^2\le \frac{v_2^2+v_3^2}{v_1^2}(x_2^2+x_3^2)=\frac{290}{9999}(1-\mathrm{\mid }{x}_1{\mathrm{\mid }}^2),$ so $\mathrm{\mid }{x}_1{\mathrm{\mid }}^2\le 290\mathrm{/}10289$. Its Rayleigh quotient satisfies $x^{\mathsf{T}}Ax=10x_1^2+2x_2^2+x_3^2\le 2+8x_1^2\le 2+\frac{2320}{10289}<\frac{9}{4},$ since $4(2320)=9280<10289$. Taking the maximum gives ${\theta }_2<9\mathrm{/}4$, so ${\lambda }_1-{\theta }_2>31\mathrm{/}4$.

The top eigenspace is $\mathrm{span}\{e_1\}$, hence ${\tau }^2=(9999\mathrm{/}10000)\mathrm{/}(1\mathrm{/}10000)=9999$. The unwanted interval is $[1,2]$, and its affine exterior point is $1+2(10-2)\mathrm{/}(2-1)=17$, so $T_1(17)=17$. The theorem's $m=2$ bound is ${\lambda }_1-{\theta }_2\le \frac{9\cdot 9999}{{17}^2}=\frac{89991}{289},$ which is valid but large. If its factor ${\tau }^2$ were deleted, the proposed right side would be $9\mathrm{/}289<31\mathrm{/}4$, contradicting step 1.2. Thus this start cannot support that angle-free bound.

In case (i), take $b=1$. Then $P=I$, $Pb=b\mathrm{\ne }0$, and $K_1=\mathbb{R}$ is invariant under $A=5I_1$. The first Arnoldi residual is zero, so Lanczos breaks down at $d=1$; every nonzero vector has Rayleigh quotient $5$, giving ${\theta }_m=5$ for all $m\ge 1$ by [F1]. In case (ii), $P$ projects onto $\mathrm{span}\{e_1,e_2\}$, so $Pb=e_1\mathrm{/}\sqrt{2}\mathrm{\ne }0$. Here $Ab=(5,0,1{)}^{\mathsf{T}}\mathrm{/}\sqrt{2}$ and $Ab-b=(4,0,0{)}^{\mathsf{T}}\mathrm{/}\sqrt{2}$, so $K_2(A,b)=\mathrm{span}\{e_1,e_3\}$, an invariant subspace. The first Arnoldi residual is nonzero, while $A{q}_2\in K_2=\mathrm{span}\{q_1,q_2\}$ makes the second residual zero; hence Lanczos breaks down at $d=2$. Since $e_1\in K_2$ has Rayleigh quotient $5$, the maximum is ${\theta }_2=5$, as [F1] predicts for the collapsed interval branch.

In case (iii), $P$ projects onto $e_1$, so $Pb=0$; $A{e}_2=2e_2$ gives $K_m(A,e_2)=\mathrm{span}\{e_2\}$ for every $m$, and therefore ${\theta }_m=2={\lambda }_{r+1}$, in agreement with [F1]. At the first Arnoldi column, $A{e}_2$ already lies in $K_1=\mathrm{span}\{e_2\}$, so subtracting its projection leaves zero residual. Thus [F3]–[F4] give exact Lanczos breakdown at $d=1$ without a top component.

In case (iv), $b$ and $Ab=(5e_1+2e_2)\mathrm{/}\sqrt{2}$ are independent, so $K_2=\mathrm{span}\{e_1,e_2\}$; this space is invariant under $A$. At the second Arnoldi column, $A{q}_2\in K_2=\mathrm{span}\{q_1,q_2\}$, so subtracting its two orthogonal projections leaves zero residual. Thus [F3]–[F4] give exact Lanczos breakdown at $d=2$. Since $Pb=e_1\mathrm{/}\sqrt{2}\mathrm{\ne }0$, [F1] gives ${\theta }_2=5$; directly, $Ab-2b=3e_1\mathrm{/}\sqrt{2}\in K_2$, so $e_1\in K_2$ and its Rayleigh quotient is $5$.