×

Accuracy of the Lanczos process for the eigenproblem and solution of equations. (English) Zbl 1427.65044

Summary: In [ibid. 31, No. 5, 2347–2359 (2010; Zbl 1215.65083)], the author showed that \(k\) steps of the finite precision Lanczos process for tridiagonalizing an \(n\times n\) Hermitian matrix \(A\) could be viewed as an exact Lanczos process for a \((k+n)\times (k+n)\) augmented Hermitian matrix, producing exactly orthogonal vectors. Here, we use this and related results to prove the highly accurate behavior of the finite precision Lanczos process when used for finding the eigensystem of \(A\), or for solving linear systems \(Ax=b\). It turns out that the finite precision process mimics the exact process in iterative rather than \(n\)-step ways and makes available backward stable results. These results are also complete, such as making available the complete eigensystem of an \(A\) with distinct eigenvalues. The matrix \(S_k\) used to obtain these results is shown to provide valuable theoretical information on the loss of orthogonality between any \(k\) vectors, among its many other useful properties.

MSC:

65F10 Iterative numerical methods for linear systems
65F15 Numerical computation of eigenvalues and eigenvectors of matrices
65F25 Orthogonalization in numerical linear algebra
65F50 Computational methods for sparse matrices
65G50 Roundoff error
15A18 Eigenvalues, singular values, and eigenvectors
15B57 Hermitian, skew-Hermitian, and related matrices

Citations:

Zbl 1215.65083
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] \AA. Björck and C. C. Paige, Loss and recapture of orthogonality in the modified Gram-Schmidt algorithm, SIAM J. Matrix Anal. Appl., 13 (1992), pp. 176-190, https://doi.org/10.1137/0613015. · Zbl 0747.65026
[2] E. Carson and J. W. Demmel, Accuracy of the \(s\)-step Lanczos method for the symmetric eigenproblem in finite precision, SIAM J. Matrix Anal. Appl., 36 (2015), pp. 793-819, https://doi.org/10.1137/140990735. · Zbl 1319.65024
[3] X.-W. Chang, Personal communication, 2018.
[4] S.-C. T. Choi, C. C. Paige, and M. A. Saunders, MINRES-QLP: A Krylov subspace method for indefinite or singular symmetric systems, SIAM J. Sci. Comput., 33 (2011), pp. 1810-1836, https://doi.org/10.1137/100787921. · Zbl 1230.65050
[5] C. Davis and W. M. Kahan, Some new bounds on perturbations of subspaces, Bull. Amer. Math. Soc., 75 (1969), pp. 863-868. · Zbl 0175.43204
[6] D. C.-L. Fong and M. A. Saunders, LSMR: An iterative algorithm for sparse least-squares problems, SIAM J. Sci. Comput., 33 (2011), pp. 2950-2971, https://doi.org/10.1137/10079687X. · Zbl 1232.65052
[7] G. H. Golub and W. Kahan, Calculating the singular values and pseudo-inverse of a matrix, SIAM J. Numer. Anal., 2 (1965), pp. 205-224, https://doi.org/10.1137/0702016. · Zbl 0194.18201
[8] G. H. Golub and C. F. Van Loan, Matrix Computations, 4th ed., The Johns Hopkins University Press, Baltimore, MD, 2013. · Zbl 1268.65037
[9] A. Greenbaum, Convergence Properties of the Conjugate Gradient Algorithm in Exact and Finite Precision Arithmetic, Ph.D. thesis, University of California Berkeley, Berkeley, CA, 1981.
[10] A. Greenbaum, Behavior of slightly perturbed Lanczos and conjugate-gradient recurrences, Linear Algebra Appl., 113 (1989), pp. 7-63, https://doi.org/10.1016/0024-3795(89)90285-1. · Zbl 0662.65032
[11] A. Greenbaum and Z. Strakoš, Predicting the behavior of finite precision Lanczos and conjugate gradient computations, SIAM J. Matrix Anal. Appl., 13 (1992), pp. 121-137, https://doi.org/10.1137/0613011. · Zbl 0755.65037
[12] C. Greif, C. C. Paige, D. Titley-Peloquin, and J. M. Varah, Numerical equivalences among Krylov subspace algorithms for skew-symmetric matrices, SIAM J. Matrix Anal. Appl., 37 (2016), pp. 1071-1087, https://doi.org/10.1137/15M1030078. · Zbl 1347.65062
[13] M. H. Gutknecht and Z. Strakoš, Accuracy of two three-term and three two-term recurrences for Krylov space solvers, SIAM J. Matrix Anal. Appl., 22 (2000), pp. 213-229, https://doi.org/10.1137/S0895479897331862. · Zbl 0976.65030
[14] S. Hammarling and N. J. Higham, Wilkinson and Backward Error Analysis, Website of the Numerical Linear Algebra Group, School of Mathematics, University of Manchester, 2019, https://nla-group.org/2019/02/18/wilkinson-and-backward-error-analysis/.
[15] M. Hestenes and E. Stiefel, Methods of conjugate gradients for solving linear systems, J. Research Nat. Bur. Standards, 49 (1952), pp. 409-436, https://doi.org/10.6028/jres.049.044. · Zbl 0048.09901
[16] C. Lanczos, An iteration method for the solution of the eigenvalue problem of linear differential and integral operators, J. Research Nat. Bur. Standards, 45 (1950), pp. 255-282, https://doi.org/10.6028/jres.045.026.
[17] C. Lanczos, Solution of systems of linear equations by minimized iterations, J. Research Nat. Bur. Standards, 49 (1952), pp. 33-53, https://doi.org/10.6028/jres.049.006.
[18] G. Meurant, The Lanczos and Conjugate Gradient Algorithms, Software Environ. Tools 19, SIAM, Philadelphia, 2006, https://doi.org/10.1137/1.9780898718140. · Zbl 1113.65032
[19] G. Meurant and Z. Strakoš, The Lanczos and conjugate gradient algorithms in finite precision arithmetic, Acta Numer., 15 (2006), pp. 471-542, https://doi.org/10.1017/S096249290626001X. · Zbl 1113.65032
[20] D. P. O’Leary, Z. Strakoš, and P. Tichý, On sensitivity of Gauss-Christoffel quadrature, Numer. Math., 107 (2007), pp. 147-174, https://doi.org/10.1007/s00211-007-0078-x. · Zbl 1117.41023
[21] C. C. Paige, The Computation of Eigenvalues and Eigenvectors of Very Large Sparse Matrices, Ph.D. thesis, London University, London, England, 1971.
[22] C. C. Paige, Error analysis of the Lanczos algorithm for tridiagonalizing a symmetric matrix, J. Inst. Math. Appl., 18 (1976), pp. 341-349, https://doi.org/10.1093/imamat/18.3.341. · Zbl 0347.65018
[23] C. C. Paige, Accuracy and effectiveness of the Lanczos algorithm for the symmetric eigenproblem, Linear Algebra Appl., 34 (1980), pp. 235-258, https://doi.org/10.1016/0024-3795(80)90167-6. · Zbl 0471.65017
[24] C. C. Paige, A useful form of unitary matrix obtained from any sequence of unit 2-norm \(n\)-vectors, SIAM J. Matrix Anal. Appl., 31 (2009), pp. 565-583, https://doi.org/10.1137/080725167. · Zbl 1217.65072
[25] C. C. Paige, An augmented stability result for the Lanczos Hermitian matrix tridiagonalization process, SIAM J. Matrix Anal. Appl., 31 (2010), pp. 2347-2359, https://doi.org/10.1137/090761343. · Zbl 1215.65083
[26] C. C. Paige, The effects of loss of orthogonality on large scale numerical computations, in Computational Science and Its Applications, ICCSA 2018, Lecture Notes in Comput. Sci. 10962, O. Gervasi et al., eds., Springer, Cham, pp. 429-439, https://doi.org/10.1007/978-3-319-95168-3_29.
[27] C. C. Paige and I. Panayotov, Hessenberg matrix properties and Ritz vectors in the finite-precision Lanczos tridiagonalization process, SIAM J. Matrix Anal. Appl., 32 (2011), pp. 1079-1094, https://doi.org/10.1137/100796285. · Zbl 1248.65040
[28] C. C. Paige, I. Panayotov, and J.-P. M. Zemke, An augmented analysis of the perturbed two-sided Lanczos tridiagonalization process, Linear Algebra Appl., 447 (2014), pp. 119-132, https://doi.org/10.1016/j.laa.2013.05.009. · Zbl 1291.65130
[29] C. C. Paige, M. Rozložník, and Z. Strakoš, Modified Gram-Schmidt (MGS), least squares, and backward stability of MGS-GMRES, SIAM J. Matrix Anal. Appl., 28 (2006), pp. 264-284, https://doi.org/10.1137/050630416. · Zbl 1113.65028
[30] C. C. Paige and M. A. Saunders, Solution of sparse indefinite systems of linear equations, SIAM J. Numer. Anal., 12 (1975), pp. 617-629, https://doi.org/10.1137/0712047. · Zbl 0319.65025
[31] C. C. Paige and M. A. Saunders, LSQR: An algorithm for sparse linear equations and sparse least squares, ACM Trans. Math. Software, 8 (1982), pp. 43-71, https://doi.org/10.1145/355984.355989. · Zbl 0478.65016
[32] C. C. Paige and M. A. Saunders, Algorithm 583: LSQR: Sparse linear equations and least squares problems, ACM Trans. Math. Software, 8 (1982), pp. 195-209, https://doi.org/10.1145/355993.356000.
[33] C. C. Paige and Z. Strakoš, Scaled total least squares fundamentals, Numer. Math., 91 (2002), pp. 117-146, https://doi.org/10.1007/s002110100314. · Zbl 0998.65046
[34] C. C. Paige and W. Wülling, Properties of a unitary matrix obtained from a sequence of normalized vectors, SIAM J. Matrix Anal. Appl., 35 (2014), pp. 526-545, https://doi.org/10.1137/120897687. · Zbl 1304.65137
[35] I. Panayotov, Eigenvalue Estimation with the Rayleigh-Ritz and Lanczos Methods, Ph.D. thesis, McGill University, Montréal, Canada, 2010.
[36] B. N. Parlett, The Symmetric Eigenvalue Problem, Classics Appl. Math. 20, SIAM, Philadelphia, 1998, https://doi.org/10.1137/1.9781611971163. · Zbl 0885.65039
[37] M. A. Saunders, H. D. Simon, and E. L. Yip, Two conjugate-gradient-type methods for unsymmetric linear equations, SIAM J. Numer. Anal., 25 (1988), pp. 927-940, https://doi.org/10.1137/0725052. · Zbl 0652.65022
[38] G. W. Stewart, On the perturbation of pseudo-inverses, projections and linear least squares problems, SIAM Rev., 19 (1977), pp. 634-662, https://doi.org/10.1137/1019104. · Zbl 0379.65021
[39] Z. Strakoš, On the real convergence rate of the conjugate gradient method, Linear Algebra Appl., 154-156 (1991), pp. 535-549, https://doi.org/10.1016/0024-3795(91)90393-B. · Zbl 0732.65021
[40] Z. Strakoš, Convergence and numerical behavior of the Krylov space methods, in NATO ASI Institute, Algorithms for Large Sparse Linear Algebraic Systems: The State of the Art and Applications in Science and Engineering, G. Winter Althaus and E. Spedicato, eds., Kluwer, Dordrecht, The Netherlands, 1998, pp. 175-197.
[41] J. H. Wilkinson, Rounding Errors in Algebraic Processes, Notes Appl. Sci. 32, Her Majesty’s Stationery Office, London, 1963. (Also published by Prentice-Hall, Englewood Cliffs, NJ, 1964. Reprinted by Dover Publications, New York, 1994.) · Zbl 1041.65502
[42] J. H. Wilkinson, The Algebraic Eigenvalue Problem, Clarendon Press, Oxford, UK, 1965. · Zbl 0258.65037
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.