Lanczos procedure

The Lanczos method (according to Cornelius Lanczos ) is both an iterative algorithm for determining some eigenvalues and possibly the associated eigenvectors of a matrix and an iterative algorithm for the approximate solution of a linear system of equations . The algorithm for eigenvalues converges fastest against the eigenvalues that are well separated from the other eigenvalues, usually against the greatest magnitude eigenvalues. The algorithm for systems of linear equations is generally the BiCG method and for special matrices the CG method mathematically equivalent.

General

The method of minimized iterates, as Lanczos called it in his original work from 1950 (eigenvalues) and 1952 (linear equation systems), is based on projections onto Krylow subspaces . Depending on the properties of the matrix whose eigenvalues are to be calculated, one or two Krylow subspaces are spanned. The general method is based on two Krylov subspaces and wherein the two starting vectors , and biorthogonal be selected to each other, ie . The bases of the Krylow spaces are bi-orthogonalized against each other using a two-sided variant of the Gram-Schmidt method . ${\ displaystyle {\ mathcal {K}} = {\ mathcal {K}} (A, q)}$ ${\ displaystyle {\ hat {\ mathcal {K}}} = {\ mathcal {K}} (A ^ {H}, {\ hat {q}})}$ ${\ displaystyle q \ in \ mathbb {C} ^ {n}}$ ${\ displaystyle {\ hat {q}} \ in \ mathbb {C} ^ {n}}$ ${\ displaystyle {\ hat {q}} ^ {H} q = 1}$

Eigenvalue approximation

The two bases mentioned above and the skewed projection of the given matrix, mostly onto a tridiagonal matrix , are used to approximate the eigenvalue . The resulting asymmetrical Lanczos method cannot always be carried out using a short term recursion. One way out is the look-ahead variants constructed on the basis of the connection to the formally orthogonal polynomials (FOPs).

If the matrix is Hermitian or even really symmetrical , the choice of normalized forces a match between the two Krylow spaces and prevents a collapse of the biorthogonalization, which now represents an orthogonalization. In this particular case, the resulting is symmetrical Lanczos method, the method of Arnoldi mathematically equivalent to the (only) is an orthogonal basis and the resulting orthogonal projection of the matrix is (usually) a Hermitian tridiagonal matrix. Serious differences between the Arnoldi method and the symmetrical Lanczos method only become clear when they are executed with finite accuracy, i.e. under the influence of rounding errors . ${\ displaystyle A \ in \ mathbb {C} ^ {n \ times n}}$ ${\ displaystyle {\ hat {q}} = q}$

variants

There are also other variants of the Lanczos method, including a variant for the eigenvalue problem for symplectic matrices, which maps them to so-called butterfly form, and a variant for complex symmetric matrices.

Approximate solution of systems of equations

Lanczos' method for the approximate solution of systems of equations is rarely used in its original form, instead it is used as a BiCG method or as a CG method .

Relationships and historical context

The two methods published by Lanczos are Krylow subspace methods . This fact, or better, this relationship, was made known by Alexander Markowitsch Ostrowski Lanczos before the first publication , as evidenced by a footnote on the first page of the first publication by Lanczos. The original article says:

“The literature available to the author showed no evidence that the methods and results of the present investigation have been found before. However, AM Ostrowski of the University of Basle and the Institute for Numerical Analysis informed the author that his method parallels the earlier work of some Russian scientists: the references given by Ostrowski are: A. Krylov, Izv. Akad. Nauk SSSR 7, 491 to 539 (1931); N. Luzin, Izv. Akad. Nauk. SSSR 7, 903 to 958 (1931). On the basis of the reviews of these papers in the Zentralblatt, the author believes that the two methods coincide only in the point of departure. The author has not, however, read these Russian papers. "

