LR algorithm

The LR algorithm , also called stair iteration , LR method or LR iteration , is a method for calculating all eigenvalues and possibly also eigenvectors of a square matrix and was introduced in 1958 by Heinz Rutishauser . It is the forerunner of the more popular QR algorithm developed by John GF Francis and Vera Nikolaevna Kublanowskaja . Both are based on the same principle of subspace iteration , but use different matrix factorizations in detail, the eponymous LR decomposition or QR decomposition . Although the LR algorithm is even less complex than the QR algorithm , the latter is more likely to be used today for the complete eigenvalue problem, since the LR algorithm is less reliable.

Process of the LR algorithm

The LR algorithm transforms the given square matrix in each step by first calculating its LR decomposition , if it exists, and then multiplying the two factors again in reverse order, i.e. H. ${\ displaystyle A =: A_ {0}}$

{\ displaystyle A_ {0}: = A}

for do

{\ displaystyle k = 1.2, \ ldots}

{\ displaystyle A_ {k-1} =: L_ {k} R_ {k}}

(LR decomposition)

{\ displaystyle A_ {k}: = R_ {k} L_ {k}}

end for

Since it is similar , all eigenvalues are retained. The LR algorithm has as the QR algorithm , the advantage of place to be feasible, d. H. by overwriting the matrix and, compared to the QR algorithm, has even lower costs, since the Gaussian transformations used in the LR decomposition (see elementary matrix ) only change one row, while Givens rotations operate on 2 rows each. In addition, with the LR algorithm, the measures known from the QR algorithm can also be used to accelerate the calculation: ${\ displaystyle A_ {k} = R_ {k} L_ {k} = L_ {k} ^ {- 1} A_ {k-1} L_ {k}}$ ${\ displaystyle A_ {k-1}}$ ${\ displaystyle A}$

for Hessenberg matrices , each LR step only costs operations ${\ displaystyle O (n ^ {2})}$
the convergence can be accelerated considerably by shifting the spectrum
By deflation, the iteration can be restricted to a partial matrix as soon as individual eigenvalues have separated.

Problems in the LR algorithm

The decisive disadvantage of the LR algorithm, however, is that the simple LR decomposition of the matrices may not exist or that small pivot elements can lead to large rounding errors. In this case, interchanges of lines are required, which lead to a modified decomposition with a permutation matrix . The corresponding modification of the procedure is , which again leads to a matrix that is too similar. However, the convergence is then no longer assured; there are examples where the modified iteration returns to the initial matrix. Therefore, preference is given to the QR algorithm , which does not have this problem. ${\ displaystyle L_ {k} R_ {k} = A_ {k-1}}$ ${\ displaystyle A_ {k-1} = P_ {k} L_ {k} R_ {k}}$ ${\ displaystyle P_ {k}}$ ${\ displaystyle A_ {k} = R_ {k} P_ {k} L_ {k} = L_ {k} ^ {- 1} (P_ {k} ^ {T} A_ {k-1} P_ {k}) L_ {k}}$ ${\ displaystyle A_ {k-1}}$ ${\ displaystyle A = A_ {0}}$

literature

Heinz Rutishauser (1958): Solution of eigenvalue problems with the LR transformation. Nat. Bur. Stand. App. Math. Ser. 49, 47-81.
JGF Francis (1961): The QR Transformation: A Unitary Analogue to the LR Transformation — Part 1. The Computer Journal Vol. 4 (3), pp. 265-271. doi : 10.1093 / comjnl / 4.3.265
Josef Stoer, Roland Bulirsch: Numerical Mathematics 2nd 5th edition, Springer-Verlag Berlin 2005, ISBN 978-3-540-23777-8 .