Arnoldi iteration

In the numerical analysis method such as the Arnoldi Lanczos method is an iterative method for determining some of the eigenvalues ​​and associated eigenvectors. It is Walter Edwin Arnoldi named. In the Arnoldi process to a given matrix and a given starting vector an orthonormal basis of the allocated Krylowraumes

Calculated. Because the columns correspond exactly calculated in the power method vectors up to a possible scaling, it is clear that the algorithm is unstable when first would calculate this basis, and would then, for example, by Gram- Schmidt orthonormalized.

However, the algorithm does not require the prior adoption of the so-called Krylowmatrix.

The algorithm (MGS variant)

Given a square matrix and a (not necessarily normalized) start vector.

For and do

End for

Use the eigenvalue problem

Following steps, the Arnoldi process has essentially determines an orthonormal basis in the matrix and a Hessenberg matrix

For these calculated in the Arnoldi process variables of the correlation is

Where the - th unit vector. It follows:

  • For the equation defines an invariant subspace of the matrix and eigenvalues ​​of the matrix are also eigenvalues ​​. In this case, the method Arnoldi breaks prematurely due to the second condition.
  • If is small, the eigenvalues ​​of good approximations to some eigenvalues ​​of. In particular, the eigenvalues ​​at the edge of the spectrum are well approximated similar to the Lanczos method.

Application to Linear Systems, FOM and GMRES

The Arnoldi method is also the core algorithm of the GMRES method for solving linear systems of equations and the full orthogonalization method ( FOM ). In the FOM to build the Krylov subspace and the bases on the starting vector, replacing the linear system matrix by the approximation. Thus, the right side is the element Krylowraums. The approximate solution in the Krylov space in the base representation determined by the system

This corresponds to the condition and defines the solution by the orthogonality condition. Therefore, the FOM is a Galerkin method. Solving the small system with a QR decomposition of, then the method differs only slightly from the pseudo-code in the article GMRES method.

Power iteration Gram–Schmidt process
78544
de