Analysis Of The Finite Precision Bi-Conjugate Gradient Algorithm For Nonsymmetric Linear Systems

. In this paper we analyze the BiCG algorithm in finite precision arithmetic and suggest reasons for its often observed robustness. By using a tridiagonal structure, which is preserved by the finite precision BiCG iteration, we are able to bound its residual norm by a minimum polynomial of a perturbed matrix (i.e. the exact GMRES residual norm applied to a perturbed matrix) multiplied by some amplification factors. Furthermore, the same analysis can be applied to the CG algorithm and we are able to relate the slowing down of convergence to loss of orthogonality in finite precision arithmetic. Finally, numerical examples are given to gain insights into these bounds. Key words. Bi-conjugate gradient algorithm, error analysis, convergence analysis, nonsymmetric linear systems AMS subject classifications. 65F10, 65N20 1. Introduction. Since its introduction by Lanczos [14] and later re-discovery by Fletcher [5] in its present form, the bi-conjugate gradient (BiCG) algorithm has evolved m..