“In the literature accessible to the author, there was no indication that the methods and results of this investigation had been previously discovered. However, AM Ostrowski from the University of Basel from the Institute for Numerical Analysis informed the author that his method corresponds to the earlier work of some Russian scientists. The references given by Ostrowski are: A. Krylov, Izv. Akad. Nauk SSSR 7, 491-539 (1931); N. Luzin, Izv. Akad. Nauk. SSSR 7, 903-958 (1931). Based on the reviews of these articles in the Zentralblatt, the author believes that the two methods are only the same in their starting point. The author, however, never read these Russian publications himself. "

A description of the method developed by Krylow can be found in the book by Faddejew and Faddejewa Numerical Methods of Linear Algebra .

If the matrix is self-adjoint (symmetrically real or Hermitian), the computed basis is orthogonal. Building on Lanczos' work, Walter Edwin Arnoldi came up with the idea of always enforcing an orthogonal basis, with the result that the projected matrix is no longer a tridiagonal matrix, but just an upper Hessenberg matrix . The resulting algorithm is the Arnoldi method published in 1951 .

The method is generally equivalent to the BiCG method and in the case of a symmetrical real (not necessarily positive definite) or Hermitian (also not necessarily positive definite) matrix to the CG method published shortly afterwards by Magnus Rudolph Hestenes and Eduard Stiefel . The two authors were also already aware of the relationship to the CG method. On page 410 (the second page) of their publication, they write:

"Recently, C. Lanczos developed a closely related routine based on his earlier paper on eigenvalue problem."

"Recently, C. Lanczos developed a closely related [to the CG method] based on his earlier publication on the eigenvalue problem."

Sequence of the Lanczos method for Hermitian matrices

Although the Lanczos method is the slightly older method, in the most interesting, the Hermitian case, it is worth comparing it as a special case of the Arnoldi method . The Arnoldi method calculates an orthonormal basis of a Krylow subspace for a matrix according to steps , for which applies ${\ displaystyle A \ in \ mathbb {C} ^ {n \ times n}}$ ${\ displaystyle m}$ ${\ displaystyle Q_ {m} = (q_ {1}, \ ldots, q_ {m}) \ in \ mathbb {C} ^ {n \ times m}}$

{\ displaystyle AQ_ {m} = Q_ {m} H_ {m} + h_ {m + 1, m} q_ {m + 1} e_ {m} ^ {T}.}

There is a Hessenberg matrix . In the Hermitian case with is then also Hermitian, i.e. even a Hermitian tridiagonal matrix ${\ displaystyle H_ {m} = Q_ {m} ^ {H} AQ_ {m}}$ ${\ displaystyle A ^ {H} = A}$ ${\ displaystyle H_ {m} ^ {H} = Q_ {m} ^ {H} A ^ {H} Q_ {m} = Q_ {m} ^ {H} AQ_ {m} = H_ {m}}$

{\ displaystyle H_ {m} = T_ {m} = {\ begin {pmatrix} \ alpha _ {1} & \ beta _ {1} & 0 & \ ldots & 0 & \\\ beta _ {1} & \ alpha _ {2 } & \ beta _ {2} & \ ddots & \ vdots \\ 0 & \ ddots & \ ddots & \ ddots & 0 \\\ vdots & \ ddots & \ beta _ {m-2} & \ ddots & \ beta _ { m-1} \\ 0 & \ dots & 0 & \ beta _ {m-1} & \ alpha _ {m} \ end {pmatrix}}.}

If you now look at the -th column of with this information , you get the simple relationship ${\ displaystyle k}$ ${\ displaystyle Aq_ {k}}$ ${\ displaystyle AQ_ {m}}$

{\ displaystyle Aq_ {k} = \ beta _ {k-1} q_ {k-1} + \ alpha _ {k} q_ {k} + \ beta _ {k} q_ {k + 1}.}

