Krylov Subspaces, Arnoldi and GMRES

If $v\in K_m(A,b)$, then [F1] gives scalars $c_0,\dots ,c_{m-1}$ with $v={\sum }_{j=0}^{m-1}{c}_j{A}^{j}b\mathrm{.}$ With $p(z):={\sum }_{j=0}^{m-1}{c}_j{z}^j$, either $p=0$ or $\mathrm{deg}p<m$, and $v=p(A)b$.

Conversely, $p=0$ gives $p(A)b=0\in K_m(A,b)$. If instead $\mathrm{deg}p<m$ and $p(z)={\sum }_{j=0}^{m-1}{c}_j{z}^j$, then $p(A)b={\sum }_{j=0}^{m-1}{c}_j{A}^{j}b,$ which lies in the span from [F1]. Hence every displayed $p(A)b$ lies in $K_m(A,b)$.

If $0\le m<\nu$ and ${\sum }_{j=0}^{m-1}{c}_j{A}^{j}b=0$, then the polynomial $p(z)={\sum }_{j=0}^{m-1}{c}_j{z}^j$ satisfies $\mathrm{deg}p<m<\nu$ and $p(A)b=0$. By minimality in [F1], this forces $p=0$, so $b,Ab,\dots ,A^{m-1}b$ are linearly independent. Therefore $\dim K_m(A,b)=m$.

Writing $q_{A,b}(z)=a_0+a_{1}z+\cdots +a_{\nu -1}{z}^{\nu -1}+z^{\nu }$, the relation $q_{A,b}(A)b=0$ from [F1] shows that $A^{\nu }b\in K_{\nu }(A,b)$. Multiplying the same relation by $A^k$ for each $k\ge 0$ gives $A^{\nu +k}b\in K_{\nu }(A,b)$ as well. Hence every generator of $K_m(A,b)$ for $m\ge \nu$ already lies in $K_{\nu }(A,b)$, so $K_m(A,b)=K_{\nu }(A,b)$.

If $b=0$, then $x_{\ast }=0\in K_0(A,b)=K_{\nu }(A,b)$. Assume now that $b\mathrm{\ne }0$. Write $q_{A,b}(z)=a_0+a_{1}z+\cdots +a_{\nu -1}{z}^{\nu -1}+z^{\nu }$. The constant term $a_0$ is nonzero, because $a_0=0$ would give $q_{A,b}(z)=zr(z)$ and then $0=q_{A,b}(A)b=Ar(A)b$, so invertibility of $A$ would imply $r(A)b=0$ with $\mathrm{deg}r=\nu -1$, contradicting [F1].

From $q_{A,b}(A)b=0$ we obtain $a_{0}b+A(a_{1}I+\cdots +a_{\nu -1}{A}^{\nu -2}+A^{\nu -1})b=0.$ Multiplying by $A^{-1}$ and dividing by $a_0$ yields $x_{\ast }=A^{-1}b=-a_0^{-1}(a_{1}I+\cdots +a_{\nu -1}{A}^{\nu -2}+A^{\nu -1})b,$ so $x_{\ast }\in K_{\nu }(A,b)$. The inclusion is already enough, and [L1] shows it persists in every later Krylov space.

By construction in [F1], the vector $w_j$ is orthogonal to each $v_i$ for $1\le i\le j$, because $h_{ij}=⟨A{v}_j,v_i⟩$ subtracts exactly the orthogonal projection of $A{v}_j$ onto $v_i$. Since there is no breakdown, $w_j\mathrm{\ne }0$, so $v_{j+1}=w_j\mathrm{/}\mathrm{\parallel }{w}_j\mathrm{\parallel }$ is a unit vector orthogonal to $v_1,\dots ,v_j$. Starting from the unit vector $v_1=b\mathrm{/}\mathrm{\parallel }b\mathrm{\parallel }$, induction gives orthonormality of $v_1,\dots ,v_m$.

Again by [F1], each $v_{j+1}$ is a linear combination of $A{v}_j,v_1,\dots ,v_j$. Induction using [F2] therefore gives $v_i\in K_i(A,b)\subseteq K_m(A,b)$ for $i\le m$. Conversely, $A{v}_j={\sum }_{i=1}^{j+1}{h}_{ij}{v}_i$ lies in $\mathrm{span}\{v_1,\dots ,v_{j+1}\}$, and induction from $v_1=b\mathrm{/}\mathrm{\parallel }b\mathrm{\parallel }$ shows that $b,Ab,\dots ,A^{m-1}b$ all lie in $\mathrm{span}\{v_1,\dots ,v_m\}$. By [F2], the two spans are equal.

