×

On the Lanczos and Golub-Kahan reduction methods applied to discrete ill-posed problems. (English) Zbl 1413.65120

Summary: The symmetric Lanczos method is commonly applied to reduce large-scale symmetric linear discrete ill-posed problems to small ones with a symmetric tridiagonal matrix. We investigate how quickly the nonnegative subdiagonal entries of this matrix decay to zero. Their fast decay to zero suggests that there is little benefit in expressing the solution of the discrete ill-posed problems in terms of the eigenvectors of the matrix compared with using a basis of Lanczos vectors, which are cheaper to compute. Similarly, we show that the solution subspace determined by the LSQR method when applied to the solution of linear discrete ill-posed problems with a nonsymmetric matrix often can be used instead of the solution subspace determined by the singular value decomposition without significant, if any, reduction of the quality of the computed solution.

MSC:

65F22 Ill-posedness and regularization problems in numerical linear algebra
65F10 Iterative numerical methods for linear systems
65F35 Numerical computation of matrix norms, conditioning, scaling
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Saad, Iterative Methods for Sparse Linear Systems, 2. ed. (2003) · Zbl 1031.65046 · doi:10.1137/1.9780898718003
[2] Saad, Numerical Methods for Large Eigenvalue Problems, Revised Edition (2011) · Zbl 1242.65068 · doi:10.1137/1.9781611970739
[3] Engl, Regularization of Inverse Problems (1996) · doi:10.1007/978-94-009-1740-8
[4] Hansen, Rank-deficient and Discrete Ill-posed Problems (1998) · Zbl 0890.65037 · doi:10.1137/1.9780898719697
[5] Gazzola, Embedded techniques for choosing the parameter in Tikhonov regularization, Numerical Linear Algebra with Applications 21 pp 796– (2014) · Zbl 1340.65068 · doi:10.1002/nla.1934
[6] Gazzola, On Krylov projection methods and Tikhonov regularization method, Electronic Transactions on Numerical Analysis 44 pp 83– (2015)
[7] Novati, A GCV based Arnoldi-Tikhonov regularization method, BIT Numerical Mathematics 54 pp 501– (2014) · Zbl 1317.65104 · doi:10.1007/s10543-013-0447-z
[8] Trefethen, Spectra and Pseudospectra: The Behavior of Nonnormal Matrices and Operators (2005) · Zbl 1085.15009
[9] Baglama, IRBL: an implicitly restarted block Lanczos method for large-scale Hermitian eigenproblems, SIAM Journal on Scientific Computing 24 pp 1650– (2003) · Zbl 1044.65027 · doi:10.1137/S1064827501397949
[10] Calvetti, On the choice of subspace for iterative methods for linear discrete ill-posed problems, International Journal of Applied Mathematics and Computer Science 11 pp 1069– (2001) · Zbl 0994.65043
[11] Dykes, The structure of iterative methods for symmetric linear discrete ill-posed problems, BIT Numerical Mathematics 54 pp 129– (2014) · Zbl 1290.65034 · doi:10.1007/s10543-014-0476-2
[12] Neuman, Implementations of range restricted iterative methods for linear discrete ill-posed problems, Linear Algebra and Its Applications 436 pp 3974– (2012) · Zbl 1241.65045 · doi:10.1016/j.laa.2010.08.033
[13] Golub, Matrix Computations, 4. ed. (2013)
[14] Paige, An algorithm for sparse linear equations and sparse least squares, ACM Transactions on Mathematical Software 8 pp 43– (1982) · Zbl 0478.65016 · doi:10.1145/355984.355989
[15] Baglama, Augmented implicitly restarted Lanczos bidiagonalization methods, SIAM Journal on Scientific Computing 27 pp 19– (2005) · Zbl 1087.65039 · doi:10.1137/04060593X
[16] Baglama, An implicitly restarted block Lanczos bidiagonalization method using Leja shifts, BIT Numerical Mathematics 53 pp 285– (2013) · Zbl 1269.65038
[17] Hansen, Regularization tools version 4.0 for Matlab 7.3, Numerical Algorithms 46 pp 189– (2007) · Zbl 1128.65029 · doi:10.1007/s11075-007-9136-9
[18] Hanke, On Lanczos based methods for the regularization of discrete ill-posed problems, BIT Numerical Mathematics 41 pp 1008– (2001) · doi:10.1023/A:1021941328858
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.