GMRES and nonnormality

Start from x₀ with nonzero residual r₀=b−Ax₀ and let β be its norm. Arnoldi builds an orthonormal Vₖ₊₁ with first column r₀/β and the relation AVₖ=Vₖ₊₁Hbarₖ. A correction Vₖy then has residual Vₖ₊₁(βe₁−Hbarₖy). Orthogonality makes the large residual norm equal to the small coefficient residual norm. GMRES solves that small least-squares problem, commonly by updating a QR factorization, and reconstructs the corresponding iterate.

In exact arithmetic with unrestarted GMRES, successive correction spaces are nested, so the minimum residual norm cannot increase. This statement is about residuals, not necessarily the forward solution error, and it does not demand a decrease at every step. For nonsingular A, full-dimensional exact GMRES reaches the solution in at most n steps, possibly earlier. A zero initial residual should stop immediately. For singular or inconsistent systems, the same universal zero-residual conclusion is unavailable, so breakdown and convergence require a separate analysis.

A real matrix is normal when it commutes with its transpose; over complex scalars use the conjugate transpose. A normal matrix has an orthonormal eigenbasis over the complex numbers, making polynomial norms directly controlled by values on its eigenvalues. A nonnormal matrix need not have such a basis, and may even be defective. Its off-diagonal coupling can make a polynomial of A large despite small polynomial values at the eigenvalues. A repeated eigenvalue therefore does not imply that the matrix acts like a scalar identity.

The shear [[1,s],[0,1]] has both eigenvalues equal to one for every s, but a residual seeded in the second coordinate sees the coupling s. One GMRES step can leave almost the entire residual when s is large, while the identity solves every right-hand side in one step. A seed in the first coordinate still solves the shear immediately. Thus nonnormality and right-hand-side geometry both matter. This example does not establish a universal slow-convergence rule for all nonnormal matrices; it refutes an eigenvalues-alone prediction.

Left preconditioning solves a system whose residual is M inverse times the original residual, so the usual Euclidean GMRES minimization concerns that transformed quantity. A small preconditioned residual need not mean the original residual is equally small. Right preconditioning instead changes the correction variables while retaining the original residual in the minimization. Neither is uniformly superior; the distinction must be explicit when interpreting convergence plots. A changing preconditioner may require a flexible algorithm rather than applying the fixed-preconditioner formulas unchanged.

Restarted GMRES discards its accumulated basis after a prescribed number of steps and begins a new cycle from the current residual. Within each exact cycle it still minimizes over its available correction space, but the globally optimal unrestarted polynomial history has been lost. Restarting can cause stagnation even when full GMRES would finish quickly. Finite-precision orthogonality loss and recursively tracked residual gaps add further diagnostic concerns. Check a true scaled residual and relate it to conditioning before treating a visually small curve as a forward-accuracy certificate.