Subspace iteration

The subspace iteration is used in numerical mathematics to approximate the eigenvalues ​​of a square matrix and the associated eigenvectors. It is a generalization of the simple vector iteration (Von Mises iteration) and, like this, requires the matrix only in the form of matrix-vector products , so it is particularly suitable for sparse matrices . In contrast to vector iteration, you can use it to determine several eigenvalues ​​with the largest amounts. In fact, the standard method for calculating all eigenvalues, the QR algorithm, can also be derived from the subspace iteration . ${\displaystyle A\in \mathbb {C} ^{n\times n}}$ ${\displaystyle A}$ ${\displaystyle A\cdot v}$

motivation

The article power method shows that a sufficiently general starting vector turns slowly in the direction of an eigenvector to the greatest eigenvalue when the matrix is ​​applied -fold as in . In order to prevent the values ​​from increasing too much, the vector is split into direction information and size information after each step, ${\displaystyle u_{0}\in \mathbb {C} ^{n}}$ ${\displaystyle k}$ ${\displaystyle A^{k}u_{0}}$ ${\displaystyle v_{1}}$ ${\displaystyle \lambda _{1}}$

${\displaystyle u_{k}\|Au_{k-1}\|:=Au_{k-1}.}$

The subspace iteration generalizes this approach by applying it simultaneously to (usually ) vectors. If these are sufficiently general, they form the basis of a -dimensional subspace that can be summarized in a basis matrix . The basic step in the process is again the multiplication with the matrix, so . After each multiplication, however, as with the power method, there is again a split into direction and size information. There are various possibilities, a numerically particularly favorable version is the use of orthonormal bases (ONB), where with the identity matrix and . After multiplying the basic matrix by , the division into direction information (ONB) and size information takes place with the help of the QR decomposition . ${\displaystyle m\leq n}$ ${\displaystyle m\ll n}$ ${\displaystyle m}$ ${\displaystyle U_{0}\in \mathbb {C} ^{n\times m}}$ ${\displaystyle AU_{0},A(AU_{0}),\ldots }$ ${\displaystyle U_{0}^{\ast }U_{0}=I_{m}\in \mathbb {R} ^{m\times m}}$ ${\displaystyle I_{m}}$ ${\displaystyle U_{0}^{\ast }={\bar {U}}_{0}^{T}}$ ${\displaystyle U}$ ${\displaystyle A}$

Sequence of the subspace iteration

The method starts with an orthogonal matrix , i. H. . In the -th step of the procedure, the matrices are calculated from the matrix using a reduced QR decomposition , ${\displaystyle {\hat {U}}_{0}\in \mathbb {C} ^{n\times m},\ m\leq n,}$ ${\displaystyle {\hat {U}}_{0}^{\ast }{\hat {U}}_{0}=I_{m}\in \mathbb {R} ^{m\times m}}$ ${\displaystyle k}$ ${\displaystyle {\hat {U}}_{k-1}\in \mathbb {C} ^{n\times m},\ m\leq n,}$ ${\displaystyle {\hat {U}}_{k},{\hat {R}}_{k}}$

${\displaystyle {\hat {U}}_{k}\cdot {\hat {R}}_{k}=A{\hat {U}}_{k-1}.}$

It forms a new orthonormal basis and is a square upper triangular matrix . The method converges if, in the eigenvalues of a gap in the amounts behind occurs th eigenvalue . Then the subspaces spanned by the bases converge against an invariant subspace of with (cf. subspace ). If there is a basis matrix of , it means that there is a matrix such that holds. The eigenvalues ​​of are then exactly the largest eigenvalues from above. In the case of subspace iteration, the limit matrix is ​​simply obtained as the limit value of the matrices , with the method calculating anyway. The eigenvalues ​​of are therefore naturally also for finite approximations of the eigenvalues ​​with the greatest magnitude. ${\displaystyle {\hat {U}}_{k}\in \mathbb {C} ^{n\times m}}$ ${\displaystyle {\hat {R}}_{k}\in \mathbb {C} ^{m\times m}}$ ${\displaystyle \lambda _{1},\ldots ,\lambda _{n}}$ ${\displaystyle A}$ ${\displaystyle m}$ ${\displaystyle |\lambda _{1}|\geq \ldots \geq |\lambda _{m}|>|\lambda _{m+1}|\geq \ldots }$ ${\displaystyle V_{k}:={\hat {U}}_{k}\mathbb {C} ^{m}}$ ${\displaystyle V}$ ${\displaystyle A}$ ${\displaystyle AV\subseteq V}$ ${\displaystyle U\in \mathbb {C} ^{n\times m}}$ ${\displaystyle V}$ ${\displaystyle S\in \mathbb {C} ^{m\times m}}$ ${\displaystyle AU=US}$ ${\displaystyle m}$ ${\displaystyle S}$ ${\displaystyle m}$ ${\displaystyle \lambda _{1},\ldots ,\lambda _{m}}$ ${\displaystyle S}$ ${\displaystyle S_{k}:={\hat {U}}_{k}^{\ast }(A{\hat {U}}_{k})}$ ${\displaystyle A{\hat {U}}_{k}}$ ${\displaystyle S_{k}}$ ${\displaystyle k}$

Cross-connection to the LR and QR algorithm

Although the actual area of ​​application of the subspace iteration is the calculation of a few eigenvalues ​​( ) of sparse matrices, the method can also be considered for the full dimension . The reduced QR decomposition then coincides with the full QR decomposition , where all the matrices have a square shape. In particular, the matrices are unitary , . The matrices are again decisive , because they contain the eigenvalue information. Now Think about it, as from stating you get from the subspace equation ${\displaystyle m\ll n}$ ${\displaystyle m=n}$ ${\displaystyle {\hat {U}}_{k}\cdot {\hat {R}}_{k}=A{\hat {U}}_{k-1}.}$ ${\displaystyle U_{k}\cdot R_{k}=AU_{k-1}}$ ${\displaystyle n\times n}$ ${\displaystyle U_{k}}$ ${\displaystyle U_{k}^{\ast }=U_{k}^{-1}}$ ${\displaystyle S_{k}:=U_{k}^{\ast }A{\hat {U}}_{k}}$ ${\displaystyle S_{k}}$ ${\displaystyle S_{k-1}}$

${\displaystyle S_{k}=U_{k}^{\ast }AU_{k}=(U_{k}^{\ast }AU_{k-1})U_{k-1}^{\ast }U_{k}=R_{k}(U_{k-1}^{\ast }U_{k}).}$

The parenthesized product is also unitary again. But it also applies directly ${\displaystyle Q_{k}:=U_{k-1}^{\ast }U_{k}}$

${\displaystyle S_{k-1}=U_{k-1}^{\ast }(AU_{k-1})=(U_{k-1}^{\ast }U_{k})R_{k}=Q_{k}R_{k}.}$

However, this means that you can calculate directly from the QR decomposition of without resorting to the original matrix. This exactly describes the simplest variant of the QR algorithm . The relationship with the older LR algorithm is analogous, where lower triangular matrices from LR decompositions are used instead of the unitary transformations . ${\displaystyle S_{k}=R_{k}Q_{k}}$ ${\displaystyle A}$ ${\displaystyle S_{k-1}=Q_{k}R_{k}}$

literature

• G. Golub, Ch. Van Loan: Matrix Computations. Johns Hopkins, Baltimore and London 1989, ISBN 0-8018-3739-1 .