Peaks and Plateaus in Residual Norm Plots Generated by Galerkin and Norm Minimizing Procedures for Solving Ax=b

Dr. Jane Cullum

The convergence of an iterative method for solving a linear system of equations Ax=b is usually monitored by tracking the size of the norms of the residuals generated. Galerkin methods, such as biconjugate gradients (BCG), often converge well. However, plots of the norms of the residuals generated by such procedures often exhibit erratic behavior. The residual norms may oscillate irregularly, forming sequences of peaks of varying size and frequency, making the user feel insecure about the method, and making it difficult to track the convergence. To correct this problem, methods such as quasi-minimal residuals (QMR), which minimize a related residual norm at each iteration, have been proposed. However, these methods exhibit a different type of irregular behavior. Plateaus appear in the residual norm plots, intervals of iterations over which there exist unacceptably small decreases in the residual norms. We first present the results of a series of numerical experiments on a Galerkin/norm minimizing pair of bidiagonalization methods which indicate certain relationships between residual norms generated by the two procedures, and between the Galerkin residual norm plots and the spectra of the associated Galerkin iteration matrices. We then derive specific relationships between the residual norms generated within each of three pairs of methods, GMRES/Arnoldi, QMR/BCG, and the pair of bidiagonalization methods. Using these relationships we can then make statements comparing the convergence rates within each pair. The arguments for the bidiagonalization procedures include the effects of finite precision arithmetic.