Any finite convergence curve is possible in the initial iterations of restarted FOM

Schweitzer, Marcel

Electronic transactions on numerical analysis, Tome 45 (2016), pp. 133-145

Résumé

We investigate the possible convergence behavior of the restarted full orthogonalization method (FOM) for non-Hermitian linear systems $A{\mathbf x} = {\mathbf b}$. For the GMRES method, it is known that any nonincreasing sequence of residual norms is possible, independent of the eigenvalues of $A \in \mathbb{C}^{n \times n}$. For FOM, however, there has not yet been any literature describing similar results. This paper complements the results for (restarted) GMRES by showing that any finite sequence of residual norms is possible in the first $n$ iterations of restarted FOM, where by finite we mean that we only consider the case that all FOM iterates are defined, and thus no "infinite" residual norms occur. We discuss the relation of our results to known results on restarted GMRES and give a new result concerning the possible convergence behavior of restarted GMRES for iteration counts exceeding the matrix dimension $n$. In addition, we give a conjecture on an implication of our result with respect to the convergence of the restarted Arnoldi approximation for $g(A){\mathbf b}$, the action of a matrix function on a vector.

Détail

Classification : 65F10, 65F50, 65F60
Keywords: linear systems, restarted Krylov subspace methods, full orthogonalization method, restarted arnoldi method for matrix functions, GMRES method