GMBACK: A Generalised Minimum Backward Error Algorithm for Nonsymmetric Linear Systems
Ebrahim M. Kasenally · SIAM Journal on Scientific Computing · 1995
A drawback of employing the residual error norm as a stopping condition in an iterative process is that the error must be small if the approximation is accurate. However, the converse need not be true. The main aims of this paper are to consider an alternative criterion for judging whether a given approximation is acceptable and to present an algorithm which computes an approximate solution to the linear system $Ax = b$ such that the normwise backward error meets some optimality condition. The notion of backward error used throughout this paper considers whether there exists close to the original problem a perturbed problem such that $(A - \Delta )x_m = b$ in which $x_m $ is the approximate solution and $\Delta $ is the perturbation. The set of all $\Delta $’s is parameterised for the Arnoldi and GMRES methods; furthermore, computable expressions are derived for the smallest $||\Delta ||_F $ in each set. The new method introduced in this paper employs the Arnoldi process to construct a basis for the Krylov subspace $\mathcal{K}_m (A,r_0 )$ and seeks an $x_m \in x_0 + \mathcal{K}_m (A,r_0 )$ to minimise the norm of the perturbation to the data given in A. The theoretical properties of the algorithm are discussed and practical implementation issues are considered with a particular focus on preconditioning. The algorithm has been extensively tested and some results are communicated.