Peaks, plateaus, numerical instabilities in a Galerkin minimal residual pair of methods for solving \(Ax=b\). (English) Zbl 0855.65022
This paper discusses a pair of bidiagonalization methods, referred to as BLanczos and BMinres, for solving unsymmetric linear equation systems \(Ax = b\).
Convergence is monitored through the residual norm \(|r_k|= |b - Ax_k|\), and it has been noted that this quantity does not decrease monotonically. In a Galerkin-type method such as
BLanczos, irregular peaks occur, whilst in a residual minimization method such as BMinres, plateaus occur; in either case convergence is hard to identify. The main purpose of the paper is discussing possible reasons for these peak and plateau formations.
It is shown in particular that, if the linear system is sufficiently well conditioned, numerical instabilities play no role in peak formations in BLanczos, and that peak or plateau production can occur in either finite precision or exact arithmetic, though more peaks are likely in the former. The question of whether there are correlations between the residual norms generated by each of the two methods when used on the same linear system is discussed. Detailed numerical examples are used to complement the discussions.
Convergence is monitored through the residual norm \(|r_k|= |b - Ax_k|\), and it has been noted that this quantity does not decrease monotonically. In a Galerkin-type method such as
BLanczos, irregular peaks occur, whilst in a residual minimization method such as BMinres, plateaus occur; in either case convergence is hard to identify. The main purpose of the paper is discussing possible reasons for these peak and plateau formations.
It is shown in particular that, if the linear system is sufficiently well conditioned, numerical instabilities play no role in peak formations in BLanczos, and that peak or plateau production can occur in either finite precision or exact arithmetic, though more peaks are likely in the former. The question of whether there are correlations between the residual norms generated by each of the two methods when used on the same linear system is discussed. Detailed numerical examples are used to complement the discussions.
Reviewer: A.Swift (Palmerston North)
MSC:
| 65F10 | Iterative numerical methods for linear systems |
| 65F15 | Numerical computation of eigenvalues and eigenvectors of matrices |
Keywords:
bidiagonalization; BLanczos; BMinres; unsymmetric linear equation systems; Galerkin-type method; residual minimization method; numerical instabilities; numerical examplesReferences:
| [1] | Brown, P., A theoretical comparison of the Arnoldi and GMRES algorithms, SIAM J. Sci. Statist. Comput., 20, 58-78 (1991) · Zbl 0719.65022 |
| [2] | Cullum, J., Peaks and plateaus in Lanczos methods for solving nonsymmetric systems of equations \(Ax = b\), (IBM Research Report RC 18084 (1992), IBM T.J. Watson Research Center: IBM T.J. Watson Research Center Yorktown Heights, NY) |
| [3] | Cullum, J.; Greenbaum, A., Residual relationships within three pairs of iterative algorithms for solving \(Ax = b\), SIAM J. Matrix Anal. Appl., 19 (1996) |
| [4] | Cullum, J.; Willoughby, R. A., Lanczos Algorithms for Large Symmetric Eigenvalue Computations Vol. 1: Theory, (Abarbanel, S.; etal., Progress in Scientific Computing, 3 (1985), Birkhaüser: Birkhaüser Basel) · Zbl 1013.65033 |
| [5] | Cullum, J.; Willoughby, R. A.; Lake, M., A Lanczos algorithm for computing singular values and vectors of large matrices, SIAM J. Sci. Statist. Comput., 4, 197-215 (1983) · Zbl 0518.65020 |
| [6] | Freund, R. W.; Golub, G. H.; Nachtigal, N., Iterative solution of linear systems, Acta Numer., 1, 57-100 (1992) · Zbl 0762.65019 |
| [7] | Freund, R.; Nachtigal, N., QMR: a quasi-minimal residual method for non-Hermitian linear systems, Numer. Math., 8, 43-71 (1992) |
| [8] | Golub, G.; Kahan, W., Calculating the singular values and pseudoinverse of a matrix, SIAM J. Numer. Anal., 2, 197-209 (1965) · Zbl 0194.18201 |
| [9] | Golub, G.; Van Loan, C., Matrix Computations (1989), The Johns Hopkins University Press: The Johns Hopkins University Press Baltimore, MD · Zbl 0733.65016 |
| [10] | Greenbaum, A., Behavior of slightly perturbed Lanczos and conjugate gradient recurrences, Linear Algebra Appl., 113, 7-63 (1989) · Zbl 0662.65032 |
| [11] | Hill, R. O.; Parlett, B. N., Refined interlacing properties, SIAM J. Matrix Anal. Appl., 13, 239-247 (1992) · Zbl 0747.15004 |
| [12] | Paige, C. C., Accuracy and effectiveness of the Lanczos algorithm for the symmetric eigenproblem, Linear Algebra Appl., 34, 235-258 (1980) · Zbl 0471.65017 |
| [13] | Paige, C. C., Error analysis of the Lanczos algorithm for tridiagonalizing a symmetric matrix, J. Inst. Math. Appl., 18, 341-349 (1976) · Zbl 0347.65018 |
| [14] | Paige, C. C., Bidiagonalization of matrices and solution of linear equations, SIAM J. Numer. Anal., 11, 197-209 (1974) · Zbl 0244.65023 |
| [15] | Paige, C. C.; Saunders, M. A., LSQR: an algorithm for sparse linear equations and sparse least squares, ACM Trans. Math. Software, 8, 43-71 (1982) · Zbl 0478.65016 |
| [16] | Saad, Y.; Schultz, M. H., GMRES: A generalized minimum residual algorithm for solving nonsymmetric linear systems, SIAM J. Sci. Statist. Comput., 7, 856-869 (1986) · Zbl 0599.65018 |
| [17] | van der Sluis, A.; van der Vorst, H. A., The convergence behavior of Ritz values in the presence of close eigenvalues, Linear Algebra Appl., 88/89, 651-694 (1987) · Zbl 0632.65035 |
| [18] | van der Vorst, H. A.; Vuik, C., The superlinear convergence behavior of GMRES, J. Comput. Appl. Math., 48, 327-341 (1993) · Zbl 0797.65026 |
| [19] | Walker, H. F., Residual smoothing and peak/plateau behavior in Krylov subspace methods, Appl. Numer. Math., 19, 279-286 (1995) · Zbl 0855.65023 |
| [20] | Zhou, Lu; Walker, H. F., Residual smoothing techniques for iterative methods, SIAM J. Sci. Comput., 15, 297-312 (1994) · Zbl 0802.65041 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
