In numerical mathematics , the unsymmetrical Lanczos method is, on the one hand, an iterative method for the approximate determination of some eigenvalues and possibly their eigenvectors of a matrix . On the other hand, it is also the basis for some algorithms for the approximate solution of systems of equations , namely the biconjugate gradient method, also known as the BiCG method for short .
The projection on a tri-diagonal shape
The algorithm uses a short recursion to generate matrices and , the columns of which form biorthogonal bases of the Krylow spaces and .
Given a square matrix . Now two (unnormalized) start vectors and are required, mostly good candidates exist from previous calculations or random vectors are chosen.
The algorithm is as follows:
- Set ,
- for do
- end for
The oblique projection of the matrix onto a tridiagonal matrix formed from the scalars has the asymmetrical tridiagonal structure
.
Implementation details
The above algorithm contains freedom in the choice of and , since in line three only the product of the two quantities is included. Common choices are
-
and
-
and .
Both options have their advantages and disadvantages.
Eigenvalue approximations
The eigenvalues of the tridiagonal matrix are then used as approximations for the eigenvalues of . The approximations for eigenvectors are given by the extended eigenvectors . Due to the relationship with a (crooked) Galerkin projection, the pairs are often referred to as scratch pairs even in the non-symmetrical case .
Refinements and enhancements
This original method based on a three-way recursion breaks down if applies. If (at least) one of the two vectors equals zero, or , then the associated Krylow subspace is an invariant subspace of and all eigenvalues of , the Ritz values, are also eigenvalues of . If, however, and and , the process can no longer be continued using a three-fold recursion .
Approximate solution of systems of equations
In the context of systems of equations , the zeroth residual is taken as the start vector .
QOR
The prolonged solution of the tridiagonal system , where denotes the first unit vector of the length , is taken as an approximate solution . This approach is known as the quasi-orthogonal residual approach , or QOR for short . If you use the QOR approach, depending on the details, a variant of the well-known BiCG method emerges.
QMR
A second approach is based on an extended tridiagonal matrix and is known as the quasi-minimal residual approach , or QMR for short . If you use the QMR approach, the well-known method of the same name of the quasi-minimal residuals, QMR for short, comes out.
LTPM
Multiplication by and in the original algorithm is too expensive , especially if it is known only as a black box. Sonneveld was the first to implement a method based on Lanczos recursion, which only works with multiplications . The class of these methods is known in English under the name Lanczos-type product methods , LTPM for short , coined by Martin H. Gutknecht .
The method given by Sonneveld is known as the method of the squared (bi) conjugate gradient, in English conjugate gradient squared , or CGS for short . Further representatives of this group are CGS2 , shifted CGS , BiCGSTAB , BiCGSTAB (ell) , GPBiCG , TFQMR and QMRCGSTAB .
literature
- Andreas Meister: Numerics of linear systems of equations. An introduction to modern procedures . 2nd edition Vieweg, Wiesbaden 2005, ISBN 3-528-13135-7 (with MATLAB implementations by Christoph Vömel).