An improved Lanczos algorithm for solving ill-conditioned linear equations (Q805137)

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.