For each column $j$, the Arnoldi relation from [F1] involves only $v_1,\dots ,v_{j+1}$. By the definition of ${\bar{H}}_m$ in the Statement, its remaining entries satisfy $h_{ij}=0$ for $i>j+1$, the same zero pattern as the square upper-Hessenberg condition [F3]. The column relations assemble exactly into $A{Q}_m=Q_{m+1}{\bar{H}}_m$.

Assume $h_{m+1,m}=0$. Then the Arnoldi step gives $A{v}_m\in \mathrm{span}\{v_1,\dots ,v_m\}=K_m(A,b)$. For every $j<m$, [L1] already gives $A{v}_j\in K_{j+1}(A,b)\subseteq K_m(A,b)$. Since the $v_j$ form a basis of $K_m(A,b)$, linearity shows $A(K_m(A,b))\subseteq K_m(A,b)$.

Conversely, assume $K_m(A,b)$ is $A$-invariant. Because $v_m\in K_m(A,b)$, one has $A{v}_m\in K_m(A,b)=\mathrm{span}\{v_1,\dots ,v_m\}$. Therefore the part of $A{v}_m$ orthogonal to that span is zero, so the Arnoldi residual $w_m$ vanishes and hence $h_{m+1,m}=\mathrm{\parallel }{w}_m\mathrm{\parallel }=0$.

Using [F1] and [L1], $Au=A{Q}_{m}y=Q_{m+1}{\bar{H}}_{m}y=Q_m{H}_{m}y+h_{m+1,m}(e_m^{\ast }y)v_{m+1}\mathrm{.}$ Since $H_{m}y=\theta y$, this becomes $Au=\theta Q_{m}y+h_{m+1,m}(e_m^{\ast }y)v_{m+1}\mathrm{.}$

Because $Q_{m}y=u$, step 1.1 is exactly $Au-\theta u=h_{m+1,m}(e_m^{\ast }y)v_{m+1}$. The Arnoldi vectors are orthonormal, so $\mathrm{\parallel }{v}_{m+1}{\mathrm{\parallel }}_2=1$, and the norm formula follows.

By [L1], the columns of $Q_m$ form a basis of $K_m(A,r_0)$, so every $x\in x_0+K_m(A,r_0)$ can be written uniquely as $x=x_0+Q_{m}y$. Since $r_0=\beta v_1=\beta Q_{m+1}{e}_1$ and $b-A{x}_0=r_0$, one has $b-Ax=r_0-A{Q}_{m}y=Q_{m+1}\beta e_1-Q_{m+1}{\bar{H}}_{m}y=Q_{m+1}(\beta e_1-{\bar{H}}_{m}y)\mathrm{.}$

The columns of $Q_{m+1}$ are orthonormal by [L1], so multiplying by $Q_{m+1}$ preserves the Euclidean norm. Therefore $\mathrm{\parallel }b-Ax{\mathrm{\parallel }}_2=\mathrm{\parallel }\beta e_1-{\bar{H}}_{m}y{\mathrm{\parallel }}_2\mathrm{.}$ Taking minima over the corresponding parametrized sets gives the stated small least-squares problem. This is the residual norm whose minimizers [F1] calls GMRES iterates.

By [L1], every $x\in x_0+K_m(A,r_0)$ has the form $x=x_0+Q_{m}y$, and for that $x$ one has $\mathrm{\parallel }b-Ax{\mathrm{\parallel }}_2=\mathrm{\parallel }\beta e_1-{\bar{H}}_{m}y{\mathrm{\parallel }}_2\mathrm{.}$

Since $y_m$ minimizes the right-hand side, the vector $x_m=x_0+Q_m{y}_m$ minimizes the left-hand side over the whole affine Krylov space. By [F1], that is exactly the GMRES condition.

Because $K_m(A,r_0)\subseteq K_{m+1}(A,r_0)$, one has $x_0+K_m(A,r_0)\subseteq x_0+K_{m+1}(A,r_0)$. In particular, $x_m$ is an admissible competitor for the $(m+1)$st minimization problem.