Because of , this can be resolved for the only unknowns , whereby because of is the norm of . This simplifies the algorithm from the article Arnoldi method with a nontrivial start vector to the Hermitian (symmetrical) Lanczos method ${\ displaystyle \ alpha _ {k} = q_ {k} ^ {H} Aq_ {k}}$ ${\ displaystyle r_ {k}: = \ beta _ {k} q_ {k + 1}}$ ${\ displaystyle \ beta _ {k}}$ ${\ displaystyle \ | q_ {k + 1} \ | _ {2} = 1}$ ${\ displaystyle r_ {k}}$ ${\ displaystyle r_ {0} \ in \ mathbb {C} ^ {n}}$

{\ displaystyle q_ {0} \ leftarrow 0, \ beta _ {0} \ leftarrow 1,}

for and do

{\ displaystyle k \ in \ mathbb {N}}

{\ displaystyle r_ {k-1} \ not = 0}

{\ displaystyle \ beta _ {k-1} \ leftarrow \ | r_ {k-1} \ |}

{\ displaystyle q_ {k} \ leftarrow r_ {k-1} / \ beta _ {k-1}}

{\ displaystyle r_ {k} \ leftarrow Aq_ {k}}

{\ displaystyle \ alpha _ {k} \ leftarrow q_ {k} ^ {H} r_ {k}}

{\ displaystyle r_ {k} \ leftarrow r_ {k} -q_ {k} \ alpha _ {k} -q_ {k-1} \ beta _ {k-1}}

end for

Compared to the general Arnoldi method , which requires a quadratically increasing effort of operations up to the step for the orthogonalization alone, this algorithm only needs operations in addition to the matrix-vector multiplications , so it is considerably more efficient. The calculation of all eigenvalues of as an approximation to the of costs little effort because of the rapid convergence of the QR algorithm . ${\ displaystyle m \ leq n}$ ${\ displaystyle O (m ^ {2} \ cdot n)}$ ${\ displaystyle m}$ ${\ displaystyle O (m \ cdot n)}$ ${\ displaystyle T_ {m}}$ ${\ displaystyle A}$

However, the statements only apply to exact calculations; the algorithm is prone to rounding errors. Because although an orthogonalization of in the Lanczos method only takes place against the previous base vector , in theory all base vectors are orthogonal in pairs. When calculating with finite accuracy, however, this orthogonality is often lost, since large eigenvalues of , so to speak , which are already represented in a matrix , creep in again via rounding errors and then cause false ghost eigenvalues in matrices . These problems are countered with re-orthogonalizations. In order to keep the effort within limits, a selective re-orthogonalization is used against some already calculated approximation eigenvectors. ${\ displaystyle q_ {k + 1}}$ ${\ displaystyle q_ {k}}$ ${\ displaystyle A}$ ${\ displaystyle T_ {k}}$ ${\ displaystyle T_ {m}, \ m \ gg k,}$

Individual evidence

↑ http://www.cs.duke.edu/courses/fall06/cps258/references/Krylov-space/Lanczos-original.pdf Lanczos, C. (1950). An Iteration Method for the Solution of the Eigenvalue Problem of Linear Differential and Integral Operators. Journal of research of the National Bureau of Standards, 45 , 255-282.

literature

Martin Hanke-Bourgeois: Fundamentals of Numerical Mathematics and Scientific Computing. 3rd edition, Vieweg + Teubner, Wiesbaden 2009.
Gene H. Golub, Charles F. Van Loan: Matrix Computations. 3. Edition. The Johns Hopkins University Press, 1996, ISBN 0-8018-5414-8 .

[An_Iteration_Method_for_the_Solution_of_the_Eigenvalue_Problem_of_Linear_Differential_and_Integral_Operators-1] ttp://www.cs.duke.edu/courses/fall06/cps258/references/Krylov-space/Lanczos-original.pdf Lanczos, C. (1950). An Iteration Method for the Solution of the Eigenvalue Problem of Linear Differential and Integral Operators. Journal of research of the National Bureau of Standards, 45 , 255-282.