An improved Lanczos algorithm for solving ill-conditioned linear equations
type: Item
instance of: scholarly article
title: An improved Lanczos algorithm for solving ill-conditioned linear equations
zbMATH Open document ID: 0728.65023
DOI: 10.1016/0898-1221(90)90161-C
author: N. E. Zubov
publication date: 1990-01-01T00:00:00Z
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.
Mathematics Subject Classification ID: 65F10
Mathematics Subject Classification ID: 65F20
zbMATH DE Number: 4203569
zbMATH Keywords: ill-conditioned linear equations
zbMATH Keywords: Lanczos algorithm
zbMATH Keywords: conjugate gradient method
zbMATH Keywords: Lanczos vectors
zbMATH Keywords: round-off errors
zbMATH Keywords: convergence
zbMATH Keywords: partial reorthogonalization
zbMATH Keywords: iteration
zbMATH Keywords: numerical examples
reviewed by: Veikko Seppälä
MaRDI profile type: Publication
cites work: Computational Variants of the Lanczos Method for the Eigenproblem
cites work: Q4114696
cites work: Q3878647
cites work: Solution of Sparse Indefinite Systems of Linear Equations
cites work: The Lanczos Algorithm with Selective Orthogonalization
cites work: Q3868672
cites work: A new look at the Lanczos algorithm for solving symmetric systems of linear equations
cites work: The Lanczos Algorithm With Partial Reorthogonalization
cites work: Lanczos versus subspace iteration for solution of eigenvalue problems
cites work: A Newton-Lanczos method for solution of non-linear finite element equations
cites work: On the application of an element-by-element lanczos solver to large offshore structural engineering problems
published in: Computers & Mathematics with Applications
description: scientific article; zbMATH DE number 4203569