By [L1], $x_{m+1}$ minimizes the residual norm over the larger affine space, so $\mathrm{\parallel }b-A{x}_{m+1}{\mathrm{\parallel }}_2\le \mathrm{\parallel }b-A{x}_m{\mathrm{\parallel }}_2\mathrm{.}$

Since $x_m-x_0\in K_m(A,r_0)$, [L1] gives a polynomial $q$ with $\mathrm{deg}q<m$ and $x_m=x_0+q(A)r_0$. Therefore $r_m=b-A{x}_m=r_0-Aq(A)r_0=p_m(A)r_0,$ where $p_m(z):=1-zq(z)$. Then $p_m(0)=1$ and $\mathrm{deg}{p}_m\le m$.

Conversely, every polynomial $p$ with $\mathrm{deg}p\le m$ and $p(0)=1$ can be written as $p(z)=1-zq(z)$ with $\mathrm{deg}q<m$. The corresponding vector $x=x_0+q(A)r_0$ lies in $x_0+K_m(A,r_0)$ by [L1], and its residual is $p(A)r_0$. Since [L2] makes $x_m$ minimize that residual norm over all such $x$, the polynomial attached in step 1.1 minimizes $\mathrm{\parallel }p(A)r_0{\mathrm{\parallel }}_2$ among all admissible $p$.

Let $x_{\ast }$ be the exact solution of $Ax=b$. Then $x_{\ast }-x_0=A^{-1}(b-A{x}_0)=A^{-1}{r}_0$, so [L1] gives $x_{\ast }\in x_0+K_{\nu }(A,r_0)$.

The exact solution has residual $b-A{x}_{\ast }=0$. Since $x_{\ast }$ is an admissible point in the $\nu$th GMRES affine space, [L2] forces the $\nu$th GMRES residual norm to be at most $0$, hence equal to $0$. Therefore unrestarted GMRES terminates by step $\nu$.

By [L1], $r_m=p_m(A)r_0=V{p}_m(\mathrm{\Lambda })V^{-1}{r}_0\mathrm{.}$ Hence $\mathrm{\parallel }{r}_m{\mathrm{\parallel }}_2\le \mathrm{\parallel }V{\mathrm{\parallel }}_2\mathrm{\parallel }{p}_m(\mathrm{\Lambda }){\mathrm{\parallel }}_2\mathrm{\parallel }{V}^{-1}{\mathrm{\parallel }}_2\mathrm{\parallel }{r}_0{\mathrm{\parallel }}_2\mathrm{.}$ Since $p_m(\mathrm{\Lambda })$ is diagonal, its operator norm is ${\max }_i\mathrm{\mid }{p}_m({\lambda }_i)\mathrm{\mid }$. Therefore $\mathrm{\parallel }{r}_m{\mathrm{\parallel }}_2\le {\kappa }_2(V){\max }_i\mathrm{\mid }{p}_m({\lambda }_i)\mathrm{\mid }\mathrm{\parallel }{r}_0{\mathrm{\parallel }}_2\mathrm{.}$

The polynomial $p_m$ from [L1] minimizes $\mathrm{\parallel }p(A)r_0{\mathrm{\parallel }}_2$ over all polynomials with $\mathrm{deg}p\le m$ and $p(0)=1$, so the bound from step 1.1 also holds after taking the minimum over that admissible class.

By [F1], the $(j+1)$st restarted iterate is obtained by applying ordinary GMRES to the system with initial guess $x^{(j)}$ and initial residual $r^{(j)}$. Therefore [L1] gives $\mathrm{\parallel }b-A{x}^{(j+1)}{\mathrm{\parallel }}_2={\min }_{x\in x^{(j)}+K_m(A,r^{(j)})}\mathrm{\parallel }b-Ax{\mathrm{\parallel }}_2\mathrm{.}$

The unrestarted theorem [L2] uses the single expanding family $x_0+K_k(A,r_0)$. After a restart, [F1] replaces that space by the new cycle space $x^{(j)}+K_m(A,r^{(j)})$, which need not contain the exact solution even when some larger unrestarted space would. Hence cyclewise minimization remains true, but the unrestarted finite-termination guarantee is no longer a formal consequence after restart.