An improved Lanczos algorithm for solving ill-conditioned linear equations

DOI10.1016/0898-1221(90)90161-CMaRDI QIDQ805137zbMATH OpenFDO

Authors N. E. Zubov

Publication date 1990

Published in Computers & Mathematics with Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0898-1221(90)90161-C

zbMATH Keywords

conjugate gradient methodconvergenceill-conditioned linear equationsiterationLanczos algorithmLanczos vectorsnumerical examplespartial reorthogonalizationround-off errors

Mathematics Subject Classification ID

Iterative numerical methods for linear systems (65F10) Numerical solutions to overdetermined systems, pseudoinverses (65F20)

Review text

The original Lanczos algorithm for solving linear systems \(Ax=b\), where A is a symmetric \(n\times n\) matrix, gives the solution in at most n steps. It is connected with the conjugate gradient method but does not require A to be definite. The iterates are n-dimensional mutually orthogonal vectors, called Lanczos vectors. Because of the sensitiveness of the algorithm to round-off errors, the actually computed L-vectors are no more mutually orthogonal, and even not linear independent, when A is large enough. The convergence have been usually lost. The first computational variant, based on the full reorthogonalization of the L-vectors, was found to be too expensive. Since the early 1970s two essentially cheaper ways to perform the reorthogonalization have been developed, called selective and partial reorthogonalization, respectively. The residual norm \(\| r_ k\| =\| Ax_ k-b\|\) at the kth step has been used as the termination criterion of the iteration process. Instead of the exact but expensive expression \(\| Ax_ k-b\|\), \(\| r_ k\|\) has been estimated by a cheap approximate formula. Both the latter two variants are effective in solving large systems whenever A is well-conditioned. If A is ill-conditioned, the estimated value of \(\| r_ k\|\) becomes unreliable and cannot be used as the termination criterion. The present paper is dealing with this difficulty. The author first analyzes the situation and then proposes an improved Lanczos algorithm which is based on the partial reorthogonalization and makes the estimated value of \(\| r_ k\|\) cheap and reliable again. At least in the light of the numerical examples given in the paper, the effort has been successful. The coincidence of the estimated and true values of \(\| r_ k\|\) is excellent, also when A is large and ill-conditioned.

Recommendations

• The Lanczos Algorithm With Partial Reorthogonalization
• On solving linear algebraic equations with an ill-conditioned matrix
• A new implementation of the Lanczos method in linear problems
• The deflated Lanczos method for ill-conditioned linear systems
• scientific article; zbMATH DE number 4157770

Cites work

• A new look at the Lanczos algorithm for solving symmetric systems of linear equations
• A Newton-Lanczos method for solution of non-linear finite element equations
• Computational Variants of the Lanczos Method for the Eigenproblem
• scientific article; zbMATH DE number 3671573 (Why is no real title available?)
• scientific article; zbMATH DE number 3682943 (Why is no real title available?)
• scientific article; zbMATH DE number 3538728 (Why is no real title available?)
• Lanczos versus subspace iteration for solution of eigenvalue problems
• On the application of an element-by-element lanczos solver to large offshore structural engineering problems
• Solution of Sparse Indefinite Systems of Linear Equations
• The Lanczos Algorithm With Partial Reorthogonalization
• The Lanczos Algorithm with Selective Orthogonalization

Cited in

(12)

• A new technique for ill-conditioned linear systems
• The block Lanczos algorithm for linear ill-posed problems
• A regularizing L-curve Lanczos method for underdetermined linear systems
• A regularizing Lanczos iteration method for underdetermined linear systems
• Lanczos-type algorithms with embedded interpolation and extrapolation models for solving large-scale systems of linear equations
• On the application of an element-by-element lanczos solver to large offshore structural engineering problems
• A new implementation of the Lanczos method in linear problems
• scientific article; zbMATH DE number 3848490 (Why is no real title available?)
• The Lanczos Algorithm With Partial Reorthogonalization
• The deflated Lanczos method for ill-conditioned linear systems
• An Improved Version of Marti's Method for Solving Ill-Posed Linear Integral Equations
• A message-passing approach to obtain the trace of matrix functions with applications to network analysis

This page was built for publication: An improved Lanczos algorithm for solving ill-conditioned linear equations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q805137)