Generalized minimal residual method ($x_k={\mathrm{argmin}}_{x\in {\mathcal{K}}_k(A,b)}\Vert Ax-b{\Vert }_2$)

With zero initial guess, the generalized minimal residual method minimizes the Euclidean norm of the linear-system residual over each Krylov subspace. The Arnoldi decomposition reduces this to ${\min }_y\Vert {\tilde{H}}_{k}y-\Vert b{\Vert }_2{e}_1{\Vert }_2$, followed by $x_k=Q_{k}y$. Givens rotations solve the small problem in $O(k^2)$ operations once the decomposition is available. For an invertible matrix $A$, the same iterate minimizes the error in the weighted norm induced by $A^{T}A$, because $\Vert Ax-b{\Vert }_2=\Vert x-x_{\ast }{\Vert }_{A^{T}A}$.

One step of restarted GMRES searches along the current residual. In the displayed nonsingular system, the first residual minimization is ${\min }_{\alpha }[(1-\alpha {)}^2+(1+\alpha {)}^2]$, whose minimizer is zero. Restarting then repeats the same problem forever and never moves. Unrestarted GMRES instead solves exactly at step two, since $b,Ab$ span the entire space. Thus a smaller search-space cost can come at the price of stagnation; nonsingularity alone does not guarantee progress for one-step restarting.