Arnoldi method

In numerical mathematics , the Arnoldi method, like the Lanczos method, is an iterative method for determining some eigenvalues and associated eigenvectors. It is named after Walter Edwin Arnoldi . In the Arnoldi method, an orthonormal basis of the assigned Krylow space becomes for a given matrix and a given start vector ${\displaystyle A\in \mathbb {C} ^{n\times n}}$ ${\displaystyle q\in \mathbb {C} ^{n}}$

${\displaystyle {\mathcal {K}}_{m}(A,q)={\mbox{span}}\{q,Aq,A^{2}q,\ldots \,A^{m-1}q\}}$

calculated. Since the columns correspond exactly to the vectors calculated in the power method, apart from any scaling , it is clear that the algorithm becomes unstable if this basis were calculated first and then orthonormalized , for example according to Gram-Schmidt . ${\displaystyle A^{i}q}$

However, the algorithm manages without the prior creation of the so-called Krylow matrix . ${\displaystyle K_{m}(A,q)=\left(q,Aq,A^{2}q,\ldots ,A^{m-1}q\right)}$

The algorithm (MGS variant)

A square matrix and a (not necessarily standardized) start vector are given . ${\displaystyle A\in \mathbb {C} ^{n\times n}}$ ${\displaystyle r_{0}\in \mathbb {C} ^{n}}$

for and do ${\displaystyle k\in \mathbb {N} }$ ${\displaystyle r_{k-1}\not =0}$

${\displaystyle h_{k,k-1}\leftarrow \|r_{k-1}\|}$

${\displaystyle q_{k}\leftarrow r_{k-1}/h_{k,k-1}}$

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

for do ${\displaystyle j=1,\ldots ,k}$

${\displaystyle h_{jk}\leftarrow \langle q_{j},r_{k}\rangle }$

${\displaystyle r_{k}\leftarrow r_{k}-q_{j}h_{jk}}$

end for

end for

Use in the eigenvalue problem

After steps, the Arnoldi method essentially determined an orthonormal basis in the matrix and a Hessenberg matrix ${\displaystyle m}$ ${\displaystyle Q_{m}=(q_{1},\ldots ,q_{m})}$

${\displaystyle H_{m}={\begin{pmatrix}h_{11}&h_{12}&\ldots &h_{1m}\\h_{21}&h_{22}&\ldots &h_{2m}\\0&\ddots &\ddots &\vdots \\&&h_{m,m-1}&h_{mm}\end{pmatrix}}.}$

The relationship applies to these quantities calculated using the Arnoldi method

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

where is the -th unit vector. It follows: ${\displaystyle e_{m}}$ ${\displaystyle m}$

• For , the equation defines an invariant subspace of the matrix and all eigenvalues ​​of the matrix are also eigenvalues ​​of . In this case, the Arnoldi procedure terminates prematurely due to the second condition . ${\displaystyle h_{m+1,m}=0}$ ${\displaystyle AQ_{m}=Q_{m}H_{m}}$ ${\displaystyle A}$ ${\displaystyle m}$ ${\displaystyle H_{m}}$ ${\displaystyle A}$ ${\displaystyle r_{k-1}\not =0}$
• If is small, the eigenvalues ​​of are good approximations to individual eigenvalues ​​of . In particular, eigenvalues ​​at the edge of the spectrum are approximated well, similar to the Lanczos method . ${\displaystyle h_{m+1,m}}$ ${\displaystyle H_{m}}$ ${\displaystyle A}$

Application to linear systems, FOM and GMRES

The Arnoldi method is also the core algorithm of the GMRES method for solving systems of linear equations and the Full Orthogonalization Method (FOM). In the FOM you build the Krylow subspace and the bases with the start vector and replace the matrix with the approximation in the linear system . The right side is so element of Krylowraums, . The approximate solution in the Krylow space is determined in the basic representation using the system ${\displaystyle Q_{m}}$ ${\displaystyle r_{0}=b}$ ${\displaystyle Ax=b}$ ${\displaystyle A}$ ${\displaystyle Q_{m}H_{m}Q_{m}^{T}}$ ${\displaystyle b=\beta q_{1}}$ ${\displaystyle x_{m}\in K_{m}(A,b)}$ ${\displaystyle x_{m}=Q_{m}y_{m}}$

${\displaystyle H_{m}y_{m}=\beta e_{1}.}$

This corresponds to the condition and defines the solution by the orthogonality condition . Therefore the FOM is a Galerkin procedure . If you solve the small system with a QR decomposition from , the method differs only minimally from the pseudocode in the article GMRES procedure . ${\displaystyle Q_{m}^{T}(b-Ax_{m})=0}$ ${\displaystyle x_{m}}$ ${\displaystyle b-Ax_{m}\perp K_{m}(A,q)}$ ${\displaystyle H_{m}y_{m}=\beta e_{1}}$ ${\displaystyle H_{m}}$

literature

• WE Arnoldi: The Principle of Minimized Iterations in the Solution of the Matrix Eigenvalue Problem . In: Quarterly of Applied Mathematics . 9, 1951, pp. 17-29.
• Gene H. Golub, Charles F. Van Loan: Matrix Computations . 3. Edition. The Johns Hopkins University Press, 1996, ISBN 0-8018-5414-8 .