Previous: Remaining topics
Up: Remaining topics
Next: Block Iterative Methods
Previous Page: Remaining topics
Next Page: Block Iterative Methods

The Lanczos Connection

As discussed by Paige and Saunders in [164] and by Golub and Van Loan in [108], it is straightforward to derive the conjugate gradient method for solving symmetric positive definite linear systems from the Lanczos algorithm for solving symmetric eigensystems and vice versa. As an example, let us consider how one can derive the Lanczos process for symmetric eigensystems from the (unpreconditioned) conjugate gradient method.

Suppose we define the matrix by

and the upper bidiagonal matrix by

where the sequences and are defined by the standard conjugate gradient algorithm discussed in §. From the equations

and , we have , where

Assuming the elements of the sequence are -conjugate, it follows that

is a tridiagonal matrix since

Since span{} = span{} and since the elements of are mutually orthogonal, it can be shown that the columns of matrix form an orthonormal basis for the subspace , where is a diagonal matrix whose th diagonal element is . The columns of the matrix are the Lanczos vectors (see Parlett [167]) whose associated projection of is the tridiagonal matrix

where is the diagonal matrix whose th diagonal element is . The extremal eigenvalues of approximate those of the matrix . Hence, the diagonal and subdiagonal elements of in (), which are readily available during iterations of the conjugate gradient algorithm (§), can be used to construct after CG iterations. This allows us to obtain good approximations to the extremal eigenvalues (and hence the condition number) of the matrix while we are generating approximations, , to the solution of the linear system .

For a nonsymmetric matrix , an equivalent nonsymmetric Lanczos algorithm (see Lanczos [139]) would produce a nonsymmetric matrix in () whose extremal eigenvalues (which may include complex-conjugate pairs) approximate those of . The nonsymmetric Lanczos method is equivalent to the BiCG method discussed